Advent of code

◂ 13 décembre 2024 ▸

  Claw Contraption : Trouver une combinaison de mouvements pour aller à des coordonnées (résolution de combinaison linéaire).

Button A: X+79, Y+87

Button B: X+44, Y+14

Prize: X=7384, Y=4824

Button A: X+28, Y+94

Button B: X+79, Y+69

Prize: X=7377, Y=13189

1. code.py
2. code_detZero.py
3. diff_detZero.diffy
4. code_numpy.py
5. diff_numpy.diffy
6. code_naif_sansEquations.py

import re
import math
from typing import Self, Iterable

# Class to show a direction (with orientation) and compare slopes (bigger if more to the left)
class Direction:
    # quadrants
    I, II, III, IV   =  1, 2, -1, 0  # (III < IV < I < II)

    def __init__(self, x:int, y:int):
        if x != 0 or y != 0:
            gcd = math.gcd(x, y)
            x //= gcd
            y //= gcd
        else:
            raise ValueError("A direction cannot be the nul vector.")
        self.x = x
        self.y = y
        self.quadrant = Direction.get_quadrant(self)

    def __repr__(self):
        return f"Direction(x={self.x}, y={self.y}, m={self.y/self.x if self.x else 'vertical'})"

    def __ge__(self, other: Self|Iterable[int]):
        return self.__gt__(other) or self.__eq__(other)
    def __le__(self, other: Self|Iterable[int]):
        return self.__lt__(other) or self.__eq__(other)
    def __gt__(self, other: Self|Iterable[int]):
        if isinstance(other, Iterable):
            other = Direction(*other)
        if not isinstance(other, Direction):
            raise TypeError("Compare Direction to other Direction or iterable, not " + str(other) )
        return other.__lt__(self)

    def __lt__(self, other: Self|Iterable[int]):
        if isinstance(other, Iterable):
            other = Direction(*other)
        if not isinstance(other, Direction):
            raise TypeError("Compare Direction to other Direction or iterable.")
        if self.quadrant == other.quadrant:
            return self.y * other.x < self.x * other.y
        else:
            return self.quadrant < other.quadrant

    def __eq__(self, other: Self|Iterable[int]):
        if isinstance(other, Iterable):
            other = Direction(*other)
        if isinstance(other, Direction):
            return (self.x, self.y) == (other.x, other.y)
        raise TypeError("Compare Direction to other Direction or iterable.")

    @staticmethod
    def get_quadrant(v):
        RIGHT, TOP, LEFT, BOTTOM = True, True, False, False
        return {(RIGHT,TOP):Direction.I, (RIGHT,BOTTOM):Direction.IV, (LEFT,TOP):Direction.II, (LEFT,BOTTOM):Direction.III}[(v.x >= 0, v.y >= 0)]

class Vector():
    def __init__(self, x:int, y:int):
        self.x = x
        self.y = y
        if x == 0 and y == 0:
            self.dir = None
        else:
            self.dir = Direction(x, y)

    def __repr__(self):
        return f"Vect(x={self.x}, y={self.y})"

    @staticmethod
    def get_values(v: Self|Iterable[int]) -> list[int]:
        if isinstance(v, Iterable):
            return list(v)
        else:
            return [v.x, v.y]

    def __eq__(self, other: Self|Iterable[int]):
        x,y = Vector.get_values(other)
        return self.x == x and self.y == y

    def __add__(self, other: Self|Iterable[int]):
        x,y = Vector.get_values(other)
        return Vector(self.x + x, self.y + y)
    def __sub__(self, other: Self|Iterable[int]):
        x,y = Vector.get_values(other)
        return Vector(self.x - x, self.y - y)
    def __mul__(self, factor:int):
        return Vector(self.x * factor, self.y * factor)
    def __radd__(self, other: Self|Iterable[int]):
        return self.__add__(other)
    def __rsub__(self, other: Self|Iterable[int]):
        return self.__sub__(other)
    def __rmul__(self, factor:int):
        return self.__mul__(factor)








PRICES = (3, 1)
DELTA_PART2 = 10_000_000_000_000

# the factor will multiply move_A + move_B to go faster
SCALE_FACTOR_INIT = 2**int(math.log(DELTA_PART2, 2))  

def calc_nb_pushes(move_A, move_B, target):
    # There's never a case where the buttons move in the same direction, but better safe than sorry
    if move_A.dir == move_B.dir:
        print("Oh myyyy, that's another algorithm altogether, then!")
        exit()

    # Let's suppose A moves at higher angle than B. If not, swap!
    if move_A.dir < move_B.dir:
        return reversed(calc_tokens(move_B, move_A, target))

    nb_moves = 0
    move_both = move_A + move_B

    # try very big steps, and then smaller and smaller
    factor = SCALE_FACTOR_INIT
    while factor >= 1:
        move = move_both * factor
        next_target = target - move
        if next_target != (0,0) and move_A.dir > next_target.dir > move_B.dir:
            target = next_target
            next_target = target - move
            nb_moves += factor
        factor //= 2

    if target != (0,0) and move_A.dir > target.dir > move_B.dir:
        target -= move_both
        nb_moves += 1
    
    if target == (0,0):
        return nb_moves, nb_moves
    elif move_A.dir == target.dir and target.x % move_A.x == 0:
        return nb_moves + target.x // move_A.x, nb_moves
    elif move_B.dir == target.dir and target.x % move_B.x == 0:
        return nb_moves, nb_moves + target.x // move_B.x
    else:
        return (0, 0)


with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

def parse_ints(line: str) -> list[int]:
    return [ int(token) for token in re.split('[^-0-9]+', line) if token ]

tokens = {'part1':0, 'part2':0}

for i in range(0, len(lines), 4):
    move_A    = Vector(*parse_ints(lines[i]))
    move_B    = Vector(*parse_ints(lines[i+1]))
    price_pos = Vector(*parse_ints(lines[i+2]))

    for id_part, target in (
                 ('part1', price_pos), 
                 ('part2', price_pos + (DELTA_PART2, DELTA_PART2)) ):
        tokens[id_part] += math.sumprod(calc_nb_pushes(move_A, move_B, target), PRICES)

print("Réponse partie 1:", tokens['part1'])
print("Réponse partie 2:", tokens['part2'])