Python

Also on Github

53.059 line-seconds (ranks third hardest after days 8 and 12 so far).

from .solver import Solver


def _trace_beam(data, initial_beam_head):
  wx = len(data[0])
  wy = len(data)
  beam_heads = [initial_beam_head]
  seen_beam_heads = set()
  while beam_heads:
    next_beam_heads = []
    for x, y, dx, dy in beam_heads:
      seen_beam_heads.add((x, y, dx, dy))
      nx, ny = (x + dx), (y + dy)
      if nx < 0 or nx >= wx or ny < 0 or ny >= wy:
        continue
      obj = data[ny][nx]
      if obj == '|' and dx != 0:
        next_beam_heads.append((nx, ny, 0, 1))
        next_beam_heads.append((nx, ny, 0, -1))
      elif obj == '-' and dy != 0:
        next_beam_heads.append((nx, ny, 1, 0))
        next_beam_heads.append((nx, ny, -1, 0))
      elif obj == '/':
        next_beam_heads.append((nx, ny, -dy, -dx))
      elif obj == '\\':
        next_beam_heads.append((nx, ny, dy, dx))
      else:
        next_beam_heads.append((nx, ny, dx, dy))
    beam_heads = [x for x in next_beam_heads if x not in seen_beam_heads]
  energized = {(x, y) for x, y, _, _ in seen_beam_heads}
  return len(energized) - 1


class Day16(Solver):

  def __init__(self):
    super().__init__(16)

  def presolve(self, input: str):
    data = input.splitlines()
    self.possible_energized_cells = (
      [_trace_beam(data, (-1, y, 1, 0)) for y in range(len(data))] +
      [_trace_beam(data, (x, -1, 0, 1)) for x in range(len(data[0]))] +
      [_trace_beam(data, (len(data[0]), y, -1, 0)) for y in range(len(data))] +
      [_trace_beam(data, (x, len(data), 0, -1)) for x in range(len(data[0]))])


  def solve_first_star(self) -> int:
    return self.possible_energized_cells[0]

  def solve_second_star(self) -> int:
    return max(self.possible_energized_cells)

C

Just tracing the ray. When it splits, recurse one way and continue the other. Didn't bother with a direction lookup table this time, just a few ifs. The ray ends when it goes out of bounds or a ray in that direction has been previously traced on a given cell (this is tracked with a separate table).

It would've been straightforward if I hadn't gotten the 'previously visited' check wrong 😞. I was checking against the direction coming in of the tile but marking the direction going out.

Ray function:

static void
ray(int x, int y, int dir)
{
	int c;

	while (x>=0 && y>=0 && x

Haskell

A pretty by-the-book "walk all paths" algorithm. This could be made a lot faster with some caching.

import Control.Monad
import Data.Array.Unboxed (UArray)
import qualified Data.Array.Unboxed as A
import Data.Foldable
import Data.Set (Set)
import qualified Data.Set as Set

type Pos = (Int, Int)

readInput :: String -> UArray Pos Char
readInput s =
  let rows = lines s
   in A.listArray ((1, 1), (length rows, length $ head rows)) $ concat rows

energized :: (Pos, Pos) -> UArray Pos Char -> Set Pos
energized start grid = go Set.empty $ Set.singleton start
  where
    go seen beams
      | Set.null beams = Set.map fst seen
      | otherwise =
          let seen' = seen `Set.union` beams
              beams' = Set.fromList $ do
                ((y, x), (dy, dx)) <- toList beams
                d'@(dy', dx') <- case grid A.! (y, x) of
                  '/' -> [(-dx, -dy)]
                  '\\' -> [(dx, dy)]
                  '|' | dx /= 0 -> [(-1, 0), (1, 0)]
                  '-' | dy /= 0 -> [(0, -1), (0, 1)]
                  _ -> [(dy, dx)]
                let p' = (y + dy', x + dx')
                    beam' = (p', d')
                guard $ A.inRange (A.bounds grid) p'
                guard $ beam' `Set.notMember` seen'
                return beam'
           in go seen' beams'

part1 = Set.size . energized ((1, 1), (0, 1))

part2 input = maximum counts
  where
    (_, (h, w)) = A.bounds input
    starts =
      concat $
        [[((y, 1), (0, 1)), ((y, w), (0, -1))] | y <- [1 .. h]]
          ++ [[((1, x), (1, 0)), ((h, x), (-1, 0))] | x <- [1 .. w]]
    counts = map (\s -> Set.size $ energized s input) starts

main = do
  input <- readInput <$> readFile "input16"
  print $ part1 input
  print $ part2 input

Scala3

This could be much more efficient (and quite a bit shorter), but I wanted to try out the scala-graph library (https://www.scala-graph.org)

import day10._
import day10.Dir._
import scalax.collection.edges.DiEdge
import scalax.collection.immutable.Graph
import scalax.collection.edges.DiEdgeImplicits
import scalax.collection.generic.AnyEdge
import scalax.collection.generic.Edge

case class Node(ps: Set[Pos])

def getNode(p: Pos, d: Dir) = Node(Set(p, walk(p, d)))
def connect(p: Pos, d1: Dir, d2: Dir) = List(getNode(p, d1) ~> getNode(p, d2), getNode(p, d2) ~> getNode(p, d1))

def parseGrid(a: List[List[Char]]) = 
    def parseCell(s: Char, pos: Pos) =
        s match
            case '.' => connect(pos, Left, Right) ++ connect(pos, Up, Down)
            case '/' => connect(pos, Left, Up) ++ connect(pos, Right, Down)
            case '\\' => connect(pos, Left, Down) ++ connect(pos, Right, Up)
            case '-' => connect(pos, Left, Right) ++ List(
                getNode(pos, Up) ~> getNode(pos, Left), getNode(pos, Up) ~> getNode(pos, Right),
                getNode(pos, Down) ~> getNode(pos, Left), getNode(pos, Down) ~> getNode(pos, Right),
            )
            case '|' => connect(pos, Up, Down) ++ List(
                getNode(pos, Left) ~> getNode(pos, Up), getNode(pos, Left) ~> getNode(pos, Down),
                getNode(pos, Right) ~> getNode(pos, Up), getNode(pos, Right) ~> getNode(pos, Down),
            )
            case _ => List().ensuring(false)
        
    val edges = a.zipWithIndex.flatMap((r, y) => r.zipWithIndex.map((v, x) => v -> Pos(x, y))).map(parseCell).reduceLeft((a, b) => a ++ b)
    Graph() ++ edges

def illuminationFrom(p: Pos, d: Dir, g: Graph[Node, DiEdge[Node]], inBounds: Pos => Boolean): Long =
    val es = getNode(p, d.opposite) ~> getNode(p, d)
    val g2 = g + es
    val n = g2.get(getNode(p, d))
    n.outerNodeTraverser.flatMap(_.ps).toSet.filter(inBounds).size

def inBounds(a: List[String])(p: Pos) = p.x >= 0 && p.x < a(0).size && p.y >= 0 && p.y < a.size

def task1(a: List[String]): Long = 
    illuminationFrom(Pos(-1, 0), Right, parseGrid(a.map(_.toList)), inBounds(a))

def task2(a: List[String]): Long = 
    val inits = (for y <- a.indices yield Seq((Pos(-1, y), Right), (Pos(a(y).size, y), Left)))
        ++ (for x <- a(0).indices yield Seq((Pos(x, -1), Down), (Pos(x, a.size), Up)))

    val g = parseGrid(a.map(_.toList))
    inits.flatten.map((p, d) => illuminationFrom(p, d, g, inBounds(a))).max