Day 18

prelude

https://adventofcode.com/2024/day/18

import {
  add,
  clone,
  distance,
  eq,
  find,
  HashMap,
  inputDay,
  munge,
} from "./lib/utilities.js"

const test = munge(`5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0`)
const testmap = [...new Array(7)].map(x => [...new Array(7)].map(x => "."))

const input = await inputDay(18)
const inputmap = [...new Array(71)].map(x => [...new Array(71)].map(x => "."))

const N = [-1, 0]
const E = [0, 1]
const S = [1, 0]
const W = [0, -1]
const WALL = "#"
const FLOOR = "."
const start = [0, 0]

part 1

Copying and modifying my Dijkstra's (actually A*) implementation from day 16, which I haven't posted because my implementation there gives slightly wrong answers! Nevertheless, it works fine on today's.

function inbounds(pt, w, h) {
  return pt[0] >= 0 && pt[0] < h && pt[1] >= 0 && pt[1] < w
}

// Search with Dijkstra's algorithm
//
// https://www.redblobgames.com/pathfinding/a-star/introduction.html#dijkstra
function search(map, start, end, debug = false, debugId = undefined) {
  // priority queue, pairs of [cost, point]
  const frontier = [[0, start]]

  // the path and the cost for the path
  const cameFrom = new HashMap([[start, null]])
  const costSoFar = new HashMap([[start, 0]])

  while (frontier.length > 0) {
    // there's no heap in the js standard library, so we'll just sort our list
    // every time through the loop. We want the lowest cost coming last so we
    // can pop it off the end
    frontier.sort((a, b) => a[0] < b[0])
    const [, pt] = frontier.pop()

    if (eq(pt, end)) break

    // for each valid (inbounds, non-wall) neighbor
    for (const next of [N, E, S, W]
      .map(d => add(pt, d))
      .filter(pt => inbounds(pt, map[0].length, map.length))
      .filter(([y, x]) => map[y][x] != WALL)) {
      const newCost = costSoFar.get(pt) + 1

      // if the new cost is lower than the current cost, or there isn't a cost
      // yet, add it to the path
      if (newCost < (costSoFar.get(next) ?? Number.MAX_VALUE)) {
        // add the cost to the front of the array, as it's likely to be more
        // expensive than what's at the end of the array; it'll get sorted in a
        // second
        frontier.unshift([newCost + distance(next, end), next])

        // update the cost for the cell
        costSoFar.set(next, newCost)

        // add how we got to the cell
        cameFrom.set(next, pt)
      }
    }
  }

  if (debug) showdebug(map, cameFrom, costSoFar, start, end, debugId)
  return [costSoFar, cameFrom]
}

Now we can write a function to get the path length for a given number of obstacles

function pathlen(map, rocks, n, debug = false, debugId = undefined) {
  const m = clone(map)
  for (const [x, y] of rocks.slice(0, n)) {
    m[y][x] = WALL
  }
  let end = [m.length - 1, m[0].length - 1]
  let res = search(m, [0, 0], end, debug, debugId)
  return res[0].get(end)
}

display(pathlen(testmap, test, 12))
display(pathlen(inputmap, input, 1024, true))

And get some nice debug output

function showdebug(map, cameFrom, costSoFar, start, end, id = "mapCanvas") {
  const width = 640
  const height = 640
  const mapw = map[0].length
  const maph = map.length
  const colw = width / mapw
  const rowh = height / maph
  const ctx = document.getElementById(id).getContext("2d")
  ctx.clearRect(0, 0, width, height)
  for (const pt of cameFrom) {
    const [y, x] = pt[0].split(",").map(Number)
    ctx.fillStyle = "#444"
    ctx.fillRect(x * colw, y * rowh, colw, rowh)
  }
  let pt = cameFrom.get(end)
  while (pt) {
    const [y, x] = pt
    ctx.fillStyle = "#D35FB7"
    ctx.fillRect(x * colw, y * rowh, colw, rowh)
    pt = cameFrom.get(pt)
  }
  for (let row = 0; row < maph; row++) {
    for (let col = 0; col < mapw; col++) {
      ctx.strokeRect(col * colw, row * rowh, colw, rowh)
      if (map[row][col] == WALL) {
        ctx.fillStyle = "#4269d0"
        ctx.fillRect(col * colw, row * rowh, colw, rowh)
      }
      if ([start, end].some(pt => eq(pt, [row, col]))) {
        ctx.fillStyle = "#FEFE62"
        ctx.fillRect(col * colw, row * rowh, colw, rowh)
      }
    }
  }
}

part 2

For part 2, iterate through the stones until we find one that doesn't have a path

// the starting point was found by trial & error, I don't want to spend your
// CPU cycles calculating it, but I ran it from 1024
for (let i = 2860; i < input.length; i++) {
  if (!pathlen(inputmap, input, i)) {
    display(input[i - 1].join(","))
    break
  }
}
// let's display the maze before and after the final brick
pathlen(inputmap, input, 2861, true, "mapPart2")
pathlen(inputmap, input, 2862, true, "mapPart2b")