Day 11

prelude

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

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

const parser = inp => inp.split(" ").map(maybeNumber)
const test = parser(`125 17`)
display(test)

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

part 1

I think I can guess where part 2 is going, but let's play along.

Start with a function to process a single stone

function t(stone) {
  if (stone == 0) return 1
  const ss = String(stone)
  if (ss.length % 2 === 0) {
    return [+ss.slice(0, ss.length / 2), +ss.slice(ss.length / 2, ss.length)]
  }
  return stone * 2024
}

We're going to have lots of repetitive results, so memoize them

/** memoize a function of a single comparable argument */
function memoize(f) {
  const memo = {}
  return n => (Object.hasOwn(memo, n) ? memo[n] : (memo[n] = f(n)))
}

Then iterate n times and return the result

function totalSize(stones, n) {
  const stoneVal = memoize(t)
  for (let i = 0; i < n; i++) {
    stones = stones.flatMap(stoneVal)
  }
  return stones.length
}

display(totalSize(test, 6))
display(totalSize(input, 25))

part 2

If we try to execute part 1's answer for part 2, it takes forever and the array grows so large that the program fails.

The key to solving it is realizing that we the array will be absolutely chock-full of duplicates, and all we care about is how many of any given number we have.

function totalSize2(stones, n) {
  const stoneVal = memoize(t)
  // An object with [stone: count] entries to track how many of each stone we
  // have
  let counts = Object.fromEntries(
    stones.map(s => [s, stones.filter(x => x == s).length]),
  )
  for (let i = 0; i < n; i++) {
    // an updated count list
    const c2 = {}
    Object.entries(counts).forEach(([stone, count]) => {
      const res = stoneVal(stone)
      if (Array.isArray(res)) {
        c2[res[0]] = count + (c2[res[0]] || 0)
        c2[res[1]] = count + (c2[res[1]] || 0)
      } else {
        c2[res] = count + (c2[res] || 0)
      }
    })
    // replace the count list
    counts = c2
  }

  // return the sum of the values of the counts list
  return Object.values(counts).reduce((a, b) => a + b)
}
display(totalSize2(test, 6))
display(totalSize2(input, 25))
display(totalSize2(input, 75))