Advent of Code 2024 - Day 15

For part 2, I had a mixed feeling about Elixir. The good part is that immutability and persistent data structures eliminate the need for backtracking. The bad part is that there’s no early return in Elixir, so I had to throw everywhere. The stupid thing is, I accidentally deleted my code again!

Oh I’d hate to accidentally delete my code for this one… I usually use reduce_while/3 if I need to return early. Tons of it in this problem.

Another fun puzzle.

https://github.com/bjorng/advent-of-code/blob/main/2024/day15/lib/day15.ex

I thought it was going to be tedious at first but in the end, just a couple modifications from part one are enough. This runs in 15ms:

https://github.com/lud/adventofcode/blob/main/lib/solutions/2024/day15.ex

After refactoring in part 2 I ended up with a recursive movable() function to return a list of movable positions or nil if blocked. I update the map in a second step.

https://github.com/liamcmitchell/advent-of-code/blob/e659d35a8a6019bf61c6faac2b514205248f4b21/2024/15/1.exs#L107-L132

I can’t get the solution for part 2. Using the example input, my grid does not look like the one in the puzzle after executing the movements. I even visualized the movements, but can’t figure out where my player does something wrong.

I guess, it is something with pushing the boxes, but I do handle the case where one box pushes two boxes simultaneously

Here are the first 30 seconds visualized (video took longer than 30 seconds, so the full run does not fit in one gif)

This is my grid after all movements:

####################
##[][]........[][]##
##[]..........[][]##
##...@..........[]##
##.............[].##
##..##[][]....[][]##
##...[]..[]...[]..##
##.....[]..[].[][]##
##........[]......##
####################

EDIT: I figured it out now. I did not consider that the player can push boxes that are diagonally placed above / under the player.

I guess, I made part 2 more complicated than it is, but might come back to optimizing it. My source code:

https://github.com/Flo0807/adventofcode/blob/main/2024/15.livemd

Day n of failing to quit Advent of Code…

This one killed me. Part 2 took me hours. It wasn’t helped by the fact I had a sneaky bug and ended up stepping through the “bigger example” frame by frame to find the edge case. At least the whole thing runs in less than 10ms.

Probably the most interesting thing I did was store the directions as anonymous functions that I then applied to the coordinates.

moves =
  for <<char::binary-1 <- String.replace(raw_moves, "\n", "")>> do
    case char do
      "^" -> fn {x, y} -> {x, y - 1} end
      "v" -> fn {x, y} -> {x, y + 1} end
      "<" -> fn {x, y} -> {x - 1, y} end
      ">" -> fn {x, y} -> {x + 1, y} end
    end
  end

It actually made debugging more difficult though, because #Function<13.8856859/1 in Day15.input/0> doesn’t tell you which direction it’s going without running the function…

I don’t know what you did but it sounds very different to what I did, which was store the boxes/walls in a map, and assume everything else was free space. Only needed to update any state when the boxes moved.

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2024/day15.exs

Here is my solution. I’m pretty happy with it, I find it rather neat :

defmodule Y2024.D15.Guards do
  defguard is_vertical(step) when step == "^" or step == "v"
  defguard is_horizontal(step) when step == "<" or step == ">"
  defguard is_box(cell) when cell == "[" or cell == "]"
end

