Advent of Code 2024

Algoritmusok

Idén is indul az Advent of Code "karácsonyváró játék". Hajrá! :) 

 

Indítottam egy HUP leaderboard-ot: 2567216-8c01cc3b

🎅

 

(a privát leaderboard-ok csak login után látszanak)

  • 3737 megtekintés

( ulysses v | 2024. 12. 02., h – 13:00 )

Csatlakoztam, egyelőre a tegnapit csináltam csak meg.

( kleinie | 2024. 12. 02., h – 15:47 )

Lehet idén én is benevezek koca programozóként. Szerintem jópofa! Már több éve figyelem, de nem éreztem erőt, hogy nekiálljak.

Egyszer találtam youtube-on: https://www.youtube.com/@TsodingDaily Elvetemült arc, 2020-ban minden napot más nyelven csinált, 2021-ben meg az egészet TempleOS-ben, HolyC-ben.

Csak nekem nem jó a HUP leaderboard? Szerintem nem jó helyre mutat a link.

Annyira nem fura az, csak ha menet közben ki-belépkednek emberek, az szét tudja túrni kicsit a pontokat:

[Local Score], which awards users on this leaderboard points much like the global leaderboard. If you add or remove users, the points will be recalculated, and the order can change. For N users, the first user to get each star gets N points, the second gets N-1, and the last gets 1. This is the default.

( goodbyte v | 2024. 12. 02., h – 16:58 )

quemu adventi calendar nincs ?

“Luck Is What Happens When Preparation Meets Opportunity" - Seneca

( enpassant v | 2024. 12. 03., k – 07:34 )

Csatlakoztam én is. Zig-ben tolom, ha valakit érdekel a megoldás, a github-omon megnézheti. ;-)

( mitch0 | 2024. 12. 05., cs – 10:51 )

Az 5. feladatnál a ti megoldásotok mit mond erre az inputra?

 

1|3
3|5

1,2,3,4,5
5,4,3,2,1
5,0,0,3,0,5,0,1,0,0,3,0,0,0,3

5,0,0,3,0,5,0,1,0,0,3,0,0,0,3

A feladat leírásából következik, hogy egy sorban nem fordulhat elő két azonos szám. Így ez UB, a feladat különböző helyes megoldásai más eredményt adhatnak rá:

1,3,3,3,5,5,0,0,0,0,0,0,0,0,0
0,0,1,3,3,3,5,5,0,0,0,0,0,0,0
0,0,0,0,1,3,3,3,5,5,0,0,0,0,0
0,0,0,0,0,0,0,1,3,3,3,5,5,0,0

Én a lehető legkevesebb cserével oldottam meg a rendezést, vagyis amire nincs szabály, az marad a helyén:

1,0,0,3,0,3,0,3,0,0,5,0,0,0,5

Igen, az eredeti példám nem valid a kontextus miatt, itt egy olyan ami szerintem valid, viszont szerintem sok megoldás nem működik rá:

10|11
10|20
10|21
11|20
11|21
20|21
20|30
20|31
21|30
21|31
30|31
30|40
30|41
31|40
31|41
40|41
40|51
41|51

51,40,41,30,31,20,21,10,11
30,10,40,11,20,41,21,31,51
40,51,20,21,11,41,31,10,30

itt a 2. részben 90 a jó válasz

( joco01 v | 2024. 12. 05., cs – 15:57 )

A feladatok túl könnyűek, és a több tízezer játékos közül csak az első 100 kap pontot. Ez így sajnos sokkal inkább azon múlik, hogy ki hány órakor tud felkelni...

Én nagyon messze vagyok még a 100. idejétől is, így leginkább nem azon múlik mikor kelek fel. ;-)

Ennyi idő alatt kb. még el sem olvasom.

Pl. Ezek voltak az idők:

1. nap

1. 4 mp, 9 mp

100. 1:24, 2:31

...

5. nap

1. 14 mp, 55 mp

100. 1:58, 3:43

Igen, szerintem is csak a móka része az érdekes és az új vagy kedvenc nyelv tanulása, használata.

Én pl. Javaban dolgozom és korábban Scala-t, most Zig-et, a jövőben pedig vagy Gleam vagy Roc nyelvet fogok használni. ;-)

Sok esetben nem is a probléma a legnagyobb hátráltató, hanem a nyelvi elemek ismeretének hiánya.

