import functools
import itertools
import os
import re
import sys
from collections import defaultdict
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
load = utils.year_load(2015)line = load(1)[0]
line.count("(") - line.count(")")position = 0
for idx, character in enumerate(line):
position = position + (1 if character == "(" else -1)
if position < 0:
break
idx + 1data = load(2)
boxes = [[int(x) for x in line.split('x')] for line in data]
sum([(3*x*y + 2*x*z + 2*y*z) for x,y,z in map(sorted, boxes)])sum([ x * y * z + 2 * (x + y) for x,y,z in map(sorted, boxes)])instructions = load(3)[0]
commands = {"^": lambda x, y: (x, y + 1), "v": lambda x, y: (x, y - 1),
">": lambda x, y: (x + 1, y), "<": lambda x, y: (x - 1, y),}
def execute_instructions(instructions, houses=None):
position = 0, 0
if houses is None:
houses = {(0, 0): 1}
for instruction in instructions:
position = commands[instruction](*position)
houses[position] = 1
return houses
len(execute_instructions(instructions))houses = execute_instructions(instructions[::2])
len(execute_instructions(instructions[1::2], houses))import hashlib
h = hashlib.md5()
prefix = "iwrupvqb"
def brute_force(n):
i = 0
while i := i + 1:
md5 = hashlib.md5((prefix + str(i)).encode(encoding="UTF-8")).hexdigest()
if md5[:n] == n * "0":
return i
brute_force(5)brute_force(6)def is_nice(s):
sufficient_vowels = len(re.findall("[aeiou]", s)) >= 3
contains_double = (np.array(list(s))[1:] == np.roll(list(s), 1)[1:]).any()
contains_forbidden = any(val in s for val in ["ab", "cd", "pq", "xy"])
return sufficient_vowels and contains_double and not contains_forbidden
sum(is_nice(x) for x in load(5))def is_nice(s):
contains_double = (np.array(list(s))[2:] == np.roll(list(s), 2)[2:]).any()
contains_double_pair = bool(re.findall("(..).*\\1", s))
return contains_double and contains_double_pair
sum(is_nice(x) for x in load(5))lines = load(6)
numbers = [[int(x) for x in re.findall("\d+", line)] for line in lines]
instructions = [line.replace("turn ", "").split()[0] for line in lines]
field = np.zeros([1000, 1000], dtype=int)
for (x1, y1, x2, y2), instruction in zip(numbers, instructions):
if instruction == "toggle":
field[x1:x2 + 1, y1:y2 + 1] ^= 1
else:
field[x1:x2 + 1, y1:y2 + 1] = int(instruction == "on")
field.sum()field = np.zeros([1000, 1000], dtype=int)
for (x1, y1, x2, y2), instruction in zip(numbers, instructions):
if instruction == "toggle":
field[x1:x2 + 1, y1:y2 + 1] += 2
else:
field[x1:x2 + 1, y1:y2 + 1] += 2 * int(instruction == "on") - 1
field[np.where(field < 0)] = 0
field.sum()circuit = {target: source for source, target in map(lambda x: x.split(" -> "), load(7))}
binops = {"AND": lambda x, y: x & y,
"OR": lambda x, y: x | y,
"LSHIFT": lambda x, y: x << y,
"RSHIFT": lambda x, y: x >> y}
@functools.cache
def evaluate(symbol):
try:
result = int(symbol)
return result
except ValueError:
pass
operation = circuit[symbol].split()
if len(operation) == 1:
return evaluate(operation[0])
elif len(operation) == 2:
return evaluate(operation[1]) ^ (2**16 - 1)
else:
arg1, op, arg2 = operation
return binops[op](evaluate(arg1), evaluate(arg2))
evaluate("a")We can reset everything by clearing out the cache, and setting a wire to a specific value (or expression) can be accomplished by modifying the circuit.
That gives
evaluate.cache_clear()
circuit["b"] = str(evaluate("a"))
evaluate("a")lines = [x[:-1] for x load(8)]
sum(len(line) - len(eval(line)) for line in lines)sum(2 + len([x for x in line if x in ["\"", "\\"]]) for line in lines)d = {}
data = [x.split() for x in load(9)]
for source, _, destination, __, distance in data:
d[(source, destination)] = int(distance)
d[(destination, source)] = int(distance)
cities = set(x[0] for x in d.keys())
tours = [sum(d[route[start], route[start + 1]] for start in range(len(cities) - 1))
for route in itertools.permutations(cities)]
min(tours)max(tours)message = "3113322113"
regex = re.compile(r"(([123])\2*)")
for _ in range(40):
runs = re.findall(regex, message)
message = ''.join([str(len(run)) + run[0] for run in map(lambda x: x[0], runs)])
len(message)for _ in range(10):
runs = re.findall(regex, message)
message = ''.join([str(len(run)) + run[0] for run in map(lambda x: x[0], runs)])
len(message)So there are two jobs here:
Is valid is not too difficult to accomplish. The “straight” condition can be rewritten as “1, 1” appears somewhere in the list of differences between neighboring characters. The “double pair” condition can be shortly expressed as matching a simple regex. Forbidding certain characters outright is most easily accomplished by never generating them as candidates
To iterate over candidate passwords, we first construct a helper method to iterate over candidate passwords that keep some prefix string fixed. The full iterator is then a chain over all these with successively shorter prefix strings.
def has_straight(password):
if isinstance(password, str):
password = np.array([ord(x) for x in password], dtype=int)
differences = np.diff(password)
return (1, 1) in zip(differences, differences[1:])
r = re.compile(r"(.)\1.*(.)\2")
def has_double_pair(password):
return bool(re.search(r, "".join(chr(x) for x in password)))
def is_valid_password(password):
return has_double_pair(password) and has_straight(password)
puzzle_input = tuple(ord(x) for x in "hxbxwxba")
password = puzzle_input
characters = tuple(ord(x) for x in "abcdefghjkmnpqrstuvwxyz")
def iterate(string, prefix_length):
n_free = len(string) - prefix_length - 1
first = characters[characters.index(string[prefix_length]) + 1 :]
suffixes = itertools.product(first, *([characters] * n_free))
for suffix in suffixes:
yield string[:prefix_length] + suffix
password_iterator = itertools.chain.from_iterable(
[iterate(password, l) for l in range(len(password))][::-1]
)
while not is_valid_password(password):
password = next(password_iterator)
print("".join(chr(x) for x in password))password = next(password_iterator)
while not is_valid_password(password):
password = next(password_iterator)
print("".join(chr(x) for x in password))For the first part, we’ve been promised that integers only appear as integers. So there’s no reason to try and read in the json properly - a simple regex does the trick
s = load(12, "int")
sum([n for line in s for n in line])That approach obviously doesn’t work for the second part, so we’ll need a json library
import json
s = json.loads(load(12, "raw"))
def find_value(structure):
if isinstance(structure, str):
return 0
if isinstance(structure, int):
return structure
if isinstance(structure, list):
return(sum(find_value(x) for x in structure))
if "red" in structure.values():
return 0
return sum(find_value(x) for x in structure.values())
find_value(s)data = load(13)
def parse(line):
words = line.split()
people = tuple(sorted([words[0], words[-1][:-1]]))
amount = int(re.search("(\d+)", line).groups(0)[0])
sign = 2 * ("gain" in words) - 1
return people, amount * sign
scores = defaultdict(int)
for line in load(13):
people, score = parse(line)
scores[people] += score
people = sorted(set([person for pair in scores.keys() for person in pair]))
def calculate_score(permutation):
score = 0
n = len(permutation)
for i in range(n):
score += scores[tuple(sorted([permutation[i], permutation[(i + 1) % n]]))]
return score
maxval = 0
for permutation in itertools.permutations(people[1:]):
score = calculate_score((people[0],) + permutation)
if score > maxval:
maxval = score
maxvalHere we see the magic of the defaultdict - since all of the pairs involving “You” have a net score of zero, we don’t need to change the scoring dictionary at all. We just add “You” to the people we are permuting over, and run everything exactly as before.
maxval = 0
for permutation in itertools.permutations(people[1:] + ["You"]):
score = calculate_score((people[0],) + permutation)
if score > maxval:
maxval = score
maxvalreindeer = load(14, "int")
def score(time, speed, on, off):
cycle_length = on + off
n_cycles = time // (cycle_length)
offset = min(on, n_cycles % cycle_length)
return speed * (n_cycles * on + offset)
max(map(lambda x: score(2503, *x), reindeer))wins = np.zeros(len(numbers))
positions = np.zeros(len(numbers))
for i in range(2503):
for idx, (speed, on, off) in enumerate(reindeer):
cycle_length = on + off
if i % cycle_length < on:
positions[idx] += speed
wins += (positions == max(positions))
max(wins)Since each of the values has to be positive, we can derive some constraints on how much of each ingredient we can use. We know there are 100 of each in total, so letting the four variables be \(w, x, y, z\), we have \(w + x + y + z = 100\). Additionally, since only one ingredient contributes a positive value to any given quantitity we have to use at least one of each. With that out of the way we can use the matrix to set up the following system of inequalities:
\[\begin{align*} 3w - 3x - y &> 0 \\ 4y - 3z &> 0 \\ -3w + 2z &> 0 \end{align*}\]From that we can derive the following bounds for the amount of each ingredient
\[\begin{align*} 1 &\leq w\leq 39\\ 1 &\leq x\leq 39\\ 1 &\leq y\leq 72\\ 1 &\leq z\leq 65 \end{align*}\]For example, the upper bound on \(w\) follows from the last inequality, which implies that \(z > 1.5 w\). The one on \(x\) comes from the first inequality, which implies that \(x < w\).
The last thing to consider is that once three of the values are fixed, the fourth is known. Together, these optimizations let us reduce the cases we have to consider from 1 million to less than 50k.
data = np.array(load(15, "int")).T
initial_bounds = [[1, 39 + 1], [1, 39 + 1], [1, 72 + 1], [1, 65 + 1]]
def calculate(part=1):
maxval = 0
for w in range(*initial_bounds[0]):
for x in range(1, w):
left, right = initial_bounds[2]
new_y = 3 * (w - x)
for y in range(left, min(right, new_y)):
z = 100 - x - y - w
score = (data @ (w, x, y, z))
if (score <= 0).any() or (part == 2 and (score[-1] != 500)):
continue
val = np.product(score[:-1])
if val > maxval:
maxval = val
return maxval
calculate()calculate(2)data = load(16)
sues = {}
for line in data:
sep = line.index(":")
sue, info = line[:sep], line[sep + 1 :]
sues[int(sue.split()[1])] = {
k: int(v) for k, v in map(lambda x: x.split(": "), info.split(", "))
}
match = {
"children": 3,
"cats": 7,
"samoyeds": 2,
"pomeranians": 3,
"akitas": 0,
"vizslas": 0,
"goldfish": 5,
"trees": 3,
"cars": 2,
"perfumes": 1,
}
for sue in sues:
comparison = sues[sue]
for key in match:
if key not in comparison:
continue
if match[key] != comparison[key]:
break
else:
print(sue)
breakfor sue in sues:
comparison = sues[sue]
for key in match:
if key not in comparison:
continue
f = lambda known, measured: known == measured
if key in ["cats", "trees"]:
f = lambda known, measured: measured > known
elif key in ["pomeranians", "goldfish"]:
f = lambda known, measured: measured < known
if not f(match[key], comparison[key]):
break
else:
print(sue)
breakdef count(value, containers):
if value == 0:
return 1
if value < 0 or len(containers) == 0:
return 0
return count(value - containers[0], containers[1:]) + count(value, containers[1:])
count(150, load(17, "np"))def count(value, containers):
result = defaultdict(int)
def inner(value, containers, depth):
if value == 0:
result[depth] += 1
return
if value < 0 or len(containers) == 0:
return
inner(value - containers[0], containers[1:], depth + 1)
inner(value, containers[1:], depth)
inner(value, containers, 0)
return result
result = count(150, load(17, "np"))
result[min(result.keys())]weights = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
initial_board = np.array(
[[0 if char == "." else 1 for char in line] for line in load(18)]
)
board = initial_board.copy()
for i in range(100):
mask = scipy.ndimage.convolve(board, weights, mode="constant")
board = ((mask == 3) | ((mask - board) == 3)).astype(int)
board.sum()def fix_corners(board):
board = np.roll(board, 1, axis=[0,1])
board[:2, :2] = 1
return np.roll(board, -1, axis=[0,1])
board = fix_corners(initial_board)
for i in range(100):
mask = scipy.ndimage.convolve(board, weights, mode='constant')
board = fix_corners(((mask == 3) | ((mask - board) == 3)).astype(int))
board.sum()data = load(19)
transitions, initial_string = data[:-2], data[-1]
transitions = [x.split(" => ") for x in transitions]
transformations = defaultdict(list)
for source, dest in transitions:
transformations[source].append(dest)
element_regex = "[A-Z][a-z]?"
elements = re.findall(element_regex, initial_string)
result = set()
for idx, element in enumerate(elements):
prefix = ''.join(elements[:idx])
suffix = ''.join(elements[idx+1:])
for transformation in transformations[element]:
result.add(prefix + transformation + suffix)
len(result)Instead of trying to make the final string starting from “e” and using the given transformations, we can equivalently try to reduce the final string to “e” using the reverse transformations - that should be the same thing.
If we’re naive about this, it’s going to take a very long time. One thing to notice is that “Ca” only appears on the right hand side of our transformation rules as “X => XCa” or “X => CaX”. So generating one unit of “Ca” always takes one step, and we can pretend there’s a rule of the form “’∅ => Ca”.
That still leaves us with more than 100k candidates for shortening after only 4 reverse substitutions, which is less than ideal. Luckily, there’s a pen and paper solution!
Looking further at the list of reactions given, all the ones that don’t produce Rn are of the form “A => BC”, and thus always take exactly one step to increase the length of the molecule by one.
The only remaining question is how efficiently we can use the Rn we have available. Now, some of the “Rn” reactions give a “C” to start with, but “C” is not the source of any reaction and it’s not present in our string, so we can completely ignore these. Looking at the remainder, all the reactions convert one element into four, apart from “H => NRnFYFAr” and “Ca => SiRnFYFAr”, which convert one to six. There are only 6 Ys in the initial string, so these reactions have to run exactly six times, and the others run 30 times (There are 36 Rns in my input)
There are 292 elements in the initial string. After getting rid of Rns I have 292 - 5 * 6 - 3 * 30 = 172 elements left, and have spent 36 reactions. Getting to one electron requires a further 171 reactions for a total of 207.
We’re looking for numbers that have lots of divisors compared to how big they are. A bit of ass-pulling lets me guess that they have to be divisible by 60.
target = 33100000
def sum_of_factors(n, part=1):
result = 0
for i in range(1, int(np.sqrt(n)) + 1):
if n % i == 0:
if part == 1:
result += i + int(n // i)
else:
div = n // i
result += (i if div <= 50 else 0) + (div if i <= 50 else 0)
return result
def run(target, part=1):
i, total = 0, 0
while total < target:
i += 60
total = sum_of_factors(i, part)
return i
run(target / 10)The only things that change for part 2 are the target, and the calculation of the sum of factors. That’s most easily done by passing a “part” flag to the sum of factors function, and a “target” parameter to run. Of course, that makes the following look fairly boring:
run(target / 11, 2)data = {k: int(v) for k, v in map(lambda x: x.split(":"), load(20))}
turns = [(armor, np.ceil(100 / (data["Damage"] - armor)) - 1) for armor in range(8)]
attack_needed = [
np.ceil(data["Hit Points"] / (x[1] + 1)) + data["Armor"] for x in turns
]
equipment = load("20_auxiliary", "int")
equipment = equipment[:10] + [x[1:] for x in equipment[10:]]
weapons = equipment[:5]
armor = equipment[5:10]
rings = equipment[10:]
# Use itertools to select one weapon, at most one armor and at most two rings
options = itertools.product(
weapons,
itertools.chain([[0, 0, 0]], armor),
itertools.chain([[0, 0, 0]], rings, itertools.combinations(rings, 2)),
)
# The two ring case has to be flattened
options = [
list(option[:-1]) + list(option[-1]) if isinstance(option[-1], tuple) else option
for option in options
]
# Then we have regular data and can just convert to a numpy array and sum
sums = [np.array(option, dtype=int).sum(axis=0) for option in options]
# We need the smallest gold value that has enough (damage, armor)
min(s[0] for s in sums if s[1] >= attack_needed[min(s[2], 7)])With all that in place, part 2 is just inverting an inequality and changing a min to a max:
max(s[0] for s in sums if s[1] < attack_needed[min(s[2], 7)])import queue
def update_effects(effects):
return tuple([max(x - 2, 0) for x in effects])
def apply_effects(state, part=1):
own_hp, boss_hp, mana, shield, poison, recharge = state
return (own_hp - (2 if shield else 9) - (1 if part == 2 else 0),
boss_hp - (6 if poison else 0),
mana + (202 if recharge > 1 else 101 if recharge else 0))
def neighbors(state, part=1):
if state[0] <= 0:
return []
new_hp, new_boss_hp, new_mana = apply_effects(state, part=part)
new_effects = update_effects(state[-3:])
neighbors = [(53, (new_hp, new_boss_hp - 4, new_mana - 53) + new_effects),
(73, (new_hp + 2, new_boss_hp - 2, new_mana - 73) + new_effects)]
costs = [113, 173, 229]
durations = [6, 6, 5]
for idx, (cost, duration) in enumerate(zip(costs, durations)):
if state[2] < cost or new_effects[idx] != 0:
continue
new_state = list(state).copy()
new_state[idx + 3] = duration
new_hp, new_boss_hp, new_mana = apply_effects(new_state, part=part)
new_effects = update_effects(new_state[-3:])
neighbors.append((cost, (new_hp, new_boss_hp, new_mana - cost) + new_effects))
return [neighbor for neighbor in neighbors if neighbor[1][2] >= 0]
initial_state = (50, 58, 500, 0, 0, 0)
q = PriorityQueue()
q.put((0, initial_state))
while q.qsize() > 0:
cost, state = q.get()
if state[1] <= 0:
break
for neighbor in neighbors(state):
extra_cost, new_state = neighbor
q.put((cost + extra_cost, new_state))
costinitial_state = (49, 58, 500, 0, 0, 0)
q = PriorityQueue()
q.put((0, initial_state))
while q.qsize() > 0:
cost, state = q.get()
if state[1] <= 0:
break
for neighbor in neighbors(state, part=2):
extra_cost, new_state = neighbor
q.put((cost + extra_cost, new_state))
costarithmetics = {
"inc": lambda x: x + 1,
"tpl": lambda x: x * 3,
"hlf": lambda x: int(x // 2),
}
jumps = {"jmp": lambda x: True, "jie": lambda x: (x % 2) == 0, "jio": lambda x: x == 1}
known_tokens = list(arithmetics.keys()) + list(jumps.keys()) + ["a", "b"]
data = [line.replace(",", "").split() for line in load(23)]
data = [
[token if token in known_tokens else int(token) for token in line] for line in data
]
def run(program, part=1):
ip = 0
registers = defaultdict(int)
registers["a"] = int(part == 2)
while ip < len(program):
instruction = program[ip]
if instruction[0] in arithmetics:
registers[instruction[1]] = arithmetics[instruction[0]](
registers[instruction[1]]
)
else:
if jumps[instruction[0]](registers[instruction[1]]):
ip += instruction[-1] - 1
ip += 1
return registers
run(data)["b"]A flag in the “run” function lets us change the relevant register for part 2
run(data, 2)["b"]Here’s a buggy implementation of part 1. It only looks at the smallest sets that can make the first compartment and completely ignores the others. For the first part that’s semi justifiable, since the amount of small numbers in the input make it very likely that the leftover set can be partitioned into two.
data = load(24, "np")
def run(splits = 3):
target = data.sum() / splits
i = 1
while True:
for combination in itertools.combinations(data[::-1], i):
if sum(combination) == target:
break
else:
i += 1
continue
break
return min(map(lambda x: np.product(x),
filter(lambda x: sum(x) == target,
itertools.combinations(data[::-1], i))))
run()For the second part, the same cheat works, but is less justifiable, since I don’t actually check that the remaining set can be partitioned into three.
run(4)def coordinates_to_n(row, column):
n = row + column
complete_triangles = (n - 1) * (n - 2) / 2
return int(complete_triangles) + column
row, column = 3010, 3019
n = coordinates_to_n(row, column)
s = 20151125
for i in range(n - 1):
s = (s * (252533)) % 33554393
s