import dataclasses
import functools
import itertools
import os
import re
import sys
from collections import defaultdict, deque, namedtuple
from queue import PriorityQueue
import more_itertools
import numpy as np
import operator
import pandas as pd
import scipy
sys.path.insert(1, "..")
import utils
load = utils.year_load(2024)Load the data, sort the two columns, find the absolute difference between them and sum the result.
data = np.sort(load(1, "int"), axis=0)
abs(np.diff(data)).sum()numpy has a handy method to find the unique values in an array, and their counts. Let’s use that to make a dictionary of value -> count pairs for the right list with a default value of zero, and then just look up that value for each element of the left list.
lookup = defaultdict(int)
lookup.update(
{value: count for value, count in zip(*np.unique(data[:, 1], return_counts=True))}
)
sum(x * lookup[x] for x in data[:, 0])Nothing too complicated going on here: load the data, and find the difference between successive values. To account for decreasing sequences, multiply by the sign of the first difference and then require that all the differences be greater than one and less than or equal to three.
data = load(2, "int")
def is_safe(line):
diff = np.diff(line)
diff = diff * np.sign(diff[0])
return int(((diff > 0) & (diff <= 3)).all())
sum(is_safe(line) for line in data)I spent a bit of time trying to see if there was a neat way of incorporating the “is valid if any one number is deleted” requirement, but I couldn’t immediately see it, so I ended up just iterating over all the possible deletions instead.
total = 0
for line in data:
for idx in range(len(line)):
if is_safe(line[:idx] + line[idx + 1 :]):
total += 1
break
totalWe get to play with regex! Well, I do – there might be better ways of tackling this. The format for a valid mul instruction is quite strict, encoding that as a regex is fairly straightforward. Once we have that, we can use re.findall to find all the occurrences and extract the integers.
data = load(3, "raw")
mul = r"mul\((\d{1,3}),(\d{1,3})\)"
sum(int(pair[0]) * int(pair[1]) for pair in re.findall(mul, data))I’m pretty happy with my part two, which I managed to do fairly elegantly. We can ignore all the sections immediately after a don't() instruction by splitting the string on those, and then discarding the start of each substring up to the first do() instruction. Concatenating all the substrings gives us a clean string with just the segments we are interested in, and we can proceed as before.
clean = "".join(
[segment[segment.find("do()") :] for segment in ("do()" + data).split("don't()")]
)
sum(int(pair[0]) * int(pair[1]) for pair in re.findall(mul, clean))data = np.array([[ord(char) for char in line] for line in load(4)])
mask = np.array([ord(char) for char in "XMAS"])
def xmas(chararray):
return (chararray == mask).all() or (chararray == mask[::-1]).all()
footprints = [np.eye(4), np.fliplr(np.eye(4)), [[1, 1, 1, 1]], [[1], [1], [1], [1]]]
sum(
scipy.ndimage.generic_filter(data, xmas, footprint=footprint, mode="constant").sum()
for footprint in footprints
)masks = ["MMASS", "SMASM", "MSAMS", "SSAMM"]
encoded_masks = [np.array([ord(char) for char in mask]) for mask in masks]
footprint = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
def x_mas(chararray):
for mask in encoded_masks:
if (chararray == mask).all():
return 1
return 0
scipy.ndimage.generic_filter(data, x_mas, footprint=footprint, mode="constant").sum()This problem screams topological sort, so that’s what I’m going with. For part one, to account for the case where multiple orderings of a line might obey the rules, the we’ll use a function to check whether the line order is compatible with the order given in the update.
That’s not too tricky: just iterate through the update, and for each item in the update
If we get through the whole update without finding a blocked item, then the order is valid and we should include it in the sum.
rules, updates = [x.split("\n") for x in load(5, "raw").split("\n\n")]
updates = [[int(x) for x in line.split(",")] for line in updates]
ancestors = defaultdict(list)
descendents = defaultdict(list)
for rule in rules:
first, last = map(int, rule.split("|"))
ancestors[last].append(first)
descendents[first].append(last)
def restriction(rules, keys):
return {key: [x for x in rules[key] if x in keys] for key in keys}
def is_sorted(keys):
keys = keys.copy()
pre = restriction(ancestors, keys)
post = restriction(descendents, keys)
while keys:
current = keys.pop(0)
if pre[current]:
return False
del pre[current]
for item in post[current]:
pre[item] = [x for x in pre[item] if x != current]
return True
sum(update[len(update) // 2] for update in updates if is_sorted(update))For part 2 we’ll actually implement the topological sort. I vaguely remembered how to do this, but it took a couple of iterations to get right.
The idea is that we start by scanning the rules dictionary for items which are eligible for immediate placement, and remove them from the list.
We then iteratively place these items, and for each item we place, we remove any blocks that they might have placed on later items. That might mean that new items are eligible for placement, and in this way we iterate through the entire list and output an order compatible with the rules.
def topological_sort(keys):
pre = restriction(ancestors, keys)
post = restriction(descendents, keys)
result = []
to_delete = [key for key in pre if not pre[key]]
for key in to_delete:
del pre[key]
while to_delete:
n = to_delete.pop()
result.append(n)
for item in post[n]:
pre[item] = [x for x in pre[item] if x != n]
if not pre[item]:
to_delete.append(item)
del pre[item]
return result
sum(topological_sort(line)[len(line) // 2] for line in updates if not is_sorted(line))obstacles = set()
for y, line in enumerate(load(6)):
for x, char in enumerate(line.strip()):
if char == "^":
position = x + 1j * y
if char == "#":
obstacles.add(x + 1j * y)
ymax, xmax = y, x
def is_valid(position):
x, y = position.real, position.imag
return 0 < y < ymax and 0 < x < xmax
direction = -1j
path = [(position, direction)]
while is_valid(position):
while position + direction in obstacles:
direction *= 1j
position += direction
path.append((position, direction))
len(set(x[0] for x in path))For part two, we should realise that only obstacles placed on the path have any chance of affecting what the guard does, so the relevant search space is significantly smaller than “every vacant square on the board”. There’s also no need to start the guard from the initial position for every new obstacle; we can just start her on the path right in front of the new obstacle. Similarly, if she ever gets back on her original path before the obstacle, we know she must be in a loop, so we can start with a visited set that covers the whole pwth right up to the new obstruction.
attempted_positions = set([path[0][0]])
total = 0
for idx in range(1, len(path)):
obstacle, _ = path[idx]
if obstacle in attempted_positions:
continue
position, direction = path[idx - 1]
obstacles.add(obstacle)
seen = set(path[:idx - 1])
while is_valid(position):
seen.add((position, direction))
while position + direction in obstacles:
direction *= 1j
while is_valid(position) and position + direction not in obstacles:
position += direction
if (position, direction) in seen:
total += 1
break
attempted_positions.add(obstacle)
obstacles.remove(obstacle)
totaldata = load(7)
data = [
[int((parts := line.split(":"))[0]), [int(i) for i in parts[1].split()]]
for line in data
]
operators = [operator.mul, operator.add]
def possible_values(operands, current=None, ops=operators):
if current is None:
current = operands[0]
operands = operands[1:]
if not operands:
yield current
else:
for op in ops:
yield from possible_values(operands[1:], op(current, operands[0]), ops)
sum(
result
for result, operands in data
if any(value == result for value in possible_values(operands))
)This is horribly slow, but has the advantage of being an incredibly fast modification of part 1. A bit of thought shows that backtracking would make things run much faster, since it would let us prune the state space much faster, so that’s one easy option for speeding things up.
def concat(x, y):
return int(str(x) + str(y))
ops = [operator.mul, operator.add, concat]
sum(
result
for result, operands in data
if any(value == result for value in possible_values(operands, ops=ops))
)Nothing too complicated going on here. For every symbol on the map that’s not a ., we find all its locations, and then we use itertools.combinations to loop over all pairs of symbols.
data = load(8, "chararray")
result = set()
for value in np.unique(data):
if value == ".":
continue
points = np.array(np.where(data == value)).T
for p1, p2 in itertools.combinations(points, 2):
result.add(tuple(2 * p1 - p2))
result.add(tuple(2 * p2 - p1))
sum(1 for x in result if 0 <= x[0] < data.shape[0] and 0 <= x[1] < data.shape[1])In python, the int function automatically rounds towards zero, so we can explicitly work out the number of steps we can take in the x and y directions before going off the map.
result = set()
for value in np.unique(data):
if value == ".":
continue
points = np.array(np.where(data == value)).T
for p1, p2 in itertools.combinations(points, 2):
dx = (p2 - p1)[1]
dy = (p2 - p1)[0]
Δ = np.array([dy, dx])
ymin, ymax = -np.inf, np.inf
xmin, xmax = -np.inf, np.inf
if dy != 0:
ymin, ymax = sorted([int((y - p1[0]) / dy) for y in [0, data.shape[0] - 1]])
if dx != 0:
xmin, xmax = sorted([int((x - p1[1]) / dx) for x in [0, data.shape[1] - 1]])
minval = max(ymin, xmin)
maxval = min(ymax, xmax)
points = [tuple(p1 + k * Δ) for k in range(minval, maxval + 1)]
result |= set(points)
len(result)data = np.array([[int(char) for char in line] for line in load(10)])
def neighbors(y, x):
result = []
val = data[y, x]
for dy, dx in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
new_y, new_x = y + dy, x + dx
if (
0 <= new_y < data.shape[0]
and 0 <= new_x < data.shape[1]
and data[new_y, new_x] == val + 1
):
result.append((new_y, new_x))
return result
@functools.cache
def p1(y, x):
r = set()
if data[y, x] == 9:
return set([(y, x)])
return r.union(*[p1(*neighbor) for neighbor in neighbors(y, x)])
starts = np.array(np.where(data == 0)).T
sum(len(p1(y, x)) for y, x in starts)@functools.cache
def p2(y, x):
if data[y, x] == 9:
return 1
return sum(p2(*neighbor) for neighbor in neighbors(y, x))
sum(p2(y, x) for y, x in starts)