Az úgy van, hogy általában lusta vagyok végiggondolni, hogy egy ciklus hol ér véget és hol kezdődik (tömbhatárok) minden ciklust inkább kidebuggolok. Erre itt azért  nem adok magamnak időt, így a szokásosnál sokkal jobban figyelek a ±1 -ek jelentőségére. Ennek meglett a lenyomata, már két napja tömbindex-határokkal álmodom. Hogyaszondja, a[di+1]

Számomra viszont ez önképzési idő, nem sajnálom rá az erőforrásaimat.

Dijkstra határokat használva (alsó határ inkluzív, felső határ exkluzív, és alapesetben nulla az alja, vagyis 0 <= i < n) egy idő után szinte nem is kell az indexeken gondolkozni :) Az ilyen intervallumokat "láncolni" is kézenfekvő, a tartalmazott elemek száma is szép (felső mínusz alsó), hátralévő elemek száma szép (felső mínusz ami éppen következik: n-i), üres intervallum ábrázolása nem gond.

A visszafelé számláló ciklus mindig extra hitvita; én ezt szeretem:

size_t i;

i = ARRAY_SIZE(a);
while (i > 0) {
  --i;
  a[i];
}

Ez pontosan annak a ciklusnak a fordítottja (beleértve az "i" kezdeti és végső értékét is) , hogy

for (i = 0; i < ARRAY_SIZE(a); ++i) {
  a[i];
}

(Szokták olyan formában is írni, hogy

size_t i;

i = ARRAY_SIZE(a);
while (i-->0) {
  a[i];
}

de én ezt nem szeretem, mert az "i" végső értéke itt mindig SIZE_MAX.)

python, aminek megvaan a maga extrém jellegzetessége, pl a[-1] az a tömb utolós eleme, a[n:k] az a résztömb (n,k dijkstra határral értelmezve)

[from:to:step]

a visszafelé (n-k, dikjstra határ, visszafelé)  a[k-1:n-1:-1] viszont, ha n==0; akkor ez nem működik, mert a[20:-1:-1] mindig üres, de a[20::-1] ez már működik, de más szintax, mint a többi; Ha erre valaki tud könnyű megoldást, már megérte a posztom.

és tipikusan többindexes tömbbökkel dolgozom, hogyaszondja i,j körüli 3x3 -as rács: a[i-1:i+1, j-1:j+1]  ez viszont i==0 | j==0 esetén csattan ésatöbbi.

C-re visszatérve,

while (i-->0) {
  a[i];
}

Nem szoktam ilyet írni. "i--" és kisebbségjellel egy kifejezésben, a C erős nyelv, nem mondom, de több hibám volt már abból, hogy a ++i, i++ dolgokat kifejezésbe raktam, mint abból, ha nem. Ettől még elismerem, hogyha mindenütt a

while (i > 0) {
  --i;
  a[i];
}

formát használod, akkor megszokod és nem lesz furcsa/idegen, hogy a ciklus elején van a változóléptetés. Ezen most egy kicsit gondolkodom.

mit szólnál az a[n:k][::-1] alakhoz? jajjderonda. de nem is jó, mert a [::-1] az shallowcopy, emiatt következő kifejezés nem változtat:  a[n:k][::-1] = 0

 a[k-1:n-1:-1] = 0 pedig változtat.

Ugyanez numpyvel már lefut, de nem szeretem azokat a kifejezéseket, amikor tudni kell, hogy ez numpy view vagy copy

a[1:3, 2:4][::-1, ::-1] = [[1,2], [3,4]]

Igazából nem szoktam ciklusokat írni a tömbre, mert numpy powwa.

Ha bizonytalan vagy segít ha kipróbálod kis számokra. A klasszik off-by-one hibák már kicsi számokal is előjönnek, és úgy könnyű elbábozni velük fejben.

Például: for(int i=0;i<arr.length<++i)) arr[i]=i*2; Képzeld el, hogy arr.length==0 és hogy arr.length==1! Jól működik? Igen! Akkor a többire is jól fog!

Az úgy van, hogy általában lusta vagyok végiggondolni, hogy egy ciklus hol ér véget és hol kezdődik (tömbhatárok) minden ciklust inkább kidebuggolok. 

Ha Gleam-et használsz, akkor tuti nem lesz ilyen problémád, mivel se tömb nincs benne, se semmilyen ciklus ;-)

Egyéb problémáid viszont bőven lesznek, hogy akkor miként is valósítsd meg azt, amit tömbbel és ciklussal csináltál volna. ;-)

( KGer | 2024. 12. 05., cs – 20:02 )

pont mostanában gondoltam rá újra kéne mert régen mennyire jó volt

egész éjszakákat tudtam ülni 1-1 fölött

( mitch0 | 2024. 12. 08., v – 10:32 )

