AoC Day 19: Go With the Flow

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

On Day 19, we're headed back to the time machine's inner workings to play with more opcodes, and this time, our opcodes can fiddle with the program's instruction pointer!

It seemed like people mostly enjoyed the opcode challenge a few days ago (me included!), so this should be fun! Let's see your solutions.

twitter logo DISCUSS (5)
markdown guide
 

For part1 I translated the code directly into C with a program in python:

import os
import string

TEMPLATE = string.Template("""
#include <stdio.h>

int regs[] = $registers;

void addr(int a, int b, int c) {
  regs[c] = regs[a] + regs[b];
}

void addi(int a, int b, int c) {
  regs[c] = regs[a] + b;
}

void mulr(int a, int b, int c) {
  regs[c] = regs[a] * regs[b];
}

void muli(int a, int b, int c) {
  regs[c] = regs[a] * b;
}

void banr(int a, int b, int c) {
  regs[c] = regs[a] & regs[b];
}

void bani(int a, int b, int c) {
  regs[c] = regs[a] & b;
}

void borr(int a, int b, int c) {
  regs[c] = regs[a] | regs[b];
}

void bori(int a, int b, int c) {
  regs[c] = regs[a] | b;
}

void setr(int a, int b, int c) {
  regs[c] = regs[a];
}

void seti(int a, int b, int c) {
  regs[c] = a;
}

void gtir(int a, int b, int c) {
  regs[c] = (a > regs[b]) ? 1 : 0;
}

void gtri(int a, int b, int c) {
  regs[c] = (regs[a] > b) ? 1 : 0;
}

void gtrr(int a, int b, int c) {
  regs[c] = (regs[a] > regs[b]) ? 1 : 0;
}

void eqir(int a, int b, int c) {
  regs[c] = (a == regs[b]) ? 1 : 0;
}

void eqri(int a, int b, int c) {
  regs[c] = (regs[a] == b) ? 1 : 0;
}

void eqrr(int a, int b, int c) {
  regs[c] = (regs[a] == regs[b]) ? 1 : 0;
}

int main() {
  while (1) {
    switch(regs[$ipreg]) {
$cases
      default: printf("Execution: %d\\n", regs[0]); return 0;
    }
    regs[$ipreg] += 1;
  }
}
""")


def compile_line(line):
    opname = line[:4]
    a, b, c = line[4:].split()
    return '%s(%s, %s, %s);' % (opname, a, b, c)


def compile_lines(lines):
    cases = []
    for lineno, line in enumerate(lines):
        cases.append('      case %d: %s break;' % (lineno, compile_line(line)))
    return '\n'.join(cases)


def compile_file(fname, registers):
    with open(fname, 'r') as program:
        registers = str(registers).replace('[', '{').replace(']', '}')
        ipreg = program.readline().strip()[4:]
        cases = compile_lines(line.strip() for line in program)
        return TEMPLATE.substitute(ipreg=ipreg, cases=cases, registers=registers)


def part1(fname):
    name, _ = os.path.splitext(fname)
    with open(name + '_part1.c', 'w') as compiled:
        program = compile_file(fname, [0, 0, 0, 0, 0, 0])
        compiled.write(program)


def part2(fname):
    name, _ = os.path.splitext(fname)
    with open(name + '_part2.c', 'w') as compiled:
        program = compile_file(fname, [1, 0, 0, 0, 0, 0])
        compiled.write(program)


if __name__ == "__main__":
    part1('test_input.txt')
    part2('test_input.txt')
    part1('input.txt')
    part2('input.txt')

The program was able to execute part1 but part2 was taking forever.

Then, after some failed ideas, I did a translator into "assembler" to study the code:

import os

OPS = {'addi': 'r[{c}] = r[{a}] + {b}',
       'addr': 'r[{c}] = r[{a}] + r[{b}]',
       'muli': 'r[{c}] = r[{a}] * {b}',
       'mulr': 'r[{c}] = r[{a}] * r[{b}]',
       'seti': 'r[{c}] = {a}',
       'setr': 'r[{c}] = r[{a}]',
       'eqrr': 'r[{c}] = 1 if r[{a}] == r[{b}] else 0',
       'gtrr': 'r[{c}] = 1 if r[{a}] > r[{b}] else 0'
       }


