@functools.cache, OITM

OITM

Először - gondolom van, aki nem ismeri, nekem ez a 2. alkalom, hogy beneveztem - pár szó a versenyről: Kategóriákra lehet nevezni, a python és algorimuselmélet (nyelvfüggetlen programozás) kategóriákban versenyzőknek lesz főleg érdekes amit írok (meg aki amúgy kódol pythonban). Adott valami trükkös algoritmuselméleti feladat, ezt kell megoldani minél hamarabb. A feladat leírásának megnyitásától eltelt idő számít, szóval itt nem érdemes 20 percet tölteni azzal, hogy a végén pár milliszekundummal gyorsabban fusson a kód. Ha az algoritmus kellően gyors, onnantól nem baj, ha a nyelv maga nem az. Kódolási időben a python eléggé versenyképes, úgyhogy ezt választottam (a hivatalos megoldások is pythonban vannak egyébként). A két kategória kicsit eltér stílusban, be lehet vetni 1-2 trükköt.

A pythonosnál "indítás előtti" letöltés van, ez alapján már akkor meg lehet írni pl. az inputbeolvasást, amikor még nem ketyeg az óra. Sokszor a feladatra is valamennyire rá lehet érezni, a 4. forduló egyik feladatában volt egy excel file egy csomó e-mail címnek látszó (de nem teljesen jó) sorral, nem volt nehez kitalálni, hogy mailcímeket kell majd validálni, csak a regexpet kellett a feladatnak megfelelő módon átírni.

A másik a nyelvfüggetlen programozásos kategória, itt a múltkorihoz képest bőven van idő (akkor 40 perc volt 1 - vagy az első fordulóban 2 feladatra, most 3 óra 2-re). Itt minden feladathoz 5-5 teszteset van, de ezek lényegesen eltérő méretűek. Az első 3-4 inputon egy buta, brute force algoritmus is sokszor lefut, elég utána ezt javítgatni, és máris van ennyi pontunk. Plusz ekkor már látszik, hogy jó az inputolvasás, a megadott 2 mintán kívül is van pár plusz megoldásunk, a fejlettebb algoritmust össze lehet hasonlítani a butával (ami biztosabban jó, mert egyszerűbb), stb., sok előnye van. Ja, és látszik, hogy mennyi hiányzik még a legnagyobb inputhoz. (pont a legutóbbi fordulónál derült ki, hogy az "unalmas" feladatra adott, buta részstringes megoldásomat könnyen fel tudom gyorsítani, és ez elég is volt)

MEMOIZATION

Sok olyan algoritmus van, ami lassú, de ha a részeredményeket eltároljuk, ezeket felhasználva már gyorsan végzünk. A klasszikus példa erre a Fibonacci. Ha a rekurzív definíciót használjuk, 5 faktoriálisához ki kell számolnunk 4 és 3 faktoriálisát, de 4-hez 3-ét újra, stb.:

def fibo(x):
    if x <= 1:
        return x
    return fibo(x - 1) + fibo(x - 2)

