AoC Day 21: Chronal Conversion

twitter logo github logo ・1 min read

Advent of Code (26 Part Series)

1) AoC Day 1: Chronal Calibration 2) AoC Day 2: Inventory Management System 3 ... 24 3) AoC Day 3: No Matter How You Slice It 4) AoC Day 4: Repose Record 5) AoC Day 5: Alchemical Reduction 6) AoC Day 6: Chronal Coordinates 7) AoC Day 7: The Sum of Its Parts 8) AoC Day 8: Memory Maneuver (Placeholder) 9) AoC Day 9: Marble Mania 10) AoC Day 10: The Stars Align 11) AoC Day 11: Chronal Charge 12) AoC Day 12: Subterranean Sustainability 13) AoC Day 13: Mine Cart Madness 14) AoC Day 14: Chocolate Charts 15) AoC Day 15: Beverage Bandits 16) AoC Day 16: Chronal Classification 17) AoC Day 17: Reservoir Research 18) AoC Day 18: Settlers of The North Pole 19) AoC Day 19: Go With the Flow 20) AoC Day 20: A Regular Map 21) AoC Day 21: Chronal Conversion 22) AoC Day 22: Mode Maze 23) AoC Day 23: Experimental Emergency Teleportation 24) AoC Day 24: Immune System Simulator 20XX 25) AoC Day 25: Four-Dimensional Adventure 26) Advent of Code Wrap-Up

...

Honestly? Your guess is as good as mine. It's Day 21, and we're exploiting an integer underflow bug in the space-time continuum? In order to save Christmas? I guess?

I think I'm going to have to spend some time on this one before I even understand exactly what it is that we have to do. All I know is that we are fiddling with the registers in our time machine again so that we don't go back in time indefinitely forever.

Ho. Ho. Ho.

Good luck! 🀢

twitter logo DISCUSS (5)
markdown guide
 

First I have translated the input into "assembler" using the disassembler I did for day 19, and then I reassembled the solution into C++.

In the code, the program exits when register 5 is equal to register 0.

  • For part1 the value of register 5 the first time the condition is evaluated, is the solution.
  • For part2 you have to check for a cycle in the values of register 5 at the condiction. The last one before the cycle is the solution.

So I've added the code to check those two conditions.

#include <iostream>
#include <set>

using namespace std;

int main() {
  set<int> seen;
  int last_r5 = 0;
  int r0, r1, r3, r4, r5;

  l6: 
  r1 = r5 | 65536;
  r5 = 10678677;

  l8:
  r4 = r1 & 255;
  r5 += r4;
  r5 &= 16777215;
  r5 *= 65899;
  r5 &= 16777215;
  if (256 > r1) goto l28;
  r4 = 0;

  l18:
  r3 = r4 + 1;
  r3 *= 256;
  if (r3 > r1) goto l26;
  r4 += 1;
  goto l18;

  l26:
  r1 = r4;
  goto l8;

  l28:
  if (last_r5 == 0) {
    cout << "Part1: " << r5 << endl;
  }
  if (seen.find(r5) == seen.end()) {
    seen.insert(r5);
    last_r5 = r5;
  } else {
    cout << "Part2: " << last_r5 << endl;
    return 0;
  }
  goto l6;
}
 

For part 1, I used the same interpreter as in the previous days. I had to convert all registers to numbers, then I just waited until the final condition could be checked.

while ($r[$ip] <= $#code) {
    $_ = 0 + $_ for @r;
    my $line = $code[ $r[$ip] ];
    my ($instruction, @args) = split ' ', $line;
    if ($r[$ip] == 28) {
        say $r[2];
        exit;
    }
    $opcodes{$instruction}->(@args);
    ++$r[$ip];
}

For part 2, the interpreter was too slow, so I rewrote the whole program by hand. Running it then took 2.5 minutes.

#!/usr/bin/perl
use strict;
use feature qw{ say };

my $prev;
my ($r0, $ip, $r2, $r3, $r4, $r5) = (0) x 6;
my %seen;

