advent of code 2024 chiri solutions day 6

part 1.js

let sx, sy
const lines = input.split("\n").map((line, y) => [...line].map((char, x) => { if (char === "^") sx = x, sy = y; return char === "#" ? 1 : 0 }))

let cx = sx, cy = sy
const UP = [-1, 0], DOWN = [1, 0], LEFT = [0, -1], RIGHT = [0, 1]
const next = new Map([[UP, RIGHT], [RIGHT, DOWN], [DOWN, LEFT], [LEFT, UP]])
let dir = UP
let visited = new Set()
let turns = 0
while (cx >= 0 && cx <= lines[0].length - 1 && cy >= 0 && cy <= lines.length) {
    let nx = cx + dir[1], ny = cy + dir[0]
    if (lines[ny]?.[nx]) {
        dir = next.get(dir)
        turns++
        continue
    }

    visited.add(`${cx},${cy}`)
    cx = nx, cy = ny
}
visited.size

part 2 v1.js

let sx, sy
const lines = input.split("\n").map((line, y) => [...line].map((char, x) => { if (char === "^") sx = x, sy = y; return char === "#" ? 1 : 0 }))

const UP = [-1, 0], DOWN = [1, 0], LEFT = [0, -1], RIGHT = [0, 1]
const next = new Map([[UP, RIGHT], [RIGHT, DOWN], [DOWN, LEFT], [LEFT, UP]])
const name = new Map([[UP, "0"], [RIGHT, "1"], [DOWN, "2"], [LEFT, "3"]])
const w = lines[0].length - 1

function loops(cx = sx, cy = sy, dir = UP, visited = new Set(), recursive = false, count = 0, ox, oy) {
    let nextdir = next.get(dir), dirname = name.get(dir)
    let turns = 0
    while (cx >= 0 && cx <= w && cy >= 0 && cy <= lines.length - 1) {
        let nx = cx + dir[1], ny = cy + dir[0]
        if (lines[ny]?.[nx] || (ny === oy && nx === ox)) {
            dir = nextdir
            dirname = name.get(dir)
            nextdir = next.get(dir)
            turns++
            continue
        }

        if (!recursive && nx >= 0 && nx <= w && ny >= 0 && ny <= lines.length - 1 && !visited.has(`${nx},${ny}`) && loops(cx, cy, nextdir, new Set(visited), true, null, nx, ny))
            count++

        const id = `${cx},${cy}`
        const oldVisitedSize = visited.size
        visited.add(id)
        visited.add(`${id},${dirname}`)
        if (visited.size === oldVisitedSize)
            return true
        
        cx = nx, cy = ny
    }
    return count ?? false
}
loops()

part 2 v2 optimised.js

// my original solution ran for my puzzle input in about 650ms on avg, but i had some ideas to speed it up, so here's a modified version
// after the the changes, this ran for my puzzle input in about 220ms on avg

// the commented code below is to early exit if ever running into a "natural loop", which is any loop that an obstruction can send the guard into but that never again touches the obstruction
// in my case the code ran slower with the natural loop checks so it's disabled, but i'm not sure whether it might go faster for some puzzle inputs

let sx, sy
const lines = input.split("\n").map((line, y) => [...line].map((char, x) => { if (char === "^") sx = x, sy = y; return char === "#" ? 1 : 0 }))

const UP = [-1, 0], DOWN = [1, 0], LEFT = [0, -1], RIGHT = [0, 1]
const dirs = [UP, RIGHT, DOWN, LEFT]
const w = lines[0].length - 1
const size = lines.length * w
// const naturalLoops = new Uint8Array(size * 5)
function toIndex(x, y) { return y * w + x }
function toDirIndex(x, y, dir) { return (dir + 1) * size + y * w + x }

// const potentialNaturalLoopVisited = []
// let potentialNaturalLoopVisitedLength = 0
function loops(cx = sx, cy = sy, dirname = 0, visited = new Uint8Array(size * 5), recursive = false, count = 0, ox, oy) {
    let dir = dirs[dirname], nextdir = (dirname + 1) % 4
    let turns = 0
    // let obTurns = 0
    // potentialNaturalLoopVisitedLength = 0
    // let obId = toIndex(ox, oy)
    while (cx >= 0 && cx <= w && cy >= 0 && cy <= lines.length - 1) {
        let nx = cx + dir[1], ny = cy + dir[0]
        if (lines[ny]?.[nx] || (ny === oy && nx === ox)) {
            dirname = nextdir
            dir = dirs[dirname]
            nextdir = (dirname + 1) % 4
            turns++
            // obTurns += +(ny === oy && nx === ox)
            continue
        }

        if (!recursive && nx >= 0 && nx <= w && ny >= 0 && ny <= lines.length - 1 && !visited[toIndex(nx, ny)] && loops(cx, cy, nextdir, new Uint8Array(visited), true, null, nx, ny))
            count++

        const id = toIndex(cx, cy)
        const idDir = toDirIndex(cx, cy, dirname)

        // if (recursive && naturalLoops[idDir] && !naturalLoops[obId])
            // return true
            
        const oldVisitedSize = visited.size
        if (visited[idDir]) {
            // if (!obTurns) for (let i = 0; i < potentialNaturalLoopVisitedLength; i++) naturalLoops[potentialNaturalLoopVisited[potentialNaturalLoopVisitedLength]] = 1
            return true
        }
        visited[id] = 1
        visited[idDir] = 1
        // if (!obTurns)
            // potentialNaturalLoopVisited[potentialNaturalLoopVisitedLength++] = id, potentialNaturalLoopVisited[potentialNaturalLoopVisitedLength++] = idDir
        
        cx = nx, cy = ny
    }
    return count ?? false
}
let start = performance.now()
;[loops(), performance.now() - start]