Hm. A 8. nap leírása kétértelmű (avagy rossz):

 

In particular, an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - but only when one of the antennas is twice as far away as the other.

 

Ez alapján ez is valid lenne:

A.#...A

de a példák alapján nem az. Hasonlóan a 2. részben ilyenkor az egész sor jó lenne a leírás szerint, de mégsem. Hóhum :)

Csak én egyszerűsítettem le a második rész megoldását? Az első részhez volt két sorom, ahol hozzáadom a deltát egyik és másik irányban az antenna-párhoz. A második részben csak e köré tettem egy ciklust, hogy a delta 0..50-szeresét adjuk hozzá. Így volt a legegyszerűbb, csak nem a legszebb.

( joco01 v | 2024. 12. 09., h – 12:46 )

A mai nap az első, amikor elkezdett számítani a jó algoritmus. A második rész első nekifutásra elfutott vagy egy percig. Azóta gyorsítottam rajta a rend kedvéért. De úgy tűnik, egyre nehezebb lesz.

( mitch0 | 2024. 12. 11., sze – 09:03 )

A 11. második felét 297GB memória használatnál lelőttem, a szó szerinti implementáció még c++-ban sem fut le :)

4 implementációt csináltam

az 3dikra már agyon optimalizáltam mindent, level45ig jutott el, level50nél már kihalt homokórával

a 4diknél vezettem be a titkot és fut le 100 ms alatt (java desktop)

level100 136ms

ez fölött már túlcsordulnak a long-jaim

level999 1632ms, csak már rossz végeredményt ad de elvileg bejárja amit be kell

Erről beszélünk, ugye? Day 11 (itt a levelekkel kicsit megzavartál :))

Kíváncsiságból lefuttattam mpz-vel:

C++ version:
1: 229043
2: 272673043446478
999: 149784474074557596060658185924435735870657851281404488941470264305379667846467964209924079184995308629484899577695587309030012929957693325743824253473503286459952467420750171739016867

real    0m0.752s
user    0m0.747s
sys     0m0.004s

 

uint64_t-vel persze gyorsabb, de rossz eredményt ad:

C++ version:
1: 229043
2: 272673043446478
999: 17455153103448592035

real    0m0.277s
user    0m0.271s
sys     0m0.004s

3 órát töltöttem azzal hogy a rekurzív implementációmat lecseréljem loop implementációra, azt remélve így sokkal gyorsabb lesz (java)

sikerült megírnom, de nem lett gyorsabb, sőt 20%al lassabb lett, viszont a kód sokkal olvashatatlanabb és érthetetlenebb

aztán még optimalizáltam rajta változókban és végül kb ugyanolyan gyors lett és teljesen olvashatatlan

ez volt a tanulságom

( Raynes v | 2024. 12. 13., p – 13:57 )

Ennek régen se volt értelme. Mármint nem ezeknek a programozási gyakorlatoknak, hanem hogy ez a karácsonnyal, adventtel van összekötve, ezeket az év bármelyik szakaszában lehet csinálni, jók is gyakorlásra.

“Windows 95/98: 32 bit extension and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company that can't stand 1 bit of competition.”

Az ízlések és pofonok különbözőek. Lehet edzőterembe járni szeptember 12-től kezdődően, vagy akár január elsejétől is. Az utóbbira jellemzően nagyobb az igény. S ha van valaki, akivel együtt edz az ember, akkor nagyobb a motiváció, tovább tart ki a lelkesedés. Ebben az esetben az eredetileg ötven emberre tervezett mulatságban - 9 év elteltével - már másfél millióan próbálnak részt venni. A reddit-es csoport decemberben felrobbant, nem lehet végiggörgetni az egy nap alatt beérkező mémeket, segítségkéréseket. (Szerencsére a megoldásoknak van külön megathread, bár a mémekből is rengeteg dolog kiderül a megoldási módszerekkel, vagy magával a megoldással kapcsolatban.)

Ez a közösség, mely

  • jellemzően segíti a programozással éppen ismerkedőket,
  • lehetőséget ad a versenyzésre egy munkahelyi kollektívában, vagy éppen egy családban

adja meg annak azt a plusz motivációt, amely nincs meg egy egyszerű feladatsorral.

