Thank you! I love seeing well-documented solutions for problems that I'm struggling with, so I try to add comments for non-trivial parts of any code I post. :)
Python
# pairwise helps picking consecutive values easier
# [A,B,C,D] -> [AB, BC, CD]
# combinations will give me combinations of elements in a sequence
# [A,B,C,D] -> [AB, AC, AD, BC, BD, CD]
from itertools import pairwise, combinations
# line will pass thorough the center if the points are on opposite ends,
# i.e., total points / 2 distance away
def part1(data: str, nail_count: int = 32):
opposite_dist = nail_count // 2
nodes = [int(n) for n in data.split(",")]
center_passes = 0
for a, b in pairwise(nodes):
if abs(a - b) == opposite_dist:
center_passes += 1
return center_passes
assert part1("1,5,2,6,8,4,1,7,3", 8) == 4
# BRUTEFORCE: take every two points and check if they intersect
def part2(data: str, nail_count: int = 32):
def intersects(s1, s2):
# expand the points
(x1, x2), (y1, y2) = s1, s2
# make sure x1 is the smaller nail and x2 is the bigger one
if x1 > x2:
x1, x2 = x2, x1
# there is an intersection if one point lies bwtween x1 and x2
# and the other lies outside it
if x1 < y1 < x2 and (y2 > x2 or y2 < x1):
return True
if x1 < y2 < x2 and (y1 > x2 or y1 < x1):
return True
return False
nodes = [int(n) for n in data.split(",")]
knots = 0
for s1, s2 in combinations(pairwise(nodes), 2):
if intersects(s1, s2):
knots += 1
return knots
assert part2("1,5,2,6,8,4,1,7,3,5,7,8,2", 8) == 21
from collections import defaultdict
# This is better than bruteforce
def part3(data: str, nail_count: int = 256):
connections = defaultdict(list)
nodes = [int(n) for n in data.split(",")]
# record all connections, both ways
for a, b in pairwise(nodes):
connections[a].append(b)
connections[b].append(a)
max_cuts = 0
for node_a in range(1, nail_count + 1):
cuts = 0
for node_b in range(node_a + 2, nail_count + 1):
# add new cuts for the node we just added between a and b
for other_node in connections[node_b - 1]:
if other_node > node_b or other_node < node_a:
cuts += 1
# also add any cuts for threads that go between node a and b
cuts += connections[node_a].count(node_b)
# remove cuts that were going from BETWEEN node_a and node_b-1 (prev node_b) to node_b
for other_node in connections[node_b]:
if node_a < other_node < node_b:
cuts -= 1
# also remove any cuts for threads that go between node a and b-1
cuts -= connections[node_a].count(node_b - 1)
max_cuts = max(max_cuts, cuts)
return max_cuts
assert part3("1,5,2,6,8,4,1,7,3,6", 8) == 7
Python
Used sliding window for part 3. The off-by-one difference between i and j tripped me up for a while.
def part1(data: str, mentor: str = 'A'):
mentors = 0
pairs = 0
for p in data:
if p == mentor:
mentors += 1
elif p == mentor.lower():
pairs += mentors
return pairs
assert part1("ABabACacBCbca") == 5
def part2(data: str):
all_pairs = 0
for mentor in 'ABC':
all_pairs += part1(data, mentor)
return all_pairs
assert part2("ABabACacBCbca") == 11
from collections import defaultdict
def part3(data: str, distance_limit: int = 1000, repeat: int = 1000):
n = len(data)
N = len(data) * repeat
pairs = 0
person_count = defaultdict(int)
curr = 0
# initialize the first window excluding the right boundary
for j in range(distance_limit):
person_count[data[j % n]] += 1
for curr in range(N):
# move left boundary (if applicable)
if (i := curr - distance_limit - 1) >= 0:
person_count[data[i % n]] -= 1
# move right boundary (if applicable)
if (j := curr + distance_limit) < N:
person_count[data[j % n]] += 1
# if mentee, record pairs
if data[curr % n].islower():
pairs += person_count[data[curr % n].upper()]
return pairs
assert (t := part3("AABCBABCABCabcabcABCCBAACBCa", 10, 1)) == 34, f"Expected 34 but got {t}"
assert (t := part3("AABCBABCABCabcabcABCCBAACBCa", 10, 2)) == 72, f"Expected 72 but got {t}"
assert (t := part3("AABCBABCABCabcabcABCCBAACBCa", 1000, 1000)) == 3442321, f"Expected 3442321 but got {t}"-
Never been more glad to have left that sinking ship early
Python
# snipped read_input implementation
data = read_input("input_p3.txt")
# part 1 and 2 can be solved using a calculator
# with only the first and last gears
def part3(data):
shafts = data.splitlines()
rotations = 100 * int(shafts[0])
for shaft in shafts[1:-1]:
gear1, gear2 = [int(g) for g in shaft.split('|')]
rotations *= gear2 / gear1
rotations /= int(shafts[-1])
return int(rotations)
assert part3("""5
7|21
18|36
27|27
10|50
10|50
11""") == 6818
print(part3(data))
"My chicks meow but that's because they're bilingual"
You don't know ???
Eh, I agree with the idea for Superman, but it's a little different for Batman. Someone who watches Batman use his advanced gadgets and hi-tech vehicles can at least surmise that he has access to a lot of money.
He might've chilled out a bit now, but he basically started as a saiyan supremacist.
HESOYAM is burned into mine
It's edited
Thank you Dave! Now we can finally put one of the world's greatest questions to rest.