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)
}
})()