Advent of Code 2023 Days 15 and 16 Highlights

Continuing the catch up, let’s look at the solutions I came up with for day 15 and day 16 tasks of Advent of Code 2023. Both days were rather easy to solve, but I liked the tasks anyways.

Day 15 in Elixir: Just a simple Map

Code

Honestly, that’s not much interesting happening here. We do a straightforward parsing:

def parse_input(input) when is_binary(input) do
  input
  |> String.trim()
  |> String.replace("\n", "")
  |> String.split(",")
end

We then use Enum.reduce to calculate the hash:

def custom_hash(s) when is_binary(s) do
  String.to_charlist(s)
  |> Enum.reduce(0, fn code, acc -> rem((acc + code) * 17, 256) end)
end

And then we solve part 1:

def p1(input) when is_list(input), do: input |> Enum.map(&custom_hash/1) |> Enum.sum()

Day 15 Part 2

Part 2 is a bit more interesting, but primarily not because it’s hard or tricky, but because the task description is VERY LONG. Once you understand that you just need to maintain lists of tuples of lense labels and focal length mapped to their box id, it’s easy to implement with a simple Map containing a list.

We will need to re-parse the input before that, though:

def reparse(input) when is_list(input) do
  Enum.map(input, fn ins ->
    if String.ends_with?(ins, "-") do
      {:remove, String.trim_trailing(ins, "-")}
    else
      [label, focus] = String.split(ins, "=")
      {:put, label, String.to_integer(focus)}
    end
  end)
end

And now we can unleash Map.put, Map.get, Enum.find_index, List.replace_at and List.delete_at, all inside the ever useful Enum.reduce:

def run(instructions) when is_list(instructions) do
  Enum.reduce(instructions, %{}, fn ins, boxes ->
    box_id = custom_hash(elem(ins, 1))
    box = Map.get(boxes, box_id, [])

    case ins do
      {:put, label, focal_length} ->
        case Enum.find_index(box, fn {another_label, _} -> another_label == label end) do
          nil ->
            Map.put(boxes, box_id, [{label, focal_length} | box])

          idx when is_number(idx) ->
            box = List.replace_at(box, idx, {label, focal_length})
            Map.put(boxes, box_id, box)
        end

      {:remove, label} ->
        idx = Enum.find_index(box, fn {another_label, _} -> another_label == label end)

        if !is_nil(idx) do
          box = List.delete_at(box, idx)
          Map.put(boxes, box_id, box)
        else
          boxes
        end
    end
  end)
  |> Enum.reject(fn {_k, v} -> length(v) == 0 end)
  |> Enum.map(fn {k, v} -> {k, Enum.reverse(v)} end)
  |> Enum.into(%{})
end

It’s worth noting that List.replace_at and List.delete_at are not very efficient. However, the lists in question are so short and the number of entries is so small, this doesn’t matter so we don’t need to worry about optimizing it.

Now we can easily arrive at the solution for the part 2:

def p2(input) do
  input
  |> reparse()
  |> run()
  |> Enum.map(fn {box_id, lenses} ->
    Enum.with_index(lenses, 1)
    |> Enum.map(fn {{_label, focal_length}, pos} -> pos * focal_length * (box_id + 1) end)
    |> Enum.sum()
  end)
  |> Enum.sum()
end

Day 16 in Julia: Grids and Sets

Code

We are dealing with a grid again, so let’s do Julia. Parsing is the usual one-liner:

parse_input(input) = (
  @pipe input |> strip |> split(_, "\n") |> collect.(_) |> mapreduce(permutedims, vcat, _)
)

We should define an enum for our beam directions:

@enum Direction up down left right

And we should be able to move a beam (using CartesianIndex arithmetics) and also know if we escaped the grid:

function move(beam)
  (heading_to, direction) = beam

  if direction == up
    (heading_to + CartesianIndex(-1, 0), direction)
  elseif direction == down
    (heading_to + CartesianIndex(1, 0), direction)
  elseif direction == left
    (heading_to + CartesianIndex(0, -1), direction)
  elseif direction == right
    (heading_to + CartesianIndex(0, 1), direction)
  end
end

function isinside(beam, grid)
  (heading_to, _direction) = beam
  (heading_to[1] >= 1 && heading_to[2] >= 1 &&
    heading_to[1] <= size(grid)[1] && heading_to[2] <= size(grid)[2])
