Spaces:
Running
Running
File size: 3,082 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
from math import gcd
from typing import Optional, Tuple
def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def find_solution(a: int, b: int, c: int) -> Optional[Tuple[int, int]]:
g = gcd(a, b)
if c % g != 0:
return None
# Scale everything down by gcd
a, b, c = a//g, b//g, c//g
# Find base solution using extended GCD
_, x0, y0 = extended_gcd(a, b)
x0 *= c
y0 *= c
# Find the general solution
# x = x0 + k*(b/g)
# y = y0 - k*(a/g)
# We need both x and y to be non-negative
k_min = -(x0 // b) if x0 < 0 else -((y0) // a)
k_max = (y0 // a) if y0 > 0 else (x0 // b)
# Find k that gives minimum positive solution
for k in range(k_min, k_max + 1):
x = x0 + k * b
y = y0 - k * a
if x >= 0 and y >= 0:
return (x, y)
return None
def solve_machine(ax: int, ay: int, bx: int, by: int, px: int, py: int, max_presses: Optional[int] = None) -> Optional[int]:
# Find solution for x-coordinate
sol_x = find_solution(ax, bx, px)
if not sol_x:
return None
# Find solution for y-coordinate
sol_y = find_solution(ay, by, py)
if not sol_y:
return None
# Check if solutions match
if sol_x[0] != sol_y[0] or sol_x[1] != sol_y[1]:
return None
# Check max presses constraint if specified
if max_presses and (sol_x[0] > max_presses or sol_x[1] > max_presses):
return None
# Calculate tokens needed (3 for A, 1 for B)
return 3 * sol_x[0] + sol_x[1]
def parse_input(filename: str):
machines = []
with open(filename, 'r') as f:
lines = f.read().strip().split('\n\n')
for machine in lines:
lines = machine.strip().split('\n')
ax = int(lines[0].split('X+')[1].split(',')[0])
ay = int(lines[0].split('Y+')[1])
bx = int(lines[1].split('X+')[1].split(',')[0])
by = int(lines[1].split('Y+')[1])
px = int(lines[2].split('X=')[1].split(',')[0])
py = int(lines[2].split('Y=')[1])
machines.append((ax, ay, bx, by, px, py))
return machines
def solve_part1(machines):
total_tokens = 0
for machine in machines:
tokens = solve_machine(*machine, max_presses=100)
if tokens is not None:
total_tokens += tokens
return str(total_tokens)
def solve_part2(machines):
offset = 10**13
total_tokens = 0
modified_machines = []
for ax, ay, bx, by, px, py in machines:
modified_machines.append((ax, ay, bx, by, px + offset, py + offset))
for machine in modified_machines:
tokens = solve_machine(*machine)
if tokens is not None:
total_tokens += tokens
return str(total_tokens)
# Read and parse input
machines = parse_input("input.txt")
# Solve part 1
print(solve_part1(machines))
# Solve part 2
print(solve_part2(machines)) |