print([fibo(x) for x in range(20)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
print(fibo(150))
# heat death of the Universe :)

Ez persze még lefut, de nagyobb számokra egyre lassabb lesz. A ciklusos megoldással persze nincs ilyen probléma, itt most pár összeadásról van csak szó, de van olyan eset, amikor a rekurzív megoldás egyszerűbb vagy logikusabb. (ahogy írtam, a kódolás ideje többet számít, ha az algoritmus amúgy kellően jó)

A klasszikus, rekurzív megoldást kijavíthatjuk úgy, hogy a függvény végén visszatérés előtt eltároljuk a már kiszámolt értékeket valahova (pl. dict, list), és a függvény elején ha megtaláljuk a választ, rögtön visszatérünk vele. Ezt nem kell megírni, mert a functools része a cache (és lru_cache) dekorátor, amit elég odatenni, és magától megoldja ezt a funkcionalitást:

from functools import cache

@cache
def fibo(x):
    if x <= 1:
        return x
    return fibo(x - 1) + fibo(x - 2)

print([fibo(x) for x in range(20)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
print(fibo(150))
# 9969216677189303386214405760200

Nagyjából ennyit kell róla tudni, ennyire egyszerű használni. Arra kell figyelni, hogy ha a függvény még mástól is függ (pl. az ötféle inputtól, esetleg a mintamegoldások inputjaitól), akkor vagy legyen az is input paraméter, vagy - ha nem akarunk annyit - a legegyszerűbb, ha ez egy beágyazott függvény.

Van egy tesója is, az lru_cache, ez paraméterezhető, lehet limitálni, hogy csak az utolsónak hivatkozott n darab értéket tartsa memóriában. A gyakorlatban ez talán hasznosabb, itt viszont felesleges, mert a program nem fut sokáig, és az adott inputra adott válasz kiszámítása után egyébként is eldobjuk.

OITM feladatok

Nézzük meg a gyakorlatban is a használatát! A boilerplate részt (file-ból számok beolvasása, meghívás, stb.) elhagyom, de a feladatokat pár szóban összefoglalom annak, aki nem versenyzik.

Lift, (nyelvfüggetlen programozás 3. forduló)

A feladat nagyjából annyi volt, hogy adottak n, k, w pozitív egész számok, és egy n hosszú, pozitív egészekből álló weights tömb. A kérdés az, hogy hányféleképp választható a weights tömbből k elem úgy, hogy az összegük pontosan w legyen. Erre azt mondtam, hogy tartsuk nyilván, hány elemet választhatok még (left), a weights melyik indexénél tartok éppen, és hogy az eddigi választásoknak mennyi eddig az összege. Legyen erre egy choose(left, idx, s) függvényünk! Ha kifutottunk a megoldások teréből, visszatérünk 0-val. Ha a left pontosan 0 és az összsúly pont w, akkor ez egy megoldás, visszatérünk 1-gyel. Egyébként meg vagy kiválasztás nélkül továbblépünk ezen a súlyon, azaz choose(left, idx + 1, s), vagy kiválasztjuk, ebben az esetben a left és s értékeit módosítjuk: choose(left - 1, idx + 1, s + weights[idx]). Meghíváskor kell még figyelni, hogy a 0-ás indexnél is kettéágazzunk, így -1-es indexszel kell meghívni a függvényt. Kóddal:

def solve(filename):
    print("---", filename, "---")
    n, k, w, weights = read_my_file(filename)

    @cache
    def choose(left, idx, s):
        if s > w or idx >= n or left < 0:
            return 0
        if s == w and left == 0:
            return 1
        return choose(left, idx + 1, s) + choose(left - 1, idx + 1, s + weights[idx])

    return choose(k, -1, 0)

Az, hogy i-edik súlytól kezdve adott darab és meglévő súly mellett hány megoldás van, nem függ attól, hogy előtte pontosan melyikeket vettük bele. A w miatt a lehetőségek száma is korlátozott, nem fog elszállni a számolás. A cache dekorátor természetesen gondoskodik arról, hogy ne kelljen mindig 0-ról számolni mindent, így gyors. Anélkül nem futna le ésszerű időn belül (első 3 inputra futott le addig, amíg volt rá türelmem). A hivatalos megoldás 3-szorosan egymásba ágyazott ciklusban tölt fel egy tömböt (a klasszikus dinamikus programozásos megoldás), számomra nehezebben áttekinthető, és ha jól tippelem, olyat is kiszámol, amit a rekurzív nem (vagy nem).

Stations, (Python 2. forduló)

Erre a hivatalos megoldás egy szép, lineáris algoritmust ad. Viszont a sajátom is a másodperc töredéke alatt lefut, és ugye a kódolási idő kritikusabb. Ha az "elég jó" kódot gyorsabb összedobni, akkor az is egy jó megoldás. Ráadásul kb. a buta, brute force-ból átalakítható, ha jó irányba indultunk az elején.

A feladat az volt, hogy egy autónak 40 literes (a kódomban MAX_FUEL) a tankja, és 10-10 litert (FUEL_PER_STATION) fogyaszt benzinkutanként. A benzinkutak árai meg vannak adva (ezt chatgpt-vel átrakattam egy xlsx-ból pythonos listába a feladat indítása előtt, nem akartam pandas-ozni itt még - későbbi fordulóban muszáj volt), ez a STATIONS tömb. A kérdés, hogy mennyibe kerül neki a hazaút. Itt sokat gondolkodtam, hogy az utolsó benzinkútnál lakik-e, vagy az után ugyanennyi távolságra, szerencsére elfogadták mindkét megoldást, gondolom többen reklamáltak miatta.

A buta megoldás itt annyi volt, hogy az auto 0, 10, 20, 30 vagy 40 litert tankolhat (a jelenlegi szinttől függően). Ha most fuel ez a szint, az index-edik benzinkútnál tart, és a home indexig kell eljutnia (ezt alapból nem tettem bele, de ugye bizonytalan voltam hol is lakik), akkor legyen egy solve függvényünk, ami visszaadja onnan a minimális költséget! Otthonról már 0, így a rekurzió triviális esete adott, egyébként nem függ semmitől, szóval használhatjuk a cache-t. Ciklussal összeszedjük a maximum 5-féle (de a 10-en kívül általában limitált mit választhatunk, el kell jutnunk a következő benzinkútig, így 0-át csak akkor tankolhatunk, ha van még anélkül is annyi, ill. nem folyhat ki, szóval 40 litert csak csontszáraz tankra tölthetünk) lehetőség költségét, és visszatérünk a minimummal (persze lehet másképp is). Kóddal talán egyszerűbb:

@cache
def solve(fuel, index, home):
    if index >= home:
        return 0
    costs = []
    for fuel_to_tank in range(0, MAX_FUEL + FUEL_PER_STATION, FUEL_PER_STATION):
        if FUEL_PER_STATION <= fuel_to_tank + fuel <= MAX_FUEL:
            costs.append(fuel_to_tank * STATIONS[index] +
                         solve(fuel + fuel_to_tank - FUEL_PER_STATION, index + 1, home))
    return min(costs)

A list comprehension (vagy generátor) szerelmesei esetleg átírhatják egyetlen return-re, ternary operatorra, és min(hosszú kifejezés)-re, mert ennek kb. az a formátuma egyébként is. Nekem ez kevésbé olvasható, de van, aki szereti (a rövid comprehensiont én is szeretem).

@cache
def solve_comprehension(fuel, index, home):
    return 0 if index >= home \
        else min([fuel_to_tank * STATIONS[index] +
                  solve_comprehension(fuel + fuel_to_tank - FUEL_PER_STATION, index + 1, home)
                  for fuel_to_tank in range(0, MAX_FUEL + FUEL_PER_STATION, FUEL_PER_STATION)
                  if FUEL_PER_STATION <= fuel_to_tank + fuel <= MAX_FUEL])

OITM 6

A tavalyi Pythonos (?) kérdéssorban is volt egy feladat, ahol két nehezen érthető, egymást hívó rekurzív függvényt kellett "megjavítani". A kérdés az volt, hogy mennyi f(1000)? Lefuttatva RecursionError: maximum recursion depth exceeded in comparison hibát kapunk:

def f(x):
    if x < 2:
        return 1
    return f(x - 1) + g(x + 1)

def g(x):
    if x < 2:
        return 1
    return x + f(x - 2)

Ez is annyiból állt, hogy a @cache-t kellett eléjük írni, és ciklusban meghívni, hogy érvényre jusson (mindet kiíratni persze felesleges):

from functools import cache

@cache
def f(x):
    if x < 2:
        return 1
    return f(x - 1) + g(x + 1)

@cache
def g(x):
    if x < 2:
        return 1
    return x + f(x - 2)

for i in range(1001):
    print(f'{i}: {f(i)}')

Érdekes módon akkor a hivatalos megoldás is a memoizationt javasolta, de kézzel, a dekorátor valami miatt nem elég ismert. Pedig amikor alkalmazható (ha nem függ a paraméterein kívül mástól, és determinisztikus), tényleg egyszerű a használata. Remélem valamit tettem az ismertségéért. :)

Találtam még egy ilyet a lemezen, ez nem tudom már melyik kategória melyik feladata (talán a Linuxos, ott is volt egy pythonos forduló). Itt is annyi volt a feladat, hogy fusson le, a cache hozzáadása, és - stack overflow ellen - egy ciklikus "rásegítés" megoldotta a dolgot, 0 gondolkodással:

from functools import cache

@cache
def f(x):
    if x == 1:
        return 1
    n = f(x - 1)
    m = n % x
    return x * m + n

print(f(1))  # 1
print(f(2))  # 3
print(f(10))  # 199
print(f(100))  # 169999

for i in range(1, 10002):
    f(i)
print(f(10001))  # ???

ui: Gondoltam, hogy most igényes leszek ha már ennyit írok, de el vagyok szokva az ékezetektől. Ha ilyen hibát láttok, szóljatok, és javítom.

szerk: tl;dr: A Murphy-fele magyarázat kimaradt, aki nem akar annyit olvasni