Raku

I spent way to much time tweaking the part 2 code to get a working solution. The solution itself is quite simple, though.

sub MAIN($input) {
    grammar Input {
        token TOP { <register-a> "\n" <register-b> "\n" <register-c> "\n\n" <program> "\n"* }
        token register-a { "Register A: " (\d+) }
        token register-b { "Register B: " (\d+) }
        token register-c { "Register C: " (\d+) }
        token program { "Program: " (\d)+%"," }
    }
    my $parsed = Input.parsefile($input);
    my $register-a = $parsed<register-a>[0].Int;
    my $register-b = $parsed<register-b>[0].Int;
    my $register-c = $parsed<register-c>[0].Int;
    my @program = $parsed<program>[0]>>.Int;

    my $part1-solution = run-program($register-a, $register-b, $register-c, @program).join(",");
    say "part1 solution: $part1-solution";

    my $part2-solution = search-for-quine(0, $register-b, $register-c, @program, 0);
    say "part2-solution: $part2-solution";
}

sub run-program($a, $b, $c, @program) {
    my ($register-a, $register-b, $register-c) Z= ($a, $b, $c);
    my $pc = 0;
    my @output;
    while $pc < @program.elems {
        my ($opcode, $operand) Z= @program[$pc, $pc+1];
        my $combo = (given $operand {
            when 0..3 { $operand }
            when 4 { $register-a }
            when 5 { $register-b }
            when 6 { $register-c }
            when 7 { Nil }
            default { say "invalid operand $operand"; exit; }
        });
        given $opcode {
            when 0 { $register-a = $register-a div (2 ** $combo); }
            when 1 { $register-b = $register-b +^ $operand; }
            when 2 { $register-b = $combo mod 8; }
            when 3 { $pc = $operand - 2 if $register-a != 0; }
            when 4 { $register-b = $register-b +^ $register-c; }
            when 5 { @output.push($combo mod 8); }
            when 6 { $register-b = $register-a div (2 ** $combo); }
            when 7 { $register-c = $register-a div (2 ** $combo); }
            default { say "invalid opcode $opcode"; exit; }
        }
        $pc += 2;
    }
    return @output;
}

sub search-for-quine($a, $b, $c, @program, $idx) {
    return $a if $idx == @program.elems;
    for ^8 {
        my $test-solution = $a * 8 + $_;
        my @output = run-program($test-solution, $b, $c, @program);
        my @program-slice = @program[*-1-$idx..*];
        if @program-slice eqv @output {
            my $found = search-for-quine($test-solution, $b, $c, @program, $idx+1);
            if $found {
                return $found;
            }
        }
    }
    # Time to back track...
    return False;
}

C#

This one is mostly thanks to reading @mykl@mykl@lemmy.world’s code to understand WTF was going on for part 2, and then once I understood the basics, finally got to solving it myself. Instructions were read in as long because I didn’t want to deal with int vs. long all the time.

using System.Collections.Immutable;
using System.Diagnostics;
using Common;

namespace Day17;

static class Program
{
    public record State(long A, long B, long C, int InstPtr, ImmutableList<long> Output);

    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var (sampleReg, sampleInst) = ReceiveInput("sample.txt");
        var (inputReg, inputInst) = ReceiveInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleReg, sampleInst)}");
        Console.WriteLine($"Part 1 input: {Part1(inputReg, inputInst)}");

        (sampleReg, sampleInst) = ReceiveInput("sample2.txt");
        Console.WriteLine($"Part 2 sample: {Part2(sampleReg, sampleInst)}");
        Console.WriteLine($"Part 2 input: {Part2(inputReg, inputInst)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(State state, ImmutableArray<long> instructions) =>
        Execute(instructions, state).Output.StringifyAndJoin(",");

    static object Part2(State state, ImmutableArray<long> instructions) =>
        RecursiveSolve(instructions, state with { A = 0 }, []).First();

    static IEnumerable<long> RecursiveSolve(ImmutableArray<long> instructions, State state, ImmutableList<long> soFar) =>
        (soFar.Count == instructions.Length) ? [state.A] :
        Enumerable.Range(0, 8)
            .Select(a => state with { A = (state.A << 3) + a })
            .Where(newState => newState.A != state.A)
            .Select(newState => new { newState, Execute(instructions, newState).Output, })
            .Where(states => states.Output.SequenceEqual(instructions.TakeLast(states.Output.Count)))
            .SelectMany(states => RecursiveSolve(instructions, states.newState, states.Output));

    static State Execute(ImmutableArray<long> instructions, State state)
    {
        while (state.InstPtr < instructions.Length)
        {
            var opcode = instructions[state.InstPtr];
            var operand = instructions[state.InstPtr + 1];
            state = Operations[opcode](state, operand);
        }

        return state;
    }

    static long ComboOperand(long operand, State state) => operand switch
    {
        >= 0 and <= 3 => operand,
        4 => state.A,
        5 => state.B,
        6 => state.C,
        _ => throw new Exception("Invalid operand."),
    };

    static long Adv(long op, State state) => state.A / (long)Math.Pow(2, ComboOperand(op, state));

    static readonly Func<State, long, State>[] Operations =
    [
        (s, op) => s with { InstPtr = s.InstPtr + 2, A = Adv(op, s) },
        (s, op) => s with { InstPtr = s.InstPtr + 2, B = s.B ^ op },
        (s, op) => s with { InstPtr = s.InstPtr + 2, B = ComboOperand(op, s) % 8 },
        (s, op) => s with { InstPtr = (s.A == 0) ? (s.InstPtr + 2) : (op <= int.MaxValue) ? (int)op : throw new ArithmeticException("Integer overflow!") },
        (s, _) => s with { InstPtr = s.InstPtr + 2, B = s.B ^ s.C },
        (s, op) => s with { InstPtr = s.InstPtr + 2, Output = s.Output.Add(ComboOperand(op, s) % 8) },
        (s, op) => s with { InstPtr = s.InstPtr + 2, B = Adv(op, s) },
        (s, op) => s with { InstPtr = s.InstPtr + 2, C = Adv(op, s) },
    ];


    static (State, ImmutableArray<long> instructions) ReceiveInput(string file)
    {
        var input = File.ReadAllLines(file);

        return
        (
            new State(
                long.Parse(input[0].Substring("Register A: ".Length)),
                long.Parse(input[1].Substring("Register B: ".Length)),
                long.Parse(input[2].Substring("Register C: ".Length)),
                0,
                []),
            input[4].Substring("Program: ".Length)
                .Split(",")
                .Select(long.Parse)
                .ToImmutableArray()
        );
    }
}

C#

public class Day17 : Solver {
  private List<int> program;
  private long a, b, c;

  public void Presolve(string input) {
    var data = input.Trim().Split("\n");
    a = long.Parse(Regex.Match(data[0], @"\d+").Value);
    b = long.Parse(Regex.Match(data[1], @"\d+").Value);
    c = long.Parse(Regex.Match(data[2], @"\d+").Value);
    program = data[4].Split(" ")[1].Split(",").Select(int.Parse).ToList();
  }

  public string SolveFirst() => String.Join(',', Execute(a, b, c));

  private List<int> Execute(long a, long b, long c) {
    List<int> output = [];
    Func<long, long> combo = operand => operand switch {
      <= 3 => operand,
      4 => a,
      5 => b,
      6 => c,
      _ => throw new InvalidDataException(),
    };
    int ip = 0;
    while (ip < program.Count - 1) {
      switch (program[ip]) {
        case 0:
          a = a >> (int)combo(program[ip + 1]);
          break;
        case 1:
          b = b ^ program[ip + 1];
          break;
        case 2:
          b = combo(program[ip + 1]) % 8;
          break;
        case 3:
          if (a != 0) {
            ip = program[ip + 1];
            continue;
          }
          break;
        case 4:
          b = b ^ c;
          break;
        case 5:
          output.Add((int)(combo(program[ip + 1]) % 8));
          break;
        case 6:
          b = a >> (int)combo(program[ip + 1]);
          break;
        case 7:
          c = a >> (int)combo(program[ip + 1]);
          break;
      }
      ip += 2;
    }
    return output;
  }

  public string SolveSecond() {
    Dictionary<int, List<(int, int, int)>> mapping = [];
    for (int start_a = 0; start_a < 512; start_a++) {
      var output = Execute(start_a, b, c);
      mapping.TryAdd(output[0], []);
      mapping[output[0]].Add((start_a / 64, start_a / 8 % 8, start_a % 8));
    }
    List<List<(int, int, int)>> possible_codes = [.. program.Select(b => mapping[b])];
    possible_codes.Reverse();
    List<int>? solution = SolvePossibleCodes(possible_codes, null);
    solution?.Reverse();
    long result = 0;
    foreach (var code in solution!) {
      result = (result << 3) | code;
    }
    return result.ToString();
  }

  private List<int>? SolvePossibleCodes(List<List<(int, int, int)>> possible_codes, (int, int)? allowed_start) {
    if (possible_codes.Count == 0) return [];
    foreach (var (high, mid, low) in possible_codes[0]) {
      if (allowed_start is null || allowed_start.Value.Item1 == high && allowed_start.Value.Item2 == mid) {
        var tail = SolvePossibleCodes(possible_codes[1..], (mid, low));
        if (tail is null) continue;
        tail.Add(low);
        if (allowed_start is null) {
          tail.Add(mid);
          tail.Add(high);
        }
        return tail;
      }
    }
    return null;
  }
}

Rust

First part was straightforward (the divisions are actually just right shifts), second part not so much. I made some assumptions about the input program, namely that in the end register 8 is divided by 8, then an output is made, then everything starts from the beginning again (if a isn’t 0). I found that the output always depends on at most 10 bits of a, so I ran through all 10-bit numbers and grouped them by the first generated output. At that point it’s just a matter of chaining these 10-bit numbers from the correct groups so that they overlap on 7 bits. The other 3 bits are consumed each round.

use rustc_hash::FxHashMap;

fn parse(input: &str) -> Option<Program> {
    let mut lines = input.lines();
    let a = lines.next()?.split_once(": ")?.1.parse().ok()?;
    let b = lines.next()?.split_once(": ")?.1.parse().ok()?;
    let c = lines.next()?.split_once(": ")?.1.parse().ok()?;
    lines.next()?;
    let program = lines
        .next()?
        .split_once(": ")?
        .1
        .split(',')
        .map(|s| s.parse())
        .collect::<Result<Vec<u8>, _>>()
        .ok()?;
    Some(Program {
        a,
        b,
        c,
        out: vec![],
        program,
        ip: 0,
    })
}

#[derive(Debug, Clone, Default)]
struct Program {
    a: u64,
    b: u64,
    c: u64,
    out: Vec<u8>,
    program: Vec<u8>,
    ip: usize,
}

impl Program {
    fn run(&mut self) {
        while self.step() {}
    }

    // Returns true if a step was taken, false if it halted
    fn step(&mut self) -> bool {
        let Some(&[opcode, operand]) = &self.program.get(self.ip..self.ip + 2) else {
            return false;
        };
        self.ip += 2;
        match opcode {
            0 => self.adv(self.combo(operand)),
            1 => self.bxl(operand),
            2 => self.bst(self.combo(operand)),
            3 => self.jnz(operand),
            4 => self.bxc(),
            5 => self.out(self.combo(operand)),
            6 => self.bdv(self.combo(operand)),
            7 => self.cdv(self.combo(operand)),
            _ => panic!(),
        }
        true
    }

    fn combo(&self, operand: u8) -> u64 {
        match operand {
            0..=3 => operand as u64,
            4 => self.a,
            5 => self.b,
            6 => self.c,
            _ => unreachable!(),
        }
    }

    fn adv(&mut self, x: u64) {
        self.a >>= x
    }

    fn bxl(&mut self, x: u8) {
        self.b ^= x as u64
    }

    fn bst(&mut self, x: u64) {
        self.b = x % 8
    }

    fn jnz(&mut self, x: u8) {
        if self.a != 0 {
            self.ip = x as usize
        }
    }

    fn bxc(&mut self) {
        self.b ^= self.c
    }

    fn out(&mut self, x: u64) {
        self.out.push((x % 8) as u8)
    }

    fn bdv(&mut self, x: u64) {
        self.b = self.a >> x
    }

    fn cdv(&mut self, x: u64) {
        self.c = self.a >> x
    }
}

fn part1(input: String) {
    let mut program = parse(&input).unwrap();
    program.run();
    if let Some(e) = program.out.first() {
        print!("{e}")
    }
    for e in program.out.iter().skip(1) {
        print!(",{e}")
    }
    println!()
}

// Some assumptions on the input:
// * There is exactly one jump instruction at the end of the program, jumping to 0
// * Right before that, an output is generated
// * Right before that, register a is shifted right by 3: adv(3)
//
// Each output depends on at most 10 bits of a (it is used with a shift of at most 7).
// Therefore we look at all 10-bit a's and group them by the first number that is output.
// Then we just need to combine these generators into a chain that fits together.
fn number_generators(mut program: Program) -> [Vec<u16>; 8] {
    let mut out = [const { vec![] }; 8];
    for a in 1..(1 << 10) {
        program.a = a as u64;
        program.out.clear();
        program.ip = 0;
        program.run();
        let &output = program.out.first().unwrap();
        out[output as usize].push(a);
    }
    out
}