Az időeltolódás miatt Európa számára a globális versenyben nem érdemes részt venni, de lokális dicsőségtáblák nagy számban létesülnek. Miután kétszer-háromszor már kigyűjtöttem mind az ötven csillagot (ez is tekinthető egy kihívásnak), az nem hajt, hogy minden feladatot annak kitűzése napján oldjak meg. Viszont újabban mindig kiválasztok egy számomra új programozási nyelvet, és az AoC feladatok adják meg azt az irányt, mellyel próbálom elsajátítani a nyelvet. Itt viszont nem percekben hanem inkább órákban, esetleg napokba telik míg munka mellett az ember megold egy feladatot. Jómagam is bármikor megmerítkezhetnék egy újabb programnyelvben, de most is extra motivációt jelentett az AoC időszak. (Igaz, bő egy hetes késésben vagyok már most is, de jelenleg akadnak fontosabb teendőim is.)

Még egy adalék: a fiam tehetséges, de lusta. Hosszú évek munkájával sikerült elérni, hogy oldogassa ezeket feladatokat - azzal a céllal, hogy készüljön különféle programozási versenyekre -, s immár már szórakozásból, mindenfajta ráhatás nélkül követi a feladatokat s próbálja azokat megoldani, lehetőleg még aznap. (Még úgy is, hogy az AoC nem vizsgaidőszak-kompatibilis.)  

Ha valakit esetleg érdekel az AoC háttere, akkor nemrég felkerült egy konferencia-előadás a verseny kitalálójával: https://www.youtube.com/watch?v=uZ8DcbhojOw

AL

  • inicializálok egy 2*2-es mátrixot 0 érékekkel
  • soronként beolvasom az inputot
  • a negatív sebességkomponenseket nemnegatívvá teszem modulo 101 ill. 103
  • p1 := p + 100*v (joggal feltételezhető, hogy túlcsordulás nem lesz)
  • (p1.x mod 101) és (p1.y mod 103) összehasonlítása rendre 50-nel ill. 51-gyel, az eredmények által meghatározott elemét a mátrixnak eggyel növeljük (abba a kvadránsba esik a robot 10mp után); ha egyenlőség adódik bármelyik összehasonlításnál, akkor nem növelünk semmit
  • ha minden sort beolvastunk, összeszorozzuk a mátrix négy elemét

Erről volt szó?

Azt kérdezték a második részben, hogy mikor áll össze a robotok mozgása egy jól felismerhető karácsonyfává.

Namost vagy van univerzális karácsonyfa felismerő mintaillesztőd, vagy végignézel szemmel pártízezer frame-t, vagy?

És a karácsonyfa környékén volt párszáz robot összevissza, zajnak.

Ez tényleg egy kicsit más jellegű feladat volt a többinél.
Egyébként az első részre e a válaszod igen.

> Namost vagy van univerzális karácsonyfa felismerő mintaillesztőd, vagy végignézel szemmel pártízezer frame-t, vagy?

Mintaillesztés: ha keresel egy hosszú egyenes vonalat, vagy folyamatosan kitöltött részt, vagy ütközés nélküli állapotot, vagy a koordináták stddev-jét minimalizálod, az mind kiadja a karácsonyfát.

Olyan is volt, aki kirenderelte az összes lehetséges állapotot egyetlen képbe, ránézett, és rögtön látszott a sok zaj között az ábra.

Kíváncsi vagyok, a feladat kiötlője hogyan gondolkodott. Szerintem elindult a kész karácsonyfából, minden pontjához (minden robothoz) rendelt egy random sebességvektort, megtekerte 12 ezer körre, és ami így adódott (negált sebességvektorokkal), az lett az első feladatfél kiinduló állapota :)

( joco01 v | 2024. 12. 14., szo – 16:02 )

Kíváncsi vagyok attól, aki a leaderboardon felül van, meséljétek már el, direkt 6-kor keltek a verseny miatt, vagy egyébként is véletlenül pont jó az időpont nektek? Én 7-kor még gondolkodni se tudok, 8-kor viszem a gyereket iskolába, általában 9-re kész vagyok a feladatokkal, és addigra már mindenki beelőzött.

Nekem van amikor belefért munka előtt a feladat, van amikor csak munka után, vagy csak másnap.

Az, hogy mennyi a pontszámod, az egy dolog, fontosabb, hogy élvezd és minél több csillag legyen ;-)

Én pl. most fogok átváltani Gleam-re. Eddig se voltam túl gyors a Zig-gel, mindent doksikból kell kinézni, és szenvedni kellett még az unsigned - signed átváltogatásokkal is, mivel még azt sem engedi együtt használni. Most a Gleam-mel kezdődik minden elölről. A sebességem újra drasztikusan esni fog. ;-)

A mai feladatot megcsináltam Zig után Gleam-mel is. Így, hogy tudtam mit hogyan kell megoldani, így is négyszer annyi idő volt, mint a Zig-gel, pedig abban sem vagyok egy ász.