$r2 = 123;
l1:
$r2 &= 456;

$r2 = $r2 == 72;
goto l1 unless $r2;

$r2 = 0;

l6:
$r5 = 0+$r2 | 65536;
$r2 = 4843319;

l8:
$r4 = 0+$r5 & 255;
$r2 += $r4;
$r2 &= 16777215;
$r2 *= 65899;
$r2 &= 16777215;
$r4 = 256 > $r5;
goto l28 if $r4;

$r4 = 0;

l18:
$r3 = $r4 + 1;
$r3 *= 256;
$r3 = $r3 > $r5;
goto l26 if $r3;

++$r4;
goto l18;

l26:
$r5 = $r4;
goto l8;

l28:
$r4 = $r2 == $r0;
$seen{$r2}++ and end();
$prev = $r2;
end() if $r4;
goto l6;

sub end {
    say $prev;
    exit
}
 

JavaScript solution

My case was exactly the same as @jmgimeno , I used the same analyzer from day 19 and I came down to the same conclusions as him:

  • for part 1, the solution is the first time the code reaches the check if register[5] is the same as register0
  • for part 2, I decided that I had to check for loops and the last solution before the 1st loop is the solution.

As usual, I'm gonna omit reader.js which is the same as the other solutions and jump to the point:

21a.js

const { readFile } = require('./reader');
const {
    operations
} = require('./16-common');
const {
    readInput,
    analyzeProgram
} = require ('./19-common');

const runProgram = (ipRegister, program) => {
    let registers = [0, 0, 0, 0, 0, 0];
    const n = program.length;
    let ip = registers[ipRegister];
    while (ip >= 0 && ip < n) {
        const instruction = program[ip];
        const op = operations[instruction[0]];
        registers = op(instruction)(registers);
        ip = ++registers[ipRegister];
        if (ip === 28) {            
            return registers[5];
        }
    }

    return registers[5];
};

(async () => {
    const lines = await readFile('21-input.txt');

    const { ipRegister, program } = readInput(lines);

    //analyzeProgram(ipRegister, program);

    const solution = runProgram(ipRegister, program);

    console.log(`The lowest non-negative integer value for register 0 that causes the program to halt after executing the fewest instructions is ${solution}.`);
})();

21b.js

const { readFile } = require('./reader');
const {
    operations
} = require('./16-common');
const {
    readInput,
    analyzeProgram
} = require ('./19-common');

const runProgram = (ipRegister, program) => {
    let registers = [0, 0, 0, 0, 0, 0];
    const n = program.length;
    let ip = registers[ipRegister];
    const frequency = new Set();
    let lastSolution;
    while (ip >= 0 && ip < n) {
        const instruction = program[ip];
        const op = operations[instruction[0]];
        registers = op(instruction)(registers);
        ip = ++registers[ipRegister];
        if (ip === 28) {            
            if (frequency.has(registers[5])) {
                return lastSolution;
            }
            else  {
                lastSolution = registers[5];
                frequency.add(lastSolution);
            }
        }
    }

    return registers[5];
};

(async () => {
    const lines = await readFile('21-input.txt');

    const { ipRegister, program } = readInput(lines);

    //analyzeProgram(ipRegister, program);

    const solution = runProgram(ipRegister, program);

    console.log(`The lowest non-negative integer value for register 0 that causes the program to halt after executing the most instructions is ${solution}.`);
})();
 

Don't know if I'm alone here but seeing all your posts starting with "AoC" over the past few days triggered a reaction in my brain that made me want to play AoE!!!

 

Ditto. Although I'm playing Red Alert 2 - Yuri's Revenge.

Classic DEV Post from Dec 22 '18

How does your workplace approach recognition?

Does your workplace have a strategy for recognising team members?

Ryan Palo profile image
Ryan is a mechanical engineer in the East SF Bay Area with a focus on dynamic languages like Ruby & Python. Goal: learn a ton and become a physics, math, and programming teacher. Message me on DEV.TO

Let's talk shop πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Sign up (for free)