def compile_line(line, lineno, ipreg):
    opname = line[:4]
    a, b, c = map(int, line[4:].split())
    if opname == 'addi' and c == ipreg and a == ipreg:
        return 'jump #%d' % (b+lineno+1,)
    elif opname == 'addr' and c == ipreg and a == ipreg:
        return 'jump r[%d] + %d' % (b, lineno+1)
    elif opname == 'addr' and c == ipreg and b == ipreg:
        return 'jump r[%d] + %d' % (a, lineno+1)
    elif opname == 'seti' and c == ipreg:
        return 'jump #%d' % (a+1,)
    elif opname == 'mulr' and a == ipreg and b == ipreg and c == ipreg:
        return 'jump #%d' %(lineno * lineno + 1,)
    elif opname == 'addr' and b == ipreg:
        return 'r[%d] = r[%d] + %d' %(c, a, lineno)
    elif opname == 'addr' and a == ipreg:
        return 'r[%d] = r[%d] + %d' % (c, b, lineno)
    elif opname == 'mulr' and b == ipreg:
        return 'r[%d] = r[%d] * %d' %(c, a, lineno)
    elif opname == 'mulr' and a == ipreg:
        return 'r[%d] = r[%d] * %d' % (c, b, lineno)
    elif opname == 'setr' and a == ipreg:
        return 'r[%d] = %d' % (c, lineno)
    else:
        return OPS[opname].format(a=a, b=b, c=c)


def compile_lines(lines, ipreg):
    cases = []
    for lineno, line in enumerate(lines):
        cases.append("%2d# %s" % (lineno, compile_line(line, lineno, ipreg)))
    return '\n'.join(cases)


def compile_file(fname, registers):
    with open(fname, 'r') as program:
        ipreg = int(program.readline()[4:])
        registers = 'r = ' + str(registers) + '\n'
        instructions = compile_lines((line.strip() for line in program), ipreg)
        return registers, instructions


def part2(fname):
    name, _ = os.path.splitext(fname)
    with open(name + '_disassembled.txt', 'w') as compiled:
        registers, instructions = compile_file(fname, [1, 0, 0, 0, 0, 0])
        compiled.write(registers)
        compiled.write(instructions)


if __name__ == "__main__":
    part2('test_input.txt')
    part2('input.txt')

Then I studied the result:

 0# jump #17
 1# r[3] = 1
 2# r[5] = 1
 3# r[4] = r[3] * r[5]
 4# r[4] = 1 if r[4] == r[1] else 0
 5# jump r[4] + 6
 6# jump #8
 7# r[0] = r[3] + r[0]
 8# r[5] = r[5] + 1
 9# r[4] = 1 if r[5] > r[1] else 0
10# jump r[4] + 11
11# jump #3
12# r[3] = r[3] + 1
13# r[4] = 1 if r[3] > r[1] else 0
14# jump r[4] + 15
15# jump #2
16# jump #257
17# r[1] = r[1] + 2
18# r[1] = r[1] * r[1]
19# r[1] = r[1] * 19
20# r[1] = r[1] * 11
21# r[4] = r[4] + 3
22# r[4] = r[4] * 22
23# r[4] = r[4] + 13
24# r[1] = r[1] + r[4]
25# jump r[0] + 26
26# jump #1
27# r[4] = 27
28# r[4] = r[4] * 28
29# r[4] = r[4] + 29
30# r[4] = r[4] * 30
31# r[4] = r[4] * 14
32# r[4] = r[4] * 32
33# r[1] = r[1] + r[4]
34# r[0] = 0
35# jump #1

And, after drawing a flowchart, I reassembled the code into:

if (r0 == 0)
    r1 = 915;
else 
    r1 = 10551315;
r3 = 1;
do {
    r5 = 1;
    do {
        r4 = r3 * r5;
        if (r4 == r1)
            r0 = r3 + r0;
        r5 = r5 + 1;
    } while (r3 <= r1);
    r3 = r3 + 1;
} while (r5 <= r1);
cout << r0;

The code sums all factors of the number stored in r1 !!!!