( egeresz | 2024. 12. 14., szo – 19:45 )

Jó a buli. 9 nap késéssel kezdtem, ma értem utol a mezőnyt (day14) köszi a leaderboard meghívást.

( kleinie | 2024. 12. 14., szo – 23:12 )

Na most, hogy már szabadságon vagyok, talán lesz időm elkezdeni. Remélem.

( Nyosigomboc v | 2024. 12. 15., v – 09:58 )

Irna par szot valaki errol az esemenyrol?

Azt ertem, hogy kb. algoritmuselmeleti feladatok vannak (mint az OITM nyelvfuggetlen kategoriaja). Milyen nyelveken lehet? Vagy sajat gepen fut, ugyhogy azzal oldom meg, amivel akarom?

Mi ez a leaderboard? Jol ertem, hogy az szamit, hogy milyen gyorsan oldod meg, nem az, hogy milyen gyors a futo kod?

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

Egy text fájl a bemenet, amit letöltesz, és egy szám a kimenet, amit be kell írnod egy mezőbe. Nálad fut, és úgy oldod meg, ahogy akarod.

A globális leaderboardot inkább felejtsd el, valószínűleg AI-s csalókkal van tele az egész. De most már szerintem a többi leaderboardot is felejtsd el ennyi idő után, de annak még van értelme, hogy megoldod az összes feladatot.

Jupyter/pythonban írom. Valóban leginkább a OITM nyelvfüggetlen kategoriájára hajaz. Nekem eddig 45 pec - 150 perc között adták meg magukat a problémák. Mivel nincs ténylegesen időkényszer/időkeret, így lazán csinálom, nem stresszel annyira, mint az OITM.

Nem értek egyet az elöttem szólóval, hogy AI-s csalókkal lenne teli a lederboard. Ugyanis rank#100 stabilan hozza az én időm hatodát, ha nehezebb a feladat akkor azok is hosszabbak. Persze, egy 0:0:9 -es eredmény erősen meredek, hogy egyáltalán hogyan olvassa el? De igazából elolvasni is elég a feladat felét, a szabad szöveges rizsát nem kell.

"teli" a leaderboard. Lehet hogy vannak benne. De semmiképpen nem teli. Svsz ilyen feladatot egy AI helper mostanában (2024.12) nem tud megbízhatóan megoldani.

De ha valakinek van 300 accountja, és intervallum-iteratíve bepróbálgatja (hiszen az oldal kiirja, hogy "your answer is too hight" akkor kis számoknál meglehet géppel, iteratíve.  De akkor meg nem a saját nevén lesz. Mégis inkább azt mondom, hogy nem AI, hanem inkább egy kis eki és mondjuk 3 ember eXtreme Programming módban, saját klienssel, ami bele van építve a munkakörnyezetébe (ha tesztre lefut, lefuttatja az élesre is és posztolja automatán)

A sok accountal és a közelítésekekl az a baj, hogy randomizáltak az input file-ok. Tippre mindenkinek más. Ebből következik, hogy az eredményként kapott számok is accountonként mások.

Ilyen eredményhez, biztosan közelítéses módszert használnak, bár az AoC csapat tett be várakozást két próbálkozás közé...

Koszi neked es Joconak is!

Az nem all igy ossze, hogy akkor miert szallnak itt a topicban ide-oda a millisec-ek. Bonuszkent persze meg lehet oldani, de itt megint az van, hogy a kodolas sebessege tobbet szamit. Mondjuk van harom azonos algoritmust hasznalo kod, elso C, masodik Java, harmadik meg Python. Legyen sorban 50ms, 300ms meg mondjuk 2 perc a futasidejuk. Viszont ugyanazt C-ben vagy Javaban lekodolni nem 2 perccel lesz tobb a Pythonehoz kepest (ha hasonloan ertesz hozzajuk), szoval innentol a minel kenyelmesebb, minel magasabb absztrakcios kepessegu nyelvek leverik a hatekonyabbakat.

Tanulasnak vagy kihivasnak persze meg lehet oldani Zigben, Rustban, Brainfuckban, vagy akarmi masban is, de nem lesz kompetitiv.

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

A milliszekundumok az inkább csak önfényezés, programozóversenyen alap :)

