Advent of Code 2022 - Day 17

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