Couldn’t find a thread for this day so sorry if it already exists. I’m stumped. I’ve got a solution that works for the sample data but is off by one for the real data. Anyone mind looking at the code and suggesting where that bug comes from? I just can’t find it. The render and pattern finding functions are not relevant to this error as they are not called, but if you have suggestions for improving those I’m open for that feedback as well.
Hard to say for sure without the input file, but the logic in fall seems slightly incorrect: it checks if the block can fall before shifting it. It’s possible to shift a block that can’t move downwards - for instance, the very first shape in the example.
I resorted to squinting at multiple buffers in my editor to find the leader length and cycle length for part 2, but here’s my part 1:
Thanks for taking a look. I don’t think that’s it b/c the first call for each new rock is to shift and it always tries to fall whether it can shift or not. But if it cannot fall it comes to rest. From the prompt:
If a downward movement would have caused a falling rock to move into the floor or an already-fallen rock, the falling rock stops where it is (having landed on something) and a new rock immediately begins falling.
I might run your code and mine on my data set and see where they diverge when I get a chance. Thanks again for looking.
ADDENDUM:
So checking our output side by side they are equivalent for the first 1712 rocks and then mine gets off and sort of jumps around a bit. Going to have to rethink the whole logic. Your solution is so nicely organized and easy to read I’m going to see if just improving my organization makes the logical error pop out.
I don’t seem to be able to edit posts any more for some reason. The issue I have is that the 1712th block is a J shape that comes to rest atop a cross shape. For some reason mine is resting atop the vertical bit of the cross rather than the horizontal bit. I must have an issue in my shift calculation or my placement of pieces on the board but I can’t find it.
+++++
Nope. Problem is in parsing the input apparently. The horizontal block that lands before the cross is supposed to go R->L->L->L, but for some reason mine is trying to go R->R->R->L. This leads to the following cross block landing on top of that horizontal piece rather than nesting alongside it. Debugging continues.
+++++
Oh for crying out loud. I didn’t trim the input. I thought I’d be clever and convert the “<” and “>” to -1 and 1 by taking their codepoint value (60 and 62) and subtracting 61. But passing the “\n” character created a shift by -51 (which does nothing but throws the cycle out of phase). Trimming the input and my solution now works. Crikey.
Okay, last time I reply to myself, I promise. Finally got this working but took some time to refactor, polish, and document since I was 10 days late anyway.
defmodule Rocks do
@moduledoc "Define shapes of falling rocks and the motions they can take."
@corners [{0, 0}, {0, 2}, {2, 0}, {2, 2}]
def horizontal(x, y), do: 0..3 |> Enum.map(fn dx -> {dx + x, y} end)
def cross(x, y),
do:
for(
dx <- 0..2,
dy <- 0..2,
{dx, dy} not in [{0, 0}, {0, 2}, {2, 2}, {2, 0}],
do: {dx + x, dy + y}
)
def jay(x, y), do: 0..2 |> Enum.flat_map(fn d -> [{x + d, y}, {x + 2, y + d}] end)
def vertical(x, y), do: 0..3 |> Enum.map(fn dy -> {x, y + dy} end)
def square(x, y), do: for(dx <- 0..1, dy <- 0..1, do: {dx + x, dy + y})
def start_at(rock, x, y), do: rock.({x, y})
@doc "Create the list of rock types in the order specified by
the prompt. Rocks begin two units from the left and 3 units
above highest point of cave."
def rocks() do
horizontal = fn {x, y} -> 0..3 |> Enum.map(fn dx -> {dx + x, y} end) end
cross = fn {x, y} ->
for dx <- 0..2, dy <- 0..2, {dx, dy} not in @corners, do: {dx + x, dy + y}
end
jay = fn {x, y} -> 0..2 |> Enum.flat_map(fn d -> [{x + d, y}, {x + 2, y + d}] end) end
vertical = fn {x, y} -> 0..3 |> Enum.map(fn dy -> {x, y + dy} end) end
square = fn {x, y} ->
for dx <- 0..1, dy <- 0..1, do: {dx + x, dy + y}
end
[horizontal, cross, jay, vertical, square] |> Enum.with_index() |> :queue.from_list()
end
def next(rocks) do
{{:value, {rock, ndx}}, rox} = :queue.out(rocks)
{{rock, ndx}, :queue.in({rock, ndx}, rox)}
end
def try_shift(rock, dx, cave_state) do
shifted = Enum.map(rock, fn {x, y} -> {x + dx, y} end)
if Cave.in_cave?(shifted) and not Cave.would_collide?(cave_state, shifted) do
shifted
else
rock
end
end
def try_fall(rock, cave_state) do
fallen = Enum.map(rock, fn {x, y} -> {x, y - 1} end)
if Cave.in_cave?(fallen) and not Cave.would_collide?(cave_state, fallen) do
{:still_falling, fallen, cave_state}
else
{:at_rest, rock, Cave.add_resting_rock(cave_state, rock)}
end
end
end
defmodule Cave do
@moduledoc "Define the initial state of the cave and functions for updating state of the cave.
We are told the cave is only 7 units wide."
def initial() do
0..6
|> Enum.map(fn x -> {x, 0} end)
|> MapSet.new()
end
def in_cave?(rock), do: Enum.all?(rock, fn {x, y} -> y > 0 and x in 0..6 end)
def add_resting_rock(cave, rock) do
Enum.reduce(rock, cave, &MapSet.put(&2, &1))
end
def would_collide?(cave, rock) do
Enum.any?(rock, fn coord -> MapSet.member?(cave, coord) end)
end
def highest(cave) do
cave
|> Enum.map(&elem(&1, 1))
|> Enum.max()
end
end
defmodule Jetstream do
@moduledoc """
Create infinite stream of air jets from parsed input. In this implementation I've used an idea
lifted from [Matt Jones](https://gist.github.com/al2o3cr/2062ecf2cc11648f88832c5c4b3c2a22). Intuitively
I like `Stream.cycle/1` better than `:queue`, but the stream became cumbersome to advance nested within
other streams and bogged down rapidly.
"""
def jetstream(input) do
Input.parse(input) |> Enum.with_index() |> :queue.from_list()
end
def next(jetstream) do
{{:value, {jet, ndx}}, jets} = :queue.out(jetstream)
{{jet, ndx}, :queue.in({jet, ndx}, jets)}
end
end
defmodule Simulate do
@moduledoc "Simulate the falling rocks and determine the height
after a given number of rocks have fallen."
@enforce_keys [:jets, :rocks]
defstruct pattern: %{}, hts_at: %{0 => 0}, jets: nil, rocks: nil, count: 0, cave: Cave.initial()
@doc "Create an initial state and then create a stream iterating that step through each rock drop."
def simulate(input, rounds) do
sim = %Simulate{jets: Jetstream.jetstream(input), rocks: Rocks.rocks()}
Stream.iterate(sim, &step/1)
|> Stream.take(rounds + 1)
# because the initial state of ht 0 is before the first rock falls, you
# must take n + 1 rounds to get the ht after the nth rock falls.
end
@doc "The rock drop step."
def step(
%Simulate{
pattern: pattern,
hts_at: hts_at,
jets: jets,
rocks: rocks,
count: count,
cave: cave
} = state
) do
{rock, next_rocks} = Rocks.next(rocks)
{next_jets, new_cave, new_count, pattern} = drop(rock, jets, cave, count + 1, pattern)
hts_at = Map.put(hts_at, new_count, Cave.highest(new_cave))
%{
state
| pattern: pattern,
hts_at: hts_at,
jets: next_jets,
rocks: next_rocks,
count: new_count,
cave: new_cave
}
end
defp drop({rock, r_ndx}, jetstream, cave, count, pattern) do
{{jet, j_ndx}, next_jets} = Jetstream.next(jetstream)
rock =
if is_function(rock) do
Rocks.start_at(rock, 2, 4 + Cave.highest(cave))
else
rock
end
{rock_state, maybe_fallen, maybe_updated_cave} =
rock
|> Rocks.try_shift(jet, cave)
|> Rocks.try_fall(cave)
ht = Cave.highest(maybe_updated_cave)
updated_pattern =
Map.update(pattern, {r_ndx, j_ndx}, [{count, ht}], fn prev -> [{count, ht} | prev] end)
case rock_state do
:at_rest ->
{next_jets, maybe_updated_cave, count, updated_pattern}
:still_falling ->
drop({maybe_fallen, r_ndx}, next_jets, maybe_updated_cave, count, updated_pattern)
end
end
end
defmodule Solve do
@moduledoc "functions for finding solution with given parameters for parts 1 and 2"
@doc """
For part 1 we want the end result after all the number of rocks specified by 'rounds'.
Because the Simulate.simulate API returns a stream of states, we drop all but the final state.
This API is awkward for part 1 but makes part 2 easier and allows reuse of code.
"""
def part1(input, rounds) do
Simulate.simulate(input, rounds)
|> Stream.drop(rounds)
|> Enum.to_list()
|> hd()
|> get_in([Access.key!(:cave)])
|> Cave.highest()
end
@doc """
For part 2 we want to avoid simulating a full gajillion or whatever rocks, but we might have to if
no pattern is found before then. So we drop the Simulate.simulate stream until a pattern is found
(or it completes all the gajillion rocks dropping). We then find all the patterns that have repeated
and take the pattern with the longest phase (some subharmonic patterns can/do show up for certain
combinations). When multiple patterns with the same phase are available take the one with the shortest
height change and earliest appearance. To calculate the total height, first calculate the number of
cycles that can occur within the number of rounds specified. Multiply that by the height change per cycle.
Then add the height of any remaining rounds that form an incomplete cycle. This is the reason for the
duplicate caching in the `%Simulate{}` struct. One cache holds the pattern of rock and jet indexes as keys
with values of {rock count, game height}. But we later need to get the height for a certain rock count.
We could iterate over the pattern map as an Enum but that could be VERY slow. Instead we keep a separate
map with rock count as keys and game height as values. Now looking up the leftover height is much quicker.
"""
def part2(input, rounds) do
[%Simulate{pattern: pattern} = sim] =
Simulate.simulate(input, rounds)
|> Stream.drop_while(fn sim -> sim.pattern |> Enum.all?(fn {_, v} -> length(v) < 5 end) end)
|> Enum.take(1)
pattern
|> Enum.filter(fn {_k, v} -> length(v) > 1 end)
|> find_cycle()
|> calc_cycles(rounds, sim)
end
defp find_cycle(patterns) do
patterns
|> Enum.flat_map(fn {_k, v} ->
Enum.sort(v)
|> Enum.chunk_every(2, 1, :discard)
|> Enum.map(fn [{a, h1}, {b, h2}] -> {b - a, h2 - h1, a} end)
end)
|> Enum.sort_by(fn {len, delta_ht, start} -> {len, -delta_ht, -start} end, :desc)
|> hd()
end
defp calc_cycles({cycle_len, cycle_ht, cycle_start}, rounds, sim) do
cycles = div(rounds - cycle_start, cycle_len)
rem = rem(rounds - cycle_start, cycle_len)
rem_ht = Map.get(sim.hts_at, cycle_start + rem)
cycles * cycle_ht + rem_ht
end
end
