AoC 2024 day 9

const fs = require("fs")

const input = fs.readFileSync(__dirname + (process.argv.includes("--test") ? "/test.txt" : "/input.txt"), "utf8").trim()

const parseDiskBlocks = (data) => {
    const diskBlocks = []
    let fileId = 0,
        isFile = true

    for (const length of data) {
        const len = +length
        diskBlocks.push(...Array(len).fill(isFile ? fileId : "."))
        if (isFile) fileId++
        isFile = !isFile
    }

    return diskBlocks
}

const computeChecksum = (diskBlocks) =>
    diskBlocks.reduce((checksum, block, index) => checksum + (block !== "." ? index * block : 0), 0)

const compactDisk = (diskBlocks) => {
    let left = 0,
        right = diskBlocks.length - 1

    while (left < diskBlocks.length && diskBlocks[left] !== ".") left++
    while (right > left) {
        while (right > left && diskBlocks[right] === ".") right--
        if (right <= left) break
        ;[diskBlocks[left], diskBlocks[right]] = [diskBlocks[right], "."]
        while (left < diskBlocks.length && diskBlocks[left] !== ".") left++
        right--
    }

    return diskBlocks
}

const part1 = (data) => {
    const diskBlocks = parseDiskBlocks(data)
    const compacted = compactDisk(diskBlocks)
    return computeChecksum(compacted)
}

const part2 = (data) => {
    const diskBlocks = parseDiskBlocks(data)
    const files = []
    const freeSpans = []

    diskBlocks.forEach((block, i) => {
        if (block !== ".") {
            files[block] ??= { id: block, size: 0, positions: [] }
            files[block].positions.push(i)
            files[block].size++
        } else if (!freeSpans.length || freeSpans.at(-1).end + 1 !== i) {
            freeSpans.push({ start: i, end: i, size: 1 })
        } else {
            freeSpans.at(-1).end++
            freeSpans.at(-1).size++
        }
    })

    files.reverse().forEach((file) => {
        if (!file) return

        const { size, positions } = file
        const fileStartPos = positions[0]
        const targetSpan = freeSpans.find((span) => span.size >= size && span.end < fileStartPos)

        if (targetSpan) {
            positions.forEach((pos) => (diskBlocks[pos] = "."))
            for (let i = 0; i < size; i++) {
                diskBlocks[targetSpan.start + i] = file.id
            }

            if (targetSpan.size === size) {
                freeSpans.splice(freeSpans.indexOf(targetSpan), 1)
            } else {
                targetSpan.start += size
                targetSpan.size -= size
            }

            freeSpans.push({
                start: fileStartPos,
                end: fileStartPos + size - 1,
                size
            })
        }
    })

    return computeChecksum(diskBlocks)
}

console.time("Part 1 Time")
console.log("Part 1:", part1(input))
console.timeEnd("Part 1 Time")

console.time("Part 2 Time")
console.log("Part 2:", part2(input))
console.timeEnd("Part 2 Time")