Általában elmondható, hogy ha egy feladatot brute force-szal akarsz megoldani, évmilliókig fut, ha pedig szépen oldod meg, akkor pár másodperc. Tehát a verseny szempontjából tényleg mindegy, hogy 1 vagy 0.1 másodpercről van szó. Amúgy eleinte a könnyebb feladatoknál még a brute force is elmegy. De ott pl. az 1 másodperces vs. 1 perces idő sok helyezésbe kerül. Ha nem érdekel a helyezés, akkor ismét mindegy.

Szerintem egy ilyen versenyre a Python kifejezetten jó, mert gyorsan lehet benne kódolni, és gyorsan le is lehet futtatni (mármint hogy nem kell lefordítani). Ha lassabban is fut (feltéve ha az algoritmus jó), fentiek alapján az tök mindegy.

Egyszer próbáld ki az Eclipse-t a saját Java projekt formátumával. Ha a saját builderét tudja használni (állítólag most már Maven projekttel is tudja), akkor a fordító "rezidensen" a memóriában van (ugyanabban a processzben mint az IDE UI), és inkrementális a build. Annyira gyors, hogy észre se veszed és kész.

A C vs python-nal egyetértek, de egy Java / Kotlin (/ c++) szerintem igen közel van fejlesztési sebességben, futás időben viszont lényegesen gyorsabb.   Jó algoritmussal persze ezeknél a "versenyeknél" mindegy.  Nem igazán számít, hogy 0.01 sec vagy 5 sec alatt fut le a cucc. (kivéve a már említett brute-force megoldásokat, de az meg max az első néhány feladatnál játszik)

Amikor elkezdtem pythonozni, akkor mértem néhány kedvenc példámnál, hogy a python megoldás cca 20-szor lassabb, mint a C.
Aztán elkezdtem numpy-zni, és, ha sikerül a problémát SIMD módon numpyval megoldani, akkor köröket verek a saját C implementációmra. Mivel numpy alapul az évtizedekig reszlegetett (blas, mkl) linalgerbra-libekre, mik hajlamosak jól optimalizálva lenni az adott cpu-hoz (avx2 vagy avx-512). Ezek persze hívhatóak lennének C/Fortranból is, de ebben nincs gyakorlatom. Viszont a numpy rendkívüli módon teker. Mondjuk a numpy sebességét nem használtam ki ennél a versenynél, de még hátra van pár nap. Hátha lesz valami feladat, ahol mátrix, einsum és hajrá.

évtizedekig reszlegetett (blas, mkl) linalgerbra-libekre, mik hajlamosak jól optimalizálva lenni az adott cpu-hoz (avx2 vagy avx-512)

Nemrég beleakadtam a blis-be, mint potenciális hobbi-projektbe. Belenéztem néhány friss commit-ba... nyilván amit most leírok, az elsősorban magamról állít ki véleményt, de: kiábrándítónak találtam. Semmi (matematikához kapcsolható) izgalmat nem keltett bennem a több oldalnyi AVX-es assembly kód.

Ha nagyon sok matrixos szamolas van benne, akkor meg a pytorch-os GPU szamitas is bevetheto. A numpy Array es a pytorch-os kozt eleg jo atjaras van. Ilyenkor mindegy milyen kod fut a CPU-n, megfelelo GPU-nak nem ellenfel.

A masik a multiprocessing-fele map, ez is eleg jol johet nehany esetben. (itt figyelni kell, hogy az adatot atkuldi pickle-n egy masik processbe, ami overhead)

Altalaban veve viszont a C koroket ver futasidoben a Pythonra (meg ugy kb. mindenre a kezzel - es hozzaertessel - optimalizalt ASM kivetelevel). Ha nincs pont a celnak megfelelo lib, egy 20-as (vagy 50-70) szorzo konnyen bejohet.

Kodolasi idoben ettol fuggetlenul jo. Foleg, hogy az itertools, functools es tarsai sokszor nehany sorban meg tudnak oldani ilyen algoritmusos fejtoroket.

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

Egyszer optimalizáltam egyet a "Word2vec" modell tensorflow implementációján.

Gondos paraméterezsel (tf szálak száma meg ilyesmik) mintegy 20%-ot növeltem.
Gondos rendszgazdai munkával további 10%-ot
TF újrafordításával az adott környezetre újabb 5%-ot
Azzal, hogy belenyúltam a batch_size paraméterbe, ami már a model eredményét is befolyásolja, további 200000% -ot.

A batch normalization reteg miatt azert az ilyesmivel vigyazni kell. Ott van egy also es felso hatar, amik kozott jol mukodik, illetve ha futtataskor nincs "vegtelen sok", streamelheto mintad, akkor megint kapsz egy felso hatart, ha nem akarsz sokat varni amig osszegyulik a kello adatmennyiseg. (Mint amikor a viccben a rendor azert kesik, mert ki volt irva a liftre, hogy 6 szemelyes, es fel oraig tartott, mig talalt meg 5 embert, aki arra az emeletre megy.)

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

