Day 7

prelude

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

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

const test = munge(`190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20`)
display(test)

const input = await inputDay(7)

part 1

To find if a target is reachable, we can make our function more efficient by starting from the end of the values list and only adding a division if it divides in evenly.

If we reach zero, the target is reachable and we return the value.

function reachable(target, vals) {
  let frontier = [target]
  for (const v of vals.reverse()) {
    const newf = []
    for (const f of frontier) {
      if (f % v === 0) {
        newf.push(f / v)
      }
      newf.push(f - v)
    }
    frontier = newf
  }
  return frontier.includes(0) ? target : 0
}

Run it on the test and the full input

const res = test
  .map(([target, ...values]) => reachable(target, values))
  .reduce((a, b) => a + b)
display(res)
const full = input
  .map(([target, ...values]) => reachable(target, values))
  .reduce((a, b) => a + b)
display(full)

part 2

For part 2, I didn't go backwards because it's a pain to invert concatenation. I was worried that this way was going to be too inefficient, but it turns out to be tractable fortunately.

Without the conditional division from part 1, the problem decomposes nicely into a reduction.

function reachable2(target, vals) {
  return vals
    .slice(1)
    .reduce(
      (frontier, v) =>
        frontier.flatMap(f => [f * v, f + v, Number(String(f) + String(v))]),
      [vals[0]],
    )
    .includes(target) ? target : 0
}

const res = test
  .map(([target, ...values]) => reachable2(target, values))
  .reduce((a, b) => a + b)
display(res)
const full = input
  .map(([target, ...values]) => reachable2(target, values))
  .reduce((a, b) => a + b)
display(full)