Spaces:
Running
Running
| 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)) |