Igen, erdekes video, mar osztottam is korabban ismerosnek. Az eredeti videoja is jo amugy, amibol az egesz indult. Matematikus, ok nem mindig a szep es hatekony kodukrol ismertek :) (fizikus meg gepesz utan is takaritottam mar kodot, utana sokkal jobban tetszett)

Annyiban mondjuk igaza van, hogy ha a videojahoz mondjuk eleg, ha lefut 1 honap alatt, es a feladatat ellatja, akkor onnantol sikernek szamit.

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

( KGer | 2024. 12. 15., v – 23:32 )

Szerkesztve: 2024. 12. 15., v – 23:32

https://adventofcode.com/2024/stats

stat-ból az látszik hogy kb csak 10% bukik el a 2-dik feladaton, pedig az jóval nehezebb szokott lenni min az első, sokszor tök más az algoritmus is

( egeresz | 2024. 12. 17., k – 10:44 )

Kommentelve és hibaellenőrzéssel szoktam programozni, lehetőleg kiemelt, nevesített függvényekkel. A nyertes, vagy nyertesközeli kódok (redditen olvasható pl.) pedig nagyon ronda, egykarekteres változóneves és a lehető legtömörebb kódok, jóhogy goto nincs benne.

Azonban a mai (day17) feladat leaderboardja rank#100 helyezettje 44 perc. Itt már a gépelés sebessége másodlagos, fontosabb, hogy merre indul az ember. Mondjuk nem rossz irányba, mint pl én. Megnézzük hova fajul el a verseny végére.

Mittudomén :)

Redditen volt linkelve, egy Python script, ami scrape-eli az oldal tartalmát, betölti valamelyik LLM-be egy féloldalnyi prompttal megtoldva, a végeredményt lefuttatja, és a vágólapra kopizza a megoldást.

Ne kérdezd, miért nem küldte be a megoldást automatikusan. :)

Ha "jo passzban vagyok" == nem vagyok fáradt sem éhes  (ezt érzem is a feladat elkezdésekor), akkor stabilan hozom a rank#100 idejének háromszorosát. Most kipróbáltam a aoc2016 -os feladatokat is, ott is stabilan hozom. Márpedig 2016-ban nem volt very large language model.

Most ugyan van very large language model, de nem tudok olyanról, ami egy ilyen feladatot képes lenne ténylegesen megoldani. Legfeljebb ad egy hintet.

Ezek miatt gondolom úgy, hogy a leaderbord top100 hihetetlen eredményei valósak, valóban emberi eredmények. Szokásos emberi csalásokkal, pl együttdolgozás vagy dopping (exstasy vagy kokain, nem értek hozzá)

Úgy vagyok meggyőzhető arról, hogy ilyen feladato egy AI képes megoldani, ha valaki mutat egy konkrét AI-t, ami megoldja. Addig feltételezem, hogy jól elterjedt babona a mindentudó/mindenható AI-ról.

Úgy vagyok meggyőzhető arról, hogy ilyen feladato egy AI képes megoldani, ha valaki mutat egy konkrét AI-t, ami megoldja.

Konkrétan láttam a repót, az övé volt, bár úgy látom, már nem elérhető: https://github.com/qianxyz

Sima ChatGPT volt mögötte, ha jól rémlik, egy olyan prompttal, hogy mindenféle sallangok nélkül dobja ki a Python (?) kódot, azt egy script egyből futtatta, és Pyperclippel egyből a vágólapra tette a megoldást.

Ezek miatt gondolom úgy, hogy a leaderbord top100 hihetetlen eredményei valósak, valóban emberi eredmények.

Persze, 2 csillag 9 másodperc alatt. :)

( KGer | 2024. 12. 18., sze – 17:35 )

Szerkesztve: 2024. 12. 18., sze – 17:36

Day17-nél vmi váratlan lehetett mert a szokásos 1 perces rekordok helyett 14p lett az első, a többi pedig 20p-ek

Hát a 2. feladat azért nem volt egyszerű, nemcsak szimulálni, hanem a saját értelmeddel értelmezni kellett egy lépéssorozatot és hogy hogyan lehet az inverzét előállítani. És ehhez addig kellett csűrni csavarni a bit blokkokat, hogy a végén már majd kifolyt a szemem :D És felteszem, hogy itt az AI nem igazán tud labdába rúgni.