So, I factored 10551315 = 3*5*31*22691 and then sum all the divisors, as the program does.

For me it has been the best problem so far !!!

 

Had our office Christmas lunch yesterday, with a few whiskies after so I didn't get Advent of Code finished by the end of the day!

Another machine simulation, building on Day 16's. While that allows for a more complex problem to be stated with fewer new details to outline, the problem is sufficiently different that I'm not sure how much code I'll be able to reuse.

We don't need to decipher the opcodes this time so I modelled them with an enum with attached names and execution functions.

enum class OpCode(val asm: String, val exec: (Registers, Arguments) -> Unit) {
    ADDR("addr", { r, (a, b, c) -> r[c] = r[a] + r[b] }),
    ADDI("addi", { r, (a, b, c) -> r[c] = r[a] +   b  }),
    ...
}

The program itself is then just the Instruction Pointer register binding followed by a list of instructions.

data class Instruction(val opcode: OpCode, val arguments: Arguments)

data class Program(val ipBinding: Int, val instructions: List<Instruction>)

And the parser is straightforward as ever:

fun parse(input: String): Program {
    val integer: Parser<Int> = INTEGER.map(String::toInt)
    val opcode = or(OpCode.values().map { opcode -> string(opcode.asm).retn(opcode) })
    val arguments = sequence(integer, WHITESPACES.next(integer), WHITESPACES.next(integer), ::Arguments)
    val operation: Parser<Instruction> = sequence(opcode, WHITESPACES.next(arguments), ::Instruction)
    val bindip = string("#ip ").next(integer)
    val program = sequence(bindip, WHITESPACES.next(operation.sepBy(WHITESPACES)), ::Program)
    return program.parse(input.trim())
}

Executing the program is just a loop running until the IP is out of range.

fun execute(program: Program): Registers {
    val registers = Registers(ipBinding = program.ipBinding)

    while (program.instructions.indices.contains(registers.ip)) {
        val instr = program.instructions[registers.ip]
        instr.opcode.exec(registers, instr.arguments)
        registers.step()
    }

    return registers
}

And part 1 is trivial:

fun part1(program: Program) = execute(program)[0]

Part 2

The second part was altogether a different problem. It runs for a very very long time, so you can't get the answer just by executing it. You have to decipher the code and work out what it's doing, then compute the result without actually running it. To cut a long story short, it initialises R3 with a huge number, then uses an extremely inefficient algorithm to find numbers which are factors of that number, adding the factors up as it goes.

In analysing the code I noted that the section which computes the very large number ends with the final instruction which is a jump to the main loop. I dropped that instruction and executed the program to get the big number.

fun part2(program: Program): Int {
    val modifiedProgram = Program(program.ipBinding, program.instructions.dropLast(1))
    val numberToFactor = execute(modifiedProgram, r0=1)[3]

Then I just reimplemented the algorithm in Kotlin with a more efficient method:

    println("numberToFactor: $numberToFactor")
    val sumOfDivisions = (1..numberToFactor).asSequence().filter { i -> numberToFactor % i == 0 }.sum()
    return sumOfDivisions
}

Full code

 

Part 1 was straight forward execution of the program.

For Part 2 I wasn't really sure how we were expected to solve, but I went with rewriting asm code into php and then looked for some possible optimization (early break from the loop in my case).

<?php
$input = require_once 'readFile.php';

$ip = explode(' ', array_shift($input))[1][0];
$programm = array_values(array_map(function($str) {
  return explode(' ', preg_replace("/\r|\n/", "", $str));
}, $input));

function execute($r, $programm, $ip) {
  $asm = require_once 'opcodes.php';
  while (true) {
    [$opcode, $a, $b, $c] = $programm[$r[$ip]];
    $r = $asm[$opcode]($r, $a, $b, $c);
    $r[$ip]++;

    if (empty($programm[$r[$ip]])) {
      return $r[0];
    }
  }
}

