Fórumok
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)
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)
Hozzászólások
+1
Csatlakoztam, egyelőre a tegnapit csináltam csak meg.
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.
Nekem működött. Csatlakoztam is.
Én voltam a láma!
A leaderboard egyébként elég furán van számolva, nem a helyezés a lényeg :)
Annyira nem fura az, csak ha menet közben ki-belépkednek emberek, az szét tudja túrni kicsit a pontokat:
quemu adventi calendar nincs ?
“Luck Is What Happens When Preparation Meets Opportunity" - Seneca
Csatlakoztam én is. Zig-ben tolom, ha valakit érdekel a megoldás, a github-omon megnézheti. ;-)
Jó szószátyár az a zig :)
Nagyon sok programozással/programnyelvekkel kapcsolatos dolgot olvasok/nézek. A "modern" nyelvekből még a Zig ami leginkább tetszik!
Én valami Lisp-et fogok használni, aztán lehet beletörik a bicskám!
Lassan ott tartunk, hogy leírod angolul/magyarul, mit szeretnél és abból az AI megcsinálja valahogy... :D
https://iotguru.cloud
Az 5. feladatnál a ti megoldásotok mit mond erre az inputra?
Az első részre 3-at, a második résznél meg elszáll a rendezésen.
Ui.: a rendezés teljesen általánossá tételével ott is 3 az eredmény. (3 + 0)
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á:
Én a lehető legkevesebb cserével oldottam meg a rendezést, vagyis amire nincs szabály, az marad a helyén:
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á:
itt a 2. részben 90 a jó válasz
[51, 40, 41, 30, 31, 20, 21, 10, 11]
[10, 11, 20, 21, 30, 31, 40, 41, 51]
[30, 10, 40, 11, 20, 41, 21, 31, 51]
[10, 11, 20, 21, 30, 31, 40, 41, 51]
[40, 51, 20, 21, 11, 41, 31, 10, 30]
[10, 11, 20, 21, 30, 31, 40, 41, 51]
90
Igen, 90 a jó válasz.
Nem lehet benne duplikátum.
nem kódoltam le a rendezést. Átadtam a coreutils:tsort shell programnak. Az meg más inputot vár, kihasználtam, hogy a topology definíció teljes (vagyis a listában lévő minden szám szerepel a topology meghatározásban)
tehát nekem 9
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
Fasza, így még inkább értelmetlen az egész leaderboard :D
Igen, ezért írtam, hogy igazából nem a "helyezés" számít, csak a móka. A feladatok egyébként egyre nehezebbek lesznek, plusz én direkt olyan nyelveken oldom meg őket amikkel meló során nem nagyon foglalkozok, szóval kicsit ilyen játékos tanulás.
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.
Olvastam olyan véleményt is, hogy valaki annyira belemélyedt az egyik elmúlt évben, hogy becsavarodott tőle, és a munkája mellett még extra stresszt jelentett neki. Ez nálam valós kockázat, úgyhogy inkább meg sem néztem a feladatokat.
Én is így vagyok vele, hogy szeretem az ilyeneket, de nincs most időm rákattanni. De legalább a munkám is épp elég izgalmas, azon is van mit gondolkodni.
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:
Ez pontosan annak a ciklusnak a fordítottja (beleértve az "i" kezdeti és végső értékét is) , hogy
(Szokták olyan formában is írni, hogy
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,
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
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!
Teljes indukció? :)
Bizonyítani nem tudom, de valamiért mindig működik. A kislányomnak segítettem ilyen hány szám van x és y között típusú feladatokban, hogy hogy kell ellenőrizni az eredményt. És akkor jöttem rá erre a megfogalmazásra. Azóta figyelek rá és mindig működik.
A teljes indukció nem két (tetszőleges) elemről szól, hanem arról, hogy van legalább egy elem, ahol igaz az állítás (ez megvan), a másik feltétele viszont az, hogy tetszőleges elem estén bizonyítható az is, hogy a következő elemre is igaz az állítás.
Hát, Terry Pratchett trolljai óta tudjuk, hogy számolni úgy kell, hogy One, Two, Many. :)
(Ami egyébként pont teljesen jól kategorizálja egy csomó IT probléma megközelítését, ha nem akarsz nagyon matekozni :) )
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. ;-)
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
Hm. A 8. nap leírása kétértelmű (avagy rossz):
Ez alapján ez is valid lenne:
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 :)
Jogos, de utána egyértelműsíti, hogy "there are two antinodes, one on either side of them".
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.
Nem pont így, de hasonlóan egyszerűen csináltam én is a 2. részt.
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.
Az enyém elsőre is gyors volt, csak rossz választ ad :) meló után kiegyenesítem majd.
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 :)
Kotlin on JVM - 200 ms
Ez igen, ha a felvetett "szó szerinti implementáció" fut le ennyi idő alatt! ;-)
A nem szó szerinti implementáció nálam is ilyen pár tucat kB-ot foglalhat és ms tartományban fut le.
Ja, hát ahhoz annyi RAM kellene, amit egyetlen földi számítógép sem bír el, nyilván nyelvtől függetlenül az így megoldhatatlan.
(dupla)
A "nem szó szerinti" megoldás nyílván gyorsabb:
C++ version:
1: 229043
2: 272673043446478
real 0m0.015s
user 0m0.012s
sys 0m0.003s
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
Nálam is, de a Zig nem is engedi, hogy tovább fusson, valamit kezdeni kell vele. ;-)
Az unsigned overflow-t sem engedi? Az elég fura.
Miért fura? Zig eléggé biztonságos nyelv ilyen szempontból.
Ja látom, külön kérni kell, ha overflow-t szeretnél: `a +% b`
java.math.BigInteger
Kotlinból egyszerűbb használni az operator overloading miatt.
Erről beszélünk, ugye? Day 11 (itt a levelekkel kicsit megzavartál :))
Kíváncsiságból lefuttattam mpz-vel:
uint64_t-vel persze gyorsabb, de rossz eredményt ad:
Zig-en az u128 a legnagyobb egész, amit használni lehet, azzal 208 még lefut.
Van bigint is, de azt elég körülményes használni, így azt nem próbáltam ki.
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
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.
“The world runs on Excel spreadsheets.” (Dylan Beattie)
Mondták már neked, hogy hallgatni arany?
Ja, nincs értelme==Raynest nem érdekli, ált nem szokott sikerülni megérteni, hogy nem mindenki az ő preferenciái alapján működik.
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
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
Day 14 :)
Mondhatni végre egy feladat, ahol használni kell az eszünket :) Kimondottan tetszett, hogy ez kilóg a sorból, nem egy egzaktul definiált dolgot keresünk, de némi erős nézéssel mégis megtalálható.
ez egy nagyon ötletes feladat volt ++
Erről volt szó?
Nem. Minden feladatnak van egy 2. része, ami csak akkor jelenik meg, ha az elsőt megoldottad. Itt most az aznapi 2. feladatról van szó, ami teljesen más jellegű, mint az ilyen online kódolási feladatok szoktak lenni.
Értem, köszi! Mézesmadzag eljárás :)
Ráadásul úgy, hogy volt egy feladat amit elkezdtem valahogy, aztán visszatöröltem mert rájöttem, hogy az ágyúval verébre ide. Aztán a második feladat meg pont azt az algoritmust kérte, amit elkezdtem elsőre, csak visszatöröltem.
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 :)
Szerintem is. De miért pont 12000? A pálya mérete 101*103, szóval 10403 a ciklus. Aztán választhat pl. 5 és 8 ezer között egy random számot.
csak egy random szófordulat volt :)
Köszi!
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.
Én 7 körül kelek, a reggeli tea mellett elkezdem. Ha egyszerű a feladat, akkor általában belefér meló előtt. Ha nem, akkor meló után folytatom. Ahogy egyre nehezednek, biztos lesz olyan is ami átcsúszik másnapra, vagy akár ki is marad :)
Jó a buli. 9 nap késéssel kezdtem, ma értem utol a mezőnyt (day14) köszi a leaderboard meghívást.
Na most, hogy már szabadságon vagyok, talán lesz időm elkezdeni. Remélem.
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.
Az első napon az első csillag 4 mp volt, a 9 mp már két csillag :) nem tudsz meggyőzni, hogy ez egy emberi teljesítmény.
"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)
9 másodperc? Tuti nem lehet. De a sok accountos közelítős módszer működhet, és a másodikat a saját nevén is behúzhatja. Ha minden nap behúzza a második helyet, azzal összetettben első lesz.
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.
>mármint hogy nem kell lefordítani
Ebben a program-mérettartományban a fordítás szub-100ms és debuggolás közben átírhatom a kódot, az is érvényre jut ennyi idő alatt bármilyen IDE-ben.
Nálam az kb. 2 másodpercet tesz hozzá. IntelliJ, Bazel, Kotlin kombó. Nem mondom, hogy jól esik, de lusta vagyok optimalizálni ezen a workflow-n.
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)
Szerintem a Java és C++ overheadje bőven túl sok. A Kotlin már egész jó, de azért még ott is több a kulcsszó és több mindent kell kézzel megírni, mint Pythonban.
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á.
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?
Lazán kapcsolódik (és talán szolgál valamiféle tanulsággal): https://www.youtube.com/watch?v=c33AZBnRHks (Someone improved my code by 40,832,277,770%)
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?
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
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.
A leaderboardot úgy nézd, hogy nagy része AI, van rá már script Githubon is
link or didn't happen
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. :)
Day18-on van egy 48s-es magyar is, őt kell megkérdezni mi a titok
Nekem kb. másfél óra alatt lett meg a 17 **, csak sajnos megint 9-kor kezdtem 6 helyett :D
Jó gyors géped lehet, az enyém még mindig teker :)
(közben persze gondolkozok egy kevésbé brute-force megoldáson :)
10-es számrendszerben ~15 jegyű megoldás lesz. Szerintem ne tekertesd azt a szegény gépet. A jó megoldás 1 mp alatt lefut :).
0.004 sec (ha már emlegetve voltak a millisec-ek ;)
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
Mert a 17/2 elég nehéz volt.
A 17/1-nél vannak 1 perc alatti eredmények, ami szintén tuti csalás.
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.
Én is így oldottam meg, de utólag kiderült, hogy nem lett volna muszáj értelmezni a kódot.
Azért valamennyire muszáj volt értelmezni a kódot, hogy értelmesen neki lehessen állni. Ha teljesen random változna az output akkor sokkal nehezebb lenne, de van egy lényeges eleme a "programnak".
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.
Igen, ezt mondom én is.
Szerk: csak próbáltam kevésbé explicit hintet adni :)
Én erre a módszerre gondoltam: mitírki(1,2,3,4,5), mitírki(1,2,3,4,5,6), mitírki(1,2,3,4,5,6,7), mitírki(1,2,3,4,6), mitírki(1,2,3,4,7) és pár ilyen után rá lehet jönni, anélkül, hogy a kódot értenéd.
É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.
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?
Szerintem nyilvánvaló, hogy nem kell stringeket generálni. És hogy visszafelé kell haladni.
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.
Szerintem is nehéz volt.
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?
Én ezzel csináltam: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
Köszi, tehát jól sejtettem, a probléma általánosan nP-teljes. A Kerbosch algoritmussal nem találkoztam még, nagyon szépen köszönöm, ezzel teljesült is a verseny "önképzés" mellékhatása :-)
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.
Day 24 part 2 programozás nélkül lett meg :) ("megoldókulcs")
A programhoz is sokat segített, hogy a "normális" adderről volt szó, és nem valami ekvivalens, de sokkal csicsább csodáról. És a cserék is "jó" helyeken voltak.
Gondoltam ezt kihagyom, de a Day25part2 nem oldható meg, ha nem teljes az összes többi. eh.
hát ezen roppant sokat küzdöttem. Végül legeneráltam az összeadógépet, és a két összeadógép között megpróbáltam szótárt építeni, és ahol a szótárépítő elesett, ott kézzel megnéztem mi az eltérés.
Engem a 21b izzasztott meg :)
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.
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
Igen, az egy sima Dijkstra volt, csak ügyesen kellett megválasztani a csúcsokat és éleket (súlyokat).
Van ez így :) Ilyenkor jól jön, ha valakivel meg lehet beszélni a problémát.