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

15 comments

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

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

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

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

  • 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}");
    }
}
15 comments