Day 5

prelude

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

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

To parse, split the top half from the bottom half and parse each line into an array of numbers. Save it as an object with keys order and pages.

function parser(input) {
  const [a, b] = input.trim().split("\n\n")
  const order = a.split("\n").map(row => row.split("|").map(maybeNumber))
  const pages = b.split("\n").map(row => row.split(",").map(maybeNumber))
  return { order, pages }
}

Parse today's output and the example:

display(test)
display(input)

part 1

Start by reducing the order list to a dictionary of {key: [values...]}, so that we can easily check if a value is invalid with dict[key].includes(maybeInvalid)

const { order } = test
const dictTest = order.reduce(
  (acc, [a, b]) =>
    Object.assign(acc, {
      [a]: Object.hasOwn(acc, a) ? acc[a].concat(b) : [b],
    }),
  {},
)
display(dictTest)

A page is valid if no element is incorrectly sorted:

function validPage(page, dict) {
  return page.every(
    (x, i, arr) => !(dict[x] ? dict[x].includes(arr[i - 1]) : false),
  )
}

Sum up the valid pages on the test input to verify we've gotten it correct

const { pages } = test

const validTest = pages
  .filter(page => validPage(page, dictTest))
  .map(page => page[Math.floor(page.length / 2)])
  .reduce((a, b) => a + b)
display(validTest)

That seemed to work, so do the same on the input to get the part 1 answer

const { order, pages } = input
const dict = order.reduce(
  (acc, [a, b]) =>
    Object.assign(acc, {
      [a]: Object.hasOwn(acc, a) ? acc[a].concat(b) : [b],
    }),
  {},
)
const valid = pages
  .filter(page => validPage(page, dict))
  .map(page => page[Math.floor(page.length / 2)])
  .reduce((a, b) => a + b)
display(valid)

part 2

Get the invalid pages, insert them into a new array in valid order, and sum the middle numbers.

Today I learned about the toSpliced method of an array (mdn docs), which is a variant of splice that returns the array instead of the elements that were deleted. It's available in modern browsers and node 20 or above.

const { pages } = input

const total = pages
  .filter(page => !validPage(page, dict))
  .map(page =>
    // insertion sort into a new array; we could also have done an in-place
    // sort with a function that checked dict
    page.reduce((acc, e) => {
      const idx = acc.findIndex(x => dict[e]?.includes(x))
      return idx == -1 ? acc.concat(e) : acc.toSpliced(idx, 0, e)
    }, []),
  )
  .map(page => page[Math.floor(page.length / 2)])
  .reduce((a, b) => a + b)

display(total)