Advent of Code 2024 Day 17

main.swift

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

import AOC
import Preamble

let input = readInput()
let chunks = input.split(on: "\n\n")

var debug = false

func debugPrint(_ s: String) {
    if debug { print(s) }
}

struct Computer {
    var regs: [Int]
    let program: [Int]
    var ip = 0
    var output: [Int] = []

    var A: Int { get { regs[0] } set { regs[0] = newValue } }
    var B: Int { get { regs[1] } set { regs[1] = newValue } }
    var C: Int { get { regs[2] } set { regs[2] = newValue } }

    mutating func step() -> Bool {
        guard ip < program.count else { return false }

        let insn = program[ip]
        let operand = program[ip + 1]

        var combo: Int {
            switch operand {
            case 0, 1, 2, 3: return operand
            case 4, 5, 6: return regs[operand - 4]
            default: fatalError()
            }
        }

        var comboDescription: String {
            switch operand {
            case 0, 1, 2, 3: return "\(operand)"
            case 4: return "A"
            case 5: return "B"
            case 6: return "C"
            default: fatalError()
            }
        }

        var ipString: String { ip < 10 ? "0\(ip)" : String(ip) }

        var nextIp: Int? = nil

        switch insn {
        case 0: // adv
            debugPrint("\(ipString) A = A >> \(comboDescription)")
            A = A / (1 << combo)
        case 1: // bxl
            debugPrint("\(ipString) B ^= \(operand)")
            B ^= operand
        case 2: // bst
            debugPrint("\(ipString) B = \(comboDescription) % 8")
            B = combo % 8
        case 3: // jnz
            debugPrint("\(ipString) if A ≠ 0 goto \(operand)")
            if A == 0 { break }
            nextIp = operand
            debugPrint("---------> BRANCH TAKEN")
        case 4: // bxc
            debugPrint("\(ipString) B ^= C")
            B = B ^ C
        case 5: // out
            debugPrint("\(ipString) out \(comboDescription)")
            output.append(combo % 8)
        case 6: // bdv
            debugPrint("\(ipString) B = A >> \(comboDescription)")
            B = A / (1 << combo)
        case 7: // cdv
            debugPrint("\(ipString) C = A >> \(comboDescription)")
            C = A / (1 << combo)
        default:
            fatalError()
        }

        ip = nextIp ?? (ip + 2)
        return true
    }

    func canBeQuine() -> Bool {
        return program.starts(with: output)
    }

    var joinedOutput: String { output.map { String($0) }.joined(separator: ",") }

    mutating func run() -> String {
        while step() { }
        return joinedOutput
    }
}

let computer0 = Computer(regs: chunks[0].allInts(), program: chunks[1].allInts())

var part1 = computer0
while part1.step() { }
part1.joinedOutput |> printAndCopy

let requiredOutput = computer0.program.map { String($0) }.joined(separator: ",")

var candidates = Array(0 ..< 8)
loop:
while true {
    var nextCandidates: [Int] = []

    for candidate in candidates {
        var puter = computer0
        puter.A = candidate
        let output = puter.run()
        guard requiredOutput.hasSuffix(output) else { continue }
        if output == requiredOutput {
            candidate |> printAndCopy
            break loop
        }
        for i in 0 ..< 8 {
            nextCandidates.append((candidate << 3) | i)
        }
    }

    candidates = nextCandidates
}