Advent of Code 2023 - Day 16

Pretty straightforward.
A MapSet to prevent loops and brute force.

import AOC

aoc 2023, 16 do
  def p1(input) do
    input
    |> Grid.parse()
    |> then(fn {max, grid} -> {max, Map.new(grid)} end)
    |> compute({{0, 0}, :east})
  end

  def compute(grid, start) do
    grid
    |> recurse([start], MapSet.new(), MapSet.new())
    |> Enum.count()
  end

  def p2(input) do
    {{rows, cols}, points} = input |> Grid.parse()
    grid = {{rows, cols}, Map.new(points)}

    (for row <- 0..(rows-1), do: [{{row, 0}, :east}, {{row, cols-1}, :west}] ++
    for col <- 0..(cols-1), do: [{{0, col}, :south}, {{rows-1, col}, :north}])
    |> List.flatten()
    |> Enum.map(&compute(grid, &1))
    |> Enum.max()
  end

  def recurse(_, [], energized, _), do: energized
  def recurse({_, map} = grid, [active | actives], energized, seen) do
    {active_pos, active_dir} = active
    if not MapSet.member?(seen, active) and Grid.in?(grid, active_pos) do
      energized_new = MapSet.put(energized, active_pos)
      seen_new = MapSet.put(seen, active)
      f = fn candidates -> candidates |> Kernel.++(actives) |> then(&recurse(grid, &1, energized_new, seen_new)) end
      item = map[active_pos]
      cond do
        item == "." or
        (item == "|" and active_dir in [:north, :south]) or
        (item == "-" and active_dir in [:east, :west]) -> f.([next(active)])
        item == "|" -> f.([next({active_pos, :north}), next({active_pos, :south})])
        item == "-" -> f.([next({active_pos, :west}), next({active_pos, :east})])
        item == "/" -> f.([next({active_pos, flip_sw(active_dir)})])
        item == "\\" -> f.([next({active_pos, flip_se(active_dir)})])
      end
    else
      recurse(grid, actives, energized, seen)
    end
  end

  def flip_sw(dir), do: %{north: :east, south: :west, west: :south, east: :north}[dir]
  def flip_se(dir), do: %{north: :west, south: :east, west: :north, east: :south}[dir]
  def next({{row, col}, :west}), do: {{row, col-1}, :west}
  def next({{row, col}, :east}), do: {{row, col+1}, :east}
  def next({{row, col}, :north}), do: {{row-1, col}, :north}
  def next({{row, col}, :south}), do: {{row+1, col}, :south}
end

TIL of ~w()a to generate a list of atoms instead of words, pretty cool!

https://github.com/woojiahao/aoc/blob/main/lib/aoc/y2023/day_16.ex

My solution:

https://github.com/bjorng/advent-of-code-2023/blob/main/day16/lib/day16.ex

Not that interested in today’s puzzles.

Parsing input

grid =
  for {row, i} <- puzzle_input |> String.split() |> Stream.with_index(),
      {val, j} <- row |> String.to_charlist() |> Stream.with_index(),
      into: %{},
      do: {{i, j}, val}

Solutions for both parts

defmodule AoC2023.Day16 do
  def part1(grid) do
    shoot(grid, {0, 0}, {0, 1}, MapSet.new())
    |> count_energized()
  end

  def part2(grid) do
    {max_i, max_j} = grid |> Map.keys() |> Enum.max()

    count =
      0..max_i
      |> Enum.map(&{&1, 0})
      |> Task.async_stream(&count_energized(shoot(grid, &1, {0, 1}, MapSet.new())), ordered: false)
      |> Enum.max()

    count =
      0..max_i
      |> Enum.map(&{&1, max_j})
      |> Task.async_stream(&count_energized(shoot(grid, &1, {0, -1}, MapSet.new())), ordered: false)
      |> Enum.reduce(count, &max/2)

    count =
      0..max_j
      |> Enum.map(&{0, &1})
      |> Task.async_stream(&count_energized(shoot(grid, &1, {1, 0}, MapSet.new())), ordered: false)
      |> Enum.reduce(count, &max/2)


    count =
      0..max_j
      |> Enum.map(&{max_i, &1})
      |> Task.async_stream(&count_energized(shoot(grid, &1, {-1, 0}, MapSet.new())), ordered: false)
      |> Enum.reduce(count, &max/2)

    elem(count, 1)
  end

  defp count_energized(set) do
    set
    |> Enum.map(&elem(&1, 0))
    |> Enum.uniq()
    |> length()
  end

  defp shoot(grid, {i, j} = position, {di, dj} = direction, acc) do
    if {position, direction} in acc do
      acc
    else
      case grid[position] do
        nil ->
          acc
  
        ?. ->
          shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
  
        ?\\ ->
          shoot(grid, {i + dj, j + di}, {dj, di}, MapSet.put(acc, {position, direction}))
  
        ?/ ->
          shoot(grid, {i - dj, j - di}, {-dj, -di}, MapSet.put(acc, {position, direction}))
  
        ?- when di == 0 ->
          shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
  
        ?| when dj == 0 ->
          shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
  
        ?- ->
          acc = shoot(grid, {i, j - 1}, {0, -1}, MapSet.put(acc, {position, direction}))
          shoot(grid, {i, j + 1}, {0, 1}, MapSet.put(acc, {position, direction}))

        ?| ->
          acc = shoot(grid, {i - 1, j}, {-1, 0}, MapSet.put(acc, {position, direction}))
          shoot(grid, {i + 1, j}, {1, 0}, MapSet.put(acc, {position, direction}))
      end
    end
  end
end

Hello,

I was afraid that the second part would ask to rotate mirrors to create the maximum energy but thanks it was much easier.

I have no idea how to optimize that so I just simulate all the beams for part 2, and it takes more than one second. Any idea?

https://github.com/lud/adventofcode/blob/main/lib/solutions/2023/day16.ex

I did the same. It also took me more than 1 second to run, so I just parallelized them

Ah yes I generally do not use task async stream because I like to debug the outputs but now that it works, i’ll try it

Edit: yeah, 500ms, good enough, thanks!

Also ordered: false comes in handy

I believe it’s possible to memoize the paths given (row, column, direction). Since you’re just choosing a different starting position, but if the beam traveling left reaches \, it should still be the same path throughout. Though, I did not try this out so it could be false

Bruteforced part 2 without memoization… takes around 16 seconds in LiveBook on my M2 Pro.

https://github.com/pehbehbeh/adventofcode/blob/main/2023/16.livemd

Not sure if this is the right place to post this (and also probably a silly question), but how are y’all parsing the example input? It seems like the escape character is messing up the rows. I’m just doing a simple String.split(input, "\n"), but the lists/rows are not equal length.