end

And we can also reflect the beams (this can be shortened a bit by doing inner ifs, but I wanted a one condition to result kind of thing - makes it easy to see if you screw something up):

function reflect(beam, tile)
  (heading_to, direction) = beam

  new_direction =
    if direction == right && tile == '/'
      up
    elseif direction == left && tile == '/'
      down
    elseif direction == up && tile == '/'
      right
    elseif direction == down && tile == '/'
      left
    elseif direction == right && tile == '\\'
      down
    elseif direction == left && tile == '\\'
      up
    elseif direction == up && tile == '\\'
      left
    elseif direction == down && tile == '\\'
      right
    end

  (heading_to, new_direction)
end

And now we are all set to do our simulation! The key here is figuring out a stopping condition. Originally, I messed that up a bit, by looking for the full repetition of all beam state - it still worked, but did a lot of useless iterations, so I used @threads to speed it up. I arrived at the solution for the part 2 (we’ll talk about it in a sec) after 84 seconds running on 24 threads.

After some thinking though, I figured that I only need to track beams entering a new tile or entering a tile from a new direction. Since I modelled beams as a tuple of heading_to (the tile a beam enters next turn, represented as CartesianIndex) and a direction (one of our Direction enum values), we can just use a set of the beams we’ve seen. We also only need to track the “new” beams. That lead to a solution that is sub-second for part 2 as well, so I didn’t need to do my multithreading trick anymore.

Anyhow, here’s our simulation function:

function simulate(grid, start=(CartesianIndex(1, 1), right))
  energized, beams, seen = falses(size(grid)...), [start], Set([start])

  while !isempty(beams)
    beam = pop!(beams)
    push!(seen, beam)

    (heading_to, direction) = beam
    energized[heading_to] = true
    tile = grid[heading_to]

    new_beams =
      if (
        tile == '.' ||
        (tile == '-' && direction ∈ [left, right]) ||
        (tile == '|' && direction ∈ [up, down])
      )
        [move(beam)]
      elseif tile == '/' || tile == '\\'
        [reflect(beam, tile) |> move]
      elseif tile == '-'
        move.([(heading_to, left), (heading_to, right)])
      elseif tile == '|'
        move.([(heading_to, up), (heading_to, down)])
      end

    @pipe filter(beam -> isinside(beam, grid) && beam ∉ seen, new_beams) |> append!(beams, _)
  end

  energized
end

We maintain a vector of beams we still need to track, a set of seen beams, and we stop once we exhaust the beams vector. Each step, we pop a beam from beams, add it to seen, energize the corresponding tile (we keep track of energized tiles with a BitMatrix energized) and then, depending on the tile and the beam we create a vector of new_beams.

We have 4 cases here:

• if it’s an empty tile or a splitter in the parallel direction of the beam, we just move the beam one step
• if it’s a mirror, we reflect the beam and move it one step
• if it’s a horizontal splitter and the beam is running vertically, we split it into left and right beams and move them (just broadcasting move function over the 2 beam array)
• if it’s a vertical splitter and the beam is running horizontally, we split it into up and down beams and move them (again, using broadcasting).

We can then filter out the new_beams that are outside the grid or have been seen before, and append! the remaining ones to the beams vector.

In the end, when there’s nothing new to explore, we just return energized bit matrix. The part 1 is now solved with a simple sum over the matrix:

p1(grid) = simulate(grid) |> sum

Day 16 Part 2

Given an efficient implementation of the beam simulation above, solving part 2 is just a matter of creating an array of all possible starting beams and running maximum over their simulated energized matrices:

function all_starts(grid)
  starts = [(CartesianIndex(1, col), down) for col in 1:size(grid)[2]]
  append!(starts, [(CartesianIndex(size(grid)[1], col), up) for col in 1:size(grid)[2]])
  append!(starts, [(CartesianIndex(row, 1), right) for row in 1:size(grid)[1]])
  append!(starts, [(CartesianIndex(row, size(grid)[2]), left) for row in 1:size(grid)[1]])

  starts
end

p2(grid) = maximum(start -> simulate(grid, start) |> sum, all_starts(grid))

Honestly, it sometimes feels like using Julia for these kinds of tasks is like cheating :)