fn part2(input: String) {
    let mut program = parse(&input).unwrap();
    let generators = number_generators(program.clone());

    let output = program.program.clone();
    // a_candidates maps from 7-bit required prefixes to the lower bits of a that
    // generate the required numbers so far.
    let mut a_candidates: FxHashMap<u8, u64> = generators[output[0] as usize]
        .iter()
        .rev() // Collects the values for each prefix
        .map(|&a| ((a >> 3) as u8, a as u64 % 8))
        .collect();
    let len = output.len();
    for (i, x) in output.iter().enumerate().skip(1) {
        let mut next_candidates = FxHashMap::default();
        for (prefix, val) in generators[*x as usize]
            .iter()
            .filter(|&a| {
                // Take only short candidates in the end to ensure that not too many numbers are generated
                let max_bits = (len - i) * 3;
                (*a as u64) < (1u64 << max_bits)
            })
            // Only use generators that match any required prefix
            .filter(|&a| a_candidates.contains_key(&((a % (1 << 7)) as u8)))
            .map(|&a| {
                let prefix = (a >> 3) as u8;
                let val = a as u64 % 8;
                let prev = a_candidates[&((a % (1 << 7)) as u8)];
                (prefix, (val << (i * 3)) | prev)
            })
        {
            // Only insert first (smallest) encountered value
            next_candidates.entry(prefix).or_insert(val);
        }
        a_candidates = next_candidates;
    }
    println!("{}", a_candidates[&0]);

    // Verify result
    program.a = a_candidates[&0];
    program.run();
    assert_eq!(program.out, program.program);
}

util::aoc_main!();

Also on github

Haskell

Runs in 10 ms. I was stuck for most of the day on the bdv and cdv instructions, as I didn’t read that the numerator was still register A. Once I got past that, it was pretty straight forward.

import Control.Monad.State.Lazy
import Data.Bits (xor)
import Data.List (isSuffixOf)
import qualified Data.Vector as V

data Instr =
        ADV Int | BXL Int | BST Int | JNZ Int | BXC | OUT Int | BDV Int | CDV Int
type Machine = (Int, Int, Int, Int, V.Vector Int)

parse :: String -> Machine
parse s =
    let (la : lb : lc : _ : lp : _) = lines s
        [a, b, c] = map (read . drop 12) [la, lb, lc]
        p = V.fromList $ read $ ('[' :) $ (++ "]") $ drop 9 lp
    in  (a, b, c, 0, p)

getA, getB, getC, getIP :: State Machine Int
getA  = gets $ \(a, _, _, _ , _) -> a
getB  = gets $ \(_, b, _, _ , _) -> b
getC  = gets $ \(_, _, c, _ , _) -> c
getIP = gets $ \(_, _, _, ip, _) -> ip

setA, setB, setC, setIP :: Int -> State Machine ()
setA  a  = modify $ \(_, b, c, ip, p) -> (a, b, c, ip, p)
setB  b  = modify $ \(a, _, c, ip, p) -> (a, b, c, ip, p)
setC  c  = modify $ \(a, b, _, ip, p) -> (a, b, c, ip, p)
setIP ip = modify $ \(a, b, c, _ , p) -> (a, b, c, ip, p)

incIP :: State Machine ()
incIP = getIP >>= (setIP . succ)

getMem :: State Machine (Maybe Int)
getMem = gets (\(_, _, _, ip, p) -> p V.!? ip) <* incIP

getCombo :: State Machine (Maybe Int)
getCombo = do
    n <- getMem
    case n of
        Just 4          -> Just <$> getA
        Just 5          -> Just <$> getB
        Just 6          -> Just <$> getC
        Just n | n <= 3 -> return $ Just n
        _               -> return Nothing

getInstr :: State Machine (Maybe Instr)
getInstr = do
    opcode <- getMem
    case opcode of
        Just 0 -> fmap        ADV  <$> getCombo
        Just 1 -> fmap        BXL  <$> getMem
        Just 2 -> fmap        BST  <$> getCombo
        Just 3 -> fmap        JNZ  <$> getMem
        Just 4 -> fmap (const BXC) <$> getMem
        Just 5 -> fmap        OUT  <$> getCombo
        Just 6 -> fmap        BDV  <$> getCombo
        Just 7 -> fmap        CDV  <$> getCombo
        _      -> return Nothing

