Nim

I’m caught up!

This one was pretty straighforward. Iterate through the beam path, recursively creating new beams when you hit splitters. The only gotcha is that you need a way to detect infinite loops that can be created by splitters. I opted to record energized non-special tiles as - or |, depending on which way the beam was traveling, and then abort any path that retreads those tiles in the same way. I meant to also use + for where the beams cross, but I forgot and it turned out not to be necessary.

Part 2 was pretty trivial once the code for part 1 was written.

• Day 16, part 1
• Day 16, part 2

Python

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)

Rust

I simply check each starting position individually for Part 2, I don’t know if there are more clever solutions. Initially that approach ran in 180ms which is a lot more than any of the previous puzzles needed, so I tried if I could optimize it.

Initially I was using two hash sets, one for counting unique energized fields, and one for detecting cycles which also included the direction in the hash. Going from the default rust hasher to FxHash sped it up to 100ms. Seeing that, I thought that this point could be further improved upon, and ended up replacing both hash sets with boolean arrays, since their size is neatly bounded by the input field size. Now it runs in merely 30ms, meaning a 6x speedup just by getting rid of the hashing.

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

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<w && y<h) {
		if (beams[y][x] & (1 << dir))
			break;

		beams[y][x] |= 1 << dir;
		c = map[y][x];

		if (dir==NN && c=='/')  dir = EE; else
		if (dir==EE && c=='/')  dir = NN; else
		if (dir==SS && c=='/')  dir = WW; else
		if (dir==WW && c=='/')  dir = SS; else
		if (dir==NN && c=='\\') dir = WW; else
		if (dir==EE && c=='\\') dir = SS; else
		if (dir==SS && c=='\\') dir = EE; else
		if (dir==WW && c=='\\') dir = NN; else
		if (dir==NN && c=='-') { ray(x,y,WW); dir = EE; } else
		if (dir==SS && c=='-') { ray(x,y,WW); dir = EE; } else
		if (dir==EE && c=='|') { ray(x,y,NN); dir = SS; } else
		if (dir==WW && c=='|') { ray(x,y,NN); dir = SS; } 

		x += dir==EE ? 1 : dir==WW ? -1 : 0;
		y += dir==SS ? 1 : dir==NN ? -1 : 0;
	}
}

https://github.com/sjmulder/aoc/blob/master/2023/c/day16.c-

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

Haskell

A bit of a mess, I probably shouldn’t have used RWS …

import Control.Monad.RWS
import Control.Parallel.Strategies
import Data.Array
import qualified Data.ByteString.Char8 as BS
import Data.Foldable (Foldable (maximum))
import Data.Set
import Relude

data Cell = Empty | VertSplitter | HorizSplitter | Slash | Backslash deriving (Show, Eq)

type Pos = (Int, Int)

type Grid = Array Pos Cell

data Direction = N | S | E | W deriving (Show, Eq, Ord)

data BeamHead = BeamHead
  { pos :: Pos,
    dir :: Direction
  }
  deriving (Show, Eq, Ord)

type Simulation = RWS Grid (Set Pos) (Set BeamHead)