function executeOptimized($r) {
  [$r0, $r1, $r2, $r3, $r4, $r5] = $r;

  $r1 = 6 * 22 + 6;
  $r3 = 2 * 2 * 19 * 11 + $r1;

  if ($r0 == 1) {
    $r1 = (27 * 28 + 29) * 30 * 14 * 32;
    $r3 += $r1;
    $r0 = 0;
  }

  while($r4 <= $r3) {
    $r5 = 1;

    while ($r5 <= $r3) {
      $r1 = $r4 * $r5;
      if ($r1 > $r3) {
        break;
      }
      if($r1 == $r3) {
        $r0 += $r4;
      }
      $r5++;
    }
    $r4++;
  }
  return $r0;
}

$r = [0, 0, 0, 0, 0, 0];

// echo "Part 1: " . execute($r, $programm, $ip) . "\n";
echo "Part 1: " . executeOptimized($r) . "\n";
$r[0] = 1;
echo "Part 2: " . executeOptimized($r) . "\n";
?>

opcodes.php

<?php
return [
  'addr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] + $r[$b];
    return $r;
  },
  'addi' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] + $b;
    return $r;
  },
  'mulr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] * $r[$b];
    return $r;
  },
  'muli' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] * $b;
    return $r;
  },
  'banr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] & $r[$b];
    return $r;
  },
  'bani' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] & $b;
    return $r;
  },
  'borr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] | $r[$b];
    return $r;
  },
  'bori' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] | $b;
    return $r;
  },
  'setr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a];
    return $r;
  },
  'seti' => function($r, $a, $b, $c) {
    $r[$c] = $a;
    return $r;
  },
  'gtir' => function($r, $a, $b, $c) {
    $r[$c] = $a > $r[$b] ? 1 : 0;
    return $r;
  },
  'gtri' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] > $b ? 1 : 0;
    return $r;
  },
  'gtrr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] > $r[$b] ? 1 : 0;
    return $r;
  },
  'eqir' => function($r, $a, $b, $c) {
    $r[$c] = $a == $r[$b] ? 1 : 0;
    return $r;
  },
  'eqri' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] == $b ? 1 : 0;
    return $r;
  },
  'eqrr' => function($r, $a, $b, $c) {
    $r[$c] = $r[$a] == $r[$b] ? 1 : 0;
    return $r;
  },
];
?>

readFile.php

<?php
$file = fopen("input.txt", "r") or exit("Unable to open file");

while(!feof($file)) {
  $array[] = fgets($file);
}

fclose($file);

return array_filter($array);
?>
 

Part 2 of this one stumped me. I'm posting my code for part 1 here so I don't feel like a total failure, but I'm pretty bummed. I knew that you had to manually step through the instructions or convert them to some sort of higher level thing so that you could see what they were trying to do slowly and shortcut it. But, when I went through all that work and came up with a wrong answer, I looked here. I was thinking that we were summing all of the numbers up until a certain large number, but I was on the wrong track. After looking here at the answer, it seemed like cheating to finish a solution and get the star.

That's one point for you, Advent.

Anyways, here's my code for part 1 in Python:

"""Day 19: Go with the flow

Figure out control flow with time machine opcodes.
"""

from day16_ops import NAMED_OPERATIONS


def execute(instructions, ip_register, initial_registers=None):
    """Executes a bunch of instructions against 6 registers"""
    ip = 0
    if initial_registers is None:
        registers = [0, 0, 0, 0, 0, 0]
    else:
        registers = initial_registers[:]
    while 0 <= ip < len(instructions):
        op, a, b, c = instructions[ip]
        registers[ip_register] = ip
        registers = op(registers, a, b, c)
        ip = registers[ip_register]
        ip += 1
    return registers

def parse_instructions(text):
    """Parses a text file of instructions into actual instructions"""
    lines = text.splitlines()
    ip_register = int(lines[0][-1])
    instructions = []
    for line in lines[1:]:
        op_name, a, b, c = line.split()
        instructions.append([NAMED_OPERATIONS[op_name], int(a), int(b), int(c)])
    return ip_register, instructions


if __name__ == "__main__":
    # Part 1
    with open("python/data/day19.txt", "r") as f:
        puzzle_input = f.read()

    ip_register, instructions = parse_instructions(puzzle_input)
    results = execute(instructions, ip_register)
    print("Value of register 0: ", results[0])

    # Part 2

    # results = execute(instructions, ip_register, [1, 0, 0, 0, 0, 0])
    # print("New value of register 0: ", results[0])
    # TOO SLOW
 

JavaScript solution

I have a generic solution for Part 1 and a customized solution to my input for Part 2.

For Part 2, because it was taking forever, I decided to print the output and let it run for a few minutes and try to understand how the registers vary and why.

Then I followed the suggestions from @jmgimeno and analyzed my program to understand what should happen and what does the loop try to accomplish, and after some deep thoughts I concluded the register 0 is the sum of the dividers of the number in register 2! So I did that algorithm myself, manually.

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

19-common.js

const {
    operations
} = require('./16-common');

const readInput = lines => {
    const ipRegex = /^#ip (?<ipRegister>\d)$/;
    const instructionRegex = /^(?<op>\w+) (?<a>\d+) (?<b>\d+) (?<c>\d+)$/;

    let ipRegister;
    const program = [];
    for (const line of lines) {
        if (ipRegister === undefined) {
            const match = line.match(ipRegex);
            if (match) {
                ipRegister = +match.groups.ipRegister;
            }
        }
        else {
            const match = line.match(instructionRegex);
            if (match) {
                const { op, a, b, c } = match.groups;
                program.push([op, +a, +b, +c]);
            }
        }
    }
    return { ipRegister, program };
};

const runProgram = (ipRegister, program, registers) => {
    const n = program.length;
    let ip = registers[ipRegister];
    let i = 0;
    while (ip >= 0 && ip < n) {
        const instruction = program[ip];
        const op = operations[instruction[0]];
        registers = op(instruction)(registers);
        ip = ++registers[ipRegister];
        i++;
        i % 1000000 === 0 && console.log(`${i}, ${registers.join(',')}`);
    }

    return registers;
};

module.exports = {
    readInput,
    runProgram
};

19a.js

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

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

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

    const result = runProgram(ipRegister, program, [0, 0, 0, 0, 0, 0]);

    console.log(`The state of the registers after executing the test program is ${result}`);
})();

19b.js

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

const analyzeProgram = (ipRegister, program) => {
    for (let i = 0; i < program.length; i++) {
        const [op, a, b, c] = program[i];
        let analysis;
        const target = c === ipRegister ? 'jumps ip to ' : `[${c}] = `;
        if (op === 'addi') { //result[c] = registers[a] + b; 
            analysis = target + `[${a}] + ${b}`;
        }
        else if (op === 'addr') { //result[c] = registers[a] + registers[b]; 
            analysis = target + `[${a}] + [${b}]`;
        } 
        else if (op === 'seti') { //result[c] = a; 
            analysis = target + `${a}`;
        }
        else if (op === 'setr') { //result[c] = registers[a]; 
            analysis = target + `[${a}]`;
        }
        else if (op === 'muli') { //result[c] = registers[a] * b; 
            analysis = target + `[${a}] * ${b}`;
        }
        else if (op === 'mulr') { //result[c] = registers[a] * registers[b]; 
            analysis = target + `[${a}] * [${b}]`;
        } 
        else if (op === 'eqrr') { //result[c] = registers[a] === registers[b] ? 1 : 0;
            analysis = target + `1 if [${a}] === [${b}] or 0 otherwise`;
        } 
        else if (op === 'gtrr') { //result[c] = registers[a] > registers[b] ? 1 : 0; 
            analysis = target + `1 if [${a}] > [${b}] or 0 otherwise`;
        } 
        console.log(`${i}: ${analysis}`);
    }
};

const runOptimizedProgram = () => {
    const number = 10551298;
    let sumDivisors = 0;
    for (let i = 1; i <= number; i++) {
        if (number % i === 0) {
            sumDivisors += i;
        }
    }
    return sumDivisors;
}

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

    //const { ipRegister, program } = readInput(lines);
    //analyzeProgram(ipRegister, program);
    //const result = runProgram(ipRegister, program, [1, 0, 0, 0, 0, 0]);

    const result = runOptimizedProgram();
    console.log(`The state of the registers after executing the test program is ${result}`);
})();
Classic DEV Post from Feb 13

How Do I Start Giving Talks on Coding?

I don't consider myself an expert in just about any aspect of computer science ...

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