defmodule Y2024.D15 do
  use Day, input: "2024/15", part1: ~c"c", part2: ~c"c"

  import Y2024.D15.Guards

  defp partX(input, transform \\ & &1) do
    {grid, steps} = parse_input(input)

    map =
      grid
      |> transform.()
      |> to_map()

    {start_rc, "@"} = Enum.find(map, &(elem(&1, 1) == "@"))

    steps
    |> Enum.reduce({map, start_rc}, &try/2)
    |> elem(0)
    |> locate()
  end

  defp part1(input), do: partX(input)

  defp part2(input), do: partX(input, &widen/1)

  defp try(step, {map, rc}) do
    if can?(map, rc, step) do
      {act(map, rc, step), to(rc, step)}
    else
      {map, rc}
    end
  end

  defp can?(_, _, ".", _, _), do: true
  defp can?(_, _, "#", _, _), do: false

  defp can?(map, rc, "[", step, expand?) when is_vertical(step) do
    can?(map, to(rc, step), step) and (not expand? or can?(map, to(rc, ">"), step, false))
  end

  defp can?(map, rc, "]", step, expand?) when is_vertical(step) do
    can?(map, to(rc, step), step) and (not expand? or can?(map, to(rc, "<"), step, false))
  end

  defp can?(map, rc, _, step, _), do: can?(map, to(rc, step), step)
  defp can?(map, rc, step, expand? \\ true), do: can?(map, rc, Map.get(map, rc), step, expand?)

  defp act(map, _, ".", _, _), do: map

  defp act(map, rc, cell, step, expand?) when is_box(cell) and is_vertical(step) do
    map
    |> act(to(rc, step), step)
    |> Map.replace(to(rc, step), cell)
    |> Map.replace(rc, ".")
    |> then(fn m ->
      if expand? do
        act(m, rc |> to(expand_dir(cell)), step, false)
      else
        m
      end
    end)
  end

  defp act(map, rc, cell, step, _) do
    map
    |> act(to(rc, step), step)
    |> Map.replace(to(rc, step), cell)
    |> Map.replace(rc, ".")
  end

  defp act(map, rc, step, expand? \\ true), do: act(map, rc, Map.get(map, rc), step, expand?)

  defp locate({{r, c}, "O"}), do: r * 100 + c
  defp locate({{r, c}, "["}), do: r * 100 + c
  defp locate({_, _}), do: 0

  defp locate(map) do
    map
    |> Enum.map(&locate/1)
    |> Enum.sum()
  end

  defp widen(grid) do
    Enum.map(grid, fn row ->
      Enum.flat_map(row, fn
        "." -> [".", "."]
        "#" -> ["#", "#"]
        "O" -> ["[", "]"]
        "@" -> ["@", "."]
      end)
    end)
  end

  defp to({r, c}, {dr, dc}), do: {r + dr, c + dc}
  defp to(rc, step), do: to(rc, dir(step))

  defp expand_dir("]"), do: dir("<")
  defp expand_dir("["), do: dir(">")

  defp dir("^"), do: {-1, 0}
  defp dir("v"), do: {+1, 0}
  defp dir("<"), do: {0, -1}
  defp dir(">"), do: {0, +1}

  defp to_map(grid) do
    grid
    |> Enum.with_index()
    |> Enum.flat_map(fn {row, r} ->
      row
      |> Enum.with_index()
      |> Enum.map(fn {cell, c} -> {{r, c}, cell} end)
    end)
    |> Enum.into(%{})
  end

  defp parse_input(input) do
    [map_chunck, steps_chunk] = input

    {parse_grid(map_chunck), parse_steps(steps_chunk)}
  end

  defp parse_grid(grid_chunk), do: Enum.map(grid_chunk, &Utils.splitrim/1)

  defp parse_steps(steps_chunk) do
    steps_chunk
    |> Enum.join("")
    |> Utils.splitrim("")
  end
end

I have been disturbed by this wording :

For these larger boxes, distances are measured from the edge of the map to the closest edge of the box in question.

It made me believe that we had to add mechanics with the right and bottom edges for a while.

I was worried about that too, but carefully looking at the example showed that it wasn’t necessary. I think the x + 100y requirement is just a simple way to convert a bunch of coordinates to a single number for the purposes of submitting an answer.

I do find it funny how AoC sometimes ties itself in knots explaining a very simple problem like getting an x,y coordinate, while at the same time writing problems where the optimal solution requires prior knowledge such as modulo, quadratic formula, Chinese remainder theorem, graph theory, shortest path algorithm, etc. etc.

part 1 was easy .. didnt bother sharing it yesterday .. plus its been awful amount of tile puzzles

but part 2.. thats a fun puzzle .. so in the end after endless refactoring, throwing away, and repeat, i just said eff it .. there is no rule i cant just parse the input and replace all single #, O and . with two of them … then it became awful lot easier to parse the new map .. plus i decided to add ids to the tiles, so i can cross reference it later ..

link: advent_of_code/solutions/2024/day_15/lib/Part2.ex at master · jarlah/advent_of_code · GitHub

now ill maybe go actually solve the problem of gaming programming …