Day 9

prelude

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

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

const parser = inp => inp.trim().split("").map(maybeNumber)
const test = parser(`2333133121414131402`)
display(test)

const input = await inputDay(9, { parser })

part 1

split the disk map into a sequence of lengths and free space. I'm representing files as triples [size, free space, id] where free space is the number of spaces available to the right of the file

function getfiles(inp) {
  const files = []
  let id = 0
  for (let i = 0; i < inp.length; i += 2) {
    files.push([inp[i], inp[i + 1] || 0, id++])
  }
  return files
}
display(s(getfiles(test)))

A function to print a debug string in the same style as the AoC problem statement

function s(files) {
  let pos = 0
  let s = []
  for (const [sz, free, id] of files) {
    for (const p of range(pos, pos + sz)) {
      s.push(id)
    }
    if (free) {
      for (const p of range(pos + sz, pos + sz + free)) {
        s.push(".")
      }
    }
    pos += sz + free
  }
  return s.map(String).join("")
}

Stuff a single file into the file list piece by piece

function fit(files) {
  let [sz, , id] = files.pop()
  for (let i = 0; i < files.length; i++) {
    const free = files[i][1]
    if (free > 0) {
      // insert the file into the list
      files.splice(i + 1, 0, [Math.min(sz, free), Math.max(free - sz, 0), id])
      // the file we're inserting next to no longer has empty space
      files[i][1] = 0
      // update the size we're looking to place
      sz -= free
    }
    if (sz <= 0) return files
  }

  files[files.length - 1][1] = 0
  files.push([sz, 0, id])
  return false
}

Run that function until it completes

// run it until it completes
function fitall(files, debug = false) {
  while (fit(files)) {
    if (debug) display(s(files))
  }
  if (debug) display(s(files))
  return files
}

fitall(getfiles(test), true)

function checksum(files) {
  let pos = 0
  let sum = 0n
  for (const [sz, free, id] of files) {
    for (const p of range(pos, pos + sz)) {
      sum += BigInt(p * id)
    }
    pos += sz + free
  }
  return sum
}
display(checksum(fitall(getfiles(test))))
display(checksum(fitall(getfiles(input))))

part 2

Took me a minute to figure out an edge case here; see the comments below

function fit2(files, debug = false) {
  if (debug) display(s(files))
  const maxid = files[files.length - 1][2]
  // for each id in descending order
  for (let id = maxid; id > 0; id--) {
    // find the active file
    const activeIdx = files.findIndex(x => x[2] === id)
    const [sz, activeFree] = files[activeIdx]

    // probe for a place where we can fit the active file. We want to go from
    // the start up to the active file
    for (let i = 0; i < activeIdx; i++) {
      const [, free] = files[i]
      if (free >= sz) {
        // remove the file we're moving
        files.splice(activeIdx, 1)
        // add its free space to its left neighbor
        files[activeIdx - 1][1] += sz + activeFree
        // insert it into the list at its new location. I got stuck here for a
        // little bit because I was re-using `free` without realizing that it
        // could have changed in the line prior
        files.splice(i + 1, 0, [sz, files[i][1] - sz, id])
        // the file we're inserting next to no longer has empty space
        files[i][1] = 0
        if (debug) display(s(files))
        break
      }
    }
  }
  return files
}

display(checksum(fit2(getfiles(test), true)))
display(checksum(fit2(getfiles(input))))