Advent of Code 2020 - Day 17

This topic is about Day 17 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

Interesting twist in part 2. I had expected the number of cycles to be hugely increased.

I did not try to make a general solution that would share most code between part 1 and part 2. Instead, I copied the my part 1 solution and added another dimension. No further optimizations were needed since both parts run in about 3.2 seconds on my computer.

Here is my solution.

Is there a mistake in the initial state of the example or am I not getting it? E.g. why does -1, 1, -1 (top left corner in z=-1) get active after 1 cycle? The only active neighbour in the initial state was 0, 1, 0 (top middle), no?

They updated the text slightly after a while since a lot of people got confused by the example (me included). In short, the top left coordinate in the z0 layer is not the same in each iteration and moves around depending on where there are active satellites.

1 Like

Struggled for about an hour trying to make sense of the examples (and thought they meant the space wrapped around which created a real headache with a growing universe :slight_smile:).

I settled for storing the active satellites in a map, keyed on coordinates. Then I ran each iteration and checked all positions within my active state plus one in each direction.

Here is my solution.

Part 2 was simply extending part 1 with an extra dimension so only posted that.

@bjorng nice to use Stream.iterate() |> Enum.drop(6), also realised reading your code that I was a bit silly to filter my Map and use Enum.count since I also only store the active satellites in my map.

1 Like

Finally ! Finally My huge copy and paste skills could be used at their full potential for part 2.

My solution finishes under 2 seconds for part 2 so I am satisfied with it. For each iteration I generate a list of changes that I apply to the map all at once at the end of each turn. Remembering day 11, this technique does not improve performance drastically compared to directly putting changes into a copy of the map directly.

But today as the “domain” (that is how I called the bounds, I was missing the “bounds” word) keeps growing, it is faster to recalculate max bounds instead of scanning the whole new map ; the changes is already a list and is smaller.

However, I use this code (this is for part 1). The 2nd argument is the coordinates for a cube that has just been activated.

  defp expand_domain({min_x, max_x, min_y, max_y, min_z, max_z}, {x, y, z}) do
    {min(min_x, x), max(max_x, x), min(min_y, y), max(max_y, y), min(min_z, z), max(max_z, z)}
  end

This is a lot of calls to min/1 and max/1 for each change. I guess using pattern matching and recursion until the domain includes the coordinates of an active point could be better.

Today, seeing that part 2 was not “run 3’000’000 cycles” was a bit disappointing but also a relief :wink:

my solution

Read it over and over… nope, I still don’t get it. :sweat: The top left coordinate of the z0 layer has 1 active satellite in the “before any cycles”. But it is active in the “After 1 cycle”. So you’re saying they move around. Where is that movement described?

They patched the text just above the graphs and added (and the frame of view follows the active cells in each cycle) as lots of people got confused.

I ended up ignoring the graphs all together as they didn’t really help me in any way.

Oh boy, I get it now! I was looking for something in the instructions, but it’s how the examples are displayed. The frame of view is moving!
I could have ignored the examples but it bothered me that my understanding after which I write the algorithm wouldn’t even comply with the example. Alright… let’s see where to find the motivation to solve this now… :joy:

1 Like

We may have to found a way to generate/generalize this to n-dimension, this one was just to ensure everyone is ready, I think.

Took sometime to make it generic, so it can work with n dimensions (not really required though). Relatively easy part two this time

This is not a win today. I wrote the code, and it had an off-by-one error with the sample input in the final cycle. I couldn’t figure it out at all.

Someone else on reddit ran into the same problem, and I ended up peeking at their code. It’s a one-line Enum.reject in my code to fix it, but I don’t fully understand why I needed it.

The neighbor selection/search could be better.

defmodule Day17 do
  def readinput() do
    File.read!("17.input.txt")
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split(&1, "", trim: true))
  end

  def neighbors3({x, y, z}) do
    for i <- -1..1 do
      for j <- -1..1 do
        for k <- -1..1 do
          {x + i, y + j, z + k}
        end
      end
    end
    |> List.flatten()
    # we have to return the neighbors of a point, so we explicitly
    # remove the point from the output
    |> Enum.reject(fn {a, b, c} -> a == x and b == y and c == z end)
  end

  def neighbors4({x, y, z, w}) do
    for i <- -1..1 do
      for j <- -1..1 do
        for k <- -1..1 do
          for l <- -1..1 do
            {x + i, y + j, z + k, w + l}
          end
        end
      end
    end
    |> List.flatten()
    |> Enum.reject(fn {a, b, c, d} -> a == x and b == y and c == z and d == w end)
  end

  def activeneighbors(state, neighborfn, point) do
    Enum.count(neighborfn.(point), &Map.has_key?(state, &1))
  end

  def cycle(state, _, 0) do
    state
    |> Map.values()
    |> Enum.count(fn cell -> cell == "#" end)
  end

  def cycle(state, neighborfn, count) do
    # find the neighbors of active cells
    tocheck =
      state
      |> Map.keys()
      |> Enum.flat_map(neighborfn)
      |> Enum.frequencies()

    Enum.map(tocheck, fn {point, _} ->
      cell = Map.get(state, point)
      countactive = activeneighbors(state, neighborfn, point)

      cond do
        cell == "#" and countactive not in [2, 3] -> {point, :inactive}
        countactive == 3 -> {point, :active}
        true -> nil
      end
    end)
    |> Enum.filter(& &1)
    |> Enum.reduce(state, fn {p, newstate}, acc ->
      case newstate do
        :inactive -> Map.delete(acc, p)
        :active -> Map.put(acc, p, "#")
      end
    end)
    # why does this happen?
    |> Enum.reject(fn {point, _} -> !Map.get(tocheck, point) end)
    |> Map.new()
    |> cycle(neighborfn, count - 1)
  end

  def part1(input \\ readinput()) do
    rows = length(input)
    cols = length(Enum.at(input, 0))

    for c <- 0..(cols - 1) do
      for r <- 0..(rows - 1) do
        {{c, r, 0}, Enum.at(input, r) |> Enum.at(c)}
      end
      |> Enum.filter(fn {_, v} -> v == "#" end)
      |> Enum.into(%{})
    end
    # i don't like this
    |> Enum.reduce(%{}, fn m, acc -> Map.merge(acc, m) end)
    |> cycle(&neighbors3/1, 6)
  end

  def part2(input \\ readinput()) do
    rows = length(input)
    cols = length(Enum.at(input, 0))

    for c <- 0..(cols - 1) do
      for r <- 0..(rows - 1) do
        {{c, r, 0, 0}, Enum.at(input, r) |> Enum.at(c)}
      end
      |> Enum.filter(fn {_, v} -> v == "#" end)
      |> Enum.into(%{})
    end
    # i don't like this
    |> Enum.reduce(%{}, fn m, acc -> Map.merge(acc, m) end)
    |> cycle(&neighbors4/1, 6)
  end
end

I refactored my solution to be generic for n dimensional space as well! That was the real fun part for me today.

Hi @faried

First thing is you can actually have multiple generators in your for construct, so you do not have to flatten:

  def neighbors3({x, y, z}) do
    for i <- -1..1,
        j <- -1..1,
        k <- -1..1 do
      {x + i, y + j, z + k}
    end
    # we have to return the neighbors of a point, so we explicitly
    # remove the point from the output
    |> Enum.reject(fn {a, b, c} -> a == x and b == y and c == z end)
  end

The best part is that you can still pull values out of a previous generated value, for example:

for values <- rows, value <- values, do: something(value)

Now, you need to use Enum.reject is simply because at one moment of the iteration, i is 0, j is 0 and k is also 0, so your expression {x + i, y + j, z + k} does not represent a neighbour but the central element itself.

That is why you have to “explicitly remove the point from the output” as you have said.

So you could filter-out the central point directly in the generator (in you case, that would be in the most inner for.

  def neighbors3({x, y, z} = coords) do
    for i <- -1..1,
        j <- -1..1,
        k <- -1..1,
        n = {x + i, y + j, z + k},
        n != coords do              # <-- accept only when !=coords
      n
    end
  end

What I did today, though, is directly count the numbers of neighbours, with a for + reduce loop. My map contains 0 for inactive cubes and 1 for active ones.

  defp active_neighbours_count(map, {x, y, z} = coords) do
    for nx <- (x - 1)..(x + 1),
        ny <- (y - 1)..(y + 1),
        nz <- (z - 1)..(z + 1),
        {nx, ny, nz} != coords,
        reduce: 0 do
      acc ->
        Map.get(map, {nx, ny, nz}, 0) + acc
    end
  end
1 Like

Thanks. I have used multiple generators with for in the past – I just didn’t think of it this time. I don’t work with Elixir on a day-to-day basis. One of the reasons I’m trying to do them all in Elixir this year is to learn from other solutions.

The Enum.reject I mentioned is in my cycle function, where I remove cubes that have no neighbors. That’s what fixes my off-by-one error. I had a lot of trouble figuring out why I need that.

1 Like

Hi there :wave:

My take on generic code that will work with n dimensions.

Part1 / Part2

Not really fast (4s for part2)
:snail:

I used MapSet to store and check coordinates; each generation builds a new set via Enum.reduce. Neighbor-fetching uses basic list comprehensions. Part 2 was mostly copy/paste from Part 1.

Github link

Here my solution: https://github.com/jkmrto/aoc2020/blob/master/lib/day17/day17.ex

My second part takes like 30 seconds, probably I am doing something wrong but not sure what.

Same here, two-line change for Part 2. Was also expecting loads of cycles, but 4th dimension was my second guess. :grinning_face_with_smiling_eyes:

17c17
<             "#", {x, cubes} -> {x + 1, MapSet.put(cubes, {x, y, 0})}
---
>             "#", {x, cubes} -> {x + 1, MapSet.put(cubes, {x, y, 0, 0})}
53,54c53,60
<   def neighbours({x, y, z} = me) do
<     all = for x <- (x - 1)..(x + 1), y <- (y - 1)..(y + 1), z <- (z - 1)..(z + 1), do: {x, y, z}
---
>   def neighbours({x, y, z, w} = me) do
>     all =
>       for x <- (x - 1)..(x + 1),
>           y <- (y - 1)..(y + 1),
>           z <- (z - 1)..(z + 1),
>           w <- (w - 1)..(w + 1),
>           do: {x, y, z, w}
>

Notes.

Not sure without looking in more detail, but could be that doing ~6400 O(n) list searches for every active cube is slow. You’re also using uniq so maybe the lists are long and have duplicates? Using MapSet may speed things up.

Also just a hunch, but my guess is that although your neighborfn excludes the original cube, in your cycle function you 1) generate a map of all the neighbors to check but then 2) in activeneighbors find all the neighbors of the neighbors, which will include the original cube. So maybe you’re adding the original cube back in to the set, even though it’s not part of your original tocheck list. Maybe…

1 Like