:strip_exif()/u/11775/SoulTaker.gif?f=community)
Ik moest ook even goed lezen wat de bedoeling was (ik ging er in eerste instantie vanuit dat een shortcut in een rechte lijn moest liggen b.v.) maar er staat expliciet in de opgave:
Volgens mij is dat niet te verenigen met jouw interpretatie
Verandering van het hashing algoritme, en
spoiler:
elke keer als ik een element neem van de start locatie, dit verwijderen, en ook de cheat in omgekeerde richting checken (dus van cheat_end naar cheat_start).
Levert volgende op:
Challenge 3
Parsing: 772.58ms
Day 20 - Part 1 :..743
generator: 4.3µs,
runner: 3.787326s
Parsing: 807.1034ms
Day 20 - Part 2 : ..943
generator: 700ns,
runner: 129.0934452s
Dat is dus bijna een 2x speed up (waarvan het grootste gedeelte door de update van het hashing algoritme komt ..
, dat was een stap van 245s naar ~150s)Waarschijnlijk is het effectiver om geen hashmap bij te houden en gewoon alles uit een array te halen, maar ik heb esthetische bezwaren daartegen
edit: nog een factor 2 eruit weten te slepen door
spoiler:
Van boven naar beneden door de lijst met open ruimtes heen te lopen, dan hoef je nooit meer boven te checken, en hoef je dus maar de helft van de ruit te checken. Voor deel 1 is dit langzamer (je verliest blijkbaar wordt door door de geordende lijst te lopen, maar voor deel 2 veel sneller.
Challenge 3:
Parsing: 895.6684ms
Day 20 - Part 1 : ...743
generator: 4.1µs,
runner: 3.8967507s
Parsing: 935.5786ms
Day 20 - Part 2 : ...943
generator: 1.1µs,
runner: 54.7016369s
[ Voor 12% gewijzigd door FCA op 20-12-2024 14:12 ]
Verandert z'n sig te weinig.
:strip_exif()/u/13818/episodebutler_60x60.gif?f=community)
Ja, dat ook nog, naast dat de 'race' uberhaupt het kortste pad moet hebben.:
[...]
Ik moest ook even goed lezen wat de bedoeling was (ik ging er in eerste instantie vanuit dat een shortcut in een rechte lijn moest liggen b.v.) maar er staat expliciet in de opgave:
[...]
Volgens mij is dat niet te verenigen met jouw interpretatie
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Zo, vandaag was wel een pittige uitdaging! Gelukkig is het weekend. Gefeliciteerd @Friits dat je de gouden ster als snelste hebt weten te pakken!
Ik had deel 1 nog vrij snel gebruteforcet (rank 87 op het global leaderboard; m'n op een-na-beste resultaat dit jaar!) maar ik denk niet dat het een spoiler is om op te merken dat je daar met deel 2 niet veel aan hebt.
Het is niet zo moeilijk om een oplossing te vinden:
Maar de korste oplossing vinden is lastiger, want:
Het deel waarmee ik moeite had het me in te beelden was dit:
De uiteindelijke code is nog best eenvoudig: 21.py Je moet alleen even het juiste perspectief hebben.
Ik had deel 1 nog vrij snel gebruteforcet (rank 87 op het global leaderboard; m'n op een-na-beste resultaat dit jaar!) maar ik denk niet dat het een spoiler is om op te merken dat je daar met deel 2 niet veel aan hebt.
Het is niet zo moeilijk om een oplossing te vinden:
spoiler:
Je kunt vrij eenvoudig bedenken wat de korste paden zijn op het laagste niveau. Bijvoorbeeld om "123A" te typen moet de robot erboven "<<^A>A>AvA" typen. Dan moet de robot daarboven "v<<AA..." typen enzovoorts, recursief.
Maar de korste oplossing vinden is lastiger, want:
spoiler:
je hebt keuzevrijheid bij het pad wat je kiest. In plaats van "<<^" kun je ook "<^<" of "^<<" doen om op dezelfde positie terecht te komen.
Een aantal van deze opties kun je elimineren: "<^<" is strict slechter dan de andere twee omdat de robot onder je daarbij nodeloos moet verplaatsen. Kortom, je hebt hooguit twee opties: of de horizontale beweging eerst, of de verticale. Maar dat geldt op elk niveau natuurlijk.
Een aantal van deze opties kun je elimineren: "<^<" is strict slechter dan de andere twee omdat de robot onder je daarbij nodeloos moet verplaatsen. Kortom, je hebt hooguit twee opties: of de horizontale beweging eerst, of de verticale. Maar dat geldt op elk niveau natuurlijk.
Het deel waarmee ik moeite had het me in te beelden was dit:
spoiler:
Het lijkt in eerste instantie alsof een kortste pad op een laag niveau ook een kortste pad op hogere niveaus zou moeten opleveren.
Waarom zou "v>" efficiënter moeten zijn dan ">v"? Op het tweede niveau is de transitie van 'v' naar '>' even kostbaar als omgekeerd (">" resp. "<"). Maar op het derde niveau is het verschillend, omdat '<' verder van de A-knop ligt dan '>'. Dus met twee robots is "v>" te prefereren boven "<v".
Ik heb een tijdje geprobeerd dit soort regels statisch te coden, maar dat leidde niet tot een correcte oplossing zelfs niet bij deel 1. Ik snap niet helemaal waarom niet. Uiteindelijk heb ik het opgelost met dynamic programming, maar het zou me niet verbazen als er ook een “statische” oplossing is.
Waarom zou "v>" efficiënter moeten zijn dan ">v"? Op het tweede niveau is de transitie van 'v' naar '>' even kostbaar als omgekeerd (">" resp. "<"). Maar op het derde niveau is het verschillend, omdat '<' verder van de A-knop ligt dan '>'. Dus met twee robots is "v>" te prefereren boven "<v".
Ik heb een tijdje geprobeerd dit soort regels statisch te coden, maar dat leidde niet tot een correcte oplossing zelfs niet bij deel 1. Ik snap niet helemaal waarom niet. Uiteindelijk heb ik het opgelost met dynamic programming, maar het zou me niet verbazen als er ook een “statische” oplossing is.
De uiteindelijke code is nog best eenvoudig: 21.py Je moet alleen even het juiste perspectief hebben.
[ Voor 4% gewijzigd door Soultaker op 21-12-2024 10:54 ]
Ik zie dat ik vrijwel dezelfde implementatie in Rust heb gemaakt voor vandaag. Volgens mij kun je er ook niet veel meer mee:
...
De uiteindelijke code is nog best eenvoudig: 21.py Je moet alleen even het juiste perspectief hebben.
Ik heb nog wel wat tijd lopen verdoen met microbenchmarks. Ik kwam de smallvec library tegen die hier best wel van pas komt. In plaats van dat de strings op de heap terecht komen, zijn het nu kleine strings die tot 8 characters gewoon op de stack blijven. Dan maakt qua performance nog best wel wat uit. De berekening door deel 2 gaat nu in 66 microseconden
Het doet er verder niet toe, maar het is wel leuk om te kijken hoe ver je kunt gaan soms. 
Ik ben wel jaloers op de @Cache optie van Python. Dat maakt deze implementatie wel een stuk makkelijker! Misschien eens zie of ik iets dergelijks kan bereiken met macros...
[ Voor 7% gewijzigd door Marcj op 21-12-2024 18:03 ]
/u/1453990/crop67501f0e3996f_cropped.png?f=community)
Ik heb er een tijd op vastgezeten vandaag. Maar uiteindelijk is mijn solver als volgt::
Volgens mij kun je er ook niet veel meer mee
https://github.com/Robbin.../blob/main/day21/day21.cc
spoiler:
[code=c++]
long long DP[5][5][25];
const int MAX_LEVEL = 25;
long long solve(const int from, const int to, const int level) {
if (level == MAX_LEVEL) {
return 1;
}
if (DP[from][to][level] != -1) {
return DP[from][to][level];
}
long long bestDist = INF;
for (auto& path : minPaths[from][to]) {
long long currDist = solve(moveId['A'], moveId[path[0]], level + 1);
for (int i = 0; i < int(path.size()) - 1; i++) {
currDist += solve(moveId[path[i]], moveId[path[i + 1]], level + 1);
}
bestDist = min(bestDist, currDist);
}
return DP[from][to][level] = bestDist;
}
[/code]
Dus ik verwerk de paden al binnen de solve voor een state zodat cache values opvragen en opslaan O(1) is.
long long DP[5][5][25];
const int MAX_LEVEL = 25;
long long solve(const int from, const int to, const int level) {
if (level == MAX_LEVEL) {
return 1;
}
if (DP[from][to][level] != -1) {
return DP[from][to][level];
}
long long bestDist = INF;
for (auto& path : minPaths[from][to]) {
long long currDist = solve(moveId['A'], moveId[path[0]], level + 1);
for (int i = 0; i < int(path.size()) - 1; i++) {
currDist += solve(moveId[path[i]], moveId[path[i + 1]], level + 1);
}
bestDist = min(bestDist, currDist);
}
return DP[from][to][level] = bestDist;
}
[/code]
Dus ik verwerk de paden al binnen de solve voor een state zodat cache values opvragen en opslaan O(1) is.
Zou fijn zijn als de code tag (formatting) ook werkt binnen spoilers trouwens
.
[ Voor 9% gewijzigd door Robbinb1993 op 21-12-2024 19:16 ]
Nice! Uiteindelijk doe je hetzelfde werk als wat onze andere oplossingen ook doen, maar dan in een andere volgorde. Qua snelheid maakt het waarschijnlijk eigenlijk niks uit.
Ja, daar ben ik ook al een paar keer tegenaan gelopenZou fijn zijn als de code tag (formatting) ook werkt binnen spoilers trouwens
Ik heb de “statische” versie uiteindelijk nog wel werkend gekregen (21-alt.py) maar het is gebaseerd op een hoop geëxperimenteer. In zekere zin is de “dynamische” oplossing simpeler. Soms loont het om het probleem abstract te houden.:
Ik zie dat ik vrijwel dezelfde implementatie in Rust heb gemaakt voor vandaag. Volgens mij kun je er ook niet veel meer mee
@cache is inderdaad heel erg handig, vooral omdat het betekent dat je je kunt focussen op de logica achter je oplossing. Maar vandaag was het niet echt een killer feature. Ik heb ruim 2 uur over de oplossing gedaan, terwijl ik de memoization handmatig in 1 à 2 minuten had kunnen implementeren. De meerwaarde daarvan was dus beperkt.
Neemt niet weg dat @cache wel heel behulpzaam kan zijn. Mijn beste score dit jaar was op dag 11 (rank 52 op het global leaderboard) en daar heb ik inderdaad gewoon @cache op de functie van deel 1 geplakt om deel 2 op te lossen: 11.py.
Het is vast mogelijk om ook in Rust de resultaten te cachen. Waarschijnlijk zijn macro's zelfs overkill. Je moet alleen een functie kunnen genereren die dezelfde signature heeft als een bestaande functie, en je moet argumenten kunnen forwarden naar de onderliggende functie (in C++ heet dat perfect forwarding).
Ja, dit of de mogelijkheid om een code-blok ingeklapt te tonen. Maar dit soort feature requests zijn al jaren (decennia?) geleden geopperd (voorbeeld) en nooit geïmplementeerd, dus ik denk dat het er ook nooit van zal komen.:
Zou fijn zijn als de code tag (formatting) ook werkt binnen spoilers trouwens
@Robbinb1993 Ah ja, ik vermoedde wel dat het in native code aanzienlijk sneller zou zijn. De truc met de 4-tuple herschrijven naar een lineaire index had ik ook bedacht, maar in Python leverde het niet direct heel veel snelheidswinst op (iets van 10%).
De truc met seenItr om dubbelen te herkennen zonder dat je elke keer je array moet clearen is ook erg mooi gevonden! Ik kan nog een paar andere optimalisaties verzinnen:
En iets compleet anders: wat ben jij voor maniak dat je je code met 3 spaties indenteert Iedereen weet toch dat alleen machten van 2 toegestaan zijn!
De truc met seenItr om dubbelen te herkennen zonder dat je elke keer je array moet clearen is ook erg mooi gevonden! Ik kan nog een paar andere optimalisaties verzinnen:
- Als je in transform() unsigned long gebruikt in plaats van signed long dan is 'ie aanzienlijk sneller (dat komt omdat de compiler dan de modulo-operatie kan herschrijven naar een bitmask; voor een signed integer is dat minder efficient omdat 'ie negatieve remainders moet ondersteunen terwijl de getallen in dit probleem nooit negatief zijn—een hoop extra werk voor niets dus).
- Je kunt de index online updaten. Dat is efficiënter en dan hoef je de invoer maar 1x in te lezen.
- Je kunt ook vrij makkelijk het antwoord van deel 1 tegelijkertijd berekenen.
En iets compleet anders: wat ben jij voor maniak dat je je code met 3 spaties indenteert
Iedereen weet toch dat alleen machten van 2 toegestaan zijn!
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Netjes en leerzaam. Draait bij mij nu ook een stuk sneller: 9ms.
Haha, niet echt een goede reden voor. Alleen dat het wat compacter oogt. Tijdens productiewerk gebruik ik wel 4 spaces. VSCode heeft geen moeite met 3.En iets compleet anders: wat ben jij voor maniak dat je je code met 3 spaties indententeert
Thanks, toch voor één dagje bovenaan gestaan op het GoT leaderboard
Met ~45 minuten voor deel 1 en ~90 minuten voor deel 2 stond ik ook rond plaats 125e en 250e op het globale leaderboard. Normaal eindig ik ergens tussen de 800–1600 en 400–800, dus dat was wel gaaf!
Vandaag was weer een normale, eenvoudige dag, en dan leg ik het toch af tegen degenen die sneller typen
[ Voor 18% gewijzigd door Friits op 22-12-2024 12:23 ]
/u/36698/avatar.png?f=community){kind=avatar}
Ik was wat aan het inhalen, en echt veels te lang over dag 19 gedaan, ik kwam elke keer te laag uit, maar ik kon me haast niet voorstellen dat mijn code fout was... achteraf gezien kan ik mezelf wel voor m'n kop stoten, want uiteindelijk kwam het door:
spoiler:
int32 ipv int64 
There's no place like 127.0.0.1
Daar mag je best trots op zijn! Het was de moeilijkste opgave (tot nu toe) en ik vind snelle tijden bij moeilijke opgaven indrukwekkender dan bij makkelijkere opgaven.:
Thanks, toch voor één dagje bovenaan gestaan op het GoT leaderboard
(Overigens is het niet helemaal waar dat eenvoudigere opgaven slechts typwedstrijden zijn; er zijn daar vaak ook meer of minder effectieve strategiën om het probleem snel op te lossen. Typsnelheid is meestal niet de doorslaggevende factor.)
Oef, ik voel je pijn.:
spoiler:int32 ipv int64
spoiler:
Wel een goede reden om Python te gebruiken. Of op z'n minst een taal als Rust of Zig met overflow detection in debug mode?
:strip_icc():strip_exif()/u/633426/crop658152b10d6b4_cropped.jpg?f=community)
Ja, dat bedoelde ik ook meer als geintje, vandaar de "
"Ik heb het idee dat de snelle oplossers heel goed zijn in het abstraheren van de omschrijving naar een algemeen probleem, met bijbehorende strategieën (en wellicht ook al een archief van standaard-algoritmen hebben opgebouwd). Dat gaat natuurlijk het beste als het probleem relatief eenvoudig is en goed in één van die "doosjes" past: transformeer de input naar een graaf, Dijkstra loslaten, en klaar!
Zelf ben ik meer een langeafstandsloper: niet de snelheid om te winnen op de 400 meter, maar wel geoefend in een langere tijd stevig doorwerken. En als we dan een halve marathon voorgeschoteld krijgen, kan ik wat van de sprinters achter me laten
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
spoiler:
Na deel 1 heb ik een lijst met mogelijke driehoekjes. Ik heb een functie die per groep kijkt welke buren toegevoegd zouden kunnen worden, en dan die mogelijke groepen teruggeeft. Zo maak ik van de driehoekjes een lijst met vierkantjes.
Dat blijf ik herhalen tot er nog maar één groep over is, dat is dan het antwoord.
Dat blijf ik herhalen tot er nog maar één groep over is, dat is dan het antwoord.
Niet supersnel, maar het werkt. Deel 1 van @Soultaker krijg ik er nog mee gedraaid, met wat geduld. Deel 2 ga ik niet eens proberen
Gek genoeg had ik de oplossing voor deel 1 en deel 2 goed, maar voor de Soultaker challenges ging deel 2 de mist in... Na nog eens goed kijken kwam ik daar ook uit...
Deel 1 kan denk ik nog wel wat sneller
https://github.com/antonr...24/23/Solution/Program.cs
code:
1
2
3
4
5
6
| input/aoc-2024-day-23-challenge-1.txt: Answer 1: 2,6224ms input/aoc-2024-day-23-challenge-1.txt: Answer 2: 2,9859ms input/aoc-2024-day-23-challenge-2.txt: Answer 1: 12,2392ms input/aoc-2024-day-23-challenge-2.txt: Answer 2: 1,3836ms input/aoc-2024-day-23-challenge-3.txt: Answer 1: 6,2536ms input/aoc-2024-day-23-challenge-3.txt: Answer 2: 2,2911ms |
Deel 1 kan denk ik nog wel wat sneller
spoiler: Idee voor part2
Neem een set van alle connections voor een computer en zich zelf
Loopt door de connections en neem steeds een intersection als de connection nog in de candidate set zit
Voeg de computer opnieuw toe aan de candidate set.
Zou wellicht nog sneller zijn om computer zelf ook meteen toe te voegen aan connection set, maar dan moet ik weer andere dingen checken.
Loopt door de connections en neem steeds een intersection als de connection nog in de candidate set zit
Voeg de computer opnieuw toe aan de candidate set.
Zou wellicht nog sneller zijn om computer zelf ook meteen toe te voegen aan connection set, maar dan moet ik weer andere dingen checken.
https://github.com/antonr...24/23/Solution/Program.cs
Mijn implementatie was met het algoritme dat de rest ook al riepen. Hij loopt best snel toch:
Ik laat hier alleen even het aantal nodes zien. Maar de sha1 van de string klopt ook
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| $ day23 < big_inputs/aoc-2024-day-23-challenge-1.txt Executing ├── Input parsed in 660µs ├── Part 1 calculated in 121µs: 960 ├── Part 2 calculated in 11,298µs: 19 └── Total time: 12,113µs $ day23 < big_inputs/aoc-2024-day-23-challenge-2.txt Executing ├── Input parsed in 1,262µs ├── Part 1 calculated in 453µs: 2540 ├── Part 2 calculated in 22,888µs: 24 └── Total time: 24,631µs $ day23 < big_inputs/aoc-2024-day-23-challenge-3.txt Executing ├── Input parsed in 2,699µs ├── Part 1 calculated in 653µs: 4722 ├── Part 2 calculated in 42,539µs: 29 └── Total time: 45,919µs |
Ik laat hier alleen even het aantal nodes zien. Maar de sha1 van de string klopt ook
Damn, jullie oplossingen schalen beter dan verwacht! Ik heb nog twee grotere testcases toegevoegd om op te benchmarken.
Het klopt wel dat mijn random test cases hier niet specifiek op testen.
Ik heb alleen de meest basale versie geïmplementeerd waarbij je een random element als pivot pakt. Ik was er nog niet aan toegekomen het verder te optimaliseren
Misschien mis ik iets, maar geldt in beide gevallen niet dat
spoiler:
je in een suboptimale set kunt blijven zitten?
Stel de graaf bevat cliques van (a, b, c), (d, e, f), en (b, c, d, e) (voorbeeld)
Hoe garandeer je dan dat je de maximale clique van 4 vindt? Het lijkt me dat je altijd ergens moet backtracken zoals @Robbinb1993 ook doet.
Stel de graaf bevat cliques van (a, b, c), (d, e, f), en (b, c, d, e) (voorbeeld)
Hoe garandeer je dan dat je de maximale clique van 4 vindt? Het lijkt me dat je altijd ergens moet backtracken zoals @Robbinb1993 ook doet.
Het klopt wel dat mijn random test cases hier niet specifiek op testen.
:strip_icc():strip_exif()/u/266124/crop63d63fdf5b8e2_cropped.jpg?f=community)
aoc-2024-day-23-challenge-3.txt: 7ms.:
Damn, jullie oplossingen schalen beter dan verwacht! Ik heb nog twee grotere testcases toegevoegd om op te benchmarken.
[...]
Ik heb alleen de meest basale versie geïmplementeerd waarbij je een random element als pivot pakt. Ik was er nog niet aan toegekomen het verder te optimaliseren
[...]
[...]
Misschien mis ik iets, maar geldt in beide gevallen niet dat
spoiler:je in een suboptimale set kunt blijven zitten?
Stel de graaf bevat cliques van (a, b, c), (d, e, f), en (b, c, d, e) (voorbeeld)
Hoe garandeer je dan dat je de maximale clique van 4 vindt? Het lijkt me dat je altijd ergens moet backtracken zoals @Robbinb1993 ook doet.
Het klopt wel dat mijn random test cases hier niet specifiek op testen.
aoc-2024-day-23-challenge-4.txt: 20ms.
aoc-2024-day-23-challenge-5.txt: 69749ms. (De max. clique heeft een grootte van 49).
spoiler:
We kunnen het nog verder optimaliseren door in plaats van normale sets, bitsets te gebruiken. Hiermee kunnen we heel eenvoudig met AND operations P en X updaten voor de volgende iteratie. Ook andere operaties worden lichter. Voor pivotting gebruiken we weer de eenvoudige manier: het eerst mogelijke element als pivot. Dit omdat het goedkoper is dan zoeken naar alle mogelijke kandidaten voor de pivot.
https://github.com/Robbin...23/day23_bron_kerbosch.cc
[ Voor 6% gewijzigd door Robbinb1993 op 23-12-2024 11:23 ]
Vanaf 5 gaat het bij mij mis (met de foute sequences er nog even bij). Ik laat het even zitten voor nu, andere dingen te doen.
spoiler:
Heb wel door waar ik mis ga denk ik, ben iets te greedy .
.code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| input/aoc-2024-day-23-challenge-1.txt: Answer 1: 960 (1,7499ms) input/aoc-2024-day-23-challenge-1.txt: Answer 2: c097c9c81c66d0574d118062a028f78a11594fbe (2,6353ms) input/aoc-2024-day-23-challenge-2.txt: Answer 1: 2540 (4,6934ms) input/aoc-2024-day-23-challenge-2.txt: Answer 2: b469c9d964c3f37e597ee0ee57513a51a52407f6 (2,867ms) input/aoc-2024-day-23-challenge-3.txt: Answer 1: 4722 (7,2894ms) input/aoc-2024-day-23-challenge-3.txt: Answer 2: 41e4b22864b072b52b4ee2e9e835bb2bcc2c3f2a (2,6584ms) input/aoc-2024-day-23-challenge-4.txt: Answer 1: 21567 (45,5121ms) input/aoc-2024-day-23-challenge-4.txt: Answer 2: 86077b441d9921a28c1749acf6a222038ae3b231 (4,5525ms) input/aoc-2024-day-23-challenge-5.txt: Answer 1: 513096 (895,8234ms) input/aoc-2024-day-23-challenge-5.txt: Answer 2: d7858bd5d7b21f32e6b12892ebe7cf03c3748ded (aa,aj,al,au,av,bf,dp,du,eb,gc,gu,id,ii,kp,la,lo,me,mn,no,oy,pd,pz,qr,rp,so,sx,tc,to,ud,ul,us,vc,vf,vo,vx,ww,xa,xe,yu,zg,zi,zj) (37,0704ms) input/aoc-2024-day-23-challenge-6.txt: Answer 1: 0 (0,0004ms) input/aoc-2024-day-23-challenge-6.txt: Answer 2: 33e12673905f41ea2f2c5ff2f694fe59bd44961b ( bf,bm,cb,cf,do,gv,gw,ib,ja,kz,nf,nm,nr,nu,ok,ow,pl,rp,uj,ux,wj,xd,yo,yt ) (0,6058ms) input/aoc-2024-day-23-challenge-7.txt: Answer 1: 110810 (135,0649ms) input/aoc-2024-day-23-challenge-7.txt: Answer 2: 9f86767250de3d0be139ca114e374a72394cc4d5 (ab,ac,ag,al,an,au,bl,bs,bt,cv,cx,dc,ei,ej,ew,fd,fe,fq,ft,fu,fv,fw,gh,gs,hb,hi,hr,ij,io,ix,jb,je,jp,jq,kk,ks,lh,ln,lo,lt,md,mg,mn,mo,mx,no,np,oh,op,oy,pt,pw,py,qf,ql,qp,qr,qs,qy,rh,rk,ro,ru,rz,sd,sp,ss,tg,tm,tr,ty,ua,up,ur,ut,ux,uy,va,vg,vo,wk,xd,xi,xk,xl,xr,yh,yv,yw,ze,zn,zo) (37,4625ms) |
Ja, en ook een nog moeilijkere testcase (dit is zo'n beetje de moeilijkste die ik kan genereren met deze constraints aangezien dit de grens van 676 vertices en 228150 edges benadert).
Je hebt bijhoorlijk veel vooruitgang geboekt in 1 dag
Ik denk dat de auteurs van Cliquer iets langer aan hun solver gewerkt hebben.
Ik heb inmiddels ook de "nette" oplossing, met wat optimalisaties loopt ie voor de kortere testcases (challenge 1-4) sneller dan mijn probabilistische (hoewel ik die natuurlijk ook verder zou kunnen optimaliseren), en voor challenge 5 doet ie er weliswaar langer over, maar geeft hij wel het correcte antwoord
spoiler:
Geinspireerd door @Robbinb1993's oplossing in C++, heb ik ook bitsets in Rust gebruikt + een snelle exit op de bound. Ik ben niet zo ver gegaan om de colorbound te implementeren, daar moet ik eerst wat beter op studeren om het te begrijpen, maar challenge 5 geeft nu bij mij in <2 sec het juiste antwoord, snel genoeg voor nu.
Verandert z'n sig te weinig.
:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Klopt, heb ze expres apart gehouden daarom. Maar ik ben wel benieuwd hoe je algoritme werkt dat je daar niet mee overweg kunt?
Wat betreft dag 24:
Wat een opgave zeg!spoiler:
Ik probeerde het heel lang programmatisch op te lossen. Uiteindelijk bleek het makkelijker om het semi-handmatig te doen.
Mijn idee voor de automatische oplossing was:
spoiler:
Ik had om te beginnen de invoer gevisualiseerd als een graaf. Dan zie je heel mooi de structuur als serie van 45 adders, maar waar de fouten zitten is niet meteen duidelijk.
Om het programmatisch op te lossen begon ik met het identificeren van verdachte wires. Bijvoorbeeld:
elke uitvoer z2 t/m z45 heeft twee XOR poorten als invoer (z0, z1 en z46 zijn speciale gevallen); als dat niet zo is klopt er iets niet en moet die poort dus geswapt worden.
De OR ports propageren de carries. Elke OR port moet twee ANDs als invoer hebben, anders klopt er iets niet. Etc.
Op die manier had ik 8 “foute” wires gevonden en toen dacht ik dat ik alleen nog maar de verschillende permutaties hoefde te proberen om uit te vinden wat met wat geswapt moet worden.
Om te checken of een permutatie correct was simuleerde ik simpelweg het circuit 1000 keer met random inputs tussen de 0 en 1045. Dat klinkt inefficiënt maar dat valt erg mee want je kunt meteen stoppen zodra je 1 fout antwoord krijgt (immers het juiste circuit geeft altijd het correcte antwoord) en als de wiring verkeerd is krijg je heel vaak een verkeerd antwoord. Omgekeerd is de kans dat je 1000 keer een false positive krijgt praktisch nihil.
Helaas vond ik met deze methode geen enkele geldige permutatie. Dus terug naar de graaf; gelukkig kon ik op basis van de “foute” wires wel de adders vinden waar bugs in zaten, en handmatig zijn de fouten redelijk eenvoudig te herstellen.
Om het programmatisch op te lossen begon ik met het identificeren van verdachte wires. Bijvoorbeeld:
elke uitvoer z2 t/m z45 heeft twee XOR poorten als invoer (z0, z1 en z46 zijn speciale gevallen); als dat niet zo is klopt er iets niet en moet die poort dus geswapt worden.
De OR ports propageren de carries. Elke OR port moet twee ANDs als invoer hebben, anders klopt er iets niet. Etc.
Op die manier had ik 8 “foute” wires gevonden en toen dacht ik dat ik alleen nog maar de verschillende permutaties hoefde te proberen om uit te vinden wat met wat geswapt moet worden.
Om te checken of een permutatie correct was simuleerde ik simpelweg het circuit 1000 keer met random inputs tussen de 0 en 1045. Dat klinkt inefficiënt maar dat valt erg mee want je kunt meteen stoppen zodra je 1 fout antwoord krijgt (immers het juiste circuit geeft altijd het correcte antwoord) en als de wiring verkeerd is krijg je heel vaak een verkeerd antwoord. Omgekeerd is de kans dat je 1000 keer een false positive krijgt praktisch nihil.
Helaas vond ik met deze methode geen enkele geldige permutatie. Dus terug naar de graaf; gelukkig kon ik op basis van de “foute” wires wel de adders vinden waar bugs in zaten, en handmatig zijn de fouten redelijk eenvoudig te herstellen.
Ik ben er dus wel even zoet mee geweest, maar ik vond het wel een erg leuk probleem om op te lossen!
Ik doe geen dijkstra, ik reken erop dat er maar 1 mogelijke weg is. Dus ik kijk steeds vanaf de huidige positie of ik vooruit, naar links, naar rechts of achteruit kan. Die laatste is er alleen maar zodat ik niets speciaals hoef te doen voor de start, voor elke andere positie komt ie daar nooit. Maar in jouw geval natuurlijk wel want dan zijn er doodlopende paden
.Dat pad vult dan een grid met afstanden en een lijst met coordinaten. Die coordinaten loop ik dan vervolgens lineair af om in het grid in een manhattan-straal van 20 te zoeken naar posities die minstens 100ps tijdswinst opleveren.
Ik kan mijn pad-vind-algoritme aanpassen zodat hij werkt met generieke doolhoven, maar daarmee ben ik er nog niet omdat je bij een cheat eventueel een vertakking kan nemen die niet bij het normale pad hoort, zonder dat je voor die vertakking al hoeft te cheaten.
Ik moet dan feitelijk een floodfill doen vanuit de start voor alle afstanden vanaf de start, en nog een floodfill vanuit de finish voor alle afstanden tot de finish, en dan voor elke bereikbare positie zoeken maar andere bereikbare posities in een straal van 20.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ja dag 24 was wel weer een AOC klassieker
spoiler:
Ook met de hand opgelost. Eerst met een test-invoer voor iedere index de (x,y) op (0,1), (1,0) en (1,1) (en de andere 43 (x,y) op (0,0) gezet) gecheckt waar de fouten ongeveer zaten, daarna met hand lopen zoeken. Zo 's ochtends vroeg zonder koffie op was het wel een gedoe om geen fouten te maken met al die memorabele namen als rht, ngn, etc )
en met een schema van een adder erbij
Nu nog eens rustig nadenken over een echt programmatische oplossing.
en met een schema van een adder erbij
Nu nog eens rustig nadenken over een echt programmatische oplossing.
Verandert z'n sig te weinig.
Dat is precies wat ik had gedaan. In theorie doe ik dan wel twee keer zoveel werk vergeleken met jouw aanpak (misschien ietsje meer zelfs, omdat je behalve naar voren ook naar links en rechts moet zoeken om geen paden te missen), hoewel het ook niet heel veel uitmaakt voor de totaaltijd, die bij vrijwel alle oplossingen die ik gezien heb wordt gedomineerd door de berekening in deel 2.
Daar heb je helemaal gelijk in, maar ik wilde verifiëren dat het antwoord daadwerkelijk klopte voordat ik m'n antwoord inzond. (Ik hebt dit jaar nog geen enkele foute inzending gedaan, en dat wil ik graag zo houden.)
Achteraf bleek de gevonden set überhaupt niet te kloppen
dus ik ben blij dat ik niet geprobeerd heb 'm in te zenden.Uiteindelijk heb ik wel een programmatische oplossing weten te schrijven, al is het relatief brute force: 24.py
Wat voor tools gebruiken jullie trouwens om dit soort problemen te visualiseren? (Ik neem aan dat de meeste mensen die dit probleem opgelost hebben de invoer op de een of andere manier gevisualiseerd hebben.) Ik gebruik GraphViz en QVGE; het werkt wel, maar het zijn geen pareltjes van gebruiksvriendelijkheid.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ik heb iig een oplossing die alle fouten in mijn input er uit haalt. Andere swaps heb ik nog geen fix voor gemaakt.
https://github.com/Janoz-...com/janoz/aoc/y2024/day24
Ben trouwens wel heel benieuwd naar andere input om nog wat automatische fixes toe te kunnen voegen
https://github.com/Janoz-...com/janoz/aoc/y2024/day24
Ben trouwens wel heel benieuwd naar andere input om nog wat automatische fixes toe te kunnen voegen
[ Voor 40% gewijzigd door Janoz op 24-12-2024 15:00 ]
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ik betwijfel of de inputs veel van elkaar verschillen; het lijkt er op dat de swaps vrij specifiek zijn dus mogelijk zijn ze met de hand gemaakt en dus voor iedereen hetzelfde. Maar als je wil proberen, mijn invoer staat hier: 24.in (antwoorden: 24.ref).:
Ben trouwens wel heel benieuwd naar andere input om nog wat automatische fixes toe te kunnen voegen
Hoe moeilijk kan het zijn?:
Het zal me niks verbazen als de structuur vrijwel hetzelfde is voor iedereen, maar dat de "intermediate" name gerandomized zijn. Die van mij ziet er op het eerste gezicht wel heel anders uit, maar ben te lui om nu een stuk code te schrijven die de structuur vergelijkt
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Bestanden heten trouwens wel dag23
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Graag gedaan @Asgardian28, het was weer leuk! Op de valreep nog ingehaald door @Soultaker, maar volgens mij heb ik op de twee moeilijke dagen bovenaan gestaan
Als nagerechtje nog mijn oplossing voor vandaag:
Tot volgend jaar
Als nagerechtje nog mijn oplossing voor vandaag:
spoiler:
items = [{i for i, c in enumerate(item) if c == '#'} for item in open('in.txt').read().split('\n\n')]
print(sum(not l&k for k in items for l in items)//2)
print(sum(not l&k for k in items for l in items)//2)
Tot volgend jaar
Pfffff dag 24 was een pittige, net pas afgerond. Gelukkig was die van vandaag goed te doen. Ik doe pas sinds 2021 mee en nu voor het eerst alles kunnen oplossen zonder hints of antwoorden Leuk om hier elke dag de discussie mee te lezen en achteraf te zien hoe ik veel eerder / beter tot een oplossing had kunnen komen. Bedankt allemaal!
Leuk om hier elke dag de discussie mee te lezen en achteraf te zien hoe ik veel eerder / beter tot een oplossing had kunnen komen. Bedankt allemaal!
Honda CB750 Hornet :: Yamaha Fazer FZ6 SA (2011 - 2023) | F1Pool.net
Dat was hem weer! Leuk dit jaar, nieuwe taal voor mij (Rust) af en toe wel wat zitten klunzen daardoor, en natuurlijk lang zitten puzzelen op de echte hersenkrakers (mijn vrouw overwoog een interventie op dag 21... 
)
Net buiten de top 3 op mijn werk (concurrentie was wat steviger dan vorig jaar).
En, extra doel:
Volledige oplossing van alle 25 dagen in minder dan een halve seconde, op een 3,5 jaar oude laptop
Langzaamste oplossing was dag 16, slechts 1 keer rayon gebruikt.
En @Soultaker bedankt voor alle extra challenges! Heeft me super geholpen om weer wat extra concepten te leren, en de uiteindelijke oplossingen sneller en mooier te maken.
)Net buiten de top 3 op mijn werk (concurrentie was wat steviger dan vorig jaar).
En, extra doel:
time cargo run --release
[..]
Parsing: 271.696µs
Day 25 - Part 1: 3365
generator: 121ns,
runner: 814.007µs
Day 25 - Part 2: Done!
generator: 50ns,
runner: 141ns
real 0m0.366s
user 0m0.463s
sys 0m0.010s
Volledige oplossing van alle 25 dagen in minder dan een halve seconde, op een 3,5 jaar oude laptop
Langzaamste oplossing was dag 16, slechts 1 keer rayon gebruikt.
En @Soultaker bedankt voor alle extra challenges! Heeft me super geholpen om weer wat extra concepten te leren, en de uiteindelijke oplossingen sneller en mooier te maken.
[ Voor 14% gewijzigd door FCA op 25-12-2024 09:25 ]
Verandert z'n sig te weinig.
Zo, dag 24 was een leuke opdracht
. Gezien m'n ervaring met nandbox.oisyn.nl had ik al vrij snel door wat de bedoeling was voor deel 2. Het intypen van een goede oplossing heeft me wel wat uurtjes gekost daarentegen . Ik ben 2x helemaal opnieuw begonnen. Algoritmisch kunnen wat lineaire searches hier en daar wellicht iets efficienter maar met <200µs is dat zinloos. Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-1.txt`
Time spent: 192.5µs
42765237996237 - igf,ihh,kwt,sta,twb,wjc,z19,z25
Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-2.txt`
Time spent: 187.0µs
30069256867894 - aqi,asd,goh,nts,uib,vwl,z15,z43
Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-3.txt`
Time spent: 187.2µs
23888547395145 - ioo,kbg,nwg,prc,qps,roh,z10,z20
Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-4.txt`
Time spent: 184.2µs
46937781801414 - afi,gmg,hra,riv,tjt,vkv,z05,z28
Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-5.txt`
Time spent: 190.9µs
57012758521972 - owg,rla,tpj,umm,z00,z01,z08,z11Ik heb niet zo'n zin om de hashes te vergelijken dus ik ga er maar van uit dat het klopt
. Jammer dat je geen inputs hebt met veel meer verwisselingen. Ik denk dat mijn algoritme ze met gemak allemaal vindt, zolang van een specifieke gate er altijd maar 1 input is die verwisseld wordt.spoiler:
Het principe is vrij simpel. Je hebt een half-adder die 2 bits input en 2 bits output heeft. De inputs worden opgeteld en de outputs zijn een resultaat en een carry.
Met inputs (a, b) en outputs (r, c):
r = a XOR b
c = a AND b
Dan bestaat er ook nog een full-adder die 3 bits optelt. Je kunt die bouwen van 2 half-adders, maar efficienter uitgeschreven wordt het:
r = (a XOR b) XOR c
c = ((a XOR b) AND c) OR (a AND b)
Waarbij de c dus altijd de carry is van de half-adder of full-adder van de vorige bit.
Ik identificeer in totaal 5 operaties:
HalfAdd(i): x(i) XOR y(i)
HalfCarry(i): x(i) AND y(i)
FullAdd(1): HalfAdd(1) XOR HalfCarry(0)
FullAdd(i>1): HalfAdd(i) XOR FullCarry(i - 1)
PartialFullCarry(1): HalfAdd(1) AND HalfCarry(0)
PartialFullCarry(i>1): HalfAdd(i) AND FullCarry(i - 1)
FullCarry(i): HalfCarry(i) OR PartialFullCarry(i)
Met de uiteindelijke outputs:
z00 = HalfAdd(0)
z{i@1..n} = FullAdd(i)
z{n} = FullCarry(n - 1)
Ik loop in bit-volgorde (van z00 t/m z45) door de outputs, waarbij ik elke operatie steeds recursief ontleedt in de deelstappen, en er dan een gate bij zoek die die deelstap doet. Als ik zo'n gate niet vindt, dan moet er een gate zijn met dezelfde operator (AND, OR, XOR) en 1 van de juiste inputs, waarbij de andere niet klopt. En bovendien moet ik al eens een gate zijn tegengekomen die de juiste input kan aanleveren.
Het blijkt altijd zo te zijn dat er precies 1 gate is met de juiste operator en 1 juiste input. De gate van de foute input swap ik dan met de gate van de juiste input, en dan ga ik verder.
Verder kan het nog zo zijn dat een z-output niet klopt. Bijvoorbeeld dat ik wel een FullAdd(10) vindt, maar dat dat niet de gate voor z10 is. In dat geval moeten z10 en die van die FullAdd(10) geswapped worden.
Als je alle z-outputs hebt doorlopen heb je ook alle swaps gedetecteerd
Met inputs (a, b) en outputs (r, c):
r = a XOR b
c = a AND b
Dan bestaat er ook nog een full-adder die 3 bits optelt. Je kunt die bouwen van 2 half-adders, maar efficienter uitgeschreven wordt het:
r = (a XOR b) XOR c
c = ((a XOR b) AND c) OR (a AND b)
Waarbij de c dus altijd de carry is van de half-adder of full-adder van de vorige bit.
Ik identificeer in totaal 5 operaties:
HalfAdd(i): x(i) XOR y(i)
HalfCarry(i): x(i) AND y(i)
FullAdd(1): HalfAdd(1) XOR HalfCarry(0)
FullAdd(i>1): HalfAdd(i) XOR FullCarry(i - 1)
PartialFullCarry(1): HalfAdd(1) AND HalfCarry(0)
PartialFullCarry(i>1): HalfAdd(i) AND FullCarry(i - 1)
FullCarry(i): HalfCarry(i) OR PartialFullCarry(i)
Met de uiteindelijke outputs:
z00 = HalfAdd(0)
z{i@1..n} = FullAdd(i)
z{n} = FullCarry(n - 1)
Ik loop in bit-volgorde (van z00 t/m z45) door de outputs, waarbij ik elke operatie steeds recursief ontleedt in de deelstappen, en er dan een gate bij zoek die die deelstap doet. Als ik zo'n gate niet vindt, dan moet er een gate zijn met dezelfde operator (AND, OR, XOR) en 1 van de juiste inputs, waarbij de andere niet klopt. En bovendien moet ik al eens een gate zijn tegengekomen die de juiste input kan aanleveren.
Het blijkt altijd zo te zijn dat er precies 1 gate is met de juiste operator en 1 juiste input. De gate van de foute input swap ik dan met de gate van de juiste input, en dan ga ik verder.
Verder kan het nog zo zijn dat een z-output niet klopt. Bijvoorbeeld dat ik wel een FullAdd(10) vindt, maar dat dat niet de gate voor z10 is. In dat geval moeten z10 en die van die FullAdd(10) geswapped worden.
Als je alle z-outputs hebt doorlopen heb je ook alle swaps gedetecteerd
[ Voor 32% gewijzigd door .oisyn op 26-12-2024 04:56 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Het is ook wel meteen compleet uitgestorven hier
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
/u/49730/babby%2520tux.png?f=community)
Deze aanpak heb ik uiteindelijk ook toegepast! Brute force ging voor geen meter:
[...]
Zo, dag 24 was een leuke opdracht
Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-1.txt` Time spent: 192.5µs 42765237996237 - igf,ihh,kwt,sta,twb,wjc,z19,z25 Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-2.txt` Time spent: 187.0µs 30069256867894 - aqi,asd,goh,nts,uib,vwl,z15,z43 Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-3.txt` Time spent: 187.2µs 23888547395145 - ioo,kbg,nwg,prc,qps,roh,z10,z20 Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-4.txt` Time spent: 184.2µs 46937781801414 - afi,gmg,hra,riv,tjt,vkv,z05,z28 Running `target\release\day24.exe -i .\extra\aoc-2024-day-24-challenge-5.txt` Time spent: 190.9µs 57012758521972 - owg,rla,tpj,umm,z00,z01,z08,z11
Ik heb niet zo'n zin om de hashes te vergelijken dus ik ga er maar van uit dat het klopt
spoiler:Het principe is vrij simpel. Je hebt een half-adder die 2 bits input en 2 bits output heeft. De inputs worden opgeteld en de outputs zijn een resultaat en een carry.
Met inputs (a, b) en outputs (r, c):
r = a XOR b
c = a AND b
Dan bestaat er ook nog een full-adder die 3 bits optelt. Je kunt die bouwen van 2 half-adders, maar efficienter uitgeschreven wordt het:
r = (a XOR b) XOR c
c = ((a XOR b) AND c) OR (a AND b)
Waarbij de c dus altijd de carry is van de half-adder of full-adder van de vorige bit.
Ik identificeer in totaal 5 operaties:
HalfAdd(i): x(i) XOR y(i)
HalfCarry(i): x(i) AND y(i)
FullAdd(1): HalfAdd(1) XOR HalfCarry(0)
FullAdd(i>1): HalfAdd(i) XOR FullCarry(i - 1)
PartialFullCarry(1): HalfAdd(1) AND HalfCarry(0)
PartialFullCarry(i>1): HalfAdd(i) AND FullCarry(i - 1)
FullCarry(i): HalfCarry(i) OR PartialFullCarry(i)
Met de uiteindelijke outputs:
z00 = HalfAdd(0)
z{i@1..n} = FullAdd(i)
z{n} = FullCarry(n - 1)
Ik loop in bit-volgorde (van z00 t/m z45) door de outputs, waarbij ik elke operatie steeds recursief ontleedt in de deelstappen, en er dan een gate bij zoek die die deelstap doet. Als ik zo'n gate niet vindt, dan moet er een gate zijn met dezelfde operator (AND, OR, XOR) en 1 van de juiste inputs, waarbij de andere niet klopt. En bovendien moet ik al eens een gate zijn tegengekomen die de juiste input kan aanleveren.
Het blijkt altijd zo te zijn dat er precies 1 gate is met de juiste operator en 1 juiste input. De gate van de foute input swap ik dan met de gate van de juiste input, en dan ga ik verder.
Verder kan het nog zo zijn dat een z-output niet klopt. Bijvoorbeeld dat ik wel een FullAdd(10) vindt, maar dat dat niet de gate voor z10 is. In dat geval moeten z10 en die van die FullAdd(10) geswapped worden.
Als je alle z-outputs hebt doorlopen heb je ook alle swaps gedetecteerd
Na het verdiepen in de schakeling heb ik het over de gates gelegd om de fouten te detecteren. Daarna de gates verwisseld in de betreffende full adders, zo waren het slechts 4 -6 mogelijke swaps en dat was prima te brute forcen. Volledig logisch oplossen kan vast ook maar ik was er wel klaar mee. Finish gehaald, zij het 2 dagen te laat.
Tja
Zeker, ik ben alweer druk bezig met de aivd-kerstpuzzel.:
Het is ook wel meteen compleet uitgestorven hier
When life gives you lemons, start a battery factory
Ik kom de komende dagen ergens nog hier terug, nu de kerstdagen (en verplichtingen) weer even voorbij zijn, kan ik mij gaan focussen op 23, 24 deel 2 en 25! Dan heb ik 2024 ook helemaal klaar. Als ik de flow een beetje kan vasthouden wil ik ook 2023 nog af gaan maken!:
Het is ook wel meteen compleet uitgestorven hier
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ik zit nog eens terug te bladeren en ik moet zeggen dat dit jaar wel een stuk makkelijker was dan vorig jaar. Echt redelijk pittige, zoals 2023 dag 21 deel 2 of 2023 dag 24 deel 2 zaten er niet tussen.
Welke vonden jullie dit jaar het lastigst?
Ik denk dat ik veruit het meeste tijd heb gespendeerd aan de binary adder (dag 24 deel 2). Het vinden van de juiste strategie bij die keypads (dag 21) kostte ook wel even tijd om uit te werken.
.Edit: heh, ik realiseer me nu dat ik voor beide jaren dezelfde dagen noem
Welke vonden jullie dit jaar het lastigst?
Ik denk dat ik veruit het meeste tijd heb gespendeerd aan de binary adder (dag 24 deel 2). Het vinden van de juiste strategie bij die keypads (dag 21) kostte ook wel even tijd om uit te werken.
.Edit: heh, ik realiseer me nu dat ik voor beide jaren dezelfde dagen noem
[ Voor 7% gewijzigd door .oisyn op 28-12-2024 14:57 ]
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Dit jaar vond ik dag 21 en 24 ook het lastigst. Van 2023 vond ik dag 24 grappig genoeg niet lastig, vanwege een lineaire algebra trucje. Dag 21 en 23 van 2023 heb ik veel te lang op gezeten.:
Ik zit nog eens terug te bladeren en ik moet zeggen dat dit jaar wel een stuk makkelijker was dan vorig jaar. Echt redelijk pittige, zoals 2023 dag 21 deel 2 of 2023 dag 24 deel 2 zaten er niet tussen.
Welke vonden jullie dit jaar het lastigst?
Ik denk dat ik veruit het meeste tijd heb gespendeerd aan de binary adder (dag 24 deel 2). Het vinden van de juiste strategie bij die keypads (dag 21) kostte ook wel even tijd om uit te werken.
.Edit: heh, ik realiseer me nu dat ik voor beide jaren dezelfde dagen noem
When life gives you lemons, start a battery factory
Ik heb voor de grap voor dag 25 nog een andere implementatie gemaakt die in O(1) per key kan opzoeken op hoeveel locks hij past
spoiler:
Voor de locks hou ik de notatie aan van AoC, dus [x,y,z,w,v], maar voor de keys doe ik het "omgekeerde" en doe ik hetzelfde als bij de locks. Dus een key van [0,0,0,0,0] past alleen op een lock van [0,0,0,0,0], en een key van [5,5,5,5,5] past overal op. En een key past op een lock als alle elementen van de lock kleiner-gelijk zijn dan die van de key.
Elke lock noteer ik in een 6x6x6x6x6 array op basis van de indices van de notatie. Daarna "smeer" ik de array uit door in alle 5 de richtingen de waarden bij elkaar op te tellen. Hierdoor staat in de array hoeveel locks matchen met de key die overeenkomt met dat element in de array. Daarna is het simpelweg een kwestie van alle keys opzoeken in de array.
Elke lock noteer ik in een 6x6x6x6x6 array op basis van de indices van de notatie. Daarna "smeer" ik de array uit door in alle 5 de richtingen de waarden bij elkaar op te tellen. Hierdoor staat in de array hoeveel locks matchen met de key die overeenkomt met dat element in de array. Daarna is het simpelweg een kwestie van alle keys opzoeken in de array.
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Als er toch nog wat mensen bezig zijn, dan hierbij wat extra testdata voor dag 25: aoc-2024-day-24-challenge-1-and-2.zip (eerste bevat geen dubbelen, tweede wel).
Technisch gezien is dat allemaal O(1). Qua algoritme wordt het eigenlijk pas interessant als de sleutels groter zouden kunnen zijn dan het 5x5 formaat. Momenteel is het zo dat parsen de grootste overhead heeft.
$ ./solve < aoc-2024-day-25-challenge-1.txt Parsing took: 384 us Solving took: 1446 us ...464 $ ./solve < aoc-2024-day-25-challenge-2.txt Parsing took: 51936 us Solving took: 2041 us ...696
Slim verzonnen. Ik had gewoon wat geneste for-loops gehackt. Dat is in theorie (7*6/2)5 = 4,084,101 iteraties maar dat is snel zat in de praktijk. Jouw optimalisatie reduceert dat tot 7×65 = 54,432 iteraties, niet per se met dezelfde constante factor natuurlijk.:
Ik heb voor de grap voor dag 25 nog een andere implementatie gemaakt die in O(1) per key kan opzoeken op hoeveel locks hij past
Technisch gezien is dat allemaal O(1). Qua algoritme wordt het eigenlijk pas interessant als de sleutels groter zouden kunnen zijn dan het 5x5 formaat. Momenteel is het zo dat parsen de grootste overhead heeft.
:strip_exif()/u/68919/logoblad.gif?f=community)
Deel 2 van dag 24 ook weten op te lossen (op nieuwjaarsdag notabene)! Deze was voor mij het lastigst.
Dus 2024 is helemaal klaar!
spoiler:
In eerste instantie dacht ik dat het voldoende zou zijn om een 1 een voor een op de x en y te zetten en dan de output controleren. Als het niet klopt, kunnen we de outputs gaan wisselen. Alleen was dat iets te makkelijk gedacht. Uitendelijk van de input iets gemaakt dat kan worden ingelezen door https://digitaljs.tilk.eu/ en toen begon het kwartje deels te vallen. Ik begon de juiste outputs (die ik hiervoor had gevonden) te vergelijken met de foute. Als ik het goed herinner, zag ik ergens een OR, wat niet zou moeten kunnen. Uiteindelijk nog even moeten puzzelen met de edgecases (eerste bit, laatste bit etc.)
Dus 2024 is helemaal klaar!
Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.
Ik ben maar eens begonnen om alles te doen en heb 2015 bijna af, maar dag 19 deel 2 is wel even een dingetje hoor
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Ik heb toevallig ook laatst alles van 2015 opgelost, en ik had ook even moeite met 19 deel 2. Maar hij is goed op te lossen met::
Ik ben maar eens begonnen om alles te doen en heb 2015 bijna af, maar dag 19 deel 2 is wel even een dingetje hoor
spoiler:
A*. Oftewel Dijkstra, maar dan nog met een heuristic van hoeveel stappen je minimaal nodig hebt vanaf dat punt om het einde te bereiken (lowerbound). En ik had het ook omgekeerd opgelost: van eindsituatie terug naar het begin.
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'