Stream.unfold
helps a lot.
My solution, my naive approach worked fine. Was worried I needed to come up something smarter for part 2, but it was quick enough.

This is how my part 1 and 2 look like: (My browser crashed while attempting to animate part 2 though)
Part 1
Part 2
livemd
- https://github.com/code-shoily/advent_of_code/blob/master/lib/2022/day_14.livemd
Ok, so I will also add visualisations (as LiveMD do not store them )
Part 1
Part 2
Y’all getting soo fancy with it!
I way overcomplicated this one in my mind. I thought initially it was going to be another pathfinding problem and set up my data structure as another digraph. After realizing it wasn’t that, I left it b/c part 1 worked with a naive approach anyway.
On part 2 I spent a ton of time trying think of a way to do something clever with just adding edges, and using the lengths of the edges to do the calculations without actually tracking the sand. I thought I just need the area of the triangle that will be formed minus the number of rocks and the number of protected spaces. I still think that should work but I couldn’t figure out how to properly calculate the protected spaces for the more complex arrangement of the real data. The simple sample data worked great. Anyway, I ended up just using the same approach for both with a minor tweak for part 2 and it was still fast enough.
defmodule Solve do
@sand_falls [{0, 1}, {-1, 1}, {1, 1}]
@origin {500, 0}
def sand_falling({x, y}, graph, limit, floor?) do
if off_grid?(y, limit) and not floor? do
{:off_grid, graph}
else
dir_falling =
@sand_falls
|> Enum.find(fn {dx, dy} -> can_fall?({dx + x, dy + y}, graph) end)
case dir_falling do
nil ->
:digraph.add_vertex(graph, {x, y}, :sand)
if floor? and {x, y} == @origin do
{:stuck_at_origin, graph}
else
{:at_rest, graph}
end
{dx, dy} ->
sand_falling({dx + x, dy + y}, graph, limit, floor?)
end
end
end
def off_grid?(y, max_y) do
y > max_y
end
defp can_fall?({x, y}, graph) do
case :digraph.vertex(graph, {x, y}) do
false -> true
_ -> false
end
end
def solve(graph, limit, floor?) do
[1]
|> Stream.cycle()
|> Enum.reduce_while({graph, 0}, fn i, {g, count} ->
case sand_falling(@origin, g, limit, floor?) do
{:at_rest, g} -> {:cont, {g, count + i}}
# only reachable with floor? == false
{:off_grid, _g} -> {:halt, count}
# only reachable with floor? == true, includes the sand that didn't drop b/c stuck at origin
{:stuck_at_origin, _g} -> {:halt, count + i}
end
end)
end
def part1({graph, limit}) do
solve(graph, limit, false)
end
def part2({graph, limit}) do
floor = limit + 2
graph =
for x <- (500 - floor)..(500 + floor), reduce: graph do
g ->
:digraph.add_vertex(g, {x, floor}, :floor)
g
end
solve(graph, floor, true)
end
end
Full parsing and bonus render function for drawing on the terminal on github.
Seems this thread has become a gallery
I feel I have to post my pictures, too. I’m definitely not a VegaLite guru, though.
Part 1
Part 2
Reading over some of the solutions here and I’m curious about using Stream.unfold/2
. Is there some benefit to this followed by a count versus an Enum.reduce
with a counter? Or could you eliminate the need for a separate count step by including a count in the unfolding accumulator?
Stream.unfold/2
returns a stream, and all streams are lazy, meaning if you don’t want a value, it does nothing.
I use Stream.unfold/2
because, in the beginning, I don’t have an enumerable (certainly I’m not going to iterate over my input), and I’m too lazy to write my own recursive function that generates the next state based on the previous state
I can introduce a counter in the unfolding step, but even so, I still need to iterate over the stream to find the correct state and its counter value. In the end, it’s of the same performance as |> Enum.count()
.
Ah, thanks for the explanation. Now that you explained that my solution of creating an enumerable that I could reduce with Stream.cycle([1])
seems like an ugly way to accomplish the same thing. Always learning, which is why I love AoC.
Another easy one to help me catch up. No issues here aside from an off-by-1 error on my first attempt to calculate part 2
I used an :ets
property that I’d never needed to before - with an :ordered_set
table :ets.next
will take a key that doesn’t exist in the table and find the “next” one in term order that does.
For instance, if the table has keys that are {x, y}
, then :ets.next(t, {500, 0})
will handle the “drop to the first occupied spot” efficiently.
TIL, nice