import collections
import functools
import itertools
import os
import re
import sys
from collections import defaultdict
from pathlib import Path
import more_itertools
import numpy as np
import pandas as pd
sys.path.insert(1, os.path.join(sys.path[0], ".."))
import utils
load = utils.year_load(2017)data = np.array([int(x) for x in load(1)[0]], dtype=int)
data[np.where(data == np.roll(data, 1))].sum()data[np.where(data == np.roll(data, len(data) // 2))].sum()data = [sorted(map(lambda x: int(x), x.split())) for x in load(2)]
sum(a[-1] - a[0] for a in data)total = 0
for line in data:
for idx, value in enumerate(line):
for j in range(idx + 1, len(line)):
total += line[j] // value if line[j] % value == 0 else 0
totalpuzzle_input = 368078
completed_squares = (int(np.sqrt(puzzle_input) - 1) // 2 * 2) + 1
remainder = (puzzle_input - completed_squares**2) % (completed_squares + 1)
(completed_squares // 2 + 1) + abs((completed_squares // 2) + 1 - remainder)coord, current_side, side_length, remainder = 0, 0, 0, 0
spiral = defaultdict(int)
spiral[coord] = 1
direction = 1
while True:
if remainder == side_length:
if current_side % 4 == 0:
coord = coord + direction - 1j * direction
side_length += 2
direction = 1j * direction
coord = coord + direction
current_side += 1
remainder = 1
else:
coord = coord + direction
remainder += 1
tmp = 0
for x, y in itertools.product([-1, 0, 1], [-1j, 0, 1j]):
if not x and not y:
continue
target = coord + x + y
tmp += spiral[target]
if tmp > puzzle_input:
break
spiral[coord] = tmp
tmplines = [x.split() for x in load(4)]
sum(len(l) == len(set(l)) for l in lines)sum(len(l) == len(set(["".join(sorted(w)) for w in l])) for l in lines)instructions = load(5, "np")
ip, count = 0, 0
while ip >= 0 and ip < len(instructions):
instructions[ip] += 1
ip += instructions[ip] - 1
count += 1
countinstructions = load(5, "np")
ip, count = 0, 0
while ip >= 0 and ip < len(instructions):
instruction = instructions[ip]
instructions[ip] += 1 if instruction < 3 else -1
ip += instruction
count += 1
countdata = np.array([0, 5, 10, 0, 11, 14, 13, 4, 11, 8, 8, 7, 1, 4, 12, 11])
l = len(data)
seen = {}
i = 0
def step(data):
idx, maxval = data.argmax(), data.max()
data[idx] = 0
delta = np.ones(len(data), dtype=int) * (maxval // l)
delta[: maxval % l] += 1
data += np.roll(delta, idx + 1)
return data
while tuple(data) not in seen:
seen[tuple(data)] = i
data = step(data)
i += 1
iI was getting the wrong answer for this for the longest time until I realised Iād left off a ā0ā at the start of my input when I copied it over.
This was made trivial by tracking when a given configuration was seen.
i - seen[(tuple(data))]tree = {}
for line in load(7):
name = line.split(" ")[0]
children = line.split(" -> ")[1].split(", ") if " -> " in line else []
weight = int(re.findall("\d+", line)[0])
tree[name] = {"weight": weight, "children": children}
parents = {}
for node in tree:
for child in tree[node]["children"]:
parents[child] = node
node = (set(tree.keys()) - set(parents.keys())).pop()
nodedef weight(node):
return tree[node]["weight"] + sum(map(weight, tree[node]["children"]))
def is_balanced(node):
return (
not tree[node]["children"] or len(set(map(weight, tree[node]["children"]))) == 1
)
while not is_balanced(node):
weights = [weight(x) for x in tree[node]["children"]]
counts = collections.Counter(weights)
wrong_weight = min(counts, key=counts.get)
node = tree[node]["children"][weights.index(wrong_weight)]
delta = max(counts, key=counts.get) - wrong_weight
tree[node]["weight"] + deltaimport operator as op
registers = defaultdict(int)
instructions = [x.split() for x in load(8)]
ops = {"<": op.lt, "<=": op.le, "==": op.eq, ">=": op.ge, ">": op.gt, "!=": op.ne}
signs = {"dec": -1, "inc": 1}
for target, sign, inc_amount, _, comparator, comparison, cmp_value in instructions:
if ops[comparison](registers[comparator], int(cmp_value)):
registers[target] += signs[sign] * int(inc_amount)
max(registers.values())maxval = 0
registers = defaultdict(int)
for target, sign, inc_amount, _, comparator, comparison, cmp_value in instructions:
if ops[comparison](registers[comparator], int(cmp_value)):
registers[target] += signs[sign] * int(inc_amount)
current_max = max(registers.values())
if current_max > maxval:
maxval = current_max
maxvaldef canonical_form(sequence):
count = 0
replacements = {"{": "[", ",": ",", "}": "]"}
mode = "group"
skip = False
result = ""
for char in sequence:
if skip:
skip = False
elif char == "!":
skip = True
elif mode == "group" and char == "<":
mode = "garbage"
elif mode == "garbage" and char == ">":
mode = "group"
elif mode == "garbage":
count += 1
elif mode == "group":
if char == "}":
result += replacements[char]
if char == "{":
result += replacements[char]
return result, count
data = load(9)[0]
data, count = canonical_form(data)
total, counter = 0, 0
for char in data:
if char == "[":
counter += 1
else:
total += counter
counter -= 1
totalcountdata = "165,1,255,31,87,52,24,113,0,91,148,254,158,2,73,153"
lengths = [int(length) for length in data.split(",")]
def knot_hash1(lengths):
knots = collections.deque(range(256))
total = 0
for idx, length in enumerate(lengths):
new = collections.deque([knots.popleft() for _ in range(length)])
new.reverse()
knots = knots + new
knots.rotate(-idx)
total += length + idx
knots.rotate(total)
return knots
knots = knot_hash1(lengths)
knots.popleft() * knots.popleft()def knot_hash64(s):
numbers = [ord(x) for x in s] + [17, 31, 73, 47, 23]
lengths = itertools.chain.from_iterable(itertools.repeat(numbers, 64))
knots = list(knot_hash1(lengths))
digits = [
functools.reduce(lambda x, y: x ^ y, knots[16 * i : 16 * (i + 1)])
for i in range(16)
]
return "".join(["{:0>2x}".format(x) for x in digits])
knot_hash64(data)To describe the hexgrid weāll use two basis vectors: x1, directed southeast, and x2, directed due north. All the other directions can be found as linear combinations of these, and the final position in this basis is just the sum of all the moves. Now, any move of the form (k, 1), with k in [-1, 0, 1] only takes one step, so the number of steps needed to reach the final position is just the value of whichever of the two basis vectors we have more of
data = open(load(11)[0].split(",")
coordinates = {"se": np.array((1, 0)),
"s": np.array((0, -1)),
"sw": np.array((-1, -1)),
"nw": np.array((-1, 0)),
"n": np.array((0, 1)),
"ne": np.array((1, 1))}
moves = np.array([coordinates[x] for x in data])
max(abs(moves.sum(axis=0)))For part 2, instead of finding just the sum of the moves, we look at the running total, and ask what the greatest value of any of the coefficients is at any point in the path.
abs(moves.cumsum(axis=0)).max()regex = "(-?\d+)"
data = load(12, "int")
graph = {line[0]: line[1:] for line in data}
neighbors = lambda state: graph[state]
len(utils.bfs(0, None, neighbors, return_visited=True))i = 0
while graph:
seed = list(graph.keys())[0]
visited = utils.bfs(seed, None, neighbors, return_visited=True)
for key in visited:
del graph[key]
i += 1
iThe only slightly tricky thing here is that we have to convert a depth to a cycle length. In each cycle, a scanner of depth d moves down (d - 1) steps, and then back up (d - 1) steps, so the cycle length is 2 * d - 2.
data = load(13, "int")
sum(map(lambda x: 0 if (x[0] % (x[1] * 2 - 2)) else x[0] * x[1], data))So, this is another application of the chinese remainder theorem, after a bit of massaging. We have multiple scanners with the same depth at different positions; each such scanner invalidates a congruence class of the integers mod cycle length.
In my input, the depths were almost coprime in the sense that there was one of the scanner depths that divided all the others, and apart from that, the depths were either coprime, or divided one another exactly.
The depths that divide one another exactly can be handled by unfolding the restriction of the smaller number to its higher multiples, and then removing the smaller number from consideration. After that, we can find what numbers would be valid for each depth.
For most of these, there was only one such modulus. Taking all the ones for which thatās the case we can use the chinese remainder theorem to solve that system of congruences, and then manually move to higher congruences to satisfy the remaining scanners.
import math
from utils import crt
scanners = defaultdict(list)
for position, depth in data:
scanners[2 * depth - 2].append((-position) % (2 * depth - 2))
scanners[2 * depth - 2].sort()
seen = []
for s1, s2 in itertools.combinations(scanners.keys(), 2):
s2, s1 = sorted([s1, s2])
if (s1 % s2) == 0:
seen.append(s2)
offsets = list(range(0, s1, s2))
new_restrictions = list(
map(sum, list(itertools.product(offsets, scanners[s2])))
)
restrictions = sorted(set(new_restrictions + scanners[s1]))
scanners[s1] = restrictions
for key in set(seen):
del scanners[key]
valid = {}
for scanner in scanners:
valid[scanner] = sorted(set(range(scanner)) - set(scanners[scanner]))
g = math.gcd(
*(
list(valid.keys())
+ [element for numbers in valid.values() for element in numbers]
)
)
congruences = []
remainder = {}
for modulus in valid:
if len(valid[modulus]) == 1:
congruences.append((int(modulus / g), int(valid[modulus][0] / g)))
else:
remainder[int(modulus / g)] = [int(x / g) for x in valid[modulus]]
N = np.product([x[0] for x in congruences])
x = crt(congruences) - N
while True:
x += N
for v in remainder:
if (x % v) not in remainder[v]:
break
else:
break
g * xprefix = load(14)[0] + "-"
hashes = [knot_hash64(prefix + str(i)) for i in range(128)]
bitstrings = [f"{int(h, 16):0128b}" for h in hashes]
sum(x.count("1") for x in bitstrings)field = np.array([[ord(x) - ord("0") for x in b] for b in bitstrings])
graph = defaultdict(list)
for i, j in itertools.product(range(128), range(128)):
neighbors = [(i, j + 1), (i + 1, j)]
neighbors = [(x, y) for x, y in neighbors if (x < 128 and y < 128)]
if not field[i, j]:
continue
for neighbor in neighbors:
if field[neighbor]:
graph[(i, j)].append(neighbor)
graph[neighbor].append((i, j))
count = field.sum() - len(graph) # singletons
neighbors = lambda x: graph[x]
while graph:
seed = list(graph.keys())[0]
visited = utils.bfs(seed, None, neighbors, return_visited=True)
for node in visited:
del graph[node]
count += 1
countA = 16807
B = 48271
a = 116
b = 299
total = 0
for i in range(40_000_000):
a = (a * A) % 2147483647
b = (b * B) % 2147483647
total += (a % 2**16) == (b % 2**16)
totala = 116
b = 299
total = 0
def gen_a(start):
current = start
while True:
current = (current * A) % 2147483647
if current % 4 == 0:
yield current
def gen_b(start):
current = start
while True:
current = (current * B) % 2147483647
if current % 8 == 0:
yield current
a = gen_a(a)
b = gen_b(b)
for i in range(5_000_000):
total += (next(a) % 2**16) == (next(b) % 2**16)
totalmoves = load(16)[0].split(",")
permutations = list("abcdefghijklmnop")
def dance(permutations, n):
seen = []
for i in range(n):
s = "".join(permutations)
if s in seen:
return seen[n % i]
seen.append(s)
for move in moves:
if move[0] == "s":
i = int(move[1:])
permutations = permutations[-i:] + permutations[:-i]
else:
if move[0] == "x":
a, b = map(int, move[1:].split("/"))
permutations[a], permutations[b] = permutations[b], permutations[a]
if move[0] == "p":
a, b = move[1:].split("/")
A = permutations.index(a)
B = permutations.index(b)
permutations[A], permutations[B] = permutations[B], permutations[A]
return permutations
"".join(dance(permutations[:], 1))For part 2, it would take too long to go through all the one billion cycles. But what if the dances hit a cycle at some point? That would make things a lot easier!
dance(permutations[:], 1_000_000_000)steps = 386
q = collections.deque([0])
for i in range(1, 2018):
q.rotate(-steps - 1)
q.appendleft(i)
q[1]50 million is at a level where the previous approach is becoming ineffective. The code below takes ~40 seconds to run. It could probably be improved, but that would take longer than 40 seconds.
q = collections.deque([0])
for i in range(1, 50_000_000):
q.rotate(-steps - 1)
q.appendleft(i)
q[q.index(0) + 1]program = [x.split() for x in load(18)]
ip = 0
registers = defaultdict(int)
binops = {
"set": lambda x, y: y,
"add": lambda x, y: x + y,
"mul": lambda x, y: x * y,
"mod": lambda x, y: x % y,
}
memory = 0
while 0 <= ip < len(program):
instruction = program[ip]
instruction, register, argument = instruction[0], instruction[1], instruction[-1]
try:
argument = int(argument)
except ValueError:
argument = registers[argument]
if instruction in binops:
op = binops[instruction]
registers[register] = op(registers[register], argument)
elif instruction == "jgz":
if registers[register] > 0:
ip += argument - 1
elif instruction == "rcv":
if registers[register] != 0:
print(memory)
break
elif instruction == "snd":
memory = argument
ip += 1Thereās a bunch of state to keep track of - letās make a class to hold it.
class Program:
def __init__(self, program, program_id, inputs):
self.program = program.copy()
self.ram = defaultdict(int)
self.ram["p"] = program_id
self.state = 1 # ready
self.count = 0
self.ip = 0
self.inputs = inputs
def __next__(self):
while 0 <= self.ip < len(self.program):
instruction = self.program[self.ip]
instruction, register, argument = (
instruction[0],
instruction[1],
instruction[-1],
)
try:
argument = int(argument)
except ValueError:
argument = self.ram[argument]
if instruction in binops:
op = binops[instruction]
self.ram[register] = op(self.ram[register], argument)
elif instruction == "jgz":
try:
comparison = int(register)
except ValueError:
comparison = self.ram[register]
if comparison > 0:
self.ip += argument - 1
elif instruction == "rcv":
if not self.inputs:
self.state = 0 # Waiting
return None
x = self.inputs.pop(0)
self.ram[register] = x
elif instruction == "snd":
self.count += 1
self.ip += 1
return argument
self.ip += 1
self.state = 2 # terminated
return NoneWith that out of the way we can implement the collaboration as follows: run program 0 until itās asking for a non-existent value (or finishes), then do the same for program 1. Keep going until both programs are waiting for the other or p1 has finished.
bus_one = []
bus_two = []
p0 = Program(program, 0, bus_two)
p1 = Program(program, 1, bus_one)
while p0.state == 1 and p1.state != 2:
while p0.state == 1:
n = next(p0)
if n is not None:
bus_one.append(n)
if bus_one and p1.state == 0:
p1.state = 1
while p1.state == 1:
n = next(p1)
if n is not None:
bus_two.append(n)
if bus_two and p0.state == 0:
p0.state = 1
p1.countThe hardest part for this was determining a sensible stopping condition ā that is one that could tell the difference between wires randomly crossing, and actually being finished. Direct inspection of the input showed where there was a dead end, so thatās just hard-coded into the below:
data = load(19)
x, y = len(data[0]), len(data)
direction = 1j
deltas = [(1j, "|"), (-1j, "|"), (1, "-"), (-1, "-")]
position = data[0].index("|")
result, character = "", ""
i = 1
while character != "L":
position = position + direction
character = data[int(position.imag)][int(position.real)]
if character == "+":
for delta, char in deltas:
if delta == -direction:
continue
lookahead = position + delta
try:
next_char = data[int(lookahead.imag)][int(lookahead.real)]
except IndexError:
continue
if next_char == char:
direction = delta
break
elif character in string.ascii_letters:
result += character
i += 1
resultI donāt know if this was intentional, but with the solution to part 1 above, counting the number of steps is trivial. Just add a loop variable to keep track of how many times we move
iItās always nice to be able to come up with a one-liner to solve these.
data = np.array(load(20, "int"), dtype=int)
abs(data[:, -3:]).sum(axis=1).argmin()For part two we could do some clever work to figure out a stopping condition based on pairs of particles being reachable in each of three dimensions, with reachable defined by being potentially able to catch up. Or we can just pick an arbitrary upper bound and hope itās good enough.
s, v, dv = data[:, :3], data[:, 3:6], data[:, -3:]
for _ in range(1000):
v += dv
s += v
values, index, count = np.unique(s, return_counts=True, return_index=True, axis=0)
indices = index[np.where(count == 1)]
s, v, dv = s[indices], v[indices], dv[indices]
len(s)This feels like the triumph of brute force over elegance. The process involves exponential growth, where the array triples in size every three iterations, so brute forcing seems like an unlikely choice, but the numbers are small enough that it just about works.
translation = str.maketrans(".#/", "01\n")
data = [x.translate(translation).split(" => ") for x in load(21)]
def hashed(array):
return tuple(array.ravel())
replacements = {}
for row in data:
src, dest = map(
lambda array: np.array(
[[int(x) for x in line] for line in array.split("\n")], dtype=bool
),
row,
)
flipped = src[::-1]
for i in range(4):
replacements[hashed(flipped)] = dest
replacements[hashed(src)] = dest
src, flipped = np.rot90(src), np.rot90(flipped)
array = np.reshape([int(x) for x in ".#...####".translate(translation)], (-1, 3))
def solve(array, n):
for i in range(n):
s = array.shape[0]
step = 2 if s % 2 == 0 else 3
new_step = 3 if step == 2 else 4
new_size = (s // step) * new_step
new_array = np.zeros((new_size, new_size), dtype=bool)
for i in range(0, s, step):
for j in range(0, s, step):
square = array[i : i + step, j : j + step]
new_square = replacements[hashed(square)]
new_array[
(i // step) * new_step : (i // step) * new_step + new_step,
(j // step) * new_step : (j // step) * new_step + new_step,
] = new_square
array = new_array
return (1 * array).sum()
solve(array, 5)solve(array, 18)direction = 1j
data = [[0 if char == "." else 1 for char in line] for line in load(22)]
size = len(data)
position = size // 2 + (size // 2) * 1j
board = defaultdict(int)
for y, line in enumerate(data):
for x, val in enumerate(line):
board[x + (size - y - 1) * 1j] = val
total = 0
for idx in range(10000):
state = board[position]
total += state == 0
direction *= (1 - 2 * state) * 1j
board[position] = 1 - state
position += direction
totalThe large number of iterations for part 2 seems to indicate that I should do something more clever here. But the following runs in about 20s on my machine, so nevermind.
direction = 1j
data = [[1j if char == "." else -1j for char in line] for line in load(22)]
size = len(data)
position = size // 2 + (size // 2) * 1j
board = defaultdict(lambda: 1j)
for y, line in enumerate(data):
for x, val in enumerate(line):
board[x + (size - y - 1) * 1j] = val
total = 0
for idx in range(10000000):
state = board[position]
total += state == 1
direction *= state
board[position] = -state * 1j
position += direction
totalprogram = [x.split() for x in load(23)]
ip = 0
registers = {x: 0 for x in "abcdefgh"}
binops = {"set": lambda x, y: y, "mul": lambda x, y: x * y, "sub": lambda x, y: x - y}
count = 0
while 0 <= ip < len(program):
instruction = program[ip]
instruction, register, argument = instruction[0], instruction[1], instruction[-1]
argument = registers[argument] if argument in registers else int(argument)
if instruction in binops:
if instruction == "mul":
count += 1
op = binops[instruction]
registers[register] = op(registers[register], argument)
elif instruction == "jnz":
operand = registers[register] if register in registers else int(register)
if operand != 0:
ip += argument - 1
ip += 1
countThe instructions warn you that trying to run part 2 as-is is a futile endeavour. And indeed, that is the case. Looking at the script thereās a very clear setup section to start with, where variables are set to values; these lines can never be reached again. After that thereās a huge loop which covers the rest of the program, and which basically says
while b != 0:
...
b += 17Inside this huge loop, we find a section at the start with two nested loops, followed by a tiny bit of cleanup. The two nested loops only involve the d and e variables, and they have the effect of setting f to zero if ever d * e = b, and doing basically nothing else. In the cleanup after the loop, 1 is added to h if f is zero. So that means that whenever b is composite, h increases by 1. So the script is equivalent to:
def is_composite(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return True
return False
b0 = 5700 + 100_000
len(list(filter(is_composite, range(b0, b0 + 17000 + 1, 17))))ports = load(24, "int")
ports = set(map(tuple, ports))
def strongest_bridge(current, components, part=1):
strength = current if part == 1 else current[1]
bridges = []
for candidate in [x for x in components if strength in x]:
value = candidate[0] if candidate[1] == strength else candidate[1]
new_components = components - set([candidate])
new_state = value if part == 1 else (current[0] + 1, value)
bridges.append(strongest_bridge(new_state, new_components, part=part))
if bridges:
best_bridge = max(bridges)
return (
2 * current + best_bridge
if part == 1
else (best_bridge[0], 2 * strength + best_bridge[1])
)
else:
return current
strongest_bridge(0, ports)Enumerating all the bridges for part 2 is basically the same as in part 1, so Iāve incuded the code there with a flag. The only difference is how the bridges are scored - here length takes priority. We can still use the max function because tuples sort lexicographically. The solution then becomes
strongest_bridge((0, 0), ports, part=2)[1]A pretty mindless translation of the requirements into code. Parsing the data was almost the fiddliest part
data = load(25, "raw")
header, *rows = data.split("\n\n")
row = rows[0]
rules = {}
directions = {"right": 1, "left": -1}
for row in rows:
state, *parameters = [x[:-1].split()[-1] for x in row.split("\n") if x]
rules[state] = (
(int(parameters[1]), directions[parameters[2]], parameters[3]),
(int(parameters[5]), directions[parameters[6]], parameters[7]),
)
ip = 0
tape = defaultdict(int)
current_state, n_steps = header.split("\n")
current_state = current_state[-2]
n_steps = int(n_steps.split()[-2])
for i in range(n_steps):
value, direction, current_state = rules[current_state][tape[ip]]
tape[ip] = value
ip += direction
sum(tape.values())