import collections
import functools
import itertools
import math
import os
import re
import sys
from collections import defaultdict, deque
from pathlib import Path
from queue import PriorityQueue
import more_itertools
import numpy as np
import pandas as pd
import scipy
sys.path.insert(1, os.path.join(sys.path[0], ".."))
import utils
from intcode import IntCodeProgram
load = utils.year_load(2019)data = load(1, "np")
(data // 3 - 2).sum()total = 0
data = list(data)
for val in data:
fuel = max(val // 3 - 2, 0)
total += fuel
if fuel:
data.append(fuel)
totalprogram = IntCodeProgram([int(x) for x in load(2)[0].split(",")])
def solve(program, noun=12, verb=2):
program.reset()
program.program[1] = noun
program.program[2] = verb
try:
val = next(program.run())
except StopIteration:
return program.program[0]
solve(program)for noun, verb in itertools.product(range(100), range(100)):
result = solve(program, noun, verb)
if result == 19690720:
result = 100 * noun + verb
break
resultlines = [x.split(",") for x in load(3)]
def path_to_segments(path):
directions = {"U": 1j, "D": -1j, "R": 1, "L": -1}
deltas = [int(p[1:]) * directions[p[0]] for p in path]
ends = np.cumsum(deltas)
lengths = np.cumsum(np.abs(deltas))
result = np.vstack([np.roll(ends, 1), ends, np.roll(lengths, 1)]).T
result[0, 0] = 0
result[0, 2] = 0
return result
def intersection(s1, s2):
if ((s1[1] - s1[0]) * (s2[1] - s2[0])).imag == 0:
return False
if (s1[0] - s1[1]).imag == 0:
s2, s1 = s1, s2
if (s1[0].real - s2[0].real) * (s1[1].real - s2[1].real) < 0 and (
s1[0].imag - s2[0].imag
) * (s1[1].imag - s2[1].imag) < 0:
intersection_point = s1[0].real + 1j * s2[0].imag
total_length = (
s1[2]
+ s2[2]
+ abs((s1[0] - intersection_point).imag)
+ abs((s2[0] - intersection_point).real)
)
return intersection_point, total_length
return False
l1 = path_to_segments(lines[0])
l2 = path_to_segments(lines[1])
intersections = [
i for s1, s2 in itertools.product(l1, l2) if (i := intersection(s1, s2))
]
int(min(abs(x[0].real) + abs(x[0].imag) for x in intersections))min(x[1] for x in intersections)As a bonus, we can visualize the walk through space
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_theme()
def plot_path(segments, **kwargs):
x = segments[:, 0].real
y = segments[:, 0].imag
plt.plot(x, y, **kwargs)
plot_path(l1)
plot_path(l2)
ax = plt.gca()
# plt.savefig("../graphs/2019-3.png", bbox_inches="tight")
low = 231832
high = 767346
total = 0
for i in range(low, high + 1):
s = str(i)
if list(s) == sorted(s):
for digit in "0123456789":
if s.count(digit) > 1:
total += 1
break
totaltotal = 0
for i in range(low, high + 1):
s = str(i)
if list(s) == sorted(s):
if (s[0] == s[1] != s[2]) or (s[-1] == s[-2] != s[-3]):
total += 1
continue
for idx in range(1, len(s) - 2):
if s[idx - 1] != s[idx] == s[idx + 1] != s[idx + 2]:
total += 1
break
totalprogram = IntCodeProgram(load(5, "np"), inputs=[1])
list(program.run())[-1]program.reset()
program.inputs = [5]
next(program.run())We construct the DAG as a dictionary, where graph[node] corresponds to node.parent.
data = load(6)
graph = {child: parent for parent, child in map(lambda x: x.split(")"), data)}
@functools.cache
def count_orbits(node):
if node == "COM":
return 0, ()
previous = count_orbits(graph[node])
return previous[0] + 1, (graph[node],) + previous[1]
sum(count_orbits(x)[0] for x in graph)Moving from orbit A to orbit B can be accomplished by moving to the last common ancestor of each node, and then switching branches. And that’s the same as getting the full ancestry of both nodes, minus anything they might have in common.
_, p1 = count_orbits("YOU")
_, p2 = count_orbits("SAN")
len(set(p1) ^ set(p2))opcodes = load(7, "np")
program = IntCodeProgram(opcodes)
results = []
for input_sequence in itertools.permutations(range(5)):
val = 0
for item in input_sequence:
program.reset()
program.inputs = [item, val]
val = next(program.run())
results.append(val)
max(results)results = []
for seq in itertools.permutations(range(5, 10)):
inputs = [[x] for x in seq]
inputs[0].append(0)
iterators = [IntCodeProgram(opcodes, inputs=inputs[i]).run() for i in range(5)]
i = 0
while True:
try:
val = next(iterators[i % 5])
inputs[(i + 1) % 5].append(val)
i += 1
except StopIteration:
break
results.append(val)
max(results)data = load(8)[0]
result = []
for i in range(len(data) // (25 * 6))[::-1]:
substring = data[25 * 6 * i : 25 * 6 * (i + 1)]
result.append((substring.count("0"), substring.count("1") * substring.count("2")))
min(result)[1]result = list("1" * 25 * 6)
for i in range(len(data) // (25 * 6))[::-1]:
substring = data[25 * 6 * i : 25 * 6 * (i + 1)]
result = [bottom if top == "2" else top for top, bottom in zip(substring, result)]
print(
"\n".join(
[
"".join(["█" if char != "0" else " " for char in line])
for line in np.array(result).reshape(6, 25)
]
)
)Adding the required functionality to the intcode compiler wasn’t too tricky. Opcodes which set values had to be modified a bit to account for the offset, but that was more or less it.
Allowing arbitrary final addresses was accomplished by the very dirty hack of changing the program type in this problem from a list to defaultdict(int). If it works, it works.
program = IntCodeProgram(load(9, "np"))
program.inputs = [1]
next(program.run())program.reset()
program.inputs = [2]
next(program.run())from math import gcd
def simplify(x, y):
if (x, y) == (0, 0):
return 0, 0
factor = gcd(x, y)
return int(x / factor), int(y / factor)
data = np.array(
[[0 if char == "." else 1 for char in line] for line in load(10)]
).T
ones = np.array(np.where(data)).T
scores = [
len(set(map(lambda x: simplify(*x), ones - ones[i]))) for i in range(len(ones))
]
position = ones[np.argmax(scores)]
print(max(scores) - 1)
print(position)There are more than 200 visible asteroids, so we only need to worry about the ones we meet on the first round - but that’s exactly the simplified asteroids, as seen from our position. We take these, and sort them according to the angle they make with the negative y axis (negative because we have y increasing as it goes down in this coordinate system). The one we’re interested in is the 201st asteroid according to this order (201st because the one we’re measuring from will automatically have an angle of zero and should not be counted)
(
np.array(
sorted(
set([simplify(*x) for x in ones - position]),
key=lambda x: (np.arctan2(x[0], -x[1])) % (2 * np.pi),
)[200]
)
+ position
)program = IntCodeProgram(load(11, "np"))
def solve(startval):
position, direction = 0 + 0j, 1j
program.reset()
field = defaultdict(int)
count = 0
program.inputs = [startval]
painted = set()
for colour, turn in more_itertools.chunked(program.run(), 2):
field[position] = colour
painted.add(position)
direction = direction * (1j * (1 - 2 * turn))
position += direction
program.inputs.append(field[position])
return painted, field
len(solve(0)[0])_, field = solve(1)
ones = np.array([x for x in field.keys() if field[x]])
offset = ones.real.min() + 1j * ones.imag.min()
ones = ones - offset
field = np.zeros((int(ones.real.max()) + 1, int(ones.imag.max()) + 1))
for value in ones:
field[int(value.real), int(value.imag)] = 1
print(
"\n".join(
["".join(["█" if char else " " for char in line]) for line in np.rot90(field)]
)
)data = load(12, "int")
positions = np.array(data, dtype=int)
velocities = np.zeros(positions.shape, dtype=int)
indices = [0, 1, 2, 3]
for i in range(1000):
for m1, m2 in itertools.combinations([0, 1, 2, 3], 2):
dv = 1 * (positions[m2] > positions[m1]) - 1 * (positions[m2] < positions[m1])
velocities[m1] += dv
velocities[m2] -= dv
positions += velocities
(np.abs(positions).sum(axis=1) * np.abs(velocities).sum(axis=1)).sum()I don’t know what optimizations are possible here, but an obvious one is to realise that the three different directions (x,y and z) are completely independent, and that instead of searching for one global cycle, we can ask if there are shorter cycles for the coordinates separately. The global cycle length is then the lcm of the individual cycle lengths, as long as each cycle starts at the initial state.
data = load(12, "int")
positions = np.array(data, dtype=int)
velocities = np.zeros(positions.shape, dtype=int)
seen_x = {}
seen_y = {}
seen_z = {}
for axis, seen in zip([0, 1, 2], [seen_x, seen_y, seen_z]):
seen[tuple(np.hstack([positions[:, axis], velocities[:, axis]]))] = 0
cycles = [False, False, False]
for i in range(1_000_000):
for m1, m2 in itertools.combinations([0, 1, 2, 3], 2):
dv = 1 * (positions[m2] > positions[m1]) - 1 * (positions[m2] < positions[m1])
velocities[m1] += dv
velocities[m2] -= dv
positions += velocities
for axis, seen in zip([0, 1, 2], [seen_x, seen_y, seen_z]):
if cycles[axis]:
continue
state = tuple(np.hstack([positions[:, axis], velocities[:, axis]]))
if state in seen:
cycles[axis] = i + 1
if all(cycles):
break
math.lcm(*cycles)program = IntCodeProgram(load(13, "np"))
tiles = set()
for x, y, kind in more_itertools.chunked(program.run(), 3):
if kind == 2:
tiles.add((x, y))
len(tiles)program.set(0, 2)
ball, paddle = 0, 0
result = 0
def ai():
global ball
global paddle
return (ball > paddle) - (ball < paddle)
program.set_input(ai)
values = more_itertools.chunked(program.run(), 3)
for x, y, kind in values:
result = result if (x != -1) else kind
paddle = paddle if (kind != 3) else x
ball = ball if (kind != 4) else x
resultgraph = {}
for line in load(14):
inputs, output = line.split(" => ")
output_amount, output_resource = output.split()
output_amount = int(output_amount)
inputs = [pair.split() for pair in inputs.split(", ")]
graph[output_resource] = (
output_amount,
[x[1] for x in inputs],
[int(x[0]) for x in inputs],
)
def topological_sort(graph):
if not graph:
return []
dependencies = functools.reduce(lambda x, y: x | set(y[1]), graph.values(), set())
ready = []
for key in graph:
if key not in dependencies:
ready.append(key)
assert ready
new_graph = {k: v for k, v in graph.items() if k not in ready}
return ready + topological_sort(new_graph)
def part1(n):
order = topological_sort(graph)
requirements = defaultdict(int)
requirements["FUEL"] = n
for resource in order:
production, kinds, amounts = graph[resource]
if resource in requirements:
n = int(np.ceil(requirements[resource] / production))
for kind, amount in zip(kinds, amounts):
requirements[kind] += n * amount
del requirements[resource]
return requirements["ORE"]
part1(1)We need to somehow reverse the relationship we found above. There are probably smarter ways of doing things, but a binary search works fine:
target = 1_000_000_000_000
lower_limit = target // part1(1)
upper_limit = lower_limit * 2
while part1(upper_limit) < target:
lower_limit *= 2
upper_limit *= 2
while (upper_limit - lower_limit) != 1:
midpoint = int((upper_limit + lower_limit) / 2)
if part1(midpoint) > target:
upper_limit = midpoint
else:
lower_limit = midpoint
lower_limitI really liked this puzzle! The approach I took is to first map out the entire area by giving the droid the necessary instructions, and then using a path finding algorithm to get from start to finish.
program = IntCodeProgram(load(15, "np"))
f = program.run()
directions = {1: 1j, 2: -1j, 3: -1, 4: 1}
reverse_directions = {v: k for k, v in directions.items()}
def neighbors(state, edges=None):
if edges is None:
return []
return [state + directions[neighbor] for neighbor in edges[state]]
def update(steps, state, neighbor):
return steps + [reverse_directions[neighbor - state]]
queue = deque([(0, 0)])
old_position = 0
visited = set()
edges = defaultdict(set)
i = 0
while queue:
i += 1
steps, position = queue.popleft()
visited.add(position)
instructions = utils.bfs(old_position, position, neighbors, [], update, edges=edges)
program.set_input(instructions)
while program.state != 1:
_ = next(f)
for direction in directions:
new_position = position + directions[direction]
opposite_direction = direction + 2 * (direction % 2) - 1
program.set_input([direction])
val = next(f)
if val == 0:
continue
program.set_input([opposite_direction])
_ = next(f)
edges[position].add(direction)
edges[new_position].add(opposite_direction)
if val == 2:
target = new_position
if new_position not in visited:
# append left to make it a dfs, so that the droid doesn't have to
# run from one side of the board to the other all the time
queue.appendleft((steps + 1, new_position))
old_position = position
utils.bfs(0, target, neighbors, edges=edges)We mapped out the whole area for part 1, so part 2 is just a bfs with no stopping condition
utils.bfs(target, None, neighbors, edges=edges)For the first part all the numbers are small, so we don’t need to be particularly clever
initial_data = [int(x) for x in load(16)[0]]
data = initial_data.copy()
base_pattern = np.array([0, 1, 0, -1])
factors = []
for i in range(1, len(data) + 1):
pattern = base_pattern.repeat(i)
repeats = int(np.ceil((len(data) + 1) / len(pattern)))
factors.append(np.tile(pattern, repeats)[1 : len(data) + 1])
factors = np.array(factors)
for i in range(100):
data = abs(factors @ data) % 10
print(*data[:8], sep="", end="\n")For part 2, the numbers get so big that this approach is impossible (just the transition matrix has \(\textrm{len(data)}^2 \times10^8\) elements, so that’s not going to work).
The first optimization we can make is to realise that calculating the \(k\)-th from last digit of the output only requires knowledge of the last \(k\) digits of the input. So the last digit is always unchanged, the last-but-one digit is always the sum of the previous last two digits etc.
In fact, we can explicitly solve this reccurrence for the second half of the input data, and looking at the data provided, that’s where the relevant digits are located! Denoting the \(k\)-th digit from the end after the \(n\)-th iteration as \(d_k^n\), we can verify that
\[\begin{align*} d^n_0 &= d^{n-1}_0 = \ldots = d^0_0 \\ d^n_1 &= d^{n-1}_1 + (d^{n-1}_0) = d^0_1 + nd^0_0 \\ d^n_2 &= d^{n-1}_2 + (d^{n-1}_1 + d^{n-1}_0) = d^0_2 + nd^0_1 + \frac12n(n+1)d^0_0 \\ \end{align*}\]Explicitly solving the recurrences for all the digits in the second half is certainly possible, but it’s going to be very tedious. Instead, we can notice that the middle expression is always \(d^{n-1}_k + d^n_{k -1}\) . That means that to calculate \(d^{100}_k\) we only need to know \(d^0_k\) and \(d^1_{k-1}, d^2_{k-1}, \ldots, d^{100}_{k-1}\), which translates to the following short routine:
active = 101 * [0]
results = []
index = functools.reduce(lambda x, y: 10 * x + y, initial_data[:7])
data = np.tile(initial_data, 10_000)
counter_index = len(data) - index
for i in range(counter_index):
active[0] = data[-1 - i]
active = np.cumsum(active) % 10
results.append(active[-1])
functools.reduce(lambda x, y: 10 * x + y, results[::-1][:8])opcodes = load(17, "np")
program = IntCodeProgram(opcodes)
data = "".join(chr(val) for val in program.run()).split("\n")[:-2]
board = np.array([[1 if char == "#" else 0 for char in line] for line in data])
neighbors = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
intersections = np.where(
(scipy.ndimage.convolve(board, neighbors, mode="constant") > 2) & board
)
np.product(intersections, axis=0).sum()For this one I solved the path by hand, and then ran the input through the black box program to get the actual output.
A = "R,6,L,12,R,6"
B = "L,12,R,6,L,8,L,12"
C = "R,12,L,10,L,10"
main = "A,A,B,C,B,C,B,C,B,A"
show_output = "n\n"
program_input = "\n".join(x for x in [main, A, B, C, show_output])
encoded_input = [ord(x) for x in program_input]
program.set(0, 2)
program.set_input(encoded_input)
[x for x in program.run()][-1]The maze we are looking at is fairly large, but it only has a few interesting points. Most of the maze is corridors of width 1; and on these stretches there are no choices about where to go, since backtracking is not an option. Instead of working with the grid we are given, we can extract the points of interest, and store the distance from each point to its neighbors.
The points of interest are:
The numbers here are barely small enough that the straightforward approach works: A BFS with a different visited list for each possible set of collected keys. To slightly improve the runtime, we’ll start by eliminating dead ends so the BFS never has to consider them.
data = np.array([[ord(c) for c in line] for line in load(18)])
indices = np.where(data == ord("@"))
start = list(zip(*indices))[0]
wall = ord("#")
free = ord(".")
data[indices] = free
window = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
walls = (data == wall) * 1
walls
s = 1
while s > 0:
walls = (data == wall) * 1
dead_ends = (scipy.ndimage.convolve(walls, window, mode="constant") > 2) & (
(data == free) | ((data >= ord("A")) & (data <= ord("Z")))
)
s = dead_ends.sum()
data[dead_ends] = wall
nw = 1 * (data != wall)
junctions = (scipy.ndimage.convolve(nw, window, mode="constant") > 2) & nw
data[np.where(junctions)] = ord("9")
queue = deque()
connections = defaultdict(dict)
painted = {}
width = data.shape[1]
def label(position):
if data[position] == ord("9"):
return str(position[0] * width + position[1])
else:
return chr(data[position])
# print(*["".join(chr(x) for x in line) for line in data], sep="\n")
for start in list(zip(*np.where(data > max(free, wall)))):
queue.append((0, start, start))
while queue:
steps, position, origin = queue.popleft()
if position in painted:
other, other_steps = painted[position]
if other != origin:
s = steps + other_steps
connections[label(other)][label(origin)] = s
connections[label(origin)][label(other)] = s
continue
painted[position] = origin, steps
y, x = position
for neighbor in [(y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)]:
if data[neighbor] == wall:
continue
queue.append((steps + 1, neighbor, origin))
state = frozenset()
start = 0, label((40, 40)), state
q = PriorityQueue()
q.put(start)
visited = defaultdict(set)
while q.qsize() > 0:
steps, l, state = q.get()
if len(state) == 26:
break
if l in visited[state]:
continue
visited[state].add(l)
for neighbor in connections[l]:
new_state = state.copy()
if neighbor in visited[state]:
continue
elif "A" <= neighbor <= "Z" and neighbor.lower() not in state:
continue
elif "a" <= neighbor <= "z":
new_state = state | frozenset(neighbor)
s = steps + connections[l][neighbor]
q.put((s, neighbor, new_state))
stepsFor part 2 we need to keep track of four different robots, which increases the number of neighbors available at each stage. However, direct inspection of the graph of the problem for this specific input reveals that the robots are never waiting for each other, so the shortest amount of steps is just the sum of the individual shortest steps to clear each subgraph. It feels a bit cheesy to completely ignore the doors in the puzzle, but it works here.
x = 40
starts = [(x - 1, x - 1), (x - 1, x + 1), (x + 1, x - 1), (x + 1, x + 1)]
dead_positions = [(x - 1, x), (x, x - 1), (x, x), (x, x + 1), (x + 1, x)]
dead_labels = [label(_) for _ in dead_positions]
part2 = {
k: {p: q for p, q in v.items() if p not in dead_labels}
for k, v in connections.items()
if k not in dead_labels
}
total = 0
for start in map(label, starts):
nodes = deque([start])
seen = set()
while nodes:
current = nodes.popleft()
if current in seen:
continue
seen.add(current)
for neighbor in part2[current]:
if neighbor not in seen:
nodes.append(neighbor)
targets = [x for x in seen if "a" <= x <= "z"]
state = frozenset()
q = PriorityQueue()
q.put((0, start, state))
visited = defaultdict(set)
while q.qsize() > 0:
steps, position, state = q.get()
if len(state) == len(targets):
break
if position in visited[state]:
continue
visited[state].add(position)
for neighbor in part2[position]:
new_state = state.copy()
if neighbor in visited[state]:
continue
if neighbor in targets:
new_state = state | frozenset(neighbor)
q.put((steps + part2[position][neighbor], neighbor, new_state))
total += steps
totalopcodes = load(19, "np")
program = IntCodeProgram(opcodes)
inputs = []
program.set_input(inputs)
size = 50
board = np.zeros((size, size), dtype=int)
for i in range(size):
for j in range(size):
program.reset()
inputs += [j, i]
board[i, j] = next(program.run())
board.sum()top_edge = []
bottom_edge = []
current_top = 0
current_bottom = 0
for j in range(1000):
bottom_val = 1
top_val = 0
current_top -= 1
while top_val == 0 and current_top <= 2 * j:
current_top += 1
program.reset()
program.set_input([j, current_top])
top_val = next(program.run())
if not top_val:
current_top = 0
if not current_bottom:
current_bottom = current_top
while bottom_val == 1:
current_bottom += 1
program.reset()
program.set_input([j, current_bottom])
bottom_val = next(program.run())
top_edge.append(current_top)
bottom_edge.append(current_bottom - 1)
axis = np.arange(len(bottom_edge))
top_slope = np.polyfit(axis, top_edge, 1)[0]
w = 99
dy = (top_slope + 1) * w
x = (np.array(bottom_edge) - np.array(top_edge) >= dy).argmax()
y = bottom_edge[x] - w
while top_edge[x + w] <= (bottom_edge[x] - w):
x -= 1
y = bottom_edge[x] - w
x += 1
y = bottom_edge[x] - w
10000 * x + yThis can be done with a fairly simple BFS. The only added difficulty is that we need some way of specifying that two portals of the same letter neighbor each other.
In terms of the number of lines, that’s what most of the following code is doing.
data = np.array([[ord(char) for char in line[:-1]] for line in load(20)], dtype=int)
portals = ((ord("A") <= data) & (data <= ord("Z"))) * 1
def label(item):
if isinstance(item, str):
item = np.array([ord(x) for x in item])
return functools.reduce(lambda x, y: -(26 * x + y), item - ord("A") + 1)
ymax, xmax = data.shape
verticals = np.where(scipy.ndimage.correlate(portals, [[1], [1]], mode="constant") == 2)
horizontals = np.where(scipy.ndimage.correlate(portals, [[1, 1]], mode="constant") == 2)
def vertical_neighbors(y, x):
return [
[y - 2, x],
[y - 1, x - 1],
[y - 1, x + 1],
[y, x - 1],
[y, x + 1],
[y + 1, x],
]
def horizontal_neighbors(y, x):
return [
[y, x - 2],
[y - 1, x - 1],
[y + 1, x - 1],
[y - 1, x],
[y + 1, x],
[y, x + 1],
]
def horizontal_window(y, x):
return np.array((y, y)), np.array((x - 1, x))
def vertical_window(y, x):
return np.array((y - 1, y)), np.array((x, x))
for portals, neighbors, window in zip(
[verticals, horizontals],
[vertical_neighbors, horizontal_neighbors],
[vertical_window, horizontal_window],
):
for portal in sorted(zip(*portals)):
w = window(*portal)
n = [
i for i in neighbors(*portal) if data[i[0] % ymax, i[1] % xmax] == ord(".")
][0]
data[tuple(n)] = label(data[w])
data[w] = ord("#")
start = next(zip(*np.where(data == label("AA"))))
destination = next(zip(*np.where(data == label("ZZ"))))
paths = deque([(start, 0)])
seen = set()
while paths:
(y, x), distance = paths.popleft()
if (y, x) in seen:
continue
if (y, x) == destination:
break
seen.add((y, x))
neighbors = [
c
for c in [(y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)]
if (data[c] == ord(".")) or data[c] < 0
]
if data[y, x] < 0:
neighbors += sorted(zip(*np.where(data == data[y, x])))
for neighbor in neighbors:
if neighbor in seen:
continue
paths.append((neighbor, distance + 1))
distanceFor part 2, we basically just need to add a level coordinate to our state, and change the way we enumerate neighbors to account for the fact that moving through a portal changes the levels
level_change = defaultdict(lambda: 1)
portals = np.where(data < 0)
for y, x in zip(*portals):
if x == 2 or y == 2 or x == xmax - 3 or y == ymax - 3:
level_change[y, x] = -1
start = next(zip(*np.where(data == label("AA")))) + (0,)
destination = next(zip(*np.where(data == label("ZZ")))) + (0,)
paths = deque([(start, 0)])
seen = set()
while paths:
(y, x, level), distance = paths.popleft()
if (y, x, level) in seen:
continue
if (y, x, level) == destination:
break
seen.add((y, x, level))
neighbors = [
c + (level,)
for c in [(y - 1, x), (y, x - 1), (y, x + 1), (y + 1, x)]
if (data[c] == ord(".")) or data[c] < 0
]
if data[y, x] < 0:
new_level = level + level_change[y, x]
if new_level >= 0:
other_neighbors = set(zip(*np.where(data == data[y, x]))) - set([(y, x)])
for neighbor in other_neighbors:
neighbors += [neighbor + (new_level,)]
for neighbor in neighbors:
if neighbor in seen:
continue
paths.append((neighbor, distance + 1))
distancePart 1 is possible to brute force, even if a bit of thought is needed to do it. With 3 different commands available, with six options for their first argument and 2 for their second, there are are 36 possible SPRINGSCRIPT instructions; each program is a max of 15 instructions, so there are more than \(2\times10^{23}\) possible programs. That’s not the right way to go.
On the other hand, there are only four inputs at any given stage, so there are only 16 distinct inputs to our assignments. The program we have to supply is just a way of mapping each input to either 0 or 1, and there are only \(2^{16}\) of those.
Additionally, we are told that jumping when there is a hole 4 tiles away will result in automatic loss, since that’s how far we jump. Similarly, not jumping when there is a hole right in front of us will result in a loss. So any valid rule has to have the following structure (0 as input is hole, 1 is ground; 0 as output is don’t jump, 1 is jump)
(this reveals that the input 0BC0 is an automatic loss)
That also means that for anything else we can assume A = 1 and D = 1, since otherwise the output is fixed. So really we just have to map the four BC states. That means there are only 16 possible programs, so we can enumerate them all. Especially since 8 of them are mirrors of the other 8.
springscript_programs = [
[],
["NOT B T", "NOT C J", "OR T J", "NOT J J"],
["NOT C J", "AND B J"],
["NOT B J", "NOT J J"],
["NOT B J", "AND C J"],
["NOT C J", "NOT J J"],
["NOT B J", "AND C J", "NOT C T", "AND B T", "OR T J"],
["NOT B T", "NOT C J", "AND T J", "NOT J J"],
]
def invert(program):
try:
if program[-1] == "NOT J J":
return program[:-1]
except:
pass
return program + ["NOT J J"]
footer = ["NOT A T", "OR T J", "AND D J", "WALK"]
springscript_programs += [invert(p) for p in springscript_programs]
springscript_programs = [p + footer for p in springscript_programs]
encoded = [
[ord(char) for char in "\n".join(program) + "\n"]
for program in springscript_programs
]
program = IntCodeProgram(load(21, "np"))
for p in springscript_programs:
encoded_program = [ord(char) for char in "\n".join(p) + "\n"]
program.reset()
program.set_input(encoded_program)
for value in program.run():
if value > 255:
break
else:
continue
break
valueWell.
For part 2 we get five more registers, for a total of 7 that are allowed to vary state. That makes 128 possible inputs, and \(\approx10^{38}\) possible mappings. The total number of 15-line springscript programs is only \(\left(3\times11\times2\right)^{15} \approx 2\times10^{27}\), so a different approach is going to be needed
Some thoughts:
springscript_program = [
"NOT B J",
"NOT C T",
"OR T J",
"AND D J", # if d is ground and there's a hole at B or C, we can jump to D
"AND H J", # but only if H is also ground
"NOT A T", # if next tile is a hole we have to jump
"OR T J",
"RUN",
]
encoded_program = [ord(char) for char in "\n".join(springscript_program) + "\n"]
program.reset()
program.set_input(encoded_program)
for value in program.run():
if value > 255:
break
print(chr(value), end="")
valueWe are asked to follow how a single number moves - the one initally at position 2019. So if we build the operations so that they take an old position and return the new position, we can completely avoid dealing with the rest of the array.
instructions = [str.split(x) for x in load(22)]
lookup = {"cut": 1, "deal": 2}
instructions = [
(0,)
if instruction[-1] == "stack"
else (lookup[instruction[0]], int(instruction[-1]))
for instruction in instructions
]
l = 10007
p = 2019
for instruction in instructions:
if instruction[0] == 0:
p = (l - p - 1) % l
elif instruction[0] == 1:
p = (p - instruction[1]) % l
else:
p = (p * instruction[1]) % l
pTo nobody’s great surprise, part 2 ups the difficulty significantly, with the usual trick of increasing the numbers of cards and rounds significantly.
Additionally, since we’re tracking what card ends up at a given spot rather than what spot a given card ends up at, we’ll need to reverse the operations defined above, and apply them in reverse order. For the first two that’s not a big issue, since the reversal is trivial. For the last one, we’ll need a way to find multiplicative inverses in the modular group. We’ll use the extended euclidean algorithm for that; it’s already implemented in the utils file.
Even with those optimizations, doing as many rounds as required isn’t possible. Instead, we can realise that each of the three operations on the position is linear, and therefore so is their composition. That means that we can model the result of each round as
\(p \rightarrow ap + b \qquad \mod l\)
for some constants a and b. We can find these constants, and thus reduce the work needed for each round to calculating a multiplication, an addition and a remainder; making each round much faster.
The number of rounds is still prohibitive if we’re stuck doing them one at a time, but once we know the coefficients for doing one round, we can easily find the coefficients for doing 2 rounds. That lets us use a multiplication by squaring approach to getting the answer.
l = 119315717514047
state = (1, 0)
for instruction in instructions[::-1]:
if instruction[0] == 0:
state = -state[0], l - state[1] - 1
elif instruction[0] == 1:
state = state[0], state[1] + instruction[1]
else:
state = [x * inverses[instruction[1]] for x in state]
state = [x % l for x in state]
def compose(c1, c2):
return (c1[0] * c2[0]) % l, (c2[0] * c1[1] + c2[1]) % l
p = 2020
i = 101741582076661
while i:
if i % 2:
p = (p * state[0] + state[1]) % l
i -= 1
else:
state = compose(state, state)
i = i >> 1
pdata = load(23, "np")
bus = [[x] for x in list(range(50))]
programs = []
for i in range(50):
program = IntCodeProgram(data, inputs=bus[i])
programs.append(program)
idx = 0
done = False
while True:
program = programs[idx]
values = program.run()
outputs = []
count = 0
for value in values:
if value == 255 and (count % 3) == 0:
done = True
break
if program.state == 1:
bus[idx].append(-1)
break
outputs += [value]
if done:
x = next(values)
y = next(values)
break
for destination, x, y in more_itertools.chunked(outputs, 3):
bus[destination] += [x, y]
idx = (idx + 1) % 50 if not outputs else destination
ydata = load(23, "np")
bus = [[x] for x in list(range(50))]
programs = []
for i in range(50):
program = IntCodeProgram(data, inputs=bus[i])
programs.append(program)
idx = 0
done = False
def is_idle(bus):
return all(i == [-1] for i in bus)
nat = [x, y]
old_y = -1
while True:
if is_idle(bus):
if nat[1] == old_y:
break
new_input = nat.copy()
bus[0] = new_input
programs[0].set_input(new_input)
old_y = nat[1]
idx = 0
program = programs[idx]
values = program.run()
outputs = []
for value in values:
if program.state == 1:
bus[idx].append(-1)
break
outputs += [value]
for destination, x, y in more_itertools.chunked(outputs, 3):
if destination == 255:
nat = [x, y]
else:
bus[destination] += [x, y]
idx = (idx + 1) % 50
old_yinitial_state = np.array(
[[0 if char == "." else 1 for char in line] for line in load(24)]
)
state = initial_state.copy()
weights = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
seen = {}
while tuple(state.ravel()) not in seen:
seen[tuple(state.ravel())] = True
bugs = scipy.ndimage.convolve(state, weights, mode="constant")
changes = bugs != 1
empty = np.where(state == 0)
changes[empty] = ((bugs == 1) | (bugs == 2))[empty]
state = (state + changes) % 2
x = state.ravel()
(x * (2 ** np.arange(len(x)))).sum()For part 2, we need to figure out how to account for the different levels and how to account for the new neighbors.
We’ll add the different recursion levels as a new first axis in our array, and we know that it takes at least two steps before an initially empty layer can affect it’s neighbor: one to reach the layer, and one to spread to the edge/centre of the layer. That means that instead of expanding the first axis at every step, we can precompute how many we’ll need and fill with zeros.
We can get the in-plane neighbors exactly as before, and after far too much thought, we can get the new neighbors with some clever numpy indexing. This could possibly be shortened even further, but tbh it’s concise enough as it is.
length = 200
state = np.zeros((length + 3, *initial_state.shape), dtype=int)
state[int(length // 2) + 1] = initial_state
for i in range(length):
neighbors = scipy.ndimage.convolve(state, [weights], mode="constant")
neighbors[:, (0, -1), :] += np.roll(state[:, (1, 3), 2], 1, axis=0)[:, :, None]
neighbors[:, :, (0, -1)] += np.roll(state[:, 2, (1, 3)], 1, axis=0)[:, None, :]
neighbors[:, (1, 3), 2] += np.roll(state[:, (0, -1), :], -1, axis=0).sum(axis=2)
neighbors[:, 2, (1, 3)] += np.roll(state[:, :, (0, -1)], -1, axis=0).sum(axis=1)
changes = neighbors != 1
empty = np.where(state == 0)
changes[empty] = ((neighbors == 1) | (neighbors == 2))[empty]
state = (state + changes) % 2
state[:, 2, 2] = 0
state.sum()program = IntCodeProgram(load(25, "np"), inputs=[])
def run():
for char in program.run():
if program.state != 1:
print(chr(char), end="")
else:
s = input().strip()
program.inputs += [ord(x) for x in s + "\n"]