@functools.cache, OITM

Sok másik hupperhez hasonlóan én is beneveztem a mostani OITM-re (megmerettetes.hu). Az első 4 fordulóban többször használtam a kedvenc dekorátoromat, gondoltam írok róla pár szót.

( gelei v | 2023. 11. 09., cs – 10:21 )

Offtopik, de miert kellett pentek este tizre tenni az utolso 3 fordulot? Eloszor azt hittem, csak eliras. Konkretan heti 3x lenne este tiz utan kezdodo feladatsor. Ne mar. :D

Ez engem is zavar. Mondjuk ha hasonló nehézségű lesz, mint a 4. forduló, akkor nem kell rá 3 óra, fél 8-ra végzel. Ha olyan, mint a 2. meg 3., akkor fél 9, még az is belefér. A múltkori jobb volt, hogy adtak mindenre 1-1 napot, és akkor indíthattad azon belül, amikor akartad.

Idén 8 kategóriára jelentkeztem, bár ebből többre inkább kíváncsiság miatt, mint azért, mert lenne reális esélyem. Valószínűleg többet ott fogok ebből hagyni a beosztás miatt, csak hát van összesített kategória is. :-/

szerk: Ja, aki meg a "table-wrapper" classt rápakolta az Eredményeim dobozra, azt beíratnám valami UX tanfolyamra. Jó, mindenféle extensionnel megoldható, de ne kelljen már! Mondjuk nem ez az egyetlen ilyen hiba az oldalon.

A strange game. The only winning move is not to play. How about a nice game of chess?

Nekem mas az orarendem, tuti nem fogok vegezni fel kilencre. :) Sajnos a hetfo es pentek este tizes sav a legrelevansabb nekem kb., de a csutortokieket szerintem skippelni fogom.

Amugy ertem a logikat, hogy miert kell a szuk idosav, meg azt is ertem, hogy megneztek, mikor tolti ki az atlag a feladatokat, de pentek este tiz? Nincs jobb dolgotok pentek este? :D

En ezt ertem, meg azt is, hogy mi szukseg van az idoablakos rendszerre, de hogy en nem fogok este tizkor versenyezni, raadasul heti 3x, az hotziher. Most azt tegyuk felre, hogy este tizkor mar aludni szoktam, akkor is ott van, hogy heti haromszor nem szervezhetek magamnak estere programot, a penteket is beleertve.

Majd jovore raprobalok egy, max ket kategoriaban, aztan jonapot. Lehet, hogy mar nem en vagyok ennek a celkozonsege. :)

( enpassant v | 2023. 11. 09., cs – 11:20 )

Gratulálok!

A fibonaccihoz annyit, hogy ha az elejétől mész felfelé, akkor nem kell semmit sem memo(r)izálni, hiszen mindig meglesz a korábbi két érték.

Pl. Scalaban:
 

  def fibonacci(n: Int) = {
    def fib(current: Int, next: Int, index: Int): Int = {
      if (index <= 1) next
      else fib(next, current + next, index - 1)
    }
    fib(0, 1, n)
  }

Ráadásul ennél a megoldásnál működik a tail call optimization, így ciklusra fordul és nem kapunk stackoverflow hibát.

Ez a scalas megoldás jópofa, de ez kb. a ciklussal kiszámolható módszer rekurzívra átírva. (a szokásos, amikor shiftelgeted két változó tartalmát az összegükkel, csak itt paraméterben és nem változóban tartod a két értéket). Nem tudom, a scala támogat-e default paramétereket, ha igen, talán az indexet tenném az elejére, a currentet és nextet meg utána default 0 és 1 paraméterrel, és akkor közvetlenül hívható, plusz más kiinduló értékektől is megy, ha arra van szükség (nekünk anno matekórán voltak ilyen feladataink módosított Fibonaccival meg Pascal háromszöggel is, az eredetire általában vissza lehetett vezetni).

Egyébként teljesen igaz, a Fibonaccira vannak sokkal praktikusabb megoldások is. A legegyszerűbb szerintem pont a python.org nyitóoldalán díszelgő ciklusos megoldás, ezért is írtam, hogy "A ciklusos megoldással persze nincs ilyen probléma, itt most pár összeadásról van csak szó", az még egyszerűbb, és érthetőbb. Erre gondolok (itt n-ig számol, nem ennyi darabot):

# Python 3: Fibonacci series up to n
>>> def fib(n):
>>>     a, b = 0, 1
>>>     while a < n:
>>>         print(a, end=' ')
>>>         a, b = b, a+b
>>>     print()
>>> fib(1000)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Plusz ha már Fibonacci, ott a Binet formula, amiből direktben számolható minden elem, de a legszebb az benne, hogy a sok gyök öt miatt ránézésre az sem világos, hogy egyáltalán racionális számot ad. A python úgy emlékszem, nem tud tail call optimizationt (JS sem, azt is próbáltam), itt kevesebbet használják a rekurziót, gondolom amiatt nem foglalkoztak vele. Úgy vettem észre, jellemzően a funkcionális és deklaratív nyelveknél működik (Prolognál biztosan).

A Fibonacci - a gyakorlati használata mellett - viszont jó állatorvosi lónak, bemutatja ezt a jelenséget, azt, hogy rekurzívan néha könnyebb átlátni a megoldást (mi a triviális eset, utána az előző kettő összege, kész is a definíció és a kód), és hogy hogyan lehet gyorsítani ebben a konkrét esetben.

A strange game. The only winning move is not to play. How about a nice game of chess?

( egeresz | 2023. 12. 21., cs – 22:20 )

De szép!

Összeszedem mi volt meg:

OITM7, forduló3, Lift: ugye, ez volt meg nekem előszö, rekurzív forma, de saját cache megoldás, sok-sok sor

OITM7, forduló5, Mézeskalács osztozkodási probléma, 4 különböző implementációt készítettem, mire egy jó lett, a nyertesben már a @cache dekorátort használtam

OITM7, forduló7: Kati néni legkevesebb mennyi erőfeszitéssel jut át a 3129×2426 parcellából álló réten. Ez jópofa volt, a rekurzió limitbe beütötte e afejét a @cache által megtámogatott rekurzív megoldásom, ezen "cache warmup" segítségével lendültem túl, amit te fentebb "egy ciklikus 'rásegítés'" néven emlegettél.

 

Ez csak 3 forduló, 3 feladat, de számomra a verseny sava-borsát adta. Az olyan feladatok se rosszak, mint "pontosan 3 osztója van", innen rá kell jönni, hogy ezek pontosan a primnégyzetek; azonban ez inkább tiszta matek, nem programozás. Míg például a négyszög osztályozási feladat az nem tesztett. Egy óra unalmas kódolást egy óra unalmas debuggolás követte, nem is lett maxpontos :-(