224 lines
7 KiB
Python
224 lines
7 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import math
|
|
import re
|
|
import sys
|
|
|
|
import rich.progress
|
|
|
|
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))
|
|
|
|
|
|
#
|
|
# def in_range(p: coords, a: coords, b: coords) -> bool:
|
|
# slope_a = slope(button_a)
|
|
# slope_b = slope(button_b)
|
|
# slope_p = slope(p)
|
|
# slope_but_min = min(slope_a, slope_b)
|
|
# slope_but_max = max(slope_a, slope_b)
|
|
# return not (slope_p < slope_but_min or slope_p > slope_but_max)
|
|
|
|
|
|
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)
|
|
print(57, slope_but_min, slope_prize, slope_but_max)
|
|
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_slowest = max_a, max_b
|
|
# slope_fastest, slope_slowes = slope_a, slope_b
|
|
# norm_fastest, norm_slowest = norm_a, norm_b
|
|
else:
|
|
button_fastest, button_slowest = button_b, button_a
|
|
token_fastest, token_slowest = token_b, token_a
|
|
max_fastest, max_slowest = max_b, max_a
|
|
# slope_fastest, slope_slowes = slope_b, slope_a
|
|
# norm_fastest, norm_slowest = norm_b, norm_a
|
|
toks = 0
|
|
|
|
# pri_x, pri_y = prize
|
|
# slope_pri = slope((pri_x, pri_y))
|
|
# while slope_pri >= slope_but_min and slope_pri <= slope_but_max:
|
|
# toks += token_fastest
|
|
# pri_x -= button_fastest[0]
|
|
# pri_y -= button_fastest[1]
|
|
# slope_pri = slope((pri_x, pri_y))
|
|
# # print(98, pri_x, pri_y, slope_pri, toks)
|
|
# pri_x += button_fastest[0]
|
|
# pri_y += button_fastest[1]
|
|
# toks -= token_fastest
|
|
# print(100, token_fastest, toks / token_fastest, toks)
|
|
|
|
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)
|
|
)
|
|
print(120, min_presses_fastest, max_presses_fastest, presses_fastest)
|
|
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
|
|
|
|
print(101, token_fastest, toks / token_fastest, toks)
|
|
|
|
# while pri_x > 0 and pri_y > 0:
|
|
# toks += token_slowest
|
|
# pri_x -= button_slowest[0]
|
|
# pri_y -= button_slowest[1]
|
|
# print(103, token_slowest, toks)
|
|
# if (pri_x, pri_y) != (0, 0):
|
|
# toks = None
|
|
|
|
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
|
|
# dist = norm((pri_x, pri_y))
|
|
# rem_presses, remainder = divmod(dist, norm_slowest)
|
|
# presses_slowest = dist / norm_slowest
|
|
# if remainder == 0:
|
|
# toks += rem_presses * token_slowest
|
|
# else:
|
|
# toks = None
|
|
|
|
#
|
|
# with rich.progress.Progress() as progress:
|
|
# nb_a = max_a
|
|
# nb_b = 0
|
|
# task_a = progress.add_task("Button A", total=max_a)
|
|
# task_b = progress.add_task("Button B", total=max_b)
|
|
# x = nb_a * button_a[0] + nb_b * button_b[0]
|
|
# while nb_a > 0 or x < prize[0]:
|
|
# # print(54, nb_a, nb_b)
|
|
# if x == prize[0]:
|
|
# y = nb_a * button_a[1] + nb_b * button_b[1]
|
|
# if y == prize[1]:
|
|
# tok = 3 * nb_a + 1 * nb_b
|
|
# if toks is None or tok < toks:
|
|
# toks = tok
|
|
# if x >= prize[0]:
|
|
# # print(67)
|
|
# nb_a -= 1
|
|
# # progress.update(task_a, advance=1)
|
|
# elif x < prize[0]:
|
|
# nb_b += 1
|
|
# # print(71)
|
|
# # progress.update(task_b, advance=1)
|
|
# if nb_b > max_b:
|
|
# break
|
|
# x = nb_a * button_a[0] + nb_b * button_b[0]
|
|
|
|
# @functools.lru_cache(4096)
|
|
# def fun(x: int, y: int) -> int | None:
|
|
# if (x, y) == prize:
|
|
# return 0
|
|
# if x > prize[0] or y > prize[1]:
|
|
# return None
|
|
# ba = fun(x + button_a[0], y + button_a[1])
|
|
# bb = fun(x + button_b[0], y + button_b[1])
|
|
# if ba is not None:
|
|
# ba += 3
|
|
# if bb is not None:
|
|
# bb += 1
|
|
# if ba is None:
|
|
# if bb is None:
|
|
# return None
|
|
# else:
|
|
# return bb
|
|
# else:
|
|
# if bb is None or ba < bb:
|
|
# return ba
|
|
# else:
|
|
# return bb
|
|
#
|
|
# toks = fun(0, 0)
|
|
|
|
print(43, arcade, toks)
|
|
if toks is not None:
|
|
ttoks += toks
|
|
# break
|
|
|
|
print(ttoks)
|