Day 6

prelude

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

import { grid, inputDay } from "./lib/utilities.js"

const test = grid(`....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...`)
display(test)

// the guard in my input is "^", so use it as the marker
const GUARD = "^"

// our coördinate system is [row, col], where decreasing y goes up
const N = [-1, 0]
const E = [0, 1]
const S = [1, 0]
const W = [0, -1]

const input = await inputDay(6, { parser: grid })

part 1

Let's start with some helper functions.

/** return the location of tgt in 2d array m or throw */
function find(m, tgt) {
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      if (m[i][j] === tgt) return [i, j]
    }
  }
  throw new Error(`unable to find ${tgt}`)
}

/** add 2d points */
function add(pt, dir) {
  return [pt[0] + dir[0], pt[1] + dir[1]]
}

/** compare 2d points */
function cmp(d1, d2) {
  return d1[0] == d2[0] && d1[1] == d2[1]
}

/** rotate dir clockwise */
function rotate(dir) {
  if (cmp(dir, N)) return E
  if (cmp(dir, E)) return S
  if (cmp(dir, S)) return W
  if (cmp(dir, W)) return N
  throw new Error("invalid rotate")
}

/** return the value of m at pos */
function get(m, pos) {
  return m[pos[0]][pos[1]]
}

/** set the value of m at pos to val */
function set(m, pos, val) {
  m[pos[0]][pos[1]] = val
}

/** clone a 2d matrix. We're updating our map in place so we need to be careful
 *  not to lose the original
 */
function clone(m) {
  return m.map(x => x.slice())
}

Now we can write a function that accepts a map, the direction of the guard, and their position; then steps the guard forward one step

function step(m, dir, pos, debug = false) {
  if (debug) console.log(m.map(x => x.join("")).join("\n"))

  // try moving the guard
  let newpos = add(pos, dir)

  // if we've moved them off the map, return false for dir to indicate
  // completion
  if (
    newpos[0] < 0 ||
    newpos[0] > m[0].length - 1 ||
    newpos[1] < 0 ||
    newpos[1] > m.length - 1
  ) {
    return [dir, false]
  }

  // if the move is invalid, rotate clockwise until it's valid
  while (get(m, newpos) != ".") {
    dir = rotate(dir)
    newpos = add(pos, dir)
  }

  // move the guard to their new position
  set(m, pos, ".")
  set(m, newpos, GUARD)

  return [dir, newpos]
}

To find the answer, step until the position is invalid and count the unique steps

function run(m) {
  let dir = N
  let pos = find(m, GUARD)
  let positions = new Set([])
  while (pos) {
    positions.add(JSON.stringify(pos))
    ;[dir, pos] = step(m, dir, pos)
  }
  return positions.size
}
display(run(clone(test)))
display(run(clone(input)))

part 2

• For each position on the map
  • if it's empty
  • clone the initial map and place an obstacle
  • run until we exit the map or hit our step limit
  • if we hit our step limit, assume we've found a loop

This takes a few seconds on my computer, so I put it behind this button. Click to run part 2 on the full input:

function pt2(m, limit = 10_000) {
  let loops = 0
  let initialPos = find(m, GUARD)
  for (let i = 0; i < m.length; i++) {
    for (let j = 0; j < m[0].length; j++) {
      if (m[i][j] != ".") continue

      // clone the map and set the current cell to an obstacle
      let mm = clone(m)
      mm[i][j] = "O"

      // run the map until we run off the map or hit our step limit
      let pos = initialPos
      let steps = 0
      let dir = N
      while (pos && steps < limit) {
        ;[dir, pos] = step(mm, dir, pos)
        steps++
      }

      // if we hit our step limit, assume we've found a loop
      if (steps == limit) loops++
    }
  }
  return loops
}

display(pt2(test, 1000))
if (runs > 0) {
  display(pt2(input))
}

part 1 visualization

runButton // reference the button so we run on a click
const _ = (function* () {
  const vizM = clone(test)
  // I can't currently figure out how to store this state in the document such
  // that I can let a user advance the animation one step
  let pos = find(vizM, GUARD)
  let dir = N
  while (pos) {
    ;[dir, pos] = step(vizM, dir, pos)
    const stringmap = vizM
      .map(x => x.join(""))
      .join("\n")
      .replace("^", "💂")
    yield (document.getElementById("map").innerText = stringmap)
  }
})()