My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import math
2import fileinput
3from collections import defaultdict
4
5
6def emulate(instrs, **reg_init):
7 regs = defaultdict(int)
8
9 for k, v in reg_init.items():
10 regs[k] = v
11
12 pc = 0
13
14 while 0 <= pc < len(instrs):
15 op, x, y = instrs[pc]
16 y = regs[y] if y.isalpha() else int(y)
17
18 if op == 'set':
19 regs[x] = y
20 elif op == 'sub':
21 regs[x] -= y
22 elif op == 'mul':
23 regs[x] *= y
24 regs['_muls'] += 1
25 elif op == 'mod':
26 regs[x] %= y
27 elif op == 'sqrt':
28 regs[x] = int(math.sqrt(y)) + 1
29 elif op == 'jnz':
30 if (regs[x] if x.isalpha() else int(x)) != 0:
31 pc += y
32 continue
33
34 pc += 1
35
36 return regs
37
38
39# Read puzzle input
40INSTRS = []
41
42for line in fileinput.input():
43 instr = line.strip() + ' foo'
44 op, x, y = instr.split()[:3]
45 INSTRS.append((op, x, y))
46
47# Part 1
48print "`mul` instruction invocations:", emulate(INSTRS)['_muls']
49
50# Part 2
51#
52# Perform peephole optimizations to speed up execution of Part 2
53# (inspired by https://www.reddit.com/r/adventofcode/comments/7lrjei)
54#
55# Speed up composite check using modulo
56# set e 2 -> set g b
57# set g d -> mod g d
58# mul g e -> jnz g 8
59# sub g b -> set f 0
60# jnz g 2 -> jnz 1 11
61# set f 0 -> nop
62# sub e -1 -> nop
63# set g e -> nop
64# sub g b -> nop
65# jnz g -8 -> nop
66#
67# Only check integers up to sqrt(n)
68# set g d -> sqrt g b
69# sub g b -> sub g d
70
71INSTRS[10] = ['set', 'g', 'b']
72INSTRS[11] = ['mod', 'g', 'd']
73INSTRS[12] = ['jnz', 'g', '8']
74INSTRS[13] = ['set', 'f', '0']
75INSTRS[14] = ['jnz', '1', '11']
76
77INSTRS[21] = ['sqrt', 'g', 'b']
78INSTRS[22] = ['sub', 'g', 'd']
79
80print "Value in register h:", emulate(INSTRS, a=1)['h']