Advent of Code 2024 - Day 21

liamcmitchell · December 21, 2024, 4:06pm

A frustrating one for me. I spent a long time trying to understand why some combinations resulted in fewer presses and struggled to keep track of all the layers.

A few things that helped:

shortest sequences will always use repeated keys e.g. V<<, never <V<
if a sequence starts and ends on A, it is independent, cacheable and there is no need to keep track of the keys once summed

My solution:

Part 1 example (2.1ms): 126384
Part 1 input (0.9ms): 157908
Part 2 example (14.2ms): 154115708116294
Part 2 input (10.8ms): 196910339808654

I passed a cache map every but don’t like it. Is there a nicer way to cache without external deps or using Process? I’ll have a look into macros.

lud · December 21, 2024, 6:59pm

I’m pulling my hair so hard. I can’t reason about this… I spend so many time on that. I just found the correct answer for part 1.

The concept is very fun but it’s also kind of tedious…

Edit: well part 2 is not a surprise hahaha

rvnash · December 21, 2024, 7:55pm

I worked on this for hours and got pretty much no where. I knew exactly what I wanted to do, but I could not clear my head enough to do it. Gave up.

lud · December 21, 2024, 10:21pm

Finally took the time to hack the second part. That was not as simple as “just add cache”

github.com

lud/adventofcode/blob/main/lib/solutions/2024/day21.ex

defmodule AdventOfCode.Solutions.Y24.Day21 do
  alias AdventOfCode.Grid
  alias AoC.Input

  flip_map = fn grid -> Map.new(grid, fn {k, v} -> {v, k} end) end

  compute_coordinates = fn text ->
    {grid, _, _} =
      text
      |> String.split("\n", trim: true)
      |> Grid.parse_lines(fn
        c when c in ?0..?9 -> {:ok, c - ?0}
        ?A -> {:ok, :A}
        ?^ -> {:ok, :^}
        ?< -> {:ok, :<}
        ?v -> {:ok, :v}
        ?> -> {:ok, :>}
        ?A -> {:ok, :A}
        ?\s -> :ignore
      end)

This file has been truncated. show original

My times are submillisecond haha. (But I parse the 2D maps for digit coordinates at compile time).

Name               ips        average  deviation         median         99th %
part_two       22.45 K       44.55 μs    ±22.78%       41.28 μs       83.64 μs
part_one       21.73 K       46.03 μs    ±26.03%       42.16 μs       94.26 μs

@liamcmitchell I used the process dictionary for the memoization. I was not sure it would be faster that carrying a map (and I don’t actually know) but it seems okay.

I have some code duplication because instead of :<, :< I have {:<, 2} (:< is {:<, 1}), but not for the door digits.

adamu · December 22, 2024, 1:49am

Lol I came here for the answer and you’re all like “too hard ”…

FWIW spent a couple of hours on it, but my code got a length 4 too long for the 4th sample. It’s the first time I failed on the sample in part 1. I suspected it was something to do with the < arrow key being further away, but following my rule of not letting AoC take over my life, I gave up

igorb · December 22, 2024, 6:30am

This was quite a puzzle. For Part 2, it took me a while to realize that it’s not necessary to return the full sequence and only the length suffices: advent-of-code-2024/lib/advent_of_code2024/day21.ex at main · ibarakaiev/advent-of-code-2024 · GitHub.

lud · December 22, 2024, 10:46am

Got bitten by that too and had to rewrite everything

bjorng · December 22, 2024, 8:36pm

This took quite a while to figure out and implement correctly, and to make fast enough to handle part 2.

The resulting code is surprisingly fast: the combined runtime for both parts is 0.01 seconds.

github.com

bjorng/advent-of-code/blob/main/2024/day21/lib/day21.ex

