This topic is about Day 20 of the Advent of Code 2021.
We have a private leaderboard (shared with users of Erlang Forums):
https://adventofcode.com/2021/leaderboard/private/view/370884
The entry code is:
370884-a6a71927
This topic is about Day 20 of the Advent of Code 2021.
We have a private leaderboard (shared with users of Erlang Forums):
https://adventofcode.com/2021/leaderboard/private/view/370884
The entry code is:
370884-a6a71927
I wasted a lot of time by using a “smart” and efficient representation - a list of numbers and bitwise operators. That worked fine for the example, but not for my input because I failed to handle infinity properly. With a padding hack I could get it to work for part 1, but not for part 2.
I ended up scrapping my part 1 solution and implementing the more obvious solution of using a map to represent the image grid.
Part 2 runs in ~3s. I took too long to realize I should have used a Map instead of a MapSet… (Maybe a MapSet can be used, but it would probably make the code more complicated).
defmodule AdventOfCode.Day20 do
def part1(input) do
{algo, image} = parse_input(input)
image
|> make_output(algo, 1)
|> make_output(algo, 2)
|> Map.values()
|> Enum.count(&(&1 == "#"))
end
def part2(input) do
{algo, image} = parse_input(input)
Enum.reduce(1..50, image, fn n, acc ->
make_output(acc, algo, n)
end)
|> Map.values()
|> Enum.count(&(&1 == "#"))
end
def make_output(image, algo, n) do
{min_x, max_x} = image |> Map.keys() |> Enum.map(fn {x, _} -> x end) |> Enum.min_max()
{min_y, max_y} = image |> Map.keys() |> Enum.map(fn {_, y} -> y end) |> Enum.min_max()
Enum.reduce(
for(x <- (min_x - 1)..(max_x + 1), y <- (min_y - 1)..(max_y + 1), do: {x, y}),
Map.new(),
fn point, acc ->
bin = point |> get_nbs(image, n) |> Enum.join() |> String.to_integer(2)
Map.put(acc, point, Map.get(algo, bin))
end
)
end
def get_nbs({x, y}, image, n) do
Enum.map(
[{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {0, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}],
fn {x1, y1} ->
case Map.get(image, {x + x1, y + y1}) do
"#" -> 1
"." -> 0
nil -> if rem(n, 2) == 0, do: 1, else: 0
end
end
)
end
def parse_input(input) do
[algo, image] = String.split(input, "\n\n", trim: true)
algo =
algo
|> String.codepoints()
|> Enum.reject(&(&1 == "\n"))
|> Enum.with_index()
|> Map.new(fn {v, k} -> {k, v} end)
image =
image
|> String.codepoints()
|> Enum.reduce({Map.new(), 0, 0}, fn
"\n", {acc, _x, y} -> {acc, 0, y + 1}
point, {acc, x, y} -> {Map.put(acc, {x, y}, point), x + 1, y}
end)
|> elem(0)
{algo, image}
end
end
yeah, ended up doing a very straight-forward giant map solution, where initially I thought I’d be clever by only storing the 1s, but only when dealing with actual data I realised that the outside is “blinking”, so had to change it to also store the zeroes, and to figure out a cleverish way to tell the Map.get(src, {x,y}, default)
what that default should be.
A mix of structs and bitwise operations
Christmas is nearing, motivation is dropping. And I’m not even ashamed anymore: