Scala3

Learning about scala-graph yesterday seems to have paid off already. This explicitly constructs the entire graph of allowed moves, and then uses a naive dijkstra run. This works, and I don’t have to write a lot of code, but it is fairly inefficient.

import day10._
import day10.Dir._
import day11.Grid

// standing on cell p, having entered from d
case class Node(p: Pos, d: Dir)

def connect(p: Pos, d: Dir, g: Grid[Int], dists: Range) = 
    val from = Seq(-1, 1).map(i => Dir.from(d.n + i)).map(Node(p, _))
    val ends = List.iterate(p, dists.last + 1)(walk(_, d)).filter(g.inBounds)
    val costs = ends.drop(1).scanLeft(0)(_ + g(_))
    from.flatMap(f => ends.zip(costs).drop(dists.start).map((dest, c) => WDiEdge(f, Node(dest, d), c)))

def parseGrid(a: List[List[Char]], dists: Range) =
    val g = Grid(a.map(_.map(_.getNumericValue)))
    Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g, dists)))

def compute(a: List[String], dists: Range): Long =
    val g = parseGrid(a.map(_.toList), dists)
    val source = Node(Pos(-1, -1), Right)
    val sink = Node(Pos(-2, -2), Right)
    val start = Seq(Down, Right).map(d => Node(Pos(0, 0), d)).map(WDiEdge(source, _, 0))
    val end = Seq(Down, Right).map(d => Node(Pos(a(0).size - 1, a.size - 1), d)).map(WDiEdge(_, sink, 0))
    val g2 = g ++ start ++ end
    g2.get(source).shortestPathTo(g2.get(sink)).map(_.weight).getOrElse(-1.0).toLong

def task1(a: List[String]): Long = compute(a, 1 to 3)
def task2(a: List[String]): Long = compute(a, 4 to 10)

Python

749 line-seconds

import collections
import dataclasses
import heapq

import numpy as np

from .solver import Solver


@dataclasses.dataclass(order=True)
class QueueEntry:
  price: int
  x: int
  y: int
  momentum_x: int
  momentum_y: int
  deleted: bool


class Day17(Solver):
  lines: list[str]
  sx: int
  sy: int
  lower_bounds: np.ndarray

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

  def presolve(self, input: str):
    self.lines = input.splitlines()
    self.sx = len(self.lines[0])
    self.sy = len(self.lines)
    start = (self.sx - 1, self.sy - 1)
    self.lower_bounds = np.zeros((self.sx, self.sy)) + np.inf
    self.lower_bounds[start] = 0
    queue: list[QueueEntry] = [QueueEntry(0, self.sx - 1, self.sy - 1, 0, 0, False)]
    queue_entries: dict[tuple[int, int], QueueEntry] = {start: queue[0]}
    while queue:
      cur_price, x, y, _, _, deleted = dataclasses.astuple(heapq.heappop(queue))
      if deleted:
        continue
      del queue_entries[(x, y)]
      self.lower_bounds[x, y] = cur_price
      price = cur_price + int(self.lines[y][x])
      for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nx, ny = x + dx, y + dy
        if not (0 <= nx < self.sx) or not (0 <= ny < self.sy):
          continue
        if price < self.lower_bounds[nx, ny]:
          self.lower_bounds[nx, ny] = price
          if (nx, ny) in queue_entries:
            queue_entries[(nx, ny)].deleted = True
          queue_entries[(nx, ny)] = QueueEntry(price, nx, ny, 0, 0, False)
          heapq.heappush(queue, queue_entries[(nx, ny)])

  def _solve(self, maximum_run: int, minimum_run_to_turn: int):
    came_from: dict[tuple[int, int, int, int], tuple[int, int, int, int]] = {}
    start = (0, 0, 0, 0)
    queue: list[QueueEntry] = [QueueEntry(self.lower_bounds[0, 0], *start, False)]
    queue_entries: dict[tuple[int, int, int, int], QueueEntry] = {start: queue[0]}
    route: list[tuple[int, int]] = []
    prices: dict[tuple[int, int, int, int], float] = collections.defaultdict(lambda: np.inf)
    prices[start] = 0
    while queue:
      _, current_x, current_y, momentum_x, momentum_y, deleted = dataclasses.astuple(heapq.heappop(queue))
      cur_price = prices[(current_x, current_y, momentum_x, momentum_y)]
      if deleted:
        continue
      if ((current_x, current_y) == (self.sx - 1, self.sy - 1) and
          (momentum_x >= minimum_run_to_turn or momentum_y >= minimum_run_to_turn)):
        previous = came_from.get((current_x, current_y, momentum_x, momentum_y))
        route.append((current_x, current_y))
        while previous:
          x, y, *_ = previous
          if x != 0 or y != 0:
            route.append((x, y))
          previous = came_from.get(previous)
        break
      for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        dot_product = dx * momentum_x + dy * momentum_y
        if dot_product < 0 or dot_product >= maximum_run:
          continue
        if ((momentum_x or momentum_y) and dot_product == 0 and
            abs(momentum_x) < minimum_run_to_turn and abs(momentum_y) < minimum_run_to_turn):
          continue
        new_x, new_y = current_x + dx, current_y + dy
        if not (0 <= new_x < self.sx) or not (0 <= new_y < self.sy):
          continue
        new_momentum_x, new_momentum_y = (dx, dy) if dot_product == 0 else (momentum_x + dx, momentum_y + dy)
        new_position = (new_x, new_y, new_momentum_x, new_momentum_y)
        potential_new_price = cur_price + int(self.lines[new_y][new_x])
        if potential_new_price < prices[new_position]:
          queue_entry = queue_entries.get(new_position)
          if queue_entry:
            queue_entry.deleted = True
          queue_entries[new_position] = QueueEntry(potential_new_price + self.lower_bounds[new_x, new_y],
                                                   *new_position, False)
          came_from[new_position] = (current_x, current_y, momentum_x, momentum_y)
          prices[new_position] = potential_new_price
          heapq.heappush(queue, queue_entries[new_position])
    return sum(int(self.lines[y][x]) for x, y in route)

  def solve_first_star(self) -> int:
    return self._solve(3, 0)

  def solve_second_star(self) -> int:
    return self._solve(10, 4)