Annyit kellett értelmezni belőle, hogy az output mely bitjeire van befolyása az input mely bitjeinek. De hogy pontosan hogyan, azt már valóban nem kell ésszel értelmezni, azt elég leszimulálni az algoritmus futtatásával. Legalábbis nálam nagyjából ez a megoldás váza.

Én is próbáltam kitalálni a szabályszerűséget, illetve, hogyan lehetne "visszafelé futtatni", de nem igazán sikerült. Egy idő után meguntam, írtam egy kis egyszerű gén algoritmust, ami pillanatok alatt kiadta a megoldást. Így aztán nem is tudom mi a szabályszerűség.

( joco01 v | 2024. 12. 21., szo – 12:33 )

Ez a 21. nap kemény volt. 3 órát szenvedtem a második résszel, mire meglett. Az első részben generáltam a stringeket, és hamar rájöttem, hogy a másodikhoz iszonyat sok és iszonyat hosszú stringet kellene generálni, ami lehetetlen. A megoldás végül tök egyszerű, és voltak is már hasonló megoldások idén, de valahogy nem esett le, hogy most is az a módszer kell. Picit súgok: mi történik akkor, ha a legelején, még minden mozgás előtt, gombot nyomsz? És a folyamat legeslegutolsó gombnyomása hogy néz ki?

Az a baj, hogy miután kitaláltam, hogy nem lehet a teljes stringeket kigenerálni, azon gondolkodtam, hogy lehetne abszolút elkerülni a generálást, és csak számokból kihozni. De végülis azt sem lehet, mert minden szinten a választott lépésektől függenek a következő szint lépései és tök más eredményt produkál. És akkor esett le, hogy van valami a kettő között, generálunk is meg nem is.

A visszafelé haladást nem értem. Az én megoldásomban nincs ilyen. Illetve szerintem ilyen szempontból szimmetrikus a probléma, megfordítva is ugyanaz jönne ki.

( egeresz | 2024. 12. 23., h – 11:50 )

day23 part2

Van valakinek ötlete, hogy a kérdés (keressük meg a legnagyobb részgráfot, ami teljes gráf) általános esetben is lefut értelmes idő alatt? Csúcsok száma 520, a bruteforce 2**520 lépés lenne, az nem fut le. Szerencsére a feledat erősen speciális gráfot adott (amiben is a legnagyobb fokszám erősen kicsi), így a versenyfeladatot meg tudtam oldani.

Vagy valami utalás, hogy ez a probléma nP teljes?

Kotlinban Set és Map segítségével egész könnyen lehetett implementálni. A youtuber, akit követek, pythonozik, és a networkx csomaggal csinálta. Az is ugyanezt az algoritmust használja.

Nekem rémlik, hogy egyetemen (BME, BSZ tárgy) tanultuk, de nem tudtam volna magamtól kitalálni ezt az egyszerű algoritmust. Kicsit bonyolultabban, több idő alatt azért biztos ment volna, mert nem olyan nehéz feladat.

abszolult tekintetben szerintem is a day21part2 volt a legnehezebb. Csak a "becsület" csináltatta meg velem, az élményszerűsége az 3. óra táján elmúlt.

 

A day24part2 -ben az első viszonylag egyszerű megoldás-tippemben vétettem egy apró hibát, ami miatt az nem találta meg a megoldást, és akkor egy teljesen más útra tértem, majd azon eltöltöttem 10 órát. Eh.

Nekem ennek a megoldása lett a leghosszabb kódsor szinten is, szóval azért abból a szempontból is a "legnehezebb volt" (legalábbis nekem).  Külön szívás volt, hogy az elején a 21/1 megoldást próbáltam továbbvinni valahogy a 21/2-re de az végül zsákutca volt és / vagy káoszba fulladt :)  Kellett egy nagy levegő és újra kezdtem kb nulláról a 21/2-t, ami végül persze kiadta a 21/1-et is.

( KGer | 2024. 12. 28., szo – 19:16 )

Day16 part1-en elcsúsztam csúnyán

2+ napot ültem rajta, becsületbeli üggyé kerekedett

az algoritmusom jó megoldást adott a 2 teszt inputra, de az igazi inputra nem futott le időben

bevetettem ezt, bevetettem azt, 1200 soros lett a java kódom, töredékére redukáltam a gráfot, végül gyorsan lefutott, jónak tűnt a megoldás, közel is volt hozzá de nem fogadta el

vhol elcsúszott a dolog és gőzöm sincs hol

aztán megnéztem github-on megoldást h tök egyszerű volt, megszívtam