Zadanie

W dzisiejszym zadaniu musimy zagrać w grę “szpon”, mamy do dyspozycji dwa przyciski A i B wciśnięcie przycisku A kosztuje nas 3 kredyty a B jeden. Każdy przycisk ma zdefiniowany wektor przesunięcia szpona. Naszym zadaniem jest przesunąć szpona na pole z nagrodą, w jak najmniejszym koście w kredytach.

Wynikiem jest minimalna suma kredytów potrzebna do zdobycia nagród w każdej grze gdzie jest to możliwe.

Przykładowe dane:

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=12748, Y=12176

W powyższym przykładzie mamy dwie gry, pierwsza jest niemożliwa do rozwiązania, z kolei w drugiej rozwiązaniem jest wcisnąć przycisk A 80 razy i przycisk B 40 razy, co daje razem 280 kredytów

$80 \cdot 3 + 40 = 280$

Rozwiązanie

Zacznijmy od parsowania danych, możemy to w łatwy sposób zrobić za pomocą wyrażeń regularnych:

import re

PATTERN = (
    r"Button A: X\+(\d+), Y\+(\d+)\n"
    r"Button B: X\+(\d+), Y\+(\d+)\n"
    r"Prize: X=(\d+), Y=(\d+)"
)

res = 0
for x in re.finditer(PATTERN, sys.stdin.read()):
    xa, ya, xb, yb, xd, yd = map(int, x.groups())
    # xa,ya to wektor przesunięcia przycisku A a xb,yb przycisku B 
    # xd i yd oznaczają koordynaty nagrody (d jak destination)

Co dalej? Moją pierwszą myślą było rozwiązanie tego za pomocą programowania dynamicznego. Spróbujmy przygotować rekurencyjną funkcję która mogłaby znaleźć nam wynik.

@cache
def moves(x, y):
    if x == xd and y == yd:
        return 0  # nie musimy wydać więcej żetonów jak znajdziemy się na polu nagrody

    # jeśli przestrzelimy nagrodę żadna ilość tokenów nie będzie w stanie jej zdobyć
    if x > xd or y > yd:
        return float("inf")

    # wracamy ilość żetonów lepszego ruchu (tego co kosztuje ostatecznie mniej żetonów)
    return min(3 + moves(x + xa, y + ya), 1 + moves(x + xb, y + yb))

Gdy uruchomiłem kod dostałem błąd:

RecursionError: maximum recursion depth exceeded

Nie wróży to dobrze ale spróbuję zwiększyć maksymalną głębokość rekurencji, końcowy kod wygląda tak:

import re
import sys
from functools import cache

sys.setrecursionlimit(1500)

PATTERN = (
    r"Button A: X\+(\d+), Y\+(\d+)\n"
    r"Button B: X\+(\d+), Y\+(\d+)\n"
    r"Prize: X=(\d+), Y=(\d+)"
)

res = 0
for x in re.finditer(PATTERN, sys.stdin.read()):
    xa, ya, xb, yb, xd, yd = map(int, x.groups())

    @cache
    def moves(x, y):
        if x == xd and y == yd:
            return 0

        if x > xd or y > yd:
            return float("inf")

        return min(3 + moves(x + xa, y + ya), 1 + moves(x + xb, y + yb))

    m = moves(0, 0)
    if m != float("inf"):
        res += m

print(res)

O dziwo zwiększenie limitu z domyślnego 1000 na 1500 działa! Program nie jest jakiś super wydajny ale wystarczy to na razie. Zobaczmy część drugą.

Część 2

Okazuje się że w tej części do obu koordynatów nagrody musimy dodać liczbę 10000000000000 💀.

Nawet nie próbuję uruchamiać mojego poprzedniego rozwiązania, ewidentnie potrzebne jest tu bystrzejsze podejście.

Pomysł

Możemy zformułować problem minimizacji kosztu i użyć jakiegoś solwera do programowania liniowego. Zauważmy że problem można przedstawić w taki sposób: $$ min~3a + b \\ a x_a + b x_b = x_d \\ a y_a + b y_b = y_d $$ Nasze jedyne zmienne to a oraz b, i muszą one być w wyniku liczbami całkowitymi, co nieco utrudnia sprawę solverowi.

Implementacja z użyciem scipy.optimize

part2 = 0
for x in re.finditer(PATTERN, sys.stdin.read()):
    xa, ya, xb, yb, xd, yd = map(int, x.groups())
    xd += 10000000000000
    yd += 10000000000000

    c = [3, 1]
    A = [[xa, xb], [ya, yb]]
    b = [xd, yd]

    res = linprog(c, A_eq=A, b_eq=b, integrality=[3, 3])

    print(res.status)
    if res.status == 0:
        an, bn = map(int, res.x)
        part2 += int(res.fun)

print(part2)

Wreszcie na coś przydały się te studia! Uruchamiamy kod i… Otrzymujemy błędny wynik :(

Okazuje się że solver używa liczb zmiennoprzecinkowych pod spodem i przy tak dużych wartościach, pojawiają się błędy numeryczne, może być ciężko uzyskać rozwiązanie tą drogą.

W tym momencie sprawdziłem jeszcze kilka innych solverów: gurobi, pulp_cbc jednak, każdy z nich miał taki sam problem, uznałem że jest to chyba ślepy zauek i muszę szukać innego rozwiązania.

Eureka

Po rozpisaniu sobie tego jeszcze kilka razy na papierze stało się jasne coś co powinienem był zobaczyć dużo wcześniej. Gdybym pamiętał coś więcej z algebry liniowej to zauważyłbym że dla każdej gry są dwie opcje, albo mamy jedno rozwiązanie albo nieskończenie wiele. Układ równań (który z resztą napisałem na górze), można bardzo łatwo rozwiązać licząc, odwrotność macierze 2x2, jako że jestem leniwy i nawet tego nie chce mi się robić użyję numpy żeby mi rozwiązał cały układ równań.

import re
import sys

import numpy as np

PATTERN = (
    r"Button A: X\+(\d+), Y\+(\d+)\n"
    r"Button B: X\+(\d+), Y\+(\d+)\n"
    r"Prize: X=(\d+), Y=(\d+)"
)

results = [0, 0]
TO_ADD = [0, 10000000000000]

for x in re.finditer(PATTERN, sys.stdin.read()):
    for i in range(2):
        xa, ya, xb, yb, xd, yd = map(int, x.groups())
        xd += TO_ADD[i]
        yd += TO_ADD[i]

        A = np.array([[xa, xb], [ya, yb]], dtype=np.int64)
        b = np.array([xd, yd], dtype=np.int64)
        resa, resb = np.round(np.linalg.solve(A, b))

        # sprawdźmy tylko czy po zaokrągleniu wynik jest poprawny
        if resa * xa + resb * xb == xd and resa * ya + resb * yb == yd:
            results[i] += 3 * resa + resb

print(int(results[0]))
print(int(results[1]))

W ten sposób otrzymujemy kod który rozwiązuje obie części prawie natychmiastowo.

Podsumowanie

Zadanie było bardzo ciekawe, na początku za bardzo myślałem jak programista a za mało jak matematyk. Nauczyłem się też czegoś o programowaniu liniowym, nie zawsze jest ono najlepszym rozwiązaniem, otrzymywanie dokładnych wyników nie jest takie proste kiedy nakładamy ograniczenia że zmienne muszą być liczbami całkowitymi.

Zadanie#

Rozwiązanie#

Część 2#

Pomysł#

Implementacja z użyciem scipy.optimize#

Eureka#

Podsumowanie#