Day 24

prelude

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

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

const parser = inp => {
  let [gates, operations] = inp.trim().split("\n\n").map(munge)
  return [new Map(gates), operations]
}

const test = parser(
  "x00: 1\nx01: 1\nx02: 1\ny00: 0\ny01: 1\ny02: 0\n\nx00 AND y00 -> z00\nx01 XOR y01 -> z01\nx02 OR y02 -> z02",
)
display(test)

const input = await inputDay(24, { parser })
display(input)

part 1

function run(gates, operations) {
  const zs = operations
    .filter(([, , , , out]) => out.startsWith("z"))
    .map(([, , , , out]) => out)
    .sort((a, b) => a < b)
  while (!zs.every(z => gates.has(z))) {
    for (const [a, op, b, , out] of operations) {
      if (!gates.has(a) || !gates.has(b)) continue
      switch (op) {
        case "AND":
          gates.set(out, gates.get(a) & gates.get(b))
          break
        case "OR":
          gates.set(out, gates.get(a) | gates.get(b))
          break
        case "XOR":
          gates.set(out, gates.get(a) ^ gates.get(b))
          break
      }
    }
  }
  return parseInt(zs.map(z => gates.get(z)).join(""), 2)
}

display(run(...test))
display(run(...input))

part 2

To solve part 2, I figured out the structure of the 44-bit adder, took notes on what each bit was supposed to look like, then wrote this program to find four spots where the adder was wrong; then I manually verified them and found what they should have been swapped with.

This page helped me figure out what the structure of the adder was.

To add bits a and b, with an output bit and a carry bit, we have (where is xor):

By looking at the given operations, I saw that the adder is implemented on bit 1 with carry bit c01 as:

x01 ^ y01 -> temp1
temp1 ^ c01 -> z01
x01 & y01 -> temp2
temp1 & carry -> temp3
temp2 | temp3 -> c02

So I wrote this program to find the instructions that weren't structured as expected

function findswaps(operations) {
  for (let i = 1; i < 45; i++) {
    let x = `x${String(i).padStart(2, "0")}`
    let y = `y${String(i).padStart(2, "0")}`
    let z = `z${String(i).padStart(2, "0")}`

    // find yN ^ xN -> temp1 or xN ^ yN -> temp1
    const temp1 = operations.find(
      ([a, op, b, , out]) =>
        op == "XOR" && ((a == x && b == y) || (a == y && b == x)),
    )[4]
    if (!temp1) {
      display(`failed to find: ${x} ^ ${y} = _`)
      continue
    }

    // find temp1 ^ carry = zN
    const res = operations.find(([a, op, b, , out]) => op == "XOR" && out == z)
    if (!res) {
      display(`failed to find: _ ^ _ = ${z}`)
      continue
    }
    const carry = res[0] == temp1 ? res[2] : res[0]

    // find yN & xN -> temp2
    const temp2 = operations.find(
      ([a, op, b, , out]) =>
        op == "AND" && ((a == x && b == y) || (a == y && b == x)),
    )[4]
    if (!temp2) {
      display(`failed to find: ${x} & ${y} = _`)
      continue
    }

    // find temp1 ^ carry -> temp3
    const res2 = operations.find(
      ([a, op, b, , out]) =>
        op == "XOR" &&
        ((a == temp1 && b == carry) || (a == carry && b == temp1)),
    )
    if (!res2) {
      display(`failed to find: ${temp1} ^ ${carry} = _`)
      continue
    }
    const temp3 = res2[4]
  }
}
findswaps(input[1])