This topic is about Day 25 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
Here is my solution:
aand here’s mine:
the one thing that’s worth noting is that I actually keep the two herds in separate lists (as well as the grid), this way I don’t need to go through the entire grid when moving, but instead only check the (sorted) herd coordinates, and can use my previous grid as the next grid.
Also I wonder if checking that no moves have been made by doing this:
case newgrid do
^grid -> moves
_ -> move({newgrid, left, down}, width, height, moves + 1)
end
is very terrible for performance or is it “actually quite fine”?
1 Like
It could be good if the newgrid was the same term as before (the C pointer), but in your case it is bad. Except there is no better way to compare two maps for equality, it may be well optimized (though I don’t know), so I would say that it is actually quite fine, yes.
I made the first implementation I could think of, and it runs in the same time as your code (~6s) on my machine. I keep an accumulator to count the moves, so I do not have to compare the maps before and after.
Maybe using that in your own code could lead to better performance. But honestly after days 23 and 24 I am tired 
so I will not try haha.
defmodule Aoe.Y21.Day25 do
alias Aoe.Input, warn: false
@type input_path :: binary
@type file :: input_path | %Aoe.Input.FakeFile{}
@type part :: :part_one | :part_two
@type input :: binary | File.Stream.t()
@type problem :: any
@spec read_file!(file, part) :: input
def read_file!(file, _part) do
Input.stream_file_lines(file, trim: true)
end
@spec parse_input!(input, part) :: problem
def parse_input!(input, _part) do
input = Enum.to_list(input)
yo = length(input) - 1
xo = (hd(input) |> byte_size) - 1
{xo, yo}
grid =
input
|> Enum.with_index()
|> Enum.map(fn {line, y} ->
parse_line(line, y)
end)
|> Enum.reduce(%{}, fn map1, map2 -> Map.merge(map1, map2, &raise_merge/3) end)
{{xo, yo}, grid}
end
defp raise_merge(key, _, _) do
raise "duplicate key #{key}"
end
defp parse_line(line, y) do
line
|> String.to_charlist()
|> Enum.with_index()
|> Enum.reduce(%{}, fn
{?., _}, acc -> acc
{?v, x}, acc -> Map.put(acc, {x, y}, :v)
{?>, x}, acc -> Map.put(acc, {x, y}, :>)
end)
end
def part_one({{xo, yo}, grid}) do
turns = Stream.iterate(1, &(&1 + 1))
Enum.reduce_while(turns, grid, fn turn, grid ->
IO.write("turn #{turn}")
{moved, grid} = move_cucumbers({xo, yo}, grid)
case {moved, grid} do
{0, _} ->
{:halt, turn}
{n, new_grid} ->
IO.puts(" moved: #{n}")
{:cont, new_grid}
end
end)
end
defp move_cucumbers({xo, yo}, grid) do
# move east facing
{moved, grid} =
Enum.reduce(grid, {0, %{}}, fn
{coords, :v}, {moved, new_grid} ->
{moved, Map.put(new_grid, coords, :v)}
{coords, :>}, {moved, new_grid} ->
case move(coords, :>, grid, {xo, yo}) do
{:ok, new_coords} ->
{moved + 1, Map.put(new_grid, new_coords, :>)}
:nope ->
{moved, Map.put(new_grid, coords, :>)}
end
end)
# move south facing
Enum.reduce(grid, {moved, %{}}, fn
{coords, :>}, {moved, new_grid} ->
{moved, Map.put(new_grid, coords, :>)}
{coords, :v}, {moved, new_grid} ->
case move(coords, :v, grid, {xo, yo}) do
{:ok, new_coords} ->
{moved + 1, Map.put(new_grid, new_coords, :v)}
:nope ->
{moved, Map.put(new_grid, coords, :v)}
end
end)
end
defp move({x, y}, :v, grid, {_xo, yo}) do
next_coords = {x, wrap(y + 1, yo)}
if free?(grid, next_coords) do
{:ok, next_coords}
else
:nope
end
end
defp move({x, y}, :>, grid, {xo, _yo}) do
next_coords = {wrap(x + 1, xo), y}
if free?(grid, next_coords) do
{:ok, next_coords}
else
:nope
end
end
defp free?(grid, next_coords) do
not Map.has_key?(grid, next_coords)
end
defp wrap(coord, max_coord) when coord <= max_coord,
do: coord
defp wrap(coord, max_coord) when coord == max_coord + 1,
do: 0
end
Pretty straightforward use of Stream.iterate and a dirty bit to flag termination:
