Help simplify a map function

Questions / Help
,
1

Hi, I have a bunch of classes like this:

%{id: 1, time: 15},
%{id: 2, time: 16},
%{id: 3, time: 16},
%{id: 4, time: 17},
%{id: 5, time: 18},
%{id: 6, time: 18},

I need to check which of them have the same :time as any other class, meaning they overlap (doesn’t matter with which class) and flag them as overlap: true

This is what I came up with:

overlaps =
  Enum.map(classes, fn class ->

    index_of_class_with_same_time =
      Enum.find_index(classes, fn c_inner ->
        c_inner.time == class.time && c_inner.id != class.id # same time, different id
      end)

    class_with_same_time_exists? = (index_of_class_with_same_time != nil)

    if (class_with_same_time_exists?) do
      Map.put(class, :overlap, true)
    else
      class
    end
  end)

My question is whether it’s not overly complex and whether there’s some nicer way of doing this? I know it can be less verbose, I wrote it this way so that I understand it 1 year from now. But my question is about the algorithm itself. I feel like what I wrote might be quite inefficient.

Thank you

2

Another way of doing this is to group the classes by time, get the groups of classes, then check each group of classes has more than one class, if so, update each of them to have the flag, otherwise just return it.

Example 
classes
|> Enum.group_by(fn class -> Map.get(class, :time) end)
|> Map.values()
|> Enum.flat_map(fn classes ->
  if length(classes) > 1 do
    Enum.map(classes, fn class -> Map.put_new(class, :overlap, true) end)
  else
    classes
  end
end)
2 Likes
3 
classes
|> Enum.group_by(& &1.time) 
|> Map.values() 
|> Enum.flat_map(fn
  [class] -> [class]
  overlaps -> Enum.map(overlaps, &Map.put(&1, :overlap, true))
end)
3 Likes
4

:smiley: you beat me to it. I didn’t see you already got a solution when I was preparing mine! I initially was thinking marking the duplicate values with frequencies_by and then mapping on the classes and tagging overlaps to the duplicate values but group_by seemed simpler.

1 Like
5

Same! And the pattern matching on the flat_map avoids the length iteration, so if it makes sense the OP should use it instead,

1 Like
6

I am bored, so I went ahead and tried the frequencies_by approach too. I guess they are equivalent performance wise, and neither is any more elegant than the other (in my opinion). But I wanted to use Map.filter lol.

classes 
  |> Enum.frequencies_by(& &1.time) 
  |> Map.filter(fn {_, v} -> v > 1 end) 
  |> Map.keys() 
  |> MapSet.new()
  |> then(fn overlaps ->
     classes 
     |> Enum.map(fn %{time: time} = m -> time in overlaps && Map.put(m, :overlap, true) || m end)
  end)

UPDATE: == 2 became > 1, otherwise it’d report just “pairs”

7

Nice! group_by simplifies it a lot, thank you. I need to study the example with frequencies_by in the morning with fresh mind :smiley: I think I understand the principle you described, but not sure how MapSets work.

1 Like
8

December is the one time of the year I get to use frequencies_by thanks to Advent of Code. So wanted that, basically, it returns a map where the keys are whatever value that got yielded after calling the function, and values are the frequency of those. In this cases, it returns the frequency of each time (i.e. 16 => 2, 15 => 1, 17 => 2). And then I take only the ones that are more than 1 (I gotta fix that bug up there lol), and turn it into a set (so that I get faster membership checks, just in case you’re thinking of thousands of overlapping classes).

Elixir’s Enum is one of the most fun APIs I ever had the opportunity of working with!

1 Like
9

Fun with for comprehensions, just because I can :grinning_face_with_smiling_eyes:

iex(83)> classes = for {t, i}  <- Enum.with_index([15, 16, 16, 17, 18, 18], 1), do: %{id: i, time: t}
[
  %{id: 1, time: 15},
  %{id: 2, time: 16},
  %{id: 3, time: 16},
  %{id: 4, time: 17},
  %{id: 5, time: 18},
  %{id: 6, time: 18}
]
iex(84)> for %{time: t} = c <- classes, do: if Enum.find(classes -- [c], & &1.time == t), do: Map.put(c, :overlap, true), else: c
[
  %{id: 1, time: 15},
  %{id: 2, overlap: true, time: 16},
  %{id: 3, overlap: true, time: 16},
  %{id: 4, time: 17},
  %{id: 5, overlap: true, time: 18},
  %{id: 6, overlap: true, time: 18}
]
5 Likes
10

Fun with Access just because I can :slight_smile:

doubles =
  input
  |> get_in([Access.all(), :time])
  |> then(& &1 -- (&1 |> MapSet.new() |> MapSet.to_list()))
#⇒ [16, 18]
put_in(input, [Access.filter(& &1.time in doubles), :overlap], true)
#⇒ [
#   %{id: 1, time: 15},
#   %{id: 2, overlap: true, time: 16},
#   %{id: 3, overlap: true, time: 16},
#   %{id: 4, time: 17},
#   %{id: 5, overlap: true, time: 18},
#   %{id: 6, overlap: true, time: 18}]
4 Likes
11

Thank you all, these are some cool snippets to play with! Not sure I can mark one solution, coz all solutions are correct :slight_smile:

12

Is this some shortcut notation for guards? Do I understand correctly that this evals to true only if the result of find is a list, i.e. there’s more than 1 matches? Shrewd!

13

No. It’s a plain old good if/2. If you were asking about & &1.time == t, it’s a function capture.

No. if/2 distinguished truthy and falsey values. The latter is false or nil, the former is everything else. Enum.find/2 returns either a single element or nil.

14

I meant this bit ^ What does that do, please?

15

https://hexdocs.pm/elixir/Kernel.html#--/2

3 Likes
16

Hah didn’t think of that :see_no_evil::grinning_face_with_smiling_eyes: Makes sense now, thanks!

1 Like
17

Yeah, sometimes it’s a bit confusing, when one is not used to the fact that operators are in fact Kernel functions. Studying that module a bit is really worth it. :slight_smile:

3 Likes
18

PLOT TWIST! :smiley:

Of course my next step was that classes have a duration, so there’s multiple options how they can overlap. These are the classes I started with

classes = [
  %{id: 1, time: 15, duration: 1}, # 
  %{id: 2, time: 16, duration: 3}, # overlap: true
  %{id: 3, time: 17, duration: 1}, # overlap: true
  %{id: 4, time: 18, duration: 1}, # overlap: true
  %{id: 5, time: 19, duration: 1}, # 
  %{id: 6, time: 20, duration: 2}, # overlap: true
  %{id: 7, time: 21, duration: 1}, # overlap: true
]

It seems to me that group_by and frequencies_by won’t help here. This is my solution, but again, more elegant solutions would be very welcome!

My solution 
flagged =
  for c <- classes do
    if Enum.find(classes -- [c], fn cx ->
      # start of cx falls into c
      ((cx.time >= c.time) and (cx.time < (c.time + c.duration)))
      or
      # end of cx falls into c
      (((cx.time + cx.duration) > c.time) and ((cx.time + cx.duration) <= (c.time + c.duration)))
      or
      # start of cx before c and end of cx after c
      ((cx.time <= c.time) and ((cx.time + cx.duration) >= (c.time + c.duration)))
      end) do
        Map.put(c, :overlap, true) 
      else 
        c
      end
  end
19

I’d use ranges. You can save recalculation with a helper ranges data structure.

iex(100)> ranges = Map.new(classes, fn %{time: t, duration: d, id: id} -> {id, t..(t + d - 1)} end)
%{
  1 => 15..15,
  2 => 16..18,
  3 => 17..17,
  4 => 18..18,
  5 => 19..19,
  6 => 20..21,
  7 => 21..21
}
iex(101)> Enum.map(classes, fn c ->
...(101)>   if Enum.all?(classes -- [c], &Range.disjoint?(ranges[c.id], ranges[&1.id])) do
...(101)>     c
...(101)>   else
...(101)>     Map.put(c, :overlap, true)
...(101)>   end
...(101)> end)
[
  %{duration: 1, id: 1, time: 15},
  %{duration: 3, id: 2, overlap: true, time: 16},
  %{duration: 1, id: 3, overlap: true, time: 17},
  %{duration: 1, id: 4, overlap: true, time: 18},
  %{duration: 1, id: 5, time: 19},
  %{duration: 2, id: 6, overlap: true, time: 20},
  %{duration: 1, id: 7, overlap: true, time: 21}
]
2 Likes
20

Cool idea to use ranges! But what if the time is actually of type Time? Maybe do Time.to_seconds_after_midnight/1 so that I get integers to use with Range?