next :: BeamHead -> BeamHead
next (BeamHead p d) = BeamHead (next' d p) d
  where
    next' :: Direction -> Pos -> Pos
    next' direction = case direction of
      N -> first pred
      S -> first succ
      E -> second succ
      W -> second pred

advance :: BeamHead -> Simulation [BeamHead]
advance bh@(BeamHead position direction) = do
  grid <- ask
  seen <- get

  if inRange (bounds grid) position && bh `notMember` seen
    then do
      tell $ singleton position
      modify $ insert bh
      pure . fmap next $ case (grid ! position, direction) of
        (Empty, _) -> [bh]
        (VertSplitter, N) -> [bh]
        (VertSplitter, S) -> [bh]
        (HorizSplitter, E) -> [bh]
        (HorizSplitter, W) -> [bh]
        (VertSplitter, _) -> [bh {dir = N}, bh {dir = S}]
        (HorizSplitter, _) -> [bh {dir = E}, bh {dir = W}]
        (Slash, N) -> [bh {dir = E}]
        (Slash, S) -> [bh {dir = W}]
        (Slash, E) -> [bh {dir = N}]
        (Slash, W) -> [bh {dir = S}]
        (Backslash, N) -> [bh {dir = W}]
        (Backslash, S) -> [bh {dir = E}]
        (Backslash, E) -> [bh {dir = S}]
        (Backslash, W) -> [bh {dir = N}]
    else pure []

simulate :: [BeamHead] -> Simulation ()
simulate heads = do
  heads' <- foldMapM advance heads
  unless (Relude.null heads') $ simulate heads'

runSimulation :: BeamHead -> Grid -> Int
runSimulation origin g = size . snd . evalRWS (simulate [origin]) g $ mempty

part1, part2 :: Grid -> Int
part1 = runSimulation $ BeamHead (0, 0) E
part2 g = maximum $ parMap rpar (`runSimulation` g) possibleInitials
  where
    ((y0, x0), (y1, x1)) = bounds g
    possibleInitials =
      join
        [ [BeamHead (y0, x) S | x <- [x0 .. x1]],
          [BeamHead (y1, x) N | x <- [x0 .. x1]],
          [BeamHead (y, x0) E | y <- [y0 .. y1]],
          [BeamHead (y, x1) W | y <- [y0 .. y1]]
        ]

parse :: ByteString -> Maybe Grid
parse input = do
  let ls = BS.lines input
      h = length ls
  w <- BS.length <$> viaNonEmpty head ls
  mat <- traverse toCell . BS.unpack $ BS.concat ls
  pure $ listArray ((0, 0), (h - 1, w - 1)) mat
  where
    toCell '.' = Just Empty
    toCell '|' = Just VertSplitter
    toCell '-' = Just HorizSplitter
    toCell '/' = Just Slash
    toCell '\\' = Just Backslash
    toCell _ = Nothing

Dart

I’m cheating a bit by posting this as it does take 11s for the full part 2 solution, but having tracked down and eliminated the excessively long path for part 1, I can’t be bothered to do it again for part 2.

I’m an idiot. Avoiding recursively adding the same points to the seen set dropped total runtime to a hair under 0.5s, so line-seconds are around 35.

Map, Set>> seen = {};

Map fire(List> grid, Point here, Point dir) {
  seen = {};
  return _fire(grid, here, dir);
}

Map, Set>> _fire(
    List> grid, Point here, Point dir) {
  while (true) {
    here += dir;
    if (!here.x.between(0, grid.first.length - 1) ||
        !here.y.between(0, grid.length - 1)) {
      return seen;
    }
    if (seen[here]?.contains(dir) ?? false) return seen;
    seen[here] = (seen[here] ?? >{})..add(dir);

    Point split() {
      _fire(grid, here, Point(-dir.y, -dir.x));
      return Point(dir.y, dir.x);
    }

    dir = switch (grid[here.y][here.x]) {
      '/' => Point(-dir.y, -dir.x),
      r'\' => Point(dir.y, dir.x),
      '|' => (dir.x.abs() == 1) ? split() : dir,
      '-' => (dir.y.abs() == 1) ? split() : dir,
      _ => dir,
    };
  }
}

parse(List lines) => lines.map((e) => e.split('').toList()).toList();

part1(List lines) =>
    fire(parse(lines), Point(-1, 0), Point(1, 0)).length;

part2(List lines) {
  var grid = parse(lines);
  var ret = 0.to(grid.length).fold(
      0,
      (s, t) => [
            s,
            fire(grid, Point(-1, t), Point(1, 0)).length,
            fire(grid, Point(grid.first.length, t), Point(-1, 0)).length
          ].max);
  return 0.to(grid.first.length).fold(
      ret,
      (s, t) => [
            s,
            fire(grid, Point(t, -1), Point(0, 1)).length,
            fire(grid, Point(t, grid.length), Point(0, -1)).length
          ].max);
}

C#

Breadth-first search, then take the max of the values of searches starting from all the edge tiles.
https://code.dinn.ca/stevedinn/AdventOfCode/src/branch/main/2023/day16/Program.cs

Golang

Avoided recursion by having an array of “pending paths”. Whenever I hit a splitter, I follow one of the paths straight away, and push the starting point and direction of the other path to the array.

First time I ran it, hit an infinite loop. Handled it by skipping “|” and “-” if they have been visited already.

Part 2 is the same code as part 1 but I just check all the possible starting points.

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Direction int

const (
	UP    Direction = 0
	DOWN  Direction = 1
	LEFT  Direction = 2
	RIGHT Direction = 3
)

type LightPoint struct {
	row int
	col int
	dir Direction
}

func solve(A [][]rune, start LightPoint) int {
	m := len(A)
	n := len(A[0])
	visited := make([]bool, m*n)
	points := []LightPoint{}
	points = append(points, start)

	for len(points) > 0 {
		current := points[0]
		points = points[1:]
		i := current.row
		j := current.col
		dir := current.dir

		for {
			if i < 0 || i >= m || j < 0 || j >= n {
				break
			}
			if visited[i*n+j] && (A[i][j] == '-' || A[i][j] == '|') {
				break
			}

			visited[i*n+j] = true

			if A[i][j] == '.' ||
				(A[i][j] == '-' && (dir == LEFT || dir == RIGHT)) ||
				(A[i][j] == '|' && (dir == UP || dir == DOWN)) {
				switch dir {
				case UP:
					i--
				case DOWN:
					i++
				case LEFT:
					j--
				case RIGHT:
					j++
				}
				continue
			}

			if A[i][j] == '\\' {
				switch dir {
				case UP:
					dir = LEFT
					j--
				case DOWN:
					dir = RIGHT
					j++
				case LEFT:
					dir = UP
					i--
				case RIGHT:
					dir = DOWN
					i++
				}
				continue
			}

			if A[i][j] == '/' {
				switch dir {
				case UP:
					dir = RIGHT
					j++
				case DOWN:
					dir = LEFT
					j--
				case LEFT:
					dir = DOWN
					i++
				case RIGHT:
					dir = UP
					i--
				}
				continue
			}

			if A[i][j] == '-' && (dir == UP || dir == DOWN) {
				points = append(points, LightPoint{row: i, col: j + 1, dir: RIGHT})
				dir = LEFT
				j--
				continue
			}

			if A[i][j] == '|' && (dir == LEFT || dir == RIGHT) {
				points = append(points, LightPoint{row: i + 1, col: j, dir: DOWN})
				dir = UP
				i--
			}
		}
	}

	energized := 0
	for _, v := range visited {
		if v {
			energized++
		}
	}
	return energized
}

func part1(A [][]rune) {
	start := LightPoint{row: 0, col: 0, dir: RIGHT}
	energized := solve(A, start)
	fmt.Println(energized)
}

func part2(A [][]rune) {
	m := len(A)
	n := len(A[0])
	max := -1

	for i := 0; i < m; i++ {
		start := LightPoint{row: i, col: 0, dir: RIGHT}
		energized := solve(A, start)
		if energized > max {
			max = energized
		}
		start = LightPoint{row: 0, col: n - 1, dir: LEFT}
		energized = solve(A, start)
		if energized > max {
			max = energized
		}
	}

	for j := 0; j < n; j++ {
		start := LightPoint{row: 0, col: j, dir: DOWN}
		energized := solve(A, start)
		if energized > max {
			max = energized
		}
		start = LightPoint{row: m - 1, col: j, dir: UP}
		energized = solve(A, start)
		if energized > max {
			max = energized
		}
	}

	fmt.Println(max)
}

func main() {
	// file, _ := os.Open("sample.txt")
	file, _ := os.Open("input.txt")
	defer file.Close()

	scanner := bufio.NewScanner(file)

	var lines []string
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}

	var A [][]rune
	for _, line := range lines {
		A = append(A, []rune(line))
	}

	// part1(A)
	part2(A)
}