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)