defmodule Day21 do
  defmodule Keypad do
    defstruct position: {0, 0}, grid: %{}, parse: nil

    def init(grid, parse_char) do
      grid = grid
      |> String.split("\n", trim: true)
      |> parse_grid(parse_char)
      {position, _} = Enum.find(grid, fn {_, button} ->
        button === :activate
      end)
      %Keypad{position: position, grid: grid, parse: parse_char}
    end

    def press(pad, button) do
      button = pad.parse.(button)
      {to, _} = Enum.find(pad.grid, fn {_, b} -> b === button end)
      diff = sub(pad.position, to)
      moves = do_press(diff, to, pad.grid)
      Enum.each(moves, fn move ->

This file has been truncated. show original

ken-kost · January 7, 2025, 1:51pm

I implemented your solution and part 2 with real input does not pass for me.
For some reason it’s like the pads and button switch up and I get ** (CaseClauseError) no case clause matching: 60 i.e. a directional button goes with numeric pad. Test cases pass. I couldn’t figure out what might be the issue. It fails even if I add only 3 (one more) direct pad or more.
My input:

803A
528A
586A
341A
319A

Code:

defmodule Aoc2024.Solutions.Y24.Day21 do
  alias AoC.Input

  alias Aoc2024.Solutions.Y24.Day21.Keypad

  def parse(input, _part) do
    input
    |> Input.stream!(trim: true)
    |> Enum.map(fn code ->
      {number, _} = Integer.parse(code)
      {number, code}
    end)
  end

  def part_one(problem) do
    pads = [numeric(), direct(), direct()]

    problem
    |> Enum.map(fn {number, code} ->
      code
      |> String.to_charlist()
      |> press(pads)
      |> then(fn count -> number * count end)
    end)
    |> Enum.sum()
  end

  def part_two(problem) do
    pads = [numeric() | List.duplicate(direct(), 25)]

    problem
    |> Enum.map(fn {number, code} ->
      code
      |> String.to_charlist()
      |> press(pads)
      |> then(fn count -> number * count end)
    end)
    |> Enum.sum()
  end

  defp numeric() do
    parse = fn char ->
      case char do
        _ when char in ?0..?9 -> char - ?0
        ?A -> :activate
        ?. -> :panic
      end
    end

    """
    789
    456
    123
    .0A
    """
    |> Keypad.init(parse)
  end

  defp direct() do
    parse = &vector_dir/1

    """
    .^A
    <v>
    """
    |> Keypad.init(parse)
  end

  defp vector_dir(char) do
    case char do
      ?^ -> {-1, 0}
      ?< -> {0, -1}
      ?> -> {0, 1}
      ?v -> {1, 0}
      ?. -> :panic
      ?A -> :activate
    end
  end

  defp press(buttons, pads) do
    buttons |> press_recursive(pads) |> elem(0) |> count(0) |> elem(0)
  end

  defp press_recursive(buttons, pads) do
    Enum.map_reduce(buttons, pads, fn button, pads ->
      case pads do
        [] ->
          {count([button], _counter = 0), []}

        [pad | pads] ->
          cache_key = {button, pad.position, length(pads)}

          case Process.get(cache_key) do
            nil ->
              case button do
                {:alt, [alt | alts]} ->
                  {first, [pad | pads]} = press_recursive(alt, [pad | pads])

                  rest =
                    Enum.map(alts, fn alt ->
                      {buttons, _} = press_recursive(alt, [pad | pads])
                      buttons
                    end)

                  {count({:alt, [first | rest]}, 0), [pad | pads]}

                _ when is_integer(button) ->
                  {buttons, pad} = Keypad.press(pad, button)
                  {buttons, pads} = press_recursive(buttons, pads)
                  {count(buttons, 0), [pad | pads]}
              end
              |> then(fn {value, [pad | _rest] = pads} ->
                Process.put(cache_key, {value, pad})
                {value, pads}
              end)

            {value, pad} ->
              {value, [pad | pads]}
          end
      end
    end)
  end

  # Characters counts are enclosed in a tuple to
  # distinguish them from counting characters

  @spec count(integer() | {integer()} | [integer()] | {:alt, [integer()]}, integer()) ::
          {integer()}
  defp count(char, counter) when is_integer(char), do: {counter + 1}
  defp count({number}, counter), do: {number + counter}
  defp count([number | rest], counter), do: count(rest, counter + elem(count(number, 0), 0))
  defp count({:alt, alternatives}, counter), do: {counter + count_alternatives(alternatives)}
  defp count([], counter), do: {counter}

  defp count_alternatives(alternatives),
    do: alternatives |> Enum.map(&count(&1, 0)) |> Enum.min() |> elem(0)
end

defmodule Aoc2024.Solutions.Y24.Day21.Keypad do
  defstruct position: {0, 0}, grid: %{}, parse: nil

  def init(grid, parse_char) do
    grid =
      grid
      |> String.split("\n", trim: true)
      |> parse_grid(parse_char)

    {position, _} =
      Enum.find(grid, fn {_, button} ->
        button === :activate
      end)

    %__MODULE__{position: position, grid: grid, parse: parse_char}
  end

  def press(pad, button) do
    button = pad.parse.(button)
    {to, _} = Enum.find(pad.grid, fn {_, b} -> b === button end)
    diff = sub(pad.position, to)
    moves = do_press(diff, to, pad.grid)

    Enum.each(moves, fn move ->
      ^to = Enum.reduce(move, pad.position, &add/2)
    end)

    moves =
      Enum.map(moves, fn move ->
        Enum.map(move, &symbolic_dir/1) ++ [?A]
      end)

    moves =
      case moves do
        [move] -> move
        _ -> [{:alt, moves}]
      end

    pad = %{pad | position: to}

    {moves, pad}
  end

  defp do_press({0, 0}, _to, _grid), do: [[]]

  defp do_press(diff, to, grid) do
    [{-1, 0}, {0, -1}, {0, 1}, {1, 0}]
    |> Enum.filter(fn dir ->
      new_diff = add(diff, dir)
      new_pos = add(to, new_diff)

      Map.has_key?(grid, new_pos) and
        distance(new_diff) < distance(diff) and
        Map.fetch!(grid, add(to, new_diff)) !== :panic
    end)
    |> Enum.flat_map(fn dir ->
      new_diff = add(diff, dir)

      do_press(new_diff, to, grid)
      |> Enum.map(fn path ->
        [dir | path]
      end)
    end)
  end

  defp distance({a, b}), do: abs(a) + abs(b)

  defp symbolic_dir(dir) do
    case dir do
      {-1, 0} -> ?^
      {1, 0} -> ?v
      {0, -1} -> ?<
      {0, 1} -> ?>
    end
  end

  defp add({a, b}, {c, d}), do: {a + c, b + d}

  defp sub({a, b}, {c, d}), do: {a - c, b - d}

  defp parse_grid(grid, parse_char) do
    grid
    |> Enum.with_index()
    |> Enum.flat_map(fn {line, row} ->
      String.to_charlist(line)
      |> Enum.with_index()
      |> Enum.map(fn {char, col} ->
        position = {row, col}
        {position, parse_char.(char)}
      end)
    end)
    |> Map.new()
  end
end

Maybe you have some ideas what could be the issue?

bjorng · January 7, 2025, 3:08pm

I don’t know how your Input module is implemented, so I couldn’t run your code without modifications.

If run my code with your input, it doesn’t crash.

If I take your code and replace your parse function with my parse function, it produces the correct result for my input.

So I suspect that something is wrong with either your parse function or your Input module.

With your input, my parse function returns the following:

[{803, "803A"}, {528, "528A"}, {586, "586A"}, {341, "341A"}, {319, "319A"}]

ken-kost · January 7, 2025, 3:36pm

Thanks, I’ll try it out. impending update

ken-kost · January 8, 2025, 11:30am

I thought I could edit my post
Anyway, @bjorng

input
|> Input.stream!(trim: true) #=> #Stream<[
  enum: %File.Stream{
    path: "/home/ken/aoc_2024/priv/input/2024/day-21.inp",
    modes: [:raw, :read_ahead, :binary],
    line_or_bytes: :line,
    raw: true,
    node: :nonode@nohost
  },
  funs: [#Function<49.118167795/1 in Stream.map/2>,
   #Function<39.118167795/1 in Stream.filter/2>]
]>
|> Enum.map(fn code ->
  {number, _} = Integer.parse(code)
  {number, code}
end) #=> [{803, "803A"}, {528, "528A"}, {586, "586A"}, {341, "341A"}, {319, "319A"}]

[lib/aoc_2024/solutions/y24/day21.ex:15: Aoc2024.Solutions.Y24.Day21.parse/2]
parse2(Input.stream!(input, trim: true)) #=> [{803, "803A"}, {528, "528A"}, {586, "586A"}, {341, "341A"}, {319, "319A"}]

parse2 is your function - they return the same. I checked every other line of code multiple times, nothing stands out to me - everything is the same AFAIK. I’m flabbergasted to say the least.

Here is some more debug data I ran with pads = [numeric() | List.duplicate(direct(), 3)]:

"BUTTONS ~c\"^>A\""
[lib/aoc_2024/solutions/y24/day21.ex:103: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
cache_key #=> {65, {1, 2}, 2}

"LENGTH OF PADS 2"
[lib/aoc_2024/solutions/y24/day21.ex:105: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
pad #=> %Aoc2024.Solutions.Y24.Day21.Keypad{
  position: {1, 2},
  grid: %{
    {0, 0} => :panic,
    {0, 1} => {-1, 0},
    {0, 2} => :activate,
    {1, 0} => {0, -1},
    {1, 1} => {1, 0},
    {1, 2} => {0, 1}
  },
  parse: #Function<1.134059619/1 in Aoc2024.Solutions.Y24.Day21.vector_dir>
}

[lib/aoc_2024/solutions/y24/day21.ex:107: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
Process.get(cache_key) #=> {{17},
 %Aoc2024.Solutions.Y24.Day21.Keypad{
   position: {3, 2},
   grid: %{
     {0, 0} => 7,
     {0, 1} => 8,
     {0, 2} => 9,
     {1, 0} => 4,
     {1, 1} => 5,
     {1, 2} => 6,
     {2, 0} => 1,
     {2, 1} => 2,
     {2, 2} => 3,
     {3, 0} => :panic,
     {3, 1} => 0,
     {3, 2} => :activate
   },
   parse: #Function<2.134059619/1 in Aoc2024.Solutions.Y24.Day21.numeric/0>
 }}

"VALUE FOUND"
[lib/aoc_2024/solutions/y24/day21.ex:138: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
pad #=> %Aoc2024.Solutions.Y24.Day21.Keypad{
  position: {3, 2},
  grid: %{
    {0, 0} => 7,
    {0, 1} => 8,
    {0, 2} => 9,
    {1, 0} => 4,
    {1, 1} => 5,
    {1, 2} => 6,
    {2, 0} => 1,
    {2, 1} => 2,
    {2, 2} => 3,
    {3, 0} => :panic,
    {3, 1} => 0,
    {3, 2} => :activate
  },
  parse: #Function<2.134059619/1 in Aoc2024.Solutions.Y24.Day21.numeric/0>
}

"BUTTONS ~c\">^A\""
[lib/aoc_2024/solutions/y24/day21.ex:103: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
cache_key #=> {62, {3, 2}, 2}

"LENGTH OF PADS 2"
[lib/aoc_2024/solutions/y24/day21.ex:105: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
pad #=> %Aoc2024.Solutions.Y24.Day21.Keypad{
  position: {3, 2},
  grid: %{
    {0, 0} => 7,
    {0, 1} => 8,
    {0, 2} => 9,
    {1, 0} => 4,
    {1, 1} => 5,
    {1, 2} => 6,
    {2, 0} => 1,
    {2, 1} => 2,
    {2, 2} => 3,
    {3, 0} => :panic,
    {3, 1} => 0,
    {3, 2} => :activate
  },
  parse: #Function<2.134059619/1 in Aoc2024.Solutions.Y24.Day21.numeric/0>
}

[lib/aoc_2024/solutions/y24/day21.ex:107: Aoc2024.Solutions.Y24.Day21.press_recursive/2]
Process.get(cache_key) #=> nil

">"
part_two: Aoc2024.Solutions.Y24.Day21.part_two/1 error: ** (CaseClauseError) no case clause matching: 62
    (aoc_2024 0.1.0) lib/aoc_2024/solutions/y24/day21.ex:53: anonymous fn/1 in Aoc2024.Solutions.Y24.Day21.numeric/0
    (aoc_2024 0.1.0) lib/aoc_2024/solutions/y24/day21.ex:178: Aoc2024.Solutions.Y24.Day21.Keypad.press/2
    (aoc_2024 0.1.0) lib/aoc_2024/solutions/y24/day21.ex:124: anonymous fn/3 in Aoc2024.Solutions.Y24.Day21.press_recursive/2
    (elixir 1.18.0) lib/enum.ex:1840: Enum."-map_reduce/3-lists^mapfoldl/2-0-"/3
    (aoc_2024 0.1.0) lib/aoc_2024/solutions/y24/day21.ex:115: anonymous fn/2 in Aoc2024.Solutions.Y24.Day21.press_recursive/2
    (elixir 1.18.0) lib/enum.ex:1714: Enum."-map/2-lists^map/1-1-"/2
    (aoc_2024 0.1.0) lib/aoc_2024/solutions/y24/day21.ex:114: anonymous fn/3 in Aoc2024.Solutions.Y24.Day21.press_recursive/2
    (elixir 1.18.0) lib/enum.ex:1840: Enum."-map_reduce/3-lists^mapfoldl/2-0-"/3

The previous step succeeded because cache was found, but for the fail step nothing was found. I’ll give it another go later, this is a puzzle beyond advent of code for me, an exercise in debugging.

lud · January 8, 2025, 11:37am

AoC.Input.stream!(path) is just File.stream!(path)

AoC.Input.stream!(path, trim: true) is the same mapped with this:

      stream
      |> Stream.map(&String.trim/1)
      |> Stream.filter(fn
        "" -> false
        _ -> true
      end)

@ken-kost your code works on my machine and finds the right answer with my input. I just copypasted everything and replaced the Aoc2024 namespace with my own.

EDIT: OK I can reproduce it now. I was testing in an ExUnit test and it worked properly, but not straight from iex

EDIT2: OK I get it, it’s the part 1 that pollutes the process dictionary for part two. I guess you tried to run that with mix aoc.run and it keeps the same process. I’m very sorry for all the time you lost because of it. I’ll make sure to spawn a new process in the command to prevent process dictionary cache pollution.

ken-kost · January 8, 2025, 12:25pm

I’m very sorry for all the time you lost because of it

It’s totally fine, I’m glad you figured it out.
Yea, I do mix aoc.run

I enjoy using your lib, consider me QA.

So the process dictionary got polluted. Interesting. Makes sense now in hindsight.

lud · January 8, 2025, 12:48pm

<3

I guess because how you compute the cache level. But I am not sure why.

When I read your code I see that the cache key (using length(pads)) should have 0 for the numeric keypad, as it enters map_reduce first.

But I probably missed some logic because on part_one with this code:

        [pad | pads] ->
          pad_is_numeric? =
            case map_size(pad.grid) do
              12 -> true
              6 -> false
            end

          if pad_is_numeric? do
            length(pads) |> dbg()
          end

          cache_key = {button, pad.position, length(pads)}

You get 2,

And on part_two you get 25.

lud · January 8, 2025, 1:02pm

@ken-kost Can you upgrade :aoc to 0.14.0 and tell me if it’s working?

ken-kost · January 8, 2025, 1:19pm

Yep, working.