Add helper to check solutions and reorder to new layout

5 files changed, 202 insertions, 0 deletions

diff --git a/21/input b/21/input
new file mode 100644
index 0000000..d60c037
--- /dev/null
+++ b/21/input
@@ -0,0 +1,32 @@
+#ip 3

+seti 123 0 1

+bani 1 456 1

+eqri 1 72 1

+addr 1 3 3

+seti 0 0 3

+seti 0 7 1

+bori 1 65536 4

+seti 3798839 3 1

+bani 4 255 5

+addr 1 5 1

+bani 1 16777215 1

+muli 1 65899 1

+bani 1 16777215 1

+gtir 256 4 5

+addr 5 3 3

+addi 3 1 3

+seti 27 6 3

+seti 0 2 5

+addi 5 1 2

+muli 2 256 2

+gtrr 2 4 2

+addr 2 3 3

+addi 3 1 3

+seti 25 3 3

+addi 5 1 5

+seti 17 1 3

+setr 5 6 4

+seti 7 8 3

+eqrr 1 0 5

+addr 5 3 3

+seti 5 6 3

diff --git a/21/part1 b/21/part1
new file mode 100644
index 0000000..0a15881
--- /dev/null
+++ b/21/part1
@@ -0,0 +1,41 @@
+--- Day 21: Chronal Conversion ---
+
+You should have been watching where you were going, because as you wander the new North Pole base,
+you trip and fall into a very deep hole!
+
+Just kidding.  You're falling through time again.
+
+If you keep up your current pace, you should have resolved all of the temporal anomalies by the next
+time the device activates. Since you have very little interest in browsing history in 500-year
+increments for the rest of your life, you need to find a way to get back to your present time.
+
+After a little research, you discover two important facts about the behavior of the device:
+
+First, you discover that the device is hard-wired to always send you back in time in 500-year
+increments. Changing this is probably not feasible.
+
+Second, you discover the activation system (your puzzle input) for the time travel module. 
+Currently, it appears to run forever without halting.
+
+If you can cause the activation system to halt at a specific moment, maybe you can make the device
+send you so far back in time that you cause an integer underflow in time itself and wrap around back
+to your current time!
+
+The device executes the program as specified in manual section one and manual section two.
+
+Your goal is to figure out how the program works and cause it to halt.  You can only control
+register 0; every other register begins at 0 as usual.
+
+Because time travel is a dangerous activity, the activation system begins with a few instructions
+which verify that bitwise AND (via bani) does a numeric operation and not an operation as if the
+inputs were interpreted as strings. If the test fails, it enters an infinite loop re-running the
+test instead of allowing the program to execute normally.  If the test passes, the program
+continues, and assumes that all other bitwise operations (banr, bori, and borr) also interpret their
+inputs as numbers. (Clearly, the Elves who wrote this system were worried that someone might
+introduce a bug while trying to emulate this system with a scripting language.)
+
+What is the lowest non-negative integer value for register 0 that causes the program to halt after
+executing the fewest instructions? (Executing the same instruction multiple times counts as multiple
+instructions executed.)
+
+
diff --git a/21/part2 b/21/part2
new file mode 100644
index 0000000..f2435cb
--- /dev/null
+++ b/21/part2
@@ -0,0 +1,9 @@
+--- Part Two ---
+
+In order to determine the timing window for your underflow exploit, you also need an upper bound:
+
+What is the lowest non-negative integer value for register 0 that causes the program to halt after
+executing the most instructions? (The program must actually halt; running forever does not count as
+halting.)
+
+
diff --git a/21/solve.py b/21/solve.py
new file mode 100644
index 0000000..e2b8fce
--- /dev/null
+++ b/21/solve.py
@@ -0,0 +1,112 @@
+import sys

+sys.path.append("../common")

+import aoc

+from math import sqrt

+

+def parse_command(l):

+    s = l.split(" ")

+    args = [s[0]]

+    args = args + [int(v) for v in s[1:]]

+    return args

+

+data = aoc.data.split("\n")

+

+inspaddr = int(data[0][4:])

+instructs = [parse_command(l) for l in data[1:] if len(l) != 0]

+

+register = [0 for x in range(inspaddr+1)]

+

+opmap = dict()

+opmap["addr"] = lambda a, b : register[a] + register[b]

+opmap["addi"] = lambda a, b : register[a] + b

+opmap["mulr"] = lambda a, b : register[a] * register[b]

+opmap["muli"] = lambda a, b : register[a] * b

+opmap["banr"] = lambda a, b : register[a] & register[b]

+opmap["bani"] = lambda a, b : register[a] & b

+opmap["borr"] = lambda a, b : register[a] | register[b]

+opmap["bori"] = lambda a, b : register[a] | b

+opmap["setr"] = lambda a, b : register[a]

+opmap["seti"] = lambda a, b : a

+opmap["gtir"] = lambda a, b : 1 * (a > register[b])

+opmap["gtri"] = lambda a, b : 1 * (register[a] > b)

+opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b])

+opmap["eqir"] = lambda a, b : 1 * (a == register[b])

+opmap["eqri"] = lambda a, b : 1 * (register[a] == b)

+opmap["eqrr"] = lambda a, b : 1 * (register[a] == register[b])

+

+def varname(v):

+    return "R"+str(v)

+

+dismap = dict()

+dismap["addr"] = lambda a, b : "%s + %s" % (varname(a), varname(b))

+dismap["addi"] = lambda a, b : "%s + %d" % (varname(a), b)

+dismap["mulr"] = lambda a, b : "%s * %s" % (varname(a), varname(b))

+dismap["muli"] = lambda a, b : "%s * %d" % (varname(a), b)

+dismap["banr"] = lambda a, b : "%s & %s" % (varname(a), varname(b))

+dismap["bani"] = lambda a, b : "%s & %d" % (varname(a), b)

+dismap["borr"] = lambda a, b : "%s | %s" % (varname(a), varname(b))

+dismap["bori"] = lambda a, b : "%s | %d" % (varname(a), b)

+dismap["setr"] = lambda a, b : "%s" % (varname(a))

+dismap["seti"] = lambda a, b : "%d" % (a)

+dismap["gtir"] = lambda a, b : "(%d > %s)" % (a, varname(b))

+dismap["gtri"] = lambda a, b : "(%s > %d)" % (varname(a), b)

+dismap["gtrr"] = lambda a, b : "(%s > %s)" % (varname(a), varname(b))

+dismap["eqir"] = lambda a, b : "(%d == %s)" % (a, varname(b))

+dismap["eqri"] = lambda a, b : "(%s == %d)" % (varname(a), b)

+dismap["eqrr"] = lambda a, b : "(%s == %s)" % (varname(a), varname(b))

+

+def disassemble(s, e):

+    for i in range(s, e):

+        ins = instructs[i]

+        aoc.debug(i ,":",varname(ins[3]),"=", dismap[ins[0]](ins[1], ins[2]))

+    aoc.debug()

+

+def execute():

+    global register, insptr

+

+    while register[inspaddr] < len(instructs):

+        insptr = register[inspaddr]

+        ins = instructs[insptr]

+

+        # execute command

+        if len(register) <= ins[3]:

+            register += [0 for x in range(ins[3] - len(register) + 1)]

+        register[ins[3]] = opmap[ins[0]](ins[1], ins[2])

+

+        # part 1

+        #if insptr == 13 and register[4] == 1:

+        #    aoc.debug(register)

+        #    return

+

+        # increment instruction pointer

+        register[inspaddr] += 1

+

+def solve1(args):

+    r0 = 1797184 # (first opportunity for comparison r1 and r0)

+

+    #disassemble(0, len(instructs))

+    #execute()

+

+    return r0

+

+def solve2(args):

+    r1 = 0

+    candidates = list()

+    while True:

+        r4 = r1 | 65536 # flip 9th bit

+        r1 = 3798839

+        while True: # scan bytes of r4 and add them to r1 and multiply

+            r5 = r4 & 255

+            r1 += r5

+            r1 = r1 & 16777215

+            r1 *= 65899  # equals 1 00000001 01101011

+            r1 = r1 & 16777215

+            if r4 < 256:

+                break

+            r4 = int(r4/256) # bit shift 8 to the right

+        if r1 not in candidates:

+            candidates.append(r1)

+        elif r1 == candidates[-1]:

+            return candidates[-1]

+

+aoc.run(solve1, solve2, sols=[1797184, 11011493])

diff --git a/21/test1 b/21/test1
new file mode 100644
index 0000000..d7d2a21
--- /dev/null
+++ b/21/test1
@@ -0,0 +1,8 @@
+#ip 0
+seti 5 0 1
+seti 6 0 2
+addi 0 1 0
+addr 1 2 3
+setr 1 0 0
+seti 8 0 4
+seti 9 0 5