Python https://github.com/massahud/advent-of-code-2023/blob/main/day17/day17.ipynb

C

Very not pretty and not efficient. Using what I think is dynamic programming - essentially I just propagate cost total through a (x, y, heading, steps in heading) state space, so every cell in that N-dimensional array holds the minimum total cost known to get to that state which is updated iteratively from the neighbours until it settles down.

Debugging was annoying because terminals aren’t great at showing 4D grids. My mistakes were in the initial situation and missing the “4 steps to come to a stop at the end” aspect in part 2.

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

Haskell

Wowee, I took some wrong turns solving today’s puzzle! After fixing some really inefficient pruning I ended up with a Dijkstra search that runs in 2.971s (for a less-than-impressive 124.782 l-s).

import Control.Monad
import Data.Array.Unboxed (UArray)
import qualified Data.Array.Unboxed as Array
import Data.Char
import qualified Data.HashSet as Set
import qualified Data.PQueue.Prio.Min as PQ

readInput :: String -> UArray (Int, Int) Int
readInput s =
  let rows = lines s
   in Array.amap digitToInt
        . Array.listArray ((1, 1), (length rows, length $ head rows))
        $ concat rows

walk :: (Int, Int) -> UArray (Int, Int) Int -> Int
walk (minStraight, maxStraight) grid = go Set.empty initPaths
  where
    initPaths = PQ.fromList [(0, ((1, 1), (d, 0))) | d <- [(0, 1), (1, 0)]]
    goal = snd $ Array.bounds grid
    go done paths =
      case PQ.minViewWithKey paths of
        Nothing -> error "no route"
        Just ((n, (p@(y, x), hist@((dy, dx), k))), rest)
          | p == goal && k >= minStraight -> n
          | (p, hist) `Set.member` done -> go done rest
          | otherwise ->
              let next = do
                    h'@((dy', dx'), _) <-
                      join
                        [ guard (k >= minStraight) >> [((dx, dy), 1), ((-dx, -dy), 1)],
                          guard (k < maxStraight) >> [((dy, dx), k + 1)]
                        ]
                    let p' = (y + dy', x + dx')
                    guard $ Array.inRange (Array.bounds grid) p'
                    return (n + grid Array.! p', (p', h'))
               in go (Set.insert (p, hist) done) $
                    (PQ.union rest . PQ.fromList) next

main = do
  input <- readInput <$> readFile "input17"
  print $ walk (0, 3) input
  print $ walk (4, 10) input