From 87ab487d59fa85dbe2afa55cc841b02805ae42ca Mon Sep 17 00:00:00 2001 From: Louis Burda Date: Fri, 7 Apr 2023 17:18:18 -0400 Subject: Reorder days into src --- src/21/input | 32 ++++++++++++++++ src/21/part1 | 41 +++++++++++++++++++++ src/21/part2 | 27 ++++++++++++++ src/21/solve.py | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/21/test1 | 8 ++++ 5 files changed, 220 insertions(+) create mode 100644 src/21/input create mode 100644 src/21/part1 create mode 100644 src/21/part2 create mode 100644 src/21/solve.py create mode 100644 src/21/test1 (limited to 'src/21') diff --git a/src/21/input b/src/21/input new file mode 100644 index 0000000..d60c037 --- /dev/null +++ b/src/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/src/21/part1 b/src/21/part1 new file mode 100644 index 0000000..679f3ec --- /dev/null +++ b/src/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/src/21/part2 b/src/21/part2 new file mode 100644 index 0000000..192cbb3 --- /dev/null +++ b/src/21/part2 @@ -0,0 +1,27 @@ +--- Part Two --- + +There are many areas the springdroid can't reach. You flip through the manual and discover a way to +increase its sensor range. + +Instead of ending your springcode program with WALK, use RUN. Doing this will enable +extended sensor mode, capable of sensing ground up to nine tiles away. This data is available in +five new read-only registers: + + + - Register E indicates whether there is ground five tiles away. + + - Register F indicates whether there is ground six tiles away. + + - Register G indicates whether there is ground seven tiles away. + + - Register H indicates whether there is ground eight tiles away. + + - Register I indicates whether there is ground nine tiles away. + + +All other functions remain the same. + +Successfully survey the rest of the hull by ending your program with RUN. What amount of hull +damage does the springdroid now report? + + diff --git a/src/21/solve.py b/src/21/solve.py new file mode 100644 index 0000000..e2b8fce --- /dev/null +++ b/src/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/src/21/test1 b/src/21/test1 new file mode 100644 index 0000000..d7d2a21 --- /dev/null +++ b/src/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 -- cgit v1.2.3-71-gd317