#!/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)