execInstr :: Instr -> State Machine (Maybe Int)
execInstr (ADV n) = (getA >>= (setA . (`div` (2^n)))) *> return Nothing
execInstr (BDV n) = (getA >>= (setB . (`div` (2^n)))) *> return Nothing
execInstr (CDV n) = (getA >>= (setC . (`div` (2^n)))) *> return Nothing
execInstr (BXL n) = (getB >>= (setB . xor n)) *> return Nothing
execInstr (BST n) = setB (n `mod` 8) *> return Nothing
execInstr (JNZ n) = do
    a <- getA
    case a of
        0 -> return ()
        _ -> setIP n
    return Nothing
execInstr  BXC    = ((xor <$> getB <*> getC) >>= setB) *> return Nothing
execInstr (OUT n) = return $ Just $ n `mod` 8

run :: State Machine [Int]
run = do
    mInstr <- getInstr
    case mInstr of
        Nothing    -> return []
        Just instr -> do
            mOut <- execInstr instr
            case mOut of
                Nothing ->           run
                Just n  -> (n :) <$> run

solve2 :: Machine -> Int
solve2 machine@(_, _, _, _, p') = head [a | x <- [1 .. 7], a <- go [x]]
    where
        p = V.toList p'
        go as =
            let a = foldl ((+) . (* 8)) 0 as
            in  case evalState (setA a *> run) machine of
                    ns  | ns == p           -> [a]
                        | ns `isSuffixOf` p ->
                            concatMap go [as ++ [a] | a <- [0 .. 7]]
                        | otherwise         -> []

main :: IO ()
main = do
    machine@(_, _, _, _, p) <- parse <$> getContents
    putStrLn $ init $ tail $ show $ evalState run machine
    print $ solve2 machine

Haskell

Woah, that was suddenly a hard one: several tricky things combined. I’m not a big fan of the kind of problems like part 2 today, but eh - you can’t please everyone.

import Control.Monad
import Control.Monad.RWS
import Data.Bits
import Data.Foldable
import Data.List
import Data.List.Split
import Data.Vector (Vector)
import Data.Vector qualified as Vector

type Machine = RWS (Vector Int) [Int] (Int, Int, Int)

readInput :: String -> ((Int, Int, Int), Vector Int)
readInput s =
  let (regs, _ : [prog]) = break null $ lines s
   in ( let [a, b, c] = map (read . last . words) regs in (a, b, c),
        let [_, s] = words prog in Vector.fromList $ map read $ splitOn "," s
      )

stepMachine :: Int -> Machine Int
stepMachine ip = do
  opcode <- asks (Vector.! ip)
  operand <- asks (Vector.! (ip + 1))
  (a, b, c) <- get
  let combo = [0, 1, 2, 3, a, b, c, undefined] !! operand
      ip' = ip + 2
      adv = a `div` (2 ^ combo)
      store 'A' v = modify (\(_, b, c) -> (v, b, c))
      store 'B' v = modify (\(a, _, c) -> (a, v, c))
      store 'C' v = modify (\(a, b, _) -> (a, b, v))
  case opcode of
    0 -> store 'A' adv >> return ip'
    1 -> store 'B' (b `xor` operand) >> return ip'
    2 -> store 'B' (combo .&. 7) >> return ip'
    3 -> return $ if a == 0 then ip' else operand
    4 -> store 'B' (b `xor` c) >> return ip'
    5 -> tell [combo .&. 7] >> return ip'
    6 -> store 'B' adv >> return ip'
    7 -> store 'C' adv >> return ip'

part1 (regs, prog) =
  let (a, s, w) = runRWS (go 0) prog regs
   in intercalate "," $ map show w
  where
    go ip = when (ip < Vector.length prog) $ stepMachine ip >>= go

part2 (_, prog) = minimum $ foldM go 0 $ reverse $ toList prog
  where
    go a d = do
      b <- [0 .. 7]
      let a' = (a `shiftL` 3) .|. b
          b1 = b `xor` 5
          b2 = b1 `xor` (a' `shiftR` b1)
          b3 = b2 `xor` 6
      guard $ b3 .&. 7 == d
      return a'

main = do
  input <- readInput <$> readFile "input17"
  putStrLn $ part1 input
  print $ part2 input

Haskell

Part 2 was tricky, I tried executing the algorithm backwards, which worked fine for the example but not with the input program, because it uses one-way functions .-. Then I tried to write an algorithm that would try all valid combinations of powers of 8 and but I failed, I then did it by hand.

import Control.Arrow
import Data.Bits
import qualified Data.Char as Char
import qualified Data.List as List

replace c r c' = if c' == c then r else c'

parse :: String -> ([Integer], [Int])
parse = map (replace ',' ' ')
        >>> filter ((Char.isDigit &&& Char.isSpace) >>> uncurry (||))
        >>> words
        >>> splitAt 3
        >>> (map read *** map read)

type InstructionPointer = Int

adv = 0
bxl = 1
bst = 2
jnz = 3
bxc = 4
out = 5
bdv = 6
cdv = 7

lookupCombo _    0 = 0
lookupCombo _    1 = 1
lookupCombo _    2 = 2
lookupCombo _    3 = 3
lookupCombo regs 4 = regs !! 0
lookupCombo regs 5 = regs !! 1
lookupCombo regs 6 = regs !! 2
lookupCombo regs 7 = error "Invalid operand"

execute :: InstructionPointer -> [Integer] -> [Int] -> [Int]
execute ip regs@(regA:regB:regC:[]) ops
        | ip >= length ops = []
        | instruction == adv = execute (ip + 2) [regA `div` (2 ^ comboValue), regB, regC] ops
        | instruction == bxl = execute (ip + 2) [regA, xor regB (toInteger operand), regC] ops
        | instruction == bst = execute (ip + 2) [regA, comboValue `mod` 8, regC] ops
        | instruction == jnz && regA == 0 = execute (ip + 2) regs ops
        | instruction == jnz && regA /= 0 = execute operand regs ops
        | instruction == bxc = execute (ip + 2) [regA, xor regB regC, regC] ops
        | instruction == out = (fromIntegral comboValue) `mod` 8 : execute (ip + 2) regs ops
        | instruction == bdv = execute (ip + 2) [regA, regA `div` (2 ^ comboValue), regC] ops
        | instruction == cdv = execute (ip + 2) [regA, regB, regA `div` (2 ^ comboValue)] ops
        where
                (instruction, operand) = (ops !! ip, ops !! (succ ip))
                comboValue             = lookupCombo regs operand

part1 = uncurry (execute 0)
        >>> List.map show
        >>> List.intercalate ","

valid i t n = ((n `div` (8^i)) `mod` 8) `xor` 7 `xor` (n `div` (4*(8^i))) == t

part2 = const 247839653009594

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse
```haskell

C

Was looking forward to a VM! Really took my leisure for part 1, writing a disassembler, tracing, all pretty.

Part 2 reminded me of 2021 day 24 where we also had to reverse an input. It’s been on my mind recently and I was thinking if there would be a way to backfeed an output through a program, yielding a representation like: “the input plus 3498 is a multiple of 40, and divisible by a number that’s 5 mod 8” (considering lossy functions like modulo and integer division).

Today’s input didn’t lend itself to that, however, but analysing it having the solution ‘click’ was very satisfying.

#include "common.h"

#define MEMZ 32
#define OUTZ 32
#define BUFZ 64

enum { ADV, BXL, BST, JNZ, BXC, OUT, BDV, CDV };

struct vm {
	int64_t mem[MEMZ]; int nm, pc;
	int64_t out[OUTZ]; int no;
	int64_t a,b,c;
} vm;

/* returns 0 if halted, 1 otherwise */
static int
step(void)
{
	int64_t op, ar, ac;	/* operator, lit. arg, combo arg */

	assert(vm.pc >= 0);
	assert(vm.pc+2 <= MEMZ);

	if (vm.pc >= vm.nm)
		return 0;

	op = vm.mem[vm.pc++];
	ar = vm.mem[vm.pc++];
	ac = ar==4 ? vm.a : ar==5 ? vm.b : ar==6 ? vm.c : ar;

	switch (op) {
	case ADV: vm.a = vm.a >> ac; break;
	case BDV: vm.b = vm.a >> ac; break;
	case CDV: vm.c = vm.a >> ac; break;
	case BXL: vm.b = vm.b ^ ar; break;
	case BXC: vm.b = vm.b ^ vm.c; break;
	case BST: vm.b = ac % 8; break;
	case JNZ: if (vm.a) vm.pc = ar; break;
	case OUT: assert(vm.no < OUTZ); vm.out[vm.no++] = ac%8; break;
	default: assert(!"invalid opcode"); return 0;
	}

	return 1;
}

static int64_t
recur_p2(int64_t a0, int pos)
{
	int64_t a, i;

	/*
	 * The code in the input uses up to 7 low bits of the A register
	 * to produce a single number, then chops off the low 3 bits and
	 * continues.
	 *
	 * That means bits above the current triplet influence what
	 * number it generates, but bits below don't. To generate a
	 * desired sequence then, we append, not prepend,  candidate
	 * triplets.
	 *
	 * We may end up in a situation where, given the prefix found
	 * for the numbers so far, no triplet yields the desired next
	 * number. Then we have to backtrack and find another prefix,
	 * hence the recursion.
	 */

	if (pos >= vm.nm)
		return a0 >> 3;

	for (i=0; i<8; i++) {
		vm.a=a= a0+i;
		vm.b=vm.c=vm.pc=vm.no= 0;

		while (step() && !vm.no)
			;

		if (vm.no && vm.out[0] == vm.mem[vm.nm-pos-1])
			if ((a = recur_p2(a << 3, pos+1)))
				return a;
	}

	return 0;
}

int
main(int argc, char **argv)
{
	char b[BUFZ], *tok, *rest;
	int i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	fgets(b, BUFZ, stdin); sscanf(b, "Register A: %lld", &vm.a);
	fgets(b, BUFZ, stdin); sscanf(b, "Register B: %lld", &vm.b);
	fgets(b, BUFZ, stdin); sscanf(b, "Register C: %lld", &vm.c);
	fgets(b, BUFZ, stdin);

	assert(vm.b == 0);	/* assumption for part 2 */
	assert(vm.c == 0);

	rest = fgets(b, sizeof(b), stdin);
	strsep(&rest, ":");

	while ((tok = strsep(&rest, ","))) {
		assert(vm.nm < MEMZ);
		vm.mem[vm.nm++] = atoll(tok);
	}

	while (step())
		;
	for (i=0; i<vm.no; i++)
		printf(i ? ",%lld" : "17: %lld", vm.out[i]);

	printf(" %lld\n", recur_p2(0, 0));
	return 0;
}

https://github.com/sjmulder/aoc/blob/master/2024/c/day17.c

Dart

Part one was an exercise in building a simple OpCode machine. Part two was trickier. It was clear that the a register was repeatedly being divided by 8, and testing a few values showed that each 3-bits of the initial value defined one entry in the output, so I built a recursive routine that brute-forced each one in turn. Only <1ms to run though, so not that brutal.

(It’s worth pointing out that at some stages multiple 3-bit values gave rise to the required value, causing a failure to resolve later on if not checked.)

(edit: for-loop in buildQuine now avoids using a 0 for the initial triplet, as this should not be a valid value, and if it turns out to generate the required digit of the quine, you will get an infinite recursion. Thanks to SteveDinn for bringing this to my attention.)

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

var prog = <int>[];
typedef State = (int, int, int);
State parse(List<String> lines) {
  var regs = lines.takeTo('').map((e) => int.parse(e.split(' ').last)).toList();
  var (a, b, c) = (regs[0], regs[1], regs[2]);
  prog = lines.last.split(' ').last.split(',').map(int.parse).toList();
  return (a, b, c);
}

List<int> runProg(State rec) {
  var (int a, int b, int c) = rec;
  combo(int v) => switch (v) { 4 => a, 5 => b, 6 => c, _ => v };
  var output = <int>[], pc = 0;
  while (pc < prog.length) {
    var code = prog[pc], arg = prog[pc + 1];
    var _ = switch (code) {
      0 => a ~/= pow(2, combo(arg)),
      1 => b ^= arg,
      2 => b = combo(arg) % 8,
      3 => (a != 0) ? (pc = arg - 2) : 0,
      4 => b ^= c, //ignores arg
      5 => output.add(combo(arg) % 8),
      6 => b = a ~/ pow(2, combo(arg)),
      7 => c = a ~/ pow(2, combo(arg)),
      _ => 0
    };
    pc += 2;
  }
  return output;
}

Function eq = const ListEquality().equals;
Iterable<int> buildQuine(State rec, List<int> quine, [top = false]) sync* {
  var (int a0, int b0, int c0) = rec;
  if (top) a0 = 0;
  if (quine.length == prog.length) {
    yield a0;
    return;
  }
  for (var a in (top ? 1 : 0).to(8)) {
    var newState = (a0 * 8 + a, b0, c0);
    var newQuine = runProg(newState);
    if (eq(prog.slice(prog.length - newQuine.length), newQuine)) {
      yield* buildQuine(newState, newQuine);
    }
  }
}

part1(List<String> lines) => runProg(parse(lines)).join(',');

part2(List<String> lines) => buildQuine(parse(lines), [], true).first;

Rust

Part 2 really broke me. I ended up converting the instructions into a pair of equations, that I then used to do DFS to find the A value. Then I realised the compute function already does this for me…

#[cfg(test)]
mod tests {
    use regex::Regex;

    fn compute(registers: &mut [u64], instructions: &[u64]) -> String {
        let mut out = vec![];
        let mut ip = 0;
        loop {
            let opcode = instructions[ip];
            let operand = instructions[ip + 1];

            match opcode {
                0 => {
                    println!(
                        "0: A <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[0] /= 1 << combo(operand, registers)
                }
                1 => {
                    println!("1: B <= B[{}]^{}", registers[1], operand);
                    registers[1] ^= operand
                }
                2 => {
                    println!(
                        "2: B <= {} ({}:{:?})",
                        combo(operand, registers) % 8,
                        operand,
                        registers
                    );
                    registers[1] = combo(operand, registers) % 8
                }
                3 => {
                    if registers[0] != 0 {
                        println!("3: JUMP {}", operand);
                        ip = operand as usize;
                        continue;
                    }
                }
                4 => {
                    println!("4: B <= B[{}]^C[{}]", registers[1], registers[2]);
                    registers[1] ^= registers[2]
                }
                5 => {
                    out.push(combo(operand, registers) % 8);
                    println!(
                        "5: OUT: {} ({}:{:?})",
                        out.last().unwrap(),
                        operand,
                        registers
                    );
                }

                6 => {
                    println!(
                        "6: B <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[1] = registers[0] / (1 << combo(operand, registers))
                }
                7 => {
                    println!(
                        "7: C <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[2] = registers[0] / (1 << combo(operand, registers))
                }
                _ => unreachable!(),
            }
            ip += 2;
            if ip >= instructions.len() {
                break;
            }
        }
        out.iter()
            .map(|v| v.to_string())
            .collect::<Vec<String>>()
            .join(",")
    }

    fn combo(p0: u64, regs: &[u64]) -> u64 {
        match p0 {
            0..=3 => p0,
            4..=6 => regs[(p0 - 4) as usize],
            _ => unreachable!(),
        }
    }

    #[test]
    fn day17_part1_test() {
        let input = std::fs::read_to_string("src/input/day_17.txt").unwrap();
        let mut parts = input.split("\n\n");
        let re = Regex::new(r"[\-0-9]+").unwrap();
        let mut registers = re
            .captures_iter(parts.next().unwrap())
            .map(|x| {
                let first = x.get(0).unwrap().as_str();
                first.parse::<u64>().unwrap()
            })
            .collect::<Vec<u64>>();

        let instructions = parts
            .next()
            .unwrap()
            .replace("Program: ", "")
            .split(",")
            .map(|s| s.parse::<u64>().unwrap())
            .collect::<Vec<u64>>();

        let out = compute(&mut registers, &instructions);
        println!("{out}");
    }

    #[test]
    fn day17_part2_test() {
        let input = std::fs::read_to_string("src/input/day_17.txt").unwrap();
        let mut parts = input.split("\n\n");
        let _ = parts.next().unwrap();

        let instructions = parts
            .next()
            .unwrap()
            .replace("Program: ", "")
            .split(",")
            .map(|s| s.parse::<u64>().unwrap())
            .collect::<Vec<u64>>();

        fn search_generic(a_prev: u64, i: usize, instructions: &Vec<u64>) -> Option<u64> {
            let out = instructions[i];
            for j in 0..8 {
                let next_a = (a_prev << 3) + j;
                let expected = instructions[i..]
                    .iter()
                    .map(|v| v.to_string())
                    .collect::<Vec<String>>()
                    .join(",");

                let mut regs = [next_a, 0, 0];
                if expected == compute(&mut regs, instructions) {
                    if i == 0 {
                        return Some(next_a);
                    }
                    if let Some(a) = search_generic(next_a, i - 1, instructions) {
                        return Some(a);
                    }
                }
            }
            None
        }

        let res_a = search_generic(0, instructions.len() - 1, &instructions).unwrap();

        let mut registers = [res_a, 0, 0];
        let out = compute(&mut registers, &instructions);
        let expected = instructions
            .iter()
            .map(|v| v.to_string())
            .collect::<Vec<String>>()
            .join(",");

        assert_eq!(expected, out);
        println!("{res_a}");
    }
}