Advent of Code 2025

Algoritmusok

Idén is fut az Advent of Code "karácsonyváró játék", bár idén már csak 12 napos a móka.

 

A tavalyi HUP leaderboard 2567216-8c01cc3b idén is él.

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

Hajrá! :) 

  • 1065 megtekintés

( 6030999 | 2025. 12. 08., h – 21:04 )

Csinálom, de kicsit olyan érzésem van, mint valami hagyományőrző nyírágseprűkészítőnek...

_______Peter
I am a stone. I do not move.

( joco01 v | 2025. 12. 08., h – 21:26 )

Én kiléptem a leaderboard-okról, mert belefáradtam, hogy nem programozásról szól, hanem korán kelésről, meg hogy ki mennyire nem szégyell AI-t használni. Maximum személyesen lenne érdekes ez a része. Szóval csinálom egyedül, így még fun.

( KGer | 2025. 12. 08., h – 22:22 )

én ezt nagyon szeretem, csak sajnos sok időbe telt, van hogy 1 napig ültem egy feladaton annyira belehabarodtam

sajnálom hogy 12 fordulós lett és hogy nincs global leaderboard

idén már jogosultnak éreztem volna az 5 sec alatt megoldja AI-k indulását is, ha valaki össze tud rá dobni egy aoc agent-et és nyeri, akkor jogosan nyer, hisz rengeteg munka van abban is

( enpassant v | 2025. 12. 09., k – 08:54 )

Tavaly Zig, majd Gleam. Idén megint Zig, de olyan rövid, hogy lehet, hogy végig ez marad. Kezdem egyre jobban megismerni. Még így is sokszor annyi munka, mint más nyelveken, de egyre jobban élvezem.

( kleinie | 2025. 12. 09., k – 16:02 )

Tavaly én is neki akartam állni, aztán végül nem volt időm foglalkozni vele. De talán majd most!

Vagy utólag megcsinálom az előző évit is.

Make it as simple as possible, but not simpler. - A. Einstein

( egeresz | 2025. 12. 10., sze – 21:25 )

DAY10 part2 finom volt, nemde?

nem spoilerezném el, csak annyt tennék hozzá, hogy a "jó ötletem" négy egymásutáni nagyságrendi gyorsitás implementálása után még mindig nem futott le milliárd év alatt, kénytelen voltam valami más jó ötlet után nézni. Egész felélénkültem, hogy végre egy nem szokásos feladat.

Ha kicsit kisebb számok lettek volna, az igazságosabb lett volna, mert akkor hozzád hasonlóan pár jó ötlettel is meg lehetett volna oldani. De így vagy komoly matek tudás kell (amit már verseny előtt kellett volna összeszedni), vagy ha szerencsés vagy, akkor a választott nyelvedben van egy könnyen kézre eső ILP solver, és akkor percek alatt megoldod, különben lehet órákig vergődni, hiába vagy amúgy jó programozó.

-spoiler-

Szerintem ahhoz is komoly matek kell, hogy az ember egyáltalán rájöjjön, hogy a gombok tekinthetők műveleteknek, a műveletek ábrázolhatóak vektorokban, ezen vektorok egész együtthatós lineáris kombinációját keressük, így és az egész végül is egy lineáris egyenletrendszer optimális megoldáskeresése
egy ismerős az egyik népszerűbb generatív llm modellel kihozta ugyanezt, ami arra utal, hogy ez a megközelítés mégiscsak tipusfeladat volt valahol a github/stackoverflow/egyetemi tudásanyag valamelyik bugyrában.

Szerintem ahhoz is komoly matek kell, hogy az ember egyáltalán rájöjjön, hogy a gombok tekinthetők műveleteknek

Szerintem alap linalg, amit programozóknak tudnia kellene.

Még csak most olvastam a feladatot, (meg amúgy is csak jöttment senki vagyok) ezért bocs, ha baromságokat írok:

A joltage vektor elemszáma a tér (ami amúgy Manhattan-tér) dimenziója. Egy gomb definíciója, hogy ezen térbeli egységvektorok közül melyek összege. Így ezek a vektorok tuti lineárisan függetlenek.

Nagyon leegyszerűsített példa: (0,1) (1,0) {12,18}. Ebből próbálgatás nélkül kiszámítható, hogy 18*(0,1) + 12*(1,0) megoldás az egyetlen, és 30 gombnyomást jelent. Ha van még (1,1) gomb is, akkor is megoldás az előző, de így a legkevesebb gombnyomás 12*(1,1) + 6*(0,1) = 18 adódik. A valódi input-ban persze sokkal bonyolultabb adatok vannak, gondolom arra gondoltál fentebb, hogy a tisztán (rekurzív) bruteforce módszer milliárd év alatt is esélytelen.

Így elsőre azt mondanám, hogy minden gombra könnyen kiszámítható egy felső korlát. A feladatban megadott példák közül az elsőnél:

(3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}

(3) < 7; (1,3) < 5; (2) < 4; (2,3) < 4; (0,2) < 3; (0,1) < 3

Mert pl. a 0. cél érték 3, tehát a 0-t tartalmazó gomb 3+ megnyomása biztosan nem adhat helyes eredményt. (Elvileg ezeknél = is lehet, szélsőséges esetben.) Vagy akár mondhatjuk, hogy ha a (2) gomb már kétszer és a (0,2) kétszer meg van nyomva, akkor nincs értelme (...,2,...) gombot nyomni. Így csökkenthető a rekurzív hívások száma, bár most fogalmam sincs, hogy ez elég-e arra, hogy emberi idő alatt lefusson.

Ha egy adatsorra teljesül, hogy gombok száma = cél vektor dimenziója, akkor ott pontosan 1db, próbálgatás nélül kiszámítható megoldása lenne.

spoiler:

Most ugrott be egy módszer, ami működhet. Mivel a lehetséges legkevesebb gombnyomás kell, az a leggyorsabb, hogy előbb kell kipróbálni az összes Ndb gombnyomást, és utána az N+1 gombnyomásokat. Így az első jó, az kapásból a minimum is. És ezt a joltage vektor legnagyobb értékével kell kezdeni. Azt pedig, hogy egy próbálkozásban melyik gombokat kell megnyomni, mod gombok_száma adja.

Azért trükkös a feladat, mert majdnem mindenki azt gondolja, hogy először elő kell állítani a lineáris egyenletrendszer összes megoldását, majd azok közül kiválasztani a legkevesebb gombnyomással keletkezőt.

( KGer | 2025. 12. 12., p – 13:03 )

a top3 hupos helyezett általában mennyi idő alatt oldja meg és mit használ?

1-2 óra és 1-2 nap között a feladat nehézség / ihlet / rendelkezésre álló szabadidő függvényében :) Az idei 10-est első körben z3-mal csináltam meg, még most is reszelem a "rendes" megoldást...

A legtöbbet c++-ban írtam, de volt kotlin és lua is.

A megoldásaim fent vannak github-on: mitchnull/advent-of-code

Bár én sem vagyok a top3-ban, de végül sikerült az idei összes csillagot megszerezni.

Én C#-ban írtam. Egy feladat tipikusan 1 óra körül, a vége felé inkább 3 óra. Csak az alap C#/.NET library-t használom, egyetlen kivétel a 10. feladat 2. része. Itt miután rájöttem, hogy matematikailag milyen amúgy jól leírt algoritmusra vezethető vissza, külső library-t használtam. A 12. feladatnak sokáig neki sem álltam, nem is értettem, hogy mások hogyan tudtak erre belátható idő alatt lefutó megoldást találni. Aztán rájöttem, hogy nem is kell :)

Igen, a 12-esnél a tanulság: "nem lehet minden feladatot megoldani".  Ettől függetlenül azért nem volt szép húzás, hogy a példa input nagyon nem olyan volt, mint az igazi (és nem úgy mint általában, hogy esetleg könnyebb, hanem pont fordítva, a példa input "megoldhatatlan"...)