re: AoC Day 19: Go With the Flow VIEW POST

VIEW FULL DISCUSSION
 

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

code of conduct - report abuse