Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

🖥️ - 2024 DAY 17 SOLUTIONS - 🖥️

Day 17: Chronospatial Computer

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

14 comments

  • 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()
        );
    }
}

  • 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.

  • 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;

    • I'm confused reading the buildQuine() method. It reads to me that when you call it from the top level with top = true, A0 will be set to 0, and then when we get to the 0 to 8 loop, the 'A' register will be 0 * 8 + 0 for the first iteration, and then recurse with top = false, but with a0 still ending up 0, causing infinite recursion.

      Am I missing something?

      I got it to work with a check that avoids the recursion if the last state's A register value is the same as the new state's value.

      • Oh, good catch. That's certainly the case if an initial value of 0 correctly generates the required value of the quine. As I'd already started running some code against the live data that's what I tested against, and so it's only when I just tested it against the example data that I saw the problem.

        I have changed the for-loop to read for (var a in (top ? 1 : 0).to(8)) for maximum terseness :-)

        That still works for the example and my live data, and I don't think there should be a valid solution that relies on the first triplet being 0. Thanks for your reply!

  • 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.

    Also on github

  • 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.

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

  • 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.

  • 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.

  • 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;
}

  • 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...

     rust
        
#[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}");
    }
}
14 comments