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
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.
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 ).
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.
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
Read it over and over… nope, I still don’t get it. 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…
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
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.
Hi there
My take on generic code that will work with n dimensions.
Not really fast (4s for part2)
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.
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.
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}
>
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…