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