124 lines
3.5 KiB
Python
124 lines
3.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import math
|
|
import re
|
|
import sys
|
|
|
|
input_file = sys.argv[1]
|
|
|
|
with open(input_file) as fd:
|
|
lines = [line.rstrip() for line in fd.readlines()]
|
|
|
|
coords = tuple[int, int]
|
|
prizes: list[coords] = list()
|
|
buttons: list[tuple[coords, coords]] = list()
|
|
|
|
for li, line in enumerate(lines):
|
|
machine = li // 4
|
|
offset = li % 4
|
|
if offset == 0:
|
|
match = re.match(r"^Button A: X\+([0-9]+), Y\+([0-9]+)$", line)
|
|
assert match
|
|
button_a = int(match[1]), int(match[2])
|
|
elif offset == 1:
|
|
match = re.match(r"^Button B: X\+([0-9]+), Y\+([0-9]+)$", line)
|
|
assert match
|
|
button_b = int(match[1]), int(match[2])
|
|
buttons.append((button_a, button_b))
|
|
elif offset == 2:
|
|
match = re.match("^Prize: X=([0-9]+), Y=([0-9]+)$", line)
|
|
assert match
|
|
prize = int(match[1]), int(match[2])
|
|
# prize = prize[0] + 10000000000000, prize[1] + 10000000000000
|
|
prizes.append(prize)
|
|
|
|
assert len(prizes) == len(buttons)
|
|
|
|
|
|
def slope(point: coords) -> float:
|
|
return point[1] / point[0]
|
|
|
|
|
|
def norm(point: coords) -> float:
|
|
return math.sqrt(math.pow(point[1], 2) + math.pow(point[0], 2))
|
|
|
|
|
|
ttoks = 0
|
|
token_a, token_b = 3, 1
|
|
for arcade, prize in enumerate(prizes):
|
|
butts = buttons[arcade]
|
|
button_a, button_b = butts
|
|
|
|
print(43, prize, button_a, button_b)
|
|
toks = None
|
|
|
|
max_a_x = int(math.ceil(prize[0] / button_a[0]))
|
|
max_a_y = int(math.ceil(prize[1] / button_a[1]))
|
|
max_a = min(max_a_x, max_a_y)
|
|
max_b_x = int(math.ceil(prize[0] / button_b[0]))
|
|
max_b_y = int(math.ceil(prize[1] / button_b[1]))
|
|
max_b = min(max_b_x, max_b_y)
|
|
|
|
slope_a = slope(button_a)
|
|
slope_b = slope(button_b)
|
|
slope_prize = slope(prize)
|
|
slope_but_min = min(slope_a, slope_b)
|
|
slope_but_max = max(slope_a, slope_b)
|
|
if slope_prize < slope_but_min or slope_prize > slope_but_max:
|
|
print("Not in range")
|
|
continue
|
|
|
|
norm_a = norm(button_a)
|
|
norm_b = norm(button_b)
|
|
speed_a = norm_a / 3
|
|
speed_b = norm_b / 1
|
|
|
|
if speed_a > speed_b:
|
|
button_fastest, button_slowest = button_a, button_b
|
|
token_fastest, token_slowest = token_a, token_b
|
|
max_fastest = max_a
|
|
else:
|
|
button_fastest, button_slowest = button_b, button_a
|
|
token_fastest, token_slowest = token_b, token_a
|
|
max_fastest = max_b
|
|
toks = 0
|
|
|
|
min_presses_fastest = 0
|
|
max_presses_fastest = max_fastest
|
|
while min_presses_fastest + 1 < max_presses_fastest:
|
|
presses_fastest = int(
|
|
math.floor((min_presses_fastest + max_presses_fastest) / 2)
|
|
)
|
|
pri_x, pri_y = (
|
|
prize[0] - button_fastest[0] * presses_fastest,
|
|
prize[1] - button_fastest[1] * presses_fastest,
|
|
)
|
|
slope_pri = slope((pri_x, pri_y))
|
|
if slope_pri >= slope_but_min and slope_pri <= slope_but_max:
|
|
min_presses_fastest = presses_fastest
|
|
else:
|
|
max_presses_fastest = presses_fastest
|
|
|
|
presses_fastest = max_presses_fastest
|
|
pri_x, pri_y = (
|
|
prize[0] - button_fastest[0] * presses_fastest,
|
|
prize[1] - button_fastest[1] * presses_fastest,
|
|
)
|
|
pri_x += button_fastest[0]
|
|
pri_y += button_fastest[1]
|
|
toks = presses_fastest * token_fastest
|
|
toks -= token_fastest
|
|
|
|
|
|
presses_slowest, remainder = divmod(pri_x, button_slowest[0])
|
|
if remainder == 0 and (pri_y == presses_slowest * button_slowest[1]):
|
|
toks += presses_slowest * token_slowest
|
|
else:
|
|
toks = None
|
|
|
|
print(76, toks)
|
|
if toks is not None:
|
|
ttoks += toks
|
|
|
|
print(ttoks)
|