Advent of Code 2024

[Robbinb1993]

[b].oisyn schreef op maandag 16 december 2024 @ 01:18:
@Robbinb1993 Wat mijn implementatie denk ik vooral sneller maakt is het feit dat jij 2x de processmove doorloopt. Ik gooi alle dozen in een queue, zodat ik later die queue nog een keer kan aflopen om de posities te updaten.

Ik call de processMultiWidthMove methode vanuit move nu nog maar 1 keer:
https://github.com/Robbin.../blob/main/day15/day15.cc. Dit maakte het ongeveer 20% sneller. Ik denk dat er nog wel winst te behalen valt door processMultiWidthMove iteratief te maken, aangezien recursief vanwege de vele function calls ook overhead geeft.

Soultaker schreef op maandag 16 december 2024 @ 08:24:
Hier nog wat extra testcases voor dag 16: aoc-2024-day-16-testcases.zip (antwoorden zitten erbij).

De cases zijn te klein om te benchmarken; het zijn meer edge cases om de correctheid van je oplossing te valideren.

De turnalot case was nuttig om nog een bottleneck uit mn code te halen.

[ Voor 34% gewijzigd door Robbinb1993 op 16-12-2024 11:58 ]

[Varienaja]

Wauw. Weinig reacties vandaag. En ook nog relatief weinig gouden sterren in ons leaderboard. Ist dit een lastige? Ik had ook wat probleempjes. (Een pad mag zichzelf kruisen. En als je meerdere paden zoekt dan kan het zijn dat je eenzelfde punt met dezelfde kosten meerdere keren moet bekijken.) Maar desondanks vond ik 'm erg goed te doen.

Anyway. Dag 16 in Java.

[Soultaker]

Ter aanvulling van de eerdere testdata, hier nog wat grotere data geschikt om te benchmarken:
aoc-2024-day-16-mazes.zip.

Antwoorden en referentie-tijden:

$ time ./solve2 < maze-small.txt 
..27.02
..03

real	0m0.014s
user	0m0.003s
sys	0m0.011s

$ time ./solve2 < maze-medium.txt
..05.26
..27

real	0m0.107s
user	0m0.093s
sys	0m0.013s

$ time ./solve2 < maze-large.txt
...17.22
...23

real	0m2.194s
user	0m1.632s
sys	0m0.554s

[Soultaker]

Varienaja schreef op maandag 16 december 2024 @ 17:51:
Wauw. Weinig reacties vandaag. En ook nog relatief weinig gouden sterren in ons leaderboard.

Het komt waarschijnlijk omdat het weekend weer voorbij is, dus hebben mensen minder vrije tijd om aan AoC te besteden.

Maar er zijn ook mensen waarvan ik weet dat ze de problemen vooral 's avonds oplossen, zoals b.v. @.oisyn, die het probleem van vandaag ook nog niet heeft opgelost, terwijl ik zeker weet dat hij er weinig moeite mee zal hebben. Die ster komt dus nog wel.

Los daarvan is dit een voorbeeld van een probleem wat lastig is voor de meer casual deelnemers, terwijl het vrij eenvoudig is voor mensen die bekend zijn met

spoiler:

Dijkstra's algoritme.

[.oisyn]

Oh ik zit nog helemaal niet in de GoT groep.
.edit: oh jawel, je hoeft blijkbaar niet ieder jaar opnieuw aan te melden

[ Voor 46% gewijzigd door .oisyn op 16-12-2024 19:51 ]

[KabouterSuper]

Vandaag met veel onnodige pijn een oplossing voor deel een. Nu te moe om überhaupt te snappen wat ze met deel 2 willen weten.

[MatHack]

Deel 1 had ik zelf ook zo geïmplementeerd, doordat die nog op de plank lag van een ander jaar. Nu eindelijk bezig met deel 2, want er moest ook nog werk/studie gedaan worden vandaag.

KabouterSuper schreef op maandag 16 december 2024 @ 20:22:
Vandaag met veel onnodige pijn een oplossing voor deel een. Nu te moe om überhaupt te snappen wat ze met deel 2 willen weten.

spoiler: uitleg dag 16, deel 2

Er zijn meerdere paden die dezelfde score hebben als de score gevonden in deel 1, vind de tiles die samen al die paden maken.

[ Voor 49% gewijzigd door MatHack op 16-12-2024 20:28 ]

[Robbinb1993]

Soultaker schreef op maandag 16 december 2024 @ 18:29:
Ter aanvulling van de eerdere testdata, hier nog wat grotere data geschikt om te benchmarken:
aoc-2024-day-16-mazes.zip.

Antwoorden en referentie-tijden:

$ time ./solve2 < maze-small.txt 
..27.02
..03

real	0m0.014s
user	0m0.003s
sys	0m0.011s

$ time ./solve2 < maze-medium.txt
..05.26
..27

real	0m0.107s
user	0m0.093s
sys	0m0.013s

$ time ./solve2 < maze-large.txt
...17.22
...23

real	0m2.194s
user	0m1.632s
sys	0m0.554s

maze-small.txt: 5ms.
maze-medium.txt: 151ms.
maze-large.txt: 4460ms.

spoiler:

De bottleneck zit vooral in Dijkstra. Ik heb het gecompressed met ID's waarin x, y en dir opgeslagen zijn. Misschien dat het sneller kan met een heuristic?

https://github.com/Robbin.../blob/main/day16/day16.cc

[W1LL3M]

Varienaja schreef op maandag 16 december 2024 @ 17:51:
Wauw. Weinig reacties vandaag. En ook nog relatief weinig gouden sterren in ons leaderboard. Ist dit een lastige? Ik had ook wat probleempjes. (Een pad mag zichzelf kruisen. En als je meerdere paden zoekt dan kan het zijn dat je eenzelfde punt met dezelfde kosten meerdere keren moet bekijken.) Maar desondanks vond ik 'm erg goed te doen.

Anyway. Dag 16 in Java.

Een pad mag zichzelf kruisen, maar dan maak je wel 2 afslagen van 1000 punten ieder te veel, dus die optie valt sowieso al af.

[FCA]

Deel 1 was redelijk soepel te doen

spoiler:

had gisteren zelfs nog lopen spelen met Dijkstra implementeren, maar de implementatie was niet bruikbaar voor vandaag want algemene grafen in Rust is ... interessant. Iets met heel veel Rc<RefCell<Edge>> e.d. om een algemene graaf te implementeren

Voor deel 2 kwam er werk tussen (wie plant er nou meetings die voor 9 uur beginnen ) en hoewel ik wel een eerste implementatie in de trein had zitten bouwen zat er een stom foutje in waardoor ik in een infinite loop terecht kwam, en kwam ik er in een drukke trein niet meer uit, tot ik na een hele ochtend vol meetings eindelijk een kwartiertje rust/lunchpauze had en het probleem kon oplossen.

spoiler:

Ik zat lang te kloten met het vinden van een goede manier om nodes als "klaar" te beschouwen, zeker omdat je er vanuit verschillende richtingen kunt komen, en ik dat dan als andere nodes wilde beschouwen. Uiteindelijk een check op de afstand van de node gedaan: als ik al een kortere afstand heb gevonden voor die node overslaan, anders (ook als de afstand gelijk is) doorgaan.

[FCA]

Soultaker schreef op maandag 16 december 2024 @ 18:29:
Ter aanvulling van de eerdere testdata, hier nog wat grotere data geschikt om te benchmarken:
aoc-2024-day-16-mazes.zip.

Antwoorden en referentie-tijden:

$ time ./solve2 < maze-small.txt 
..27.02
..03

real	0m0.014s
user	0m0.003s
sys	0m0.011s

$ time ./solve2 < maze-medium.txt
..05.26
..27

real	0m0.107s
user	0m0.093s
sys	0m0.013s

$ time ./solve2 < maze-large.txt
...17.22
...23

real	0m2.194s
user	0m1.632s
sys	0m0.554s

Hmmm... mijn implementatie is niet bijzonder snel blijkt, en er zit een of andere obscure edge case alleen in de medium maze. Ik krijg het goede antwoord voor het kleine maze (in ~170ms), het goede antwoord voor je test-mazes (en de AOC input natuurlijk), het goede antwoord voor deel 1 van het grote maze (deel 2 duurt me te lang, deel 1 duurt er al 12s over), maar voor je medium maze krijg ik heel snel het foute antwoord (hij vindt blijkbaar geen enkele route van start naar het einde).

[.oisyn]

W1LL3M schreef op maandag 16 december 2024 @ 20:55:
[...]

Een pad mag zichzelf kruisen, maar dan maak je wel 2 afslagen van 1000 punten ieder te veel, dus die optie valt sowieso al af.

Dat is sowieso niet waar.

#########
#######E#
####....# 
####.##.#
#.......#
#.##.####
#.##.####
#S...####
#########

Er zijn 2 kortste paden die elkaar kruisen. Beide hebben 3 90-graden bochten. Het gekruiste punt is goedkoper via de ene kant te bereiken dan via de de andere kant.

Ik moet zeggen dat ik deel 2 nog best lastig vindt . Ik moet nog even terug naar de tekentafel, want ik kan niet echt een lekkere datastructuur vinden die de gebaande paden goed opslaat.

[ Voor 19% gewijzigd door .oisyn op 16-12-2024 22:03 ]

[W1LL3M]

.oisyn schreef op maandag 16 december 2024 @ 22:00:
[...]


Dat is sowieso niet waar.

#########
#######E#
####OOOO# 
####O##O#
#OOOOOOO#
#O##O####
#O##O####
#SOOO####
#########

Dit pad kruist elkaar. Beide hebben 3 90-graden bochten. Het gekruiste punt is goedkoper via de ene kant te bereiken dan via de de andere kant.

Daar kruisen 2 afzonderlijke paden elkaar, en inderdaad, je kunt de 2 kruispunten met verschillende scores bereiken, je kunt bijhouden van welke kant je kwam ze uit elkaar te houden.
Tuurlijk, dat kan, maar Varienaja stelde dat "Een pad mag zichzelf kruisen". Dat mag wel maar heeft geen nut.

Part 2 ook al afgerond zonder Dijkstra algoritme, maar het draait nog in < 3 seconden dus acceptabel.

[ Voor 18% gewijzigd door W1LL3M op 16-12-2024 22:19 ]

[.oisyn]

Ah, je hebt idd gelijk dat hij dat strict gezien zei, en dan heb je een punt, maar volgens mij was dat niet wat hij bedoelde

[W1LL3M]

Als bijvoorbeeld rechts afslaan (veel) goedkoper was dan links zou het voordeliger kunnen zijn om je eigen pad te kruisen

[dcm360]

W1LL3M schreef op maandag 16 december 2024 @ 22:24:
Als bijvoorbeeld rechts afslaan (veel) goedkoper was dan links zou het voordeliger kunnen zijn om je eigen pad te kruisen

Maar is het wel kruisen als je dan een driekwart draai rechtsom maakt op dezelfde plaats? Want dat is dan ineens de goedkoopste oplossing om naar links te gaan.
En ik heb in mijn hoofd nu soort van visueel zitten hoe dat er in de praktijk uit zou zien als race...

[ Voor 13% gewijzigd door dcm360 op 16-12-2024 23:10 ]

[.oisyn]

Robbinb1993 schreef op maandag 16 december 2024 @ 20:45:
[...]


maze-small.txt: 5ms.
maze-medium.txt: 151ms.
maze-large.txt: 4460ms.

spoiler:

De bottleneck zit vooral in Dijkstra. Ik heb het gecompressed met ID's waarin x, y en dir opgeslagen zijn. Misschien dat het sneller kan met een heuristic?

https://github.com/Robbin.../blob/main/day16/day16.cc

Ik had A* met een min-cost heuristic maar ik heb 'm weggegooid want het maakte het alleen maar duurder.

maze-small in 4,6ms, medium heeft een unwrap panic en large een stack overflow . Ik ga naar bed

.edit: oh medium vind geen pad naar het eind. Daar had had @FCA ook last van.
.edit2: oh haha ik zie het al, hij moet naar links. Dat laat mijn methode niet toe omdat hij maar 1x kan draaien

.edit: ok even wat snelle fixes. Medium: 192ms, large 7,42s. Ik loop wel heel veel werk dubbel te doen zie ik nu dus dat kan wel beter.

[ Voor 19% gewijzigd door .oisyn op 17-12-2024 01:26 ]

[Friits]

Nog even een latertje, en dan snel naar bed want om 5:45 gaat de wekker weer...

Hier is mijn oplossing voor dag 16.

Dijkstra-"light" dus.

[ Voor 88% gewijzigd door Friits op 17-12-2024 06:00 ]

[Soultaker]

Vandaag was wel even een pittige opgave, maar wel leuk! Een typische Advent of Code probleem ook. Op basis van eerdere ervaring was het al duidelijk dat het de bedoeling was dat je voor deel 2

spoiler:

moest gaan reverse engineeren om uit te vinden wat het programma daadwerkelijk doet.

Maar zelfs als je dat gedaan hebt, is het nog steeds verre van triviaal om de oplossing te vinden. Ik heb 'm semi-gebruteforcet, met de cruciale observatie dat:

spoiler: Deel 2

de waarde van de i-de uitvoer (beginnend bij i=0) hangt hooguit af van bits 3i tot 3i + 10 (exclusief) in de initiële waarde van register A, dus je kunt A reconstrueren door van links naar rechts door het programma (de gewenste uitvoer) te lopen, en dan hoef je steeds maar 1024 waarden te proberen, waarbij je op moet passen dat je geen eerdere uitvoerwaarden invalideert.

Python code

Ik denk dat er ook een mooie wiskundige oplossing is, of eentje gebaseerd op constraint satisfaction, maar dat wordt me wat te ingewikkeld zo op de vroege morgen.

edit:
Ander idee, aanzienlijk minder bruteforce:

spoiler:

Je kunt vermoedelijk ook terugrekenen van het einde naar het begin?

---

Overigens, wat was jullie invoer? Mijn theorie is dat iedereen ongeveer dezelfde invoer heeft op een paar waarden na. Mijn invoer:

spoiler:

Register A: 59590048
Register B: 0
Register C: 0

Program: 2,4,1,5,7,5,0,3,1,6,4,3,5,5,3,0

[ Voor 5% gewijzigd door Soultaker op 17-12-2024 08:19 ]

[Soultaker]

Nog even over dag 16:

Robbinb1993 schreef op maandag 16 december 2024 @ 20:45:

spoiler:

De bottleneck zit vooral in Dijkstra. Ik heb het gecompressed met ID's waarin x, y en dir opgeslagen zijn. Misschien dat het sneller kan met een heuristic?

Mijn oplossing met een std::priority_queue<> is ongeveer net zo snel als die van jou, wat logisch is, want we doen praktisch hetzelfde (ik vermoed dat je compressie weinig verschil maakt). Om het sneller te maken:

spoiler:

heb ik de queue geïmplementeerd als een vector-van-vectors, waarbij elk element in de buitenste vector overeenkomt met een afstand. Dit werkt omdat de afstanden relatief kleine integers zijn. Op die manier kan ik in O(1) (amortized) tijd elementen toevoegen en verwijderen, terwijl een binary heap zoals std::priority_queue<> implementeert O(log n) is.

Lelijke C++ code: solve2.cc

.oisyn schreef op dinsdag 17 december 2024 @ 00:59:
Ik had A* met een min-cost heuristic maar ik heb 'm weggegooid want het maakte het alleen maar duurder.

Ah ja, dat is een uitstekende heuristiek in de echte wereld, waar het korste pad ongeveer overeenkomt met de hemelsbrede afstand, maar juist in doolhoven gaat dat niet op, en heeft A* weinig nut (het zou er ook niet veel slechter op moeten worden).

.edit2: oh haha ik zie het al, hij moet naar links. Dat laat mijn methode niet toe omdat hij maar 1x kan draaien

Oh interessant, dat had ik niet eens expres gedaan. Zou eigenlijk in m'n kleinere testdata moeten zitten. Als ik het goed begrijp zou dit dus al verkeerd moeten gaan:

####
#ES#
####

[ Voor 3% gewijzigd door Soultaker op 17-12-2024 08:35 ]

[Friits]

Poeh, dat was wel een uurtje stevig nadenken vanochtend. Deel 1 was redelijk triviaal, deel 2 niet. Gelukkig had ik afgelopen maanden een paar vergelijkbare AoC-puzzels gedaan, dus ik had snel door wat de bedoeling was. Ondertussen uiteraard ook nog heel naïef een for-loopje aangezet

Uiteindelijk heb ik er dit van weten te maken.

spoiler:

Wie deze puzzel leuk vond, kan z'n tanden nog stukbijten op 2017 dag 23 en 2018 dag 19.
En natuurlijk een hoop puzzels uit 2019, het jaar van IntCode!

[Robbinb1993]

[b]Soultaker schreef op dinsdag 17 december 2024 @ 08:34:

spoiler:

Om het sneller te maken heb ik de queue geïmplementeerd als een vector-van-vectors, waarbij elk element in de buitenste vector overeenkomt met een afstand

spoiler:

Slim, dat werkt in dit geval goed omdat de edge weights gelimiteerd zijn tot 1 en 1000. Als het goed is heet dit Dial's algorithm (bucket queue).

Edit: Nieuwe tijden met deze optimalisatie:

maze-small.txt: 5ms.
maze-medium.txt: 81ms.
maze-large.txt: 1635ms.

https://github.com/Robbin.../blob/main/day16/day16.cc

[ Voor 28% gewijzigd door Robbinb1993 op 17-12-2024 10:00 ]

[Janoz]

Soultaker schreef op dinsdag 17 december 2024 @ 08:07:

spoiler: Deel 2

de waarde van de i-de uitvoer (beginnend bij i=0) hangt hooguit af van bits 3i tot 3i + 10 (exclusief) in de initiële waarde van register A, dus je kunt A reconstrueren door van links naar rechts door het programma (de gewenste uitvoer) te lopen, en dan hoef je steeds maar 1024 waarden te proberen, waarbij je op moet passen dat je geen eerdere uitvoerwaarden invalideert.

edit:
Ander idee, aanzienlijk minder bruteforce:

spoiler:

Je kunt vermoedelijk ook terugrekenen van het einde naar het begin?

Klopt

spoiler:

Als je van achter naar voor gaat, veranderd de laatste digit van je programma alleen door de 3 minst significante bits van A. Daar doorheen itereren om het gewenste antwoord te krijgen en klaar

https://github.com/Janoz-...2024/day17/Day17.java#L16

Antwoord in 5ms

Ik heb er echter wel heel lang over gedaan omdat ik ergens nog een int had staan ipv een long. En dat was niet genoeg voor deel 2.

Overigens, wat was jullie invoer? Mijn theorie is dat iedereen ongeveer dezelfde invoer heeft op een paar waarden na. Mijn invoer:

spoiler:

Register A: 59590048
Register B: 0
Register C: 0

Program: 2,4,1,5,7,5,0,3,1,6,4,3,5,5,3,0

spoiler:

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

[MatHack]

Soultaker schreef op dinsdag 17 december 2024 @ 08:07:
Overigens, wat was jullie invoer? Mijn theorie is dat iedereen ongeveer dezelfde invoer heeft op een paar waarden na. Mijn invoer:

spoiler:

Register A: 59590048
Register B: 0
Register C: 0

Program: 2,4,1,5,7,5,0,3,1,6,4,3,5,5,3,0

Deel 1 was zo gepiept, nu nog nadenken over deel 2.

Zoals je al verwacht had, scheelt het inderdaad niet veel met mijn output:

spoiler:

Program: 2,4,1,5,7,5,1,6,4,1,5,5,0,3,3,0

[ Voor 4% gewijzigd door MatHack op 17-12-2024 09:44 ]

[FCA]

Deel 2 was leuke. Oplossing uiteindelijk redelijk netjes, en draait in een flits (<500 microseconde)

spoiler:

Van achter naar voren, met recursie. Ik zag al redelijk snel dat je bij de input telkens 3 bits opat, en dat de uitvoer afhing van ongveer 6 bits van register a. Je moet dan nog wel dealen met meerdere branches, waarvan sommige doodlopen. Oplossing werkt, maar ik merk dat het op de rand zit van wat ik zo snel kan begrijpen, kan het niet meer begrijpelijk uitleggen.

[FCA]

Ik denk trouwens dat de invoer bij idereen

spoiler:

eindigt op 3,0, (dus jnz(0) en ergens een 0,3 bevat (dus adv(3)). En begint met 2,4 (dus bst(4))
Anders is de moeilijkheidsgraad te variabel per input

[Soultaker]

Het algoritme zal inderdaad hetzelfde zijn, maar ik was benieuwd hoeveel variatie er in de rest van het programma zit. Inputs die gepost zijn: https://pastebin.com/raw/J5Se8UCe (spoilers)

spoiler:

De volgorde van de de bxl/bxc/adv instructies varieert.
De operands van beide bxl instructries variëren.
De ongebruikte operand van de bxc instructie varieert.

Ik denk dat dit de dependencies zijn:



Dus dan kom ik op een totaal van 12 verschillende programma's, met 3 verschillende parameters dus in theorie 6144 verschillende mogelijke invoeren.

[ Voor 25% gewijzigd door Soultaker op 17-12-2024 12:38 ]

[Creepy]

Vanmiddag eens kijken of ik het 1 en ander in kan halen, loop alweer flink wat dagen achter.

[Robbinb1993]

[b]Soultaker schreef op dinsdag 17 december 2024 @ 08:07:
Overigens, wat was jullie invoer?

spoiler:

Program: 2,4,1,1,7,5,1,5,4,5,0,3,5,5,3,0

Answer: xxxxxxxxxxxx389

Ik vond part 2 vandaag wel lastig, weinig ervaring met soortgelijke problemen. Het duurde even voordat ik door had dat B en C aan het begin van de run steeds weer opnieuw assigned worden en onafhankelijk zijn van vorige waarden, waardoor we van achter naar voren kunnen itereren. Ik dacht eerst dat eerdere runs juist invloed hadden op de waarde van B en C. Alleen de right bitshifts van A zijn uiteindelijk van invloed op B en C in latere runs.

[ Voor 51% gewijzigd door Robbinb1993 op 17-12-2024 14:00 ]

[Friits]

@Soultaker, @Robbinb1993, @Janoz, @MatHack: ik wil niet lullig doen, maar Eric (de maker van alle AoC puzzels) vraagt zijn gebruikers expliciet om de inputs niet online te delen. Dit om te voorkomen dat puzzels nagemaakt worden.

Zelf denk ik dat het niet zo'n vaart zal lopen, maar het is een van de weinige dingen die hij van ons vraagt. De beste man steekt ieder jaar ontzettend veel tijd en moeite in dit project voor ons, dus dan vind ik het wel zo netjes om hiernaar te handelen.

🙂

[Robbinb1993]

@Soultaker Nog even terugkomend op de optimalisatie van de puzzel van gisteren:

spoiler:

We kunnen de bucket queue nog verder optimaliseren door maar maximaal 1001 buckets tegelijkertijd in het geheugen te houden. Daarna kunnen we circulair weer buckets hergebruiken. Nu draai ik de large maze test case in onder de 1 seconde: https://github.com/Robbin.../blob/main/day16/day16.cc. En het is ook nog eens memory efficient.

[ Voor 4% gewijzigd door Robbinb1993 op 17-12-2024 13:51 ]

[Soultaker]

Robbinb1993 schreef op dinsdag 17 december 2024 @ 13:50:

spoiler:

We kunnen de bucket queue nog verder optimaliseren door maar maximaal 1001 buckets tegelijkertijd in het geheugen te houden. Daarna kunnen we circulair weer buckets hergebruiken. Nu draai ik de large maze test case in onder de 1 seconde: https://github.com/Robbin.../blob/main/day16/day16.cc. En het is ook nog eens memory efficient.

Slim bedacht en een hele nette oplossing. Ik had niet verwacht dat het veel verschil zou maken, maar dat doet het blijkbaar wel.

Ik heb ook nog even geëxperimenteerd met een deque<> als buitenste datastructuur waarmee je automatisch maximaal 1001 vectors hoeft bij te houden, maar dat is ongeveer net zo snel/traag als de vector, dus geheugengebruik is niet de bepalende factor hier. De code wordt wel wat simpeler dus misschien kan de compiler daar z'n voordeel mee doen door meer te inlinen of op een andere manier te optimaliseren.

[MatHack]

Moet overigens zeggen dat het voorbeeld voor deel 2 in dit geval niet heel veel helpt bij het oplossen van het echte probleem. Ik kan het voorbeeld namelijk heel makkelijk met de hand oplossen, voornamelijk omdat er geen interactie met B & C is...

[FCA]

Soultaker schreef op dinsdag 17 december 2024 @ 10:48:
Het algoritme zal inderdaad hetzelfde zijn, maar ik was benieuwd hoeveel variatie er in de rest van het programma zit. Inputs die gepost zijn: https://pastebin.com/raw/J5Se8UCe (spoilers)

spoiler:

De volgorde van de de bxl/bxc/adv instructies varieert.
De operands van beide bxl instructries variëren.
De ongebruikte operand van de bxc instructie varieert.

Ik denk dat dit de dependencies zijn:

[Afbeelding]

Dus dan kom ik op een totaal van 12 verschillende programma's, met 3 verschillende parameters dus in theorie 6144 verschillende mogelijke invoeren.

Ik gok dat het grootste gedeelte niet oplosbaar is. Een snelle check op mijn invoer, met de 3 "vrije" parameters, levert op dat er maar 7 oplosbaar zijn, en dus 505 niet. Ik denk dat dat bij de ander 11 opties voor de volgorde vergelijkbaar zal zijn.

edit: sterker nog, voor alle instructies die een oplossing hebben, zijn de values voor de bxl instructies hetzelfde: er zit alleen maar vrijheid in de bxc instructie bij mijn input.

[ Voor 8% gewijzigd door FCA op 17-12-2024 19:54 ]

[Soultaker]

FCA schreef op dinsdag 17 december 2024 @ 19:30:
Ik gok dat het grootste gedeelte niet oplosbaar is. Een snelle check op mijn invoer, met de 3 "vrije" parameters, levert op dat er maar 7 oplosbaar zijn, en dus 505 niet. Ik denk dat dat bij de ander 11 opties voor de volgorde vergelijkbaar zal zijn.

Goed punt; ik had niet nagedacht over oplosbaarheid. Overigens kom ik op 37 varianten van mijn invoer die oplosbaar zijn (https://pastebin.com/raw/aiHcLyaU) dus 444 in totaal als je vermenigvuldigt met de 12 permutaties van instructies.

edit: sterker nog, voor alle instructies die een oplossing hebben, zijn de values voor de bxl instructies hetzelfde: er zit alleen maar vrijheid in de bxc instructie bij mijn input.

Wat is jouw invoer dan precies? Dit suggereert dat je een fundamenteel ander programma hebt gekregen dan anderen; het lijkt me waarschijnlijker dat er ergens een foutje in je implementatie zit.

[MueR]

Creepy schreef op dinsdag 17 december 2024 @ 11:10:
Vanmiddag eens kijken of ik het 1 en ander in kan halen, loop alweer flink wat dagen achter.

Idem. Gisteravond wel wat ingehaald, maar ik merk dat de burnout dit jaar vroeg komt.

[FCA]

Soultaker schreef op dinsdag 17 december 2024 @ 20:33:
[...]

Goed punt; ik had niet nagedacht over oplosbaarheid. Overigens kom ik op 37 varianten van mijn invoer die oplosbaar zijn (https://pastebin.com/raw/aiHcLyaU) dus 444 in totaal als je vermenigvuldigt met de 12 permutaties van instructies.


[...]

Wat is jouw invoer dan precies? Dit suggereert dat je een fundamenteel ander programma hebt gekregen dan anderen; het lijkt me waarschijnlijker dat er ergens een foutje in je implementatie zit.

Geen idee, benieuwd of er iets mis is, mijn invoer is:

spoiler:

2,4,1,x,7,5,4,x,1,x,5,5,0,3,3,0

Met de "x" de "vrije" parameter.

[.oisyn]

Even terugkomend op dag 16

.oisyn schreef op dinsdag 17 december 2024 @ 00:59:
[...]


Ik had A* met een min-cost heuristic maar ik heb 'm weggegooid want het maakte het alleen maar duurder.

maze-small in 4,6ms, medium heeft een unwrap panic en large een stack overflow . Ik ga naar bed

.edit: oh medium vind geen pad naar het eind. Daar had had @FCA ook last van.
.edit2: oh haha ik zie het al, hij moet naar links. Dat laat mijn methode niet toe omdat hij maar 1x kan draaien

.edit: ok even wat snelle fixes. Medium: 192ms, large 7,42s. Ik loop wel heel veel werk dubbel te doen zie ik nu dus dat kan wel beter.

     Running `target\release\day16.exe -i .\extra\day16\maze-small.txt`
Time spent: 2496.7µs
327102 - 1103

     Running `target\release\day16.exe -i .\extra\day16\maze-medium.txt`
Time spent: 63642.2µs
2505726 - 8727

     Running `target\release\day16.exe -i .\extra\day16\maze-large.txt`
Time spent: 1548898.0µs
20717422 - 71423

Stuk sneller dan gisteren.

spoiler:

Mijn bookkeeping volledig omgegooid. Eerst hield ik een hashmap bij voor (positie, richting) => (cost, [(prev_pos, prev_dir); 3]. En natuurlijk een binary heap voor de queue voor Dijkstra.

Ik heb de hashtable weggegooid en vervangen voor een grid waarin ik 4 keer (een voor elke richting) een u32 opsla waar de cost in geencodeerd staat, plus 4 bits voor alle vorige orientaties die op die node terecht kwamen.

De binary heap heb ik gehouden, maar alleen om bij te houden wat de volgende cost-hoeveelheid is om te processen. De daadwerkelijke elementen staan in een aparte hashtable van cost => Vec<(prev_pos, prev_dir)>. Hierdoor staat elke unieke cost maar 1x in een heap van u32's.

Het extra werk wat ik gisteren nog deed voor het terugvinden van een pad was vooral in de situatie dat een pad splitste en later weer bij elkaar kwam. Bij het splitsen volgde ik beide paden, maar bij het terugkomen bleef ik dat samengevoegde pad 2x volgen, waarbij de tiles niet meer werden geteld omdat die al gevisit waren, maar dat alleen is niet genoeg om te stoppen omdat paden natuurlijk kunnen kruisen, dus moest ik wel doorgaan. Nu haal ik die informatie gewoon uit de grid zodra ik het oppak zodat ik het niet nog een keer kan doen

Vandaag sla ik over.

Soultaker schreef op dinsdag 17 december 2024 @ 08:34:
maar juist in doolhoven gaat dat niet op, en heeft A* weinig nut (het zou er ook niet veel slechter op moeten worden).

Het is vooral de constante factor van de overhead van die min-cost (extra data in je structuur, extra berekening) die het duurder maakt als het algoritmisch niets toevoegt.

[ Voor 47% gewijzigd door .oisyn op 18-12-2024 00:37 ]

[Janoz]

Veel te moeilijk gedacht vandaag.

spoiler:

Ik dacht dat je een route door een veranderend veld moest zoeken, dus toen ik door had dat in deel 1 het veld statisch was hoopte ik dat dat misschien de vraag voor deel 2 was. Ik heb iig nu wel een implementatie van een pathfinder die om kan gaan met een veranderend veld

[Soultaker]

Dag 16:

.oisyn schreef op dinsdag 17 december 2024 @ 23:57:

spoiler:

De binary heap heb ik gehouden, maar alleen om bij te houden wat de volgende cost-hoeveelheid is om te processen. De daadwerkelijke elementen staan in een aparte hashtable van cost => Vec<(prev_pos, prev_dir)>. Hierdoor staat elke unieke cost maar 1x in een heap van u32's.

Slim, en deze optimalisatie was nog niet eerder langsgekomen. Ik vraag me wel of het bij dit probleem veel tijdwinst oplevert t.o.v. van b.v. de bucket queue van @Robbinb1993. Met jouw aanpak skip je alle lege vectors, maar daar staat tegenover dat om elementen toe te voegen je een hashtable lookup moet doen i.p.v. een simpele array index.

Overigens kun je de twee ideeën ook nog combineren:

spoiler:

de hash table vervangen door een bucket queue, en de priority queue behouden om lege buckets over te slaan

---

Dag 18: ik verwachtte dat deel 2 vandaag een heel andere kant op zou gaan, namelijk:

spoiler:

dat je een pad moet vinden waarbij je alleen op vakje (x, y) mag komen vóór het geblokkeerd wordt.

(edit: precies wat @Janoz ook zei GMTA.)

Daar zat ik me al een beetje op voor te bereiden in deel 1, wat uiteindelijk alleen maar tot tijdverlies leidde. Stom van me om aannames te doen natuurlijk. Uiteindelijk heb ik deel 2:

spoiler:

gewoon gebruteforcet: voor elk tijdstip kijken of er een pad van begin naar eind is. Dat werkt omdat de invoer klein genoeg is. Meteen daarna heb ik het geoptimaliseerd met een binary search.

Nu draait het in ~60 ms. Python code

[Janoz]

Pff, ik dacht dat het al de opdracht voor deel 1 was

Bij mij is het 80 - 90ms, maar met zo'n 2500 mogelijkheden is zelfs bruteforce ook geen enkel issue tbh. Eigenlijk valt de opdracht van vandaag mij een beetje tegen qua moeilijkheidsgraad.

[Hagdos]

Wat @Janoz en @Soultaker zeiden, dacht ik ook. Maar ik heb ondertussen ook geleerd om nooit aannames te doen over deel 2, en niet te veel moeite te steken in wat ik denk dat deel 2 gaat zijn. Meestal zit ik er naast (wat het leuk houdt).

[bakkerjangert]

Voor deel 2 had ik wel al het goede idee wat het zou worden, aangezien ik een visualisatie had gemaakt van deel 1. Lezen blijft wel een vak overigens, blijkt maar weer eens vandaag. Code in python.

spoiler:

Voor deel 2 had ik al 3x een index ingevoerd, voordat ik door had dat het coördinaat werd gevraagd .

[Soultaker]

Extra testdata voor dag 18: aoc-2024-day-18-challenge-1-to-5.zip

Let op dat bij deze invoer het grid groter is dan de 71x71 van de officiële testdata. Je kunt aan de bestandsnaam zien want de bedoeling is (of gewoon kijken wat de maximale coördinaten in de invoer zijn). Bijvoorbeeld invoerbestand challenge-1-500x500.txt heeft coördinaten die lopen van 0 t/m 500 in beide richtingen (dus een grid van 501x501 in totaal).

Eigenlijk is alleen het antwoord bij deel 2 interessant. Om het antwoord niet te spoilen geef ik het product van de x en y coördinaat van het antwoord:

aoc-2024-day-18-challenge-1-500x500.txt: 1716
aoc-2024-day-18-challenge-2-500x500.txt: 249500
aoc-2024-day-18-challenge-3-2500x2500.txt: 1504419
aoc-2024-day-18-challenge-4-2500x2500.txt: 11136
aoc-2024-day-18-challenge-5-2500x2500.txt: 6227514

[Robbinb1993]

Soultaker schreef op woensdag 18 december 2024 @ 09:36:
Extra testdata voor dag 18: aoc-2024-day-18-challenge-1-to-5.zip

Let op dat bij deze invoer het grid groter is dan de 71x71 van de officiële testdata. Je kunt aan de bestandsnaam zien want de bedoeling is (of gewoon kijken wat de maximale coördinaten in de invoer zijn). Bijvoorbeeld invoerbestand challenge-1-500x500.txt heeft coördinaten die lopen van 0 t/m 500 in beide richtingen (dus een grid van 501x501 in totaal).

Eigenlijk is alleen het antwoord bij deel 2 interessant. Om het antwoord niet te spoilen geef ik het product van de x en y coördinaat van het antwoord:

aoc-2024-day-18-challenge-1-500x500.txt: 1716
aoc-2024-day-18-challenge-2-500x500.txt: 249500
aoc-2024-day-18-challenge-3-2500x2500.txt: 1504419
aoc-2024-day-18-challenge-4-2500x2500.txt: 11136
aoc-2024-day-18-challenge-5-2500x2500.txt: 6227514

Ik kom op dezelfde antwoorden uit. Alleen de laatste test case duurt bijna 4 seconden om te runnen. Maar het kan sneller dan:

spoiler:

binary search. We kunnen ook vanaf de eindsituatie waarbij alle blokkades geplaatst zijn, weer obstakels verwijderen, waardoor er nieuwe paden beschikbaar komen. Vervolgens bekijken we of de start- en eindcell elkaar kunnen bereiken. Hiervoor gebruiken we de eerder besproken UFDS datastructuur om dit in amortized O(1) te doen per update (sets mergen en set ID's opvragen). Zodra de start- en eindcell zich in dezelfde set bevinden, kunnen ze elkaar bereiken en hebben we het antwoord gevonden. Dit heeft een complexiteit van O(M * N * α(n)) in plaats van O(M * N * log(#obstakels)) in het geval van binary search.

Edit:aoc-2024-day-18-challenge-5-2500x2500.txt part 2 draait nu in 2 seconden met

spoiler:

Omgekeerd oplossen (obstakels verwijderen), in combinatie met UFDS datastructuur in O(M * N * α(n)).

Misschien kan het nog sneller?

https://github.com/Robbin.../blob/main/day18/day18.cc

[ Voor 46% gewijzigd door Robbinb1993 op 18-12-2024 10:51 ]

[Marcj]

Na een aantal dagen minder tijd en veel uitdagingen door zelf stomme implementatiefouten te maken, ben ik ook eindelijk weer bij. Voor vandaag ik heb maar

spoiler:

een binary search gemaakt om te zoeken naar de situatie waar we toegang hebben. Wel een domme implementatie die elke keer de hele zoek-state weg gooit en opnieuw begint. Dus daar is waarschijnlijk nog heel erg veel te winnen.

Soultaker schreef op woensdag 18 december 2024 @ 09:36:
Extra testdata voor dag 18: aoc-2024-day-18-challenge-1-to-5.zip
...

Zoals ik al verwachte is mijn implementation niet heel slim voor zulke grote uitdagingen. De laatste duurt op dit moment met mijn code ruim 4 minuten

[Soultaker]

Robbinb1993 schreef op woensdag 18 december 2024 @ 09:51:

spoiler:

Edit:aoc-2024-day-18-challenge-5-2500x2500.txt part 2 draait nu in 2 seconden met [spoiler]Omgekeerd oplossen (obstakels verwijderen), in combinatie met UFDS datastructuur in O(M * N * α(n)).[/spoiler] Misschien kan het nog sneller?

Ik had hetzelfde bedacht. edit: Ah, toch niet, mijn methode is slimmer Maar we gebruiken wel dezelfde datastructuur.

Grappig genoeg draait 'ie soms in sublineaire tijd omdat je niet altijd de hele invoer hoeft te consumeren. En de implementatie is eigenlijk heel simpel als je de disjoint set datastructuur al hebt.

Mijn timings:

$ time ./solve 2500 < aoc-2024-day-18-challenge-3-2500x2500.txt 
###,###

real    0m0.020s
user    0m0.013s
sys     0m0.007s

$ time ./solve 2500 < aoc-2024-day-18-challenge-4-2500x2500.txt 
###,###

real    0m1.804s
user    0m1.755s
sys     0m0.018s

 $ time ./solve 2500 < aoc-2024-day-18-challenge-5-2500x2500.txt 
###,###

real    0m0.465s
user    0m0.450s
sys     0m0.014s

De traagste is dus challenge-4, wat logisch is want daar moet je de meeste invoer consumeren, maar dat is nog steeds slechts 1,8 seconde, waarvan ongeveer 0,9 seconde invoer lezen is, dus ik vind het wel welletjes geweest zo.

C++ code

[ Voor 3% gewijzigd door Soultaker op 18-12-2024 10:56 ]

[Robbinb1993]

Soultaker schreef op woensdag 18 december 2024 @ 10:55:
[...]
De traagste is dus challenge-4, wat logisch is want daar moet je de meeste invoer consumeren, maar dat is nog steeds slechts 1,8 seconde, waarvan ongeveer 0,9 seconde invoer lezen is, dus ik vind het wel welletjes geweest zo.

spoiler:

Het is wel bijzonder, jouw code is inderdaad een stuk sneller voor challenge 5, alleen mijn code is weer sneller voor challenge 4: 1400ms. Ik denk dat de bottleneck in mijn code vooral het initializeren van de initiële sets is, en waarschijnlijk zitten er in case 4 in de eindsituatie zoveel blokkades, dat er weinig gemerged hoeft te worden aan het begin. Het is dan natuurlijk ook voordeliger als het antwoord meer aan het einde zit als je van eind naar begin itereert.

[ Voor 8% gewijzigd door Robbinb1993 op 18-12-2024 11:25 ]

[Soultaker]

Robbinb1993 schreef op woensdag 18 december 2024 @ 11:22:
Het is wel bijzonder, jouw code is inderdaad een stuk sneller voor challenge 5, alleen mijn code is weer sneller voor challenge 4: 1400ms. Ik denk dat de bottleneck in mijn code vooral het initializeren van de initiële sets is, en waarschijnlijk zitten er in case 4 in de eindsituatie zoveel blokkades, dat er weinig gemerged hoeft te worden aan het begin.

spoiler:

Challenge 1 en 4 zijn speciaal geconstrueerd zodat het grid pas op het eind geblokkeerd wordt, dus daar zal mijn code inderdaad relatief traag zijn. Challenge 3 is speciaal geconstrueerd zodat het grid heel vroeg geblokkeerd wordt (daar ben jij dan weer trager, neem ik aan?)

[Robbinb1993]

Soultaker schreef op woensdag 18 december 2024 @ 11:28:
[...]

spoiler:

Challenge 1 en 4 zijn speciaal geconstrueerd zodat het grid pas op het eind geblokkeerd wordt, dus daar zal mijn code inderdaad relatief traag zijn. Challenge 3 is speciaal geconstrueerd zodat het grid heel vroeg geblokkeerd wordt (daar ben jij dan weer trager, neem ik aan?)

spoiler:

Dat klopt, jouw code lost case 3 in maar 12 ms op aangezien het antwoord vrijwel direct gevonden wordt vanaf de start. In mijn geval duurt het 1394 ms omdat hij een aardige afstand moet afleggen om er te komen. Daarbij hoef je ook niet eerst alle invoer te lezen, waar dat in mijn geval dus altijd nodig is.

Erg mooie oplossing, zo heb ik nog niet eerder het vaststellen van connectivity in een grid opgelost zien worden. Duurde even voordat ik door had hoe het precies werkt. Voordeel van jouw oplossing is ook dat het 'online' is, oftewel je kan interactief de obstakels ontvangen zonder van tevoren te weten waar ze zich bevinden.

[ Voor 22% gewijzigd door Robbinb1993 op 18-12-2024 13:05 ]

[.oisyn]

Soultaker schreef op woensdag 18 december 2024 @ 07:16:
Dag 16:

[...]

Slim, en deze optimalisatie was nog niet eerder langsgekomen. Ik vraag me wel of het bij dit probleem veel tijdwinst oplevert t.o.v. van b.v. de bucket queue van @Robbinb1993. Met jouw aanpak skip je alle lege vectors, maar daar staat tegenover dat om elementen toe te voegen je een hashtable lookup moet doen i.p.v. een simpele array index.

Nou ja, een hash lookup is bijna een array index. Vooral in Rust, waar een HashMap een probing hashtable is en niet een bucketed table zoals de unordered_map in C++. Ik denk niet dat daar veel overhead zit.

Maar je kunt idd ook gewoon een circulaire array gebruiken van 1001 elementen. Je trekt de vector uit de buffer zodra je begint met die cost, en dan schrijf je hooguit naar +1 en +1001. Behalve voor jouw medium maze, dan moet je voor de eerste stap schrijven naar +2001 om naar links te gaan (als alternatief kun je turns als losse moves zien)

.edit: oh dat is precies wat Robbin ook doet, dat had ik nog niet gelezen

[ Voor 21% gewijzigd door .oisyn op 18-12-2024 12:43 ]

[bakkerjangert]

pffff, ein-de-lijk dag 17 deel 2 opgelost. Ik had al vrij snel het juiste idee, maar door verschillende bugs ging ik steeds meer aan dat idee twijfelen; ik was er ook niet 100% zeker van. Uiteindelijk een heel deel van de code opnieuw geschreven en toen werkte het als een zonnetje. Code in python.

spoiler:

Voor elke loop wordt A een factor 8 kleiner, met een truncate naar onderliggende int. De laatste output moet dus volgen uit een A-waarde van 0-7 (om op A=0 uit te komen en de loop te eindigen). In mijn geval gaf enkel 7 de juiste output voor de laatste opcode. Vervolgens kijk voor de een-na-laatste output voor de gevonden waarde van 7 maal de factor 8 per stap + een delta van 0-7 (vanwege de truncate komt dan juiste A weer terug in de volgende stap). Zo door redenerend tot de lengte van het programma, waarbij soms vertakkingen ontstaan omdat er uit de delta 0-7 meerdere juiste resultaten kunnen volgen.

[P_Tingen]

Dag 18: Ram run

Ik zag vandaag en dacht: hé, een map, dat is leuk, dus heb een zoekmechanisme gemaakt dat de uitgang zoekt. Werkt prima voor de test, maar verwerken van de echte data duurt veel te lang. Na een paar minuten maar afgebroken.

spoiler:

Ik ga recursief door de kaart, breek af als het pad al langer duurt dan wat tot nog toe is gevonden, maar het duurt nog steeds veel te lang. Als ik de kaart bekijk, na de eerste 1024 bytes, dan snap ik wel waarom; een groot open 'middenterrein' waar je eindeloos veel routes kan bedenken. Dit moet slimmer, maar hoe?

[Soultaker]

FCA schreef op dinsdag 17 december 2024 @ 22:43:
Geen idee, benieuwd of er iets mis is, mijn invoer is: [..]

Ik kom op 27 varianten van jouw invoer: https://pastebin.com/raw/dfN9zruE

Dat is anders dan mijn 37 varianten. Ik realiseer me nu pas dat het aantal variaties per programma (waarbij alleen de operands van de in totaal drie bxl en bxc instructies verschillen) niet voor alle programma's hetzelfde is; als je de instructies permuteert dan is de gewenste uitvoer natuurlijk ook weer anders.

Ook is het aantal mogelijke permutaties van de instructies slechts 12 en niet 8 zoals ik eerst dacht.

Ik heb nog een scriptje geschreven om alle programma's te generen en te checken hoeveel daarvan er oplosbaar zijn.. Het zijn er in totaal 217. Een stuk minder dan ik had eerst dacht dus.

[Satom]

Dag 17, deel 2 opgelost! Maar wellicht dat iemand mij kan helpen.

spoiler:

Ik heb het opgelost met een dubbele loop, een while(true) gevolgd door een for van 0 tot 1024. Initieel had ik deze gedachte ook, maar dan met een 3 bits getal (een loop van 0-7). Daarmee krijg ik result op het example. Alleen werkte dit niet voor de input. Na 2 dagen terug naar de tekentafel te zijn geweest, ben ik de 8 stapsgewijs gaan verhogen (puur omdat ik ten einde raad was) en voila, bij 1024 kreeg ik een juiste result. Wellicht is het puur geluk hebben..

[Soultaker]

Satom schreef op woensdag 18 december 2024 @ 17:13:
Dag 17, deel 2 opgelost! Maar wellicht dat iemand mij kan helpen.

spoiler:

Ik heb het opgelost met een dubbele loop, een while(true) gevolgd door een for van 0 tot 1024

spoiler:

Oorspronkelijk had ik ook een lusje waarbij je 1024 opties per output moet gebruiken. Zie SolveForward() in 17.py (onderaan). Als je dezelfde aanpak gebruikt dan is 2¹⁰ = 1024 bits correct, want elke output is afhankelijk van (maximaal) 10 bits in A. Het verschil met de efficiëntere aanpak van achter naar voren is dat je dan steeds aanneemt dat de bovenste 7 bits vastliggen.

Verder kan ik er niet veel zinnigs over zeggen als je geen link naar je code post

[FCA]

Soultaker schreef op woensdag 18 december 2024 @ 17:08:
[...]

Ik kom op 27 varianten van jouw invoer: https://pastebin.com/raw/dfN9zruE

Dat is anders dan mijn 37 varianten. Ik realiseer me nu pas dat het aantal variaties per programma (waarbij alleen de operands van de in totaal drie bxl en bxc instructies verschillen) niet voor alle programma's hetzelfde is; als je de instructies permuteert dan is de gewenste uitvoer natuurlijk ook weer anders.

Ook is het aantal mogelijke permutaties van de instructies slechts 12 en niet 8 zoals ik eerst dacht.

Ik heb nog een scriptje geschreven om alle programma's te generen en te checken hoeveel daarvan er oplosbaar zijn.. Het zijn er in totaal 217. Een stuk minder dan ik had eerst dacht dus.

Inderdaad, ik had een foutje gemaakt in mijn oorspronkelijke oplossing, waardoor ik teveel prunede. Gefixed, krijg nu dezelfde 27, maar wel een stukje trager.

spoiler:

Had over het hoofd gezien dat de cdv(5) samen met de bxc meer bits van register a belangrijk kon maken voor de huidige output (tot wel 10 bits).
Ik ging uit van maar 6 bits belangrijk, dat werkte wel voor mijn input gelukkig

[.oisyn]

Ik ben vandaag dag 17 aan het doen (18 vanmiddag even snel gedaan).

Dit is waar Copilot mee kwam toen ik de VM aan het intypen was:

Rust:

        match opcodes[pc] {
            0 => {
                reg_c = reg_a;
            }
            1 => {
                reg_c = reg_b;
            }
            2 => {
                reg_c = reg_a + reg_b;
            }
            3 => {
                reg_c = reg_a * reg_b;
            }
            4 => {
                reg_c = reg_a / reg_b;
            }
            5 => {
                reg_c = reg_a % reg_b;
            }
            6 => {
                reg_a = reg_c;
            }
            7 => {
                reg_b = reg_c;
            }
            8 => {
                out.push_str(&reg_c.to_string());
            }
            9 => {
                out.push(reg_c as u8 as char);
            }
            10 => {
                if reg_a != 0 {
                    pc = reg_b as usize;
                    continue;
                }
            }
            11 => {
                pc = reg_c as usize;
                continue;
            }
            12 => {
                reg_c = reg_a & reg_b;
            }
            13 => {
                reg_c = reg_a | reg_b;
            }
            14 => {
                reg_c = reg_a << reg_b;
            }
            15 => {
                reg_c = reg_a >> reg_b;
            }
            16 => {
                reg_c = !reg_a;
            }
            17 => {
                break;
            }
            _ => {
                panic!("Invalid opcode: {}", opcodes[pc]);
            }
        }

Interessant

[.oisyn]

Zit voor jullie deel 17.2 ook niet in een 32-bits unsigned int?

[dcm360]

.oisyn schreef op woensdag 18 december 2024 @ 23:02:
Zit voor jullie deel 17.2 ook niet in een 32-bits unsigned int?

Dat past (vrijwel) gegarandeerd niet inderdaad. Niet dat me dat heeft laten tegenhouden om het gisteren in een eerste poging gewoon door te laten rekenen op een Int, maar toen ik na een tijdje doorhad hoe het probleem werkte was wel duidelijk dat er een groter getal uit zou komen (en doorrekenen geen goed plan was).

[.oisyn]

dcm360 schreef op woensdag 18 december 2024 @ 23:42:
[...]

Dat past (vrijwel) gegarandeerd niet inderdaad. Niet dat me dat heeft laten tegenhouden om het gisteren in een eerste poging gewoon door te laten rekenen op een Int, maar toen ik na een tijdje doorhad hoe het probleem werkte was wel duidelijk dat er een groter getal uit zou komen (en doorrekenen geen goed plan was).

Ja ik was er ook al vrij snel achter, ik jaste vrij hard door alle mogelijke 32 bit ints . Ik heb mijn input inmiddels al gedisassembled en ik snap wel wat de bedoeling is.

Ben nog een beetje met de hand aan het prutsen (terwijl hij ondertussen op de achtergrond wel combinaties probeert Hij is momenteel bij de 110 miljard)

.edit: ok ik kan 'm net zo goed stopzetten want met 16 waardes is het dus minstens een 48-bits getal

[ Voor 8% gewijzigd door .oisyn op 19-12-2024 00:01 ]

[.oisyn]

Holy shit, vind ik beide antwoorden voor 17 nou echt in 90 74 microseconden?!

[ Voor 12% gewijzigd door .oisyn op 19-12-2024 02:46 ]

[Soultaker]

Vandaag was een eitje, bijna niet de moeite om voor uit bed te komen. Eigenlijk een makkelijkere versie van dag 12 van vorig jaar (die grappig genoeg ook bij de hot springs plaatsvond). Niet wat ik verwacht qua moeilijkheid op dag 19 van de 25.

spoiler: dag 19 deel 1

Je kunt deel 1 ook heel cheesy doen door de patronen te herschrijven naar een regular expression van de vorm ^(foo|bar|baz)$. Is simpel en supersnel, maar helaas heb je er niets aan voor deel 2.

.oisyn schreef op donderdag 19 december 2024 @ 02:22:
Holy shit, vind ik beide antwoorden voor 17 nou echt in 90 74 microseconden?!

Lees je de invoer wel uit een bestand, of heb je 'm gehardcode? Want als 'ie gehardcode is kan ik me voorstellen dat de compiler vrij veel vooruit kan rekenen.

[ Voor 19% gewijzigd door Soultaker op 19-12-2024 07:15 ]

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 06:13:
Vandaag was een eitje, bijna niet de moeite om voor uit bed te komen. Eigenlijk een makkelijkere versie van dag 12 van vorig jaar (die grappig genoeg ook bij de hot springs plaatsvond). Niet wat ik verwacht qua moeilijkheid op dag 19 van de 25.

spoiler: dag 19 deel 1

Je kunt deel 1 ook heel cheesy doen door de patronen de herschrijven naar een regular expression van de vorm ^(foo|bar|baz)$. Is simpel en supersnel, maar helaas heb je er niets aan voor deel 2.

[...]

Lees je de invoer wel uit een bestand, of heb je 'm gehardcode? Want als 'ie gehardcode is kan ik me voorstellen dat de compiler vrij veel vooruit kan rekenen.

spoiler:

Hij was inderdaad vrij eenvoudig, was wel een stuk later begonnen dan 6:00. Heb hem uiteindelijk opgelost met Trie DP.

[FCA]

Soultaker schreef op donderdag 19 december 2024 @ 06:13:
Vandaag was een eitje, bijna niet de moeite om voor uit bed te komen. Eigenlijk een makkelijkere versie van dag 12 van vorig jaar (die grappig genoeg ook bij de hot springs plaatsvond). Niet wat ik verwacht qua moeilijkheid op dag 19 van de 25.

spoiler: dag 19 deel 1

Je kunt deel 1 ook heel cheesy doen door de patronen de herschrijven naar een regular expression van de vorm ^(foo|bar|baz)$. Is simpel en supersnel, maar helaas heb je er niets aan voor deel 2.

Inderdaad

spoiler:

Voor mij was het eventjes uitvinden hoe ik het beste de cache kon opzetten voor de recursie, want &str's kunnen blijkbaar moeilijk in een HashMap in Rust (iets met lifetimes). Uiteindelijk alles .to_string() en het werkt.
Copy-paste + wat kleine aanpassingen voor deel 2, en klaar. Had ik iets meer van verwacht.
Deel 2 blijkbaar toch wel een stukje lastiger: tussen deel 1 en deel 2 zat bij mij 2,5 minuut, maar ben wel 1000 plaatsen omhoog gegaan

Ben wel benieuwd of er nog een significant snellere oplossing is dan recursie + memoizatie. Voor deel 1 met een early exit kan het best snel, maar ik vind deel 2 toch niet uitzonderlijk snel lopen nog.

En nu weer naar bed. 2 niet zo moeilijke dagen, ben benieuwd wat ons nog wacht

[ Voor 3% gewijzigd door FCA op 19-12-2024 07:04 ]

[Soultaker]

FCA schreef op donderdag 19 december 2024 @ 07:03:

spoiler:

Voor mij was het eventjes uitvinden hoe ik het beste de cache kon opzetten voor de recursie, want &str's kunnen blijkbaar moeilijk in een HashMap in Rust (iets met lifetimes). Uiteindelijk alles .to_string() en het werkt.

Voor als je later wakker wordt:

spoiler:

Ik denk dat je het jezelf ingewikkelder hebt gemaakt dan noodzakelijk. Het zou niet nodig hoeven zijn om strings te cachen; alleen posities in de string, en dat zijn altijd integers.

Zie hier voor een recursieve oplossing: 19.py

En hier een iteratieve oplossing: 19-alt.py

In het tweede voorbeeld is het heel duidelijk dat je alleen een array van integers nodig hebt.

[Robbinb1993]

FCA schreef op donderdag 19 december 2024 @ 07:03:
[...]

spoiler:

Ben wel benieuwd of er nog een significant snellere oplossing is dan recursie + memoizatie.

spoiler:

Trie DP is snel. Aho-Corasick DP is sneller.

https://github.com/Robbin.../blob/main/day19/day19.cc
https://github.com/Robbin...b/main/day19/day19_aho.cc

[ Voor 29% gewijzigd door Robbinb1993 op 19-12-2024 08:57 ]

[Friits]

Wederom appeltje-eitje vandaag. Ik was bang dat we met prefix trees aan de slag moesten, maar een eenvoudige DP-achige oplossing was prima! Niet de allersnelste oplossing, maar wel lekker snel geschreven. (En daarmee op geschoven naar de tweede plek op het GoT leaderboard )

Waarom moeilijk doen als het makkelijk kan?

[ Voor 26% gewijzigd door Friits op 19-12-2024 08:33 ]

[.oisyn]

Lees je de invoer wel uit een bestand, of heb je 'm gehardcode? Want als 'ie gehardcode is kan ik me voorstellen dat de compiler vrij veel vooruit kan rekenen.

Ik heb een generieke oplossing voor alle inputs (die het standaard stramien volgen uiteraard) die geen hercompilatie gebruikt. Wel memorymap ik altijd de inputs. Ik verbaas me meer de snelheid van het algoritme. Maar uiteindelijk test hij maar iets in de ordegrootte van 100 verschillende waardes.

[ Voor 5% gewijzigd door .oisyn op 19-12-2024 08:54 ]

[KabouterSuper]

Soultaker schreef op donderdag 19 december 2024 @ 07:20:
[...]

Voor als je later wakker wordt:

spoiler:

Ik denk dat je het jezelf ingewikkelder hebt gemaakt dan noodzakelijk. Het zou niet nodig hoeven zijn om strings te cachen; alleen posities in de string, en dat zijn altijd integers.

Zie hier voor een recursieve oplossing: 19.py

En hier een iteratieve oplossing: 19-alt.py

In het tweede voorbeeld is het heel duidelijk dat je alleen een array van integers nodig hebt.

spoiler:

Je moet dan wel per towel cachen. Met een string kan je globaal cachen, al is de vraag of je daar iets aan hebt bij deze data. Als je een miljoen dezelfde towels moet oplossen, dan kan het schelen.

Vandaag was inderdaad te gemakkelijk vandaag. Terwijl ik mijn niet-gecachte code uitvoerde, bedacht ik me dat cachen sneller ging. Toen ik die versie ernaast aanzette, bedacht ik me dat pypy nog sneller was. Pypy was inderdaad klaar voordat de nog draaiende python dat was. En de niet-gecachte versie heb ik maar gestopt want die was nog altijd bezig.

[bakkerjangert]

Ik vond het maar lastig vandaag. Als engineer met wat hobby programmeer ervaring heb ik altijd moeite met dit soort opgave. Wel weer wat geleerd vandaag. Code in python.

spoiler:

Mijn eerste ingeving was de set van towels te reduceren, door langere towels die op te bouwen zijn uit kortere towels te verwijderen. Een leuke exercitie, die de set met towels echt aanzienlijk verkleinde. Die wilde ik dan samenstellen tot alle mogelijke variaties van de lengte van het patroon en dan checken of het patroon daar in zit. Ook met de gereduceerde set towels ging dat niet lukken uiteraard. Hier kon ik verder niet zo veel mee, zeker niet voor deel 2. Uiteindelijk met een beetje hulp van co-pilot uitgekomen op een begrijpbaar algoritme: voor elke index in het patroon checken of deze opgebouwd kan worden uit de towels. Dit doe je door te checken of het laatste deel van de patroon tot de index gelijk is aan een van de towels, en als de index daarvoor al gebouwd kan worden, kan de huidige index dus ook gebouwd worden. Als de laatste index True terug geeft kan het patroon gebouwd worden. Voor deel 2 was algoritme van deel 1 simpel om te bouwen door niet met True / False te werken, maar een counter bij te houden. Als de laatste index > 0 is is het patroon te bouwen. Volgens mij heb ik deze oplossing ook al bij andere voorbij zien komen.

[Soultaker]

KabouterSuper schreef op donderdag 19 december 2024 @ 08:33:

spoiler:

Je moet dan wel per towel cachen. Met een string kan je globaal cachen, al is de vraag of je daar iets aan hebt bij deze data. Als je een miljoen dezelfde towels moet oplossen, dan kan het schelen.

spoiler:

Als het je alleen om de dubbelen te doen is, dan kun je die cache het beste buiten de functie zetten, zodat je voor elke towel 1x checkt of je 'm al eerder gezien hebt.

Jouw suggestie heeft wel het voordeel dat je 'm ook kunt gebruiken om towels op te lossen die suffixes zijn van eerder gevonden towels. Maar dan moet je eigenlijk de invoer eerst sorteren op lengte (aflopend) om daar maximaal van te profiteren.

Het probleem met het cachen van de substring is dat de tijdcomplexiteit van het hashen proportioneel is aan de lengte van de string. Hoe langer je towel, hoe trager je cache check is.

.oisyn schreef op donderdag 19 december 2024 @ 08:16:
Ik heb een generieke oplossing voor alle inputs (die het standaard stramien volgen uiteraard) die geen hercompilatie gebruikt. Wel memorymap ik altijd de inputs. Ik verbaas me meer de snelheid van het algoritme. Maar uiteindelijk test hij maar iets in de ordegrootte van 100 verschillende waardes.

Nice! Ik meet iets meer dan 1000 recursieve aanroepen voor mijn invoer. Dan is 90 microseconden erg strak, zeker als je ook nog I/O moet doen (maar dat is bij dit probleem geen grote bottleneck).

Als ik even heel los reken: 90 microseconden is ongeveer 300,000 clock cycles; zeg dat je 2/3e van de tijd gebruikt bij deel 2 dan heb je 200 clock cycles per functie-invocatie. Dat is weinig maar zou inderdaad net moeten kunnen, aangezien de operaties allemaal vrij simpel zijn en de data zo klein is dat 'ie waarschijnlijk in je cache blijft.

[ Voor 33% gewijzigd door Soultaker op 19-12-2024 09:26 ]

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 09:26:
[...]

spoiler:

Jouw suggestie heeft wel het voordeel dat je 'm ook kunt gebruiken om towels op te lossen die suffixes zijn van eerder gevonden towels. Maar dan moet je eigenlijk de invoer eerst sorteren op lengte (aflopend) om daar maximaal van te profiteren.

spoiler:

Als we eerder berekende resultaten willen hergebruiken voor latere towels, is het dan misschien beter om de DP state in een trie op te slaan? Dan kunnen we ook gebruik maken van een eerder resultaat als een deel van de prefix overlapt? Met bottom up DP kunnen we bijhouden hoeveel mogelijkheden er voor de prefix zijn, en dan kunnen we het eenvoudig hergebruiken door in het vervolg te starten vanaf waar het resultaat bekend is voor de langst bekende prefix in de trie. Maakt het wel een stuk ingewikkelder natuurlijk. Wel leuk in combinatie met Aho-Corasick om performance te testen. Het is alleen ook nog nodig om snel values van (grand)parents in de trie op te kunnen vragen vanaf de huidige trie node om values voor nieuwe states te kunnen berekenen.

[ Voor 84% gewijzigd door Robbinb1993 op 19-12-2024 09:54 ]

[Soultaker]

Extra testdata voor dag 19: aoc-2024-day-19-challenge-1-to-3.zip

Correcte antwoorden eindigen op:

aoc-2024-day-19-challenge-1.txt: ...43  ...10914
aoc-2024-day-19-challenge-2.txt: ...69  ...37240
aoc-2024-day-19-challenge-3.txt: ...78  ...88160

Antwoorden voor deel 2 passen in een 64-bits integer.

[Soultaker]

Robbinb1993 schreef op donderdag 19 december 2024 @ 09:31:

spoiler:

Als we eerder berekende resultaten willen hergebruiken voor latere towels, is het dan misschien beter om de DP state in een trie op te slaan?

In theorie zou dat kunnen, maar levert het concreet veel op? Ten eerste heeft het alleen nut als je invoer toevallig veel prefixes bevat, en ten tweede lijkt me dat als je het correct doet het hele algoritme sowieso in O(n) tijd loopt, dus qua theoretische complexiteit valt er weinig winst meer te behalen.

[Robbinb1993]

[b]Soultaker in "Advent of Code 2024"Als je het correct doet het hele algoritme sowieso in O(n) tijd loopt

Wat is n in dit geval? De som van lengtes van zowel de dictionary words als de patterns in de invoer? Met een worst case van bijvoorbeeld dictionary: 'a, aa, aaa, aaaa, aaaaa, aaaaaa, ..., 10000x a' en dan patronen ook zoiets, is de complexiteit volgensmij een stuk slechter dan O(n)?

spoiler:

In dit geval zou het wel helpen als je met een trie resultaten cached. En ik ben ook gewend dat er vaak dit soort hidden test cases voor komen buiten AoC om.

[ Voor 18% gewijzigd door Robbinb1993 op 19-12-2024 11:10 ]

[Soultaker]

Robbinb1993 schreef op donderdag 19 december 2024 @ 11:08:

spoiler:

Wat is n in dit geval? De som van lengtes van zowel de dictionary words als de patterns in de invoer? Met een worst case van bijvoorbeeld dictionary: 'a, aa, aaa, aaaa, aaaaa, aaaaaa, ..., 10000x a' en dan patronen ook zoiets, is de complexiteit volgensmij een stuk slechter dan O(n)?

Ik denk dat ik wat voorbarig was.

spoiler:

Ik zat te denken dat je een state machine kunt bouwen voor het matchen van de patterns, en dan kun je alle towels in O(n) matchen. Alleen die state machine kan groter zijn dan de patterns, dus die vlieger gaat niet op.

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 11:13:
[...]

Ik denk dat ik wat voorbarig was.

spoiler:

Ik zat te denken dat je een state machine kunt bouwen voor het matchen van de patterns, en dan kun je alle towels in O(n) matchen. Alleen die state machine kan groter zijn dan de patterns, dus die vlieger gaat niet op.

spoiler:

Ik heb zo'n state machine (automaton) gemaakt: https://github.com/Robbin...b/main/day19/day19_aho.cc. Alleen voor de bovengenoemde worst scenario test case waarbij zo'n beetje alles overlapt, is de complexiteit alsnog O(N * |dictionary|), waarbij N de lengte van de towel is. Maar als alle towels dan ook nog eens overlappen, komt een trie met cached oplossingen wel van pas.

Soultaker schreef op donderdag 19 december 2024 @ 10:56:
Extra testdata voor dag 19: aoc-2024-day-19-challenge-1-to-3.zip

Correcte antwoorden eindigen op:

aoc-2024-day-19-challenge-1.txt: ...43  ...10914
aoc-2024-day-19-challenge-2.txt: ...69  ...37240
aoc-2024-day-19-challenge-3.txt: ...78  ...88160

Antwoorden voor deel 2 passen in een 64-bits integer.

aoc-2024-day-19-challenge-1.txt: 7ms.
aoc-2024-day-19-challenge-2.txt: 5ms.
aoc-2024-day-19-challenge-3.txt: 483ms.

Case 3 draait wat traag. Ik denk dat het met bovengenoemde optimalisatie een stuk sneller kan, gezien de overlap.

Edit:
Toch niet, de overhead van de 'optimalisatie' is groter dan de tijdswinst. En aangezien de input file > 100MB is, denk ik dat 483ms wel een prima tijd is achteraf.

[ Voor 42% gewijzigd door Robbinb1993 op 19-12-2024 19:14 ]

[FCA]

Robbinb1993 schreef op donderdag 19 december 2024 @ 08:00:
[...]

spoiler:

Trie DP is snel. Aho-Corasick DP is sneller.

https://github.com/Robbin.../blob/main/day19/day19.cc
https://github.com/Robbin...b/main/day19/day19_aho.cc

Dank voor de suggesties. Met mijn duffe hoofd vandaag (griepje lijkt het) laat ik het maar even zitten.

spoiler:

Wel nog mijn cache aangepast van hashmap op string naar gewone array, met de lengte als key. Maakt het geheel inderdaad zo'n 25-30% sneller.

[deboder]

Soultaker schreef op donderdag 19 december 2024 @ 10:56:
Extra testdata voor dag 19: aoc-2024-day-19-challenge-1-to-3.zip

Correcte antwoorden eindigen op:

aoc-2024-day-19-challenge-1.txt: ...43  ...10914
aoc-2024-day-19-challenge-2.txt: ...69  ...37240
aoc-2024-day-19-challenge-3.txt: ...78  ...88160

Antwoorden voor deel 2 passen in een 64-bits integer.

Ik dacht even slim te zijn met mijn Trie oplossing.
Komt mn M3 nog geeneens er doorheen na 5 minuten ...

Deel 2: ---- time taken: 1354 ms

Thanks voor de moeite !

[Robbinb1993]

deboder schreef op donderdag 19 december 2024 @ 14:57:
[...]


Ik dacht even slim te zijn met mijn Trie oplossing.
Komt mn M3 nog geeneens er doorheen na 5 minuten ...

Deel 2: ---- time taken: 1354 ms

Thanks voor de moeite !

Met welke programmeertaal is de oplossing geschreven? Mijn Trie oplossing is ook aanzienlijk langzamer dan bovengenoemde oplossing. Maar na 2 minuten is case 3 ook opgelost. Case 2 doet er 242 ms over.

[deboder]

Robbinb1993 schreef op donderdag 19 december 2024 @ 15:50:
[...]


Met welke programmeertaal is de oplossing geschreven? Mijn Trie oplossing is ook aanzienlijk langzamer dan bovengenoemde oplossing. Maar na 2 minuten is case 3 ook opgelost. Case 2 doet er 242 ms over.

Hier mijn java oplossing:

spoiler:

[code]

Trie trie = new Trie();

protected Object solve() {

trie.insert(input.getFirst());
return input.stream()
.skip(2)
.mapToLong(this::count)
.sum();

}

long count(String word) {
long[] dp = new long[word.length()+1];
dp[0] = 1;
for (int i = 0; i < word.length(); i++) {
for (var s : trie.find(word, i)) {
dp[s+1] += dp[i];
}
}
return dp[word.length()];
}
}


class Trie {

Trie[] arr = new Trie[26];
boolean end = false;

void insert(String s) {
var cur = this;
for (int i = 0; i < s.length(); i++) {
var c = s.charAt(i);
if (c == ' ') {
cur = this;
continue;
}
if (c == ',') {
cur.end = true;
continue;
}
if (cur.arr[c - 'a'] == null) {
cur.arr[c - 'a'] = new Trie();
}
cur = cur.arr[c - 'a'];
}
cur.end = true;
}

List<Integer> find(String s, int i) {
var cur = this;
var list = new ArrayList<Integer>();
while (i < s.length()) {
var c = s.charAt(i);
if (cur.arr[c - 'a'] == null) {
return list;
}
cur = cur.arr[c - 'a'];
if (cur.end) {
list.add(i);
}
i++;
}
return list;
}

}

[/code]

tips zijn welkom

[Robbinb1993]

[b]deboder in "Advent of Code 2024"deboder schreef op donderdag 19 december 2024 @i.Stijn
tips zijn welkom

Ziet er ongeveer hetzelfde uit als wat ik doe in mijn oplossing. Denk dat het meeste verschil zit in Java vs C++, aangezien Java een hoger level is. Er is dus wel een beter algoritme mogelijk, maar die is een stuk lastiger om te implementeren.

spoiler:

Je kan misschien nog een statische array voor de Trie gebruiken door geheugen te preallocaten om de constante factor iets omlaag te brengen tijdens het opbouwen van de Trie. Misschien eerst even meten hoe lang het opbouwen van de Trie zelf kost en of het significant is. Verder kan je nog voorkomen om via een lijst de gevonden indices in 'find' terug te geven aan 'solve', maar direct tijdens het doorlopen van de Trie de DP value te updaten. Scheelt ook weer allocatie en het opbouwen en sturen van data (zie mijn solve method) als je het 'on the fly' doet.

[ Voor 45% gewijzigd door Robbinb1993 op 19-12-2024 16:46 ]

[Soultaker]

Robbinb1993 schreef op donderdag 19 december 2024 @ 11:16:

spoiler:

Ik heb zo'n state machine (automaton) gemaakt: https://github.com/Robbin...b/main/day19/day19_aho.cc. Alleen voor de bovengenoemde worst scenario test case waarbij zo'n beetje alles overlapt, is de complexiteit alsnog O(N * |dictionary|), waarbij N de lengte van het patroon is. Maar als alle patronen dan ook nog eens overlappen, komt een trie met cached oplossingen wel van pas.

Laten we voor de discussie hanteren: M = aantal patterns, m = som van de lengte van de patterns, N = aantal towels, n = som van de lengte van de towels (dus de invoer heeft lengte m + n plus wat formatting).

Het punt wat ik probeerde te maken was dat er twee soorten state machines zijn: deterministisch en nondeterministisch.

spoiler:

Je kunt de patronen combineren in een nondeterministische state machine, maar dan heb je maximaal M states tegelijk actief, dus kom je op O(Mn) qua complexiteit. Dat klinkt als wat jij beschrijft.

Je kunt elke nondeterministische state machine herschrijven naar een deterministische state machine en dan kun je matchen in O(n) tijd, maar het probleem is dat die state machine veel groter dan O(m) worden. In z'n algemeenheid is het dus geen goede oplossing. Of het goed werkt voor mijn testdata heb ik niet geprobeerd.

aoc-2024-day-19-challenge-1.txt: 7ms.
aoc-2024-day-19-challenge-2.txt: 5ms.
aoc-2024-day-19-challenge-3.txt: 483ms.

Dit is heel snel! Het algoritme dat je noemde kende ik nog niet; ik moet het nog in detail bestuderen, maar het lijkt me sterk dat het veel sneller kan zonder specifieke aannamen over de invoer te doen.

spoiler:

Zelf had ik bedacht dat je KMP matching kunt gebruiken om de complexiteit te reduceren van O(nm) naar O(n + Nm), wat in theorie dezelfde worst case is als jouw algoritme, maar in de praktijk aanzienlijk trager.

C++ code. Ik kom op 2,3 s, 0,07 s, 1,54 s voor de challenge cases.

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 16:57:
[...]
Dit is heel snel! Het algoritme dat je noemde kende ik nog niet; ik moet het nog in detail bestuderen, maar het lijkt me sterk dat het veel sneller kan zonder specifieke aannamen over de invoer te doen.

spoiler:

Zelf had ik bedacht dat je KMP matching kunt gebruiken om de complexiteit te reduceren van O(nm) naar O(n + Nm), wat in theorie dezelfde worst case is als jouw algoritme, maar in de praktijk aanzienlijk trager.

C++ code. Ik kom op 2,3 s, 0,07 s, 1,54 s voor de challenge cases.

spoiler:

Aho-Corasick is een deterministische finite state machine en generaliseert het KMP algoritme voor meerdere patronen tegelijkertijd (een dictionary). Dus in plaats van dat we patroon voor patroon zoeken, zoekt Aho Corasick alle patronen tegelijkertijd. Dus waarbij KMP de 1D-variant is, is Aho-Corasick de 2D variant van string-matching. Vaak als er een dictionary voor komt zoals bij dit probleem, is Aho-Corasick nuttig.

En nog een leuk weetje:

spoiler:

The Aho-Corasick

string-matching algorithm formed the basis of the original Unix command fgrep.

[ Voor 34% gewijzigd door Robbinb1993 op 19-12-2024 18:35 ]

[Soultaker]

Over dag 18: ik had nog een ander idee bedacht en dat blijkt goed te werken!

Robbinb1993 schreef op woensdag 18 december 2024 @ 09:51:
Edit:aoc-2024-day-18-challenge-5-2500x2500.txt part 2 draait nu in 2 seconden met

spoiler:

Omgekeerd oplossen (obstakels verwijderen), in combinatie met UFDS datastructuur in O(M * N * α(n)).

Misschien kan het nog sneller?

Ik heb een oplossing die in strict O(size²) tijd draait, geïnspireerd door jouw idee van van achter naar voren oplossen, maar met flood filling in plaats van union-find datastructuur. C++ code (zie de comments voor details). Is dit een standaardalgoritme?

[ Voor 5% gewijzigd door Soultaker op 19-12-2024 19:17 ]

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 19:16:
Over dag 18: ik had nog een ander idee bedacht en dat blijkt goed te werken!


[...]

Ik heb een oplossing die in strict O(size²) tijd draait, geïnspireerd door jouw idee van van achter naar voren oplossen, maar met flood filling in plaats van union-find datastructuur. C++ code (zie de comments voor details). Is dit een standaardalgoritme?

Slim! Heb je deze oplossing ook gebenchmarkt met de test cases van day 18? Dat scheelt ook de tijd die ik kwijt was aan het initialiseren van de UFDS-structuur.

[Soultaker]

Robbinb1993 schreef op donderdag 19 december 2024 @ 19:30:
Heb je deze oplossing ook gebenchmarkt met de test cases van day 18? Dat scheelt ook de tijd die ik kwijt was aan het initialiseren van de UFDS-structuur.

Je bedoelt mijn eigen testcases neem ik aan? Daarop is solve2 sneller dan jouw aanpak, maar soms trager dan de potentieel sublineaire oplossing die ik eerder postte. (Dat is het nadeel van van achteren naar voren werken; je moet de hele input verwerken.) In seconden:

	solve	solve2	robbin
aoc-2024-day-18-challenge-3-2500x2500.txt	0.01	1.47	2.55
aoc-2024-day-18-challenge-4-2500x2500.txt	1.61	1.18	1.76
aoc-2024-day-18-challenge-5-2500x2500.txt	0.39	1.43	2.42

[Robbinb1993]

Soultaker schreef op donderdag 19 december 2024 @ 19:46:
[...]

Je bedoelt mijn eigen testcases neem ik aan? Daarop is solve2 sneller dan jouw aanpak, maar soms trager dan de potentieel sublineaire oplossing die ik eerder postte. (Dat is het nadeel van van achteren naar voren werken; je moet de hele input verwerken.) In seconden:

	solve	solve2	robbin
aoc-2024-day-18-challenge-3-2500x2500.txt	0.01	1.47	2.55
aoc-2024-day-18-challenge-4-2500x2500.txt	1.61	1.18	1.76
aoc-2024-day-18-challenge-5-2500x2500.txt	0.39	1.43	2.42

Het heeft wel een voordeel waar ik later aan dacht: dat de start en eindcell niet per se linksboven en rechtsonder hoeven te zijn geplaatst, maar ook variabele locaties kunnen zijn.

Mijn oplossing op basis van jouw inzicht en turbo read mode:
https://github.com/Robbin...in/day18/day18_variant.cc

Ik heb uiteindelijk alleen nog maar 'gezien' of 'niet gezien' states in mijn oplossing per cel. Eerst bereken ik met floodfill alles wat in de eindsituatie nog bereikbaar is vanaf het einde. En dan geleidelijk aan als ik blokkades verwijder, breid ik dit gebied uit door te kijken of de blokkade orthagonaal grenst aan een cell die al eerder gezien is (en dus het einde kan bereiken). Anders start ik geen floodfill op die plek waar de blokkade is verwijderd. Als we het begin zijn tegengekomen, weten we dat er een weg is van eind naar begin en stoppen we.

aoc-2024-day-18-challenge-3-2500x2500.txt: 456ms.
aoc-2024-day-18-challenge-4-2500x2500.txt: 234ms.
aoc-2024-day-18-challenge-5-2500x2500.txt: 299ms.

[ Voor 31% gewijzigd door Robbinb1993 op 19-12-2024 20:52 ]

[Soultaker]

Robbinb1993 schreef op donderdag 19 december 2024 @ 19:49:
Het heeft wel een voordeel waar ik later aan dacht: dat de start en eindcell niet per se linksboven en rechtsonder hoeven te zijn geplaatst, maar ook variabele locaties kunnen zijn.

Klopt. Maar dat was onderdeel van de probleemstelling dus dat mag je dan gebruiken om te optimaliseren vind ik

Mijn oplossing op basis van jouw inzicht en turbo read mode:
https://github.com/Robbin...in/day18/day18_variant.cc

aoc-2024-day-18-challenge-3-2500x2500.txt: 456ms.
aoc-2024-day-18-challenge-4-2500x2500.txt: 234ms.
aoc-2024-day-18-challenge-5-2500x2500.txt: 299ms.

Oh interessant. Het lijkt dat de winst vooral in de I/O zit: als ik jouw I/O in mijn code copy/paste dan kom ik op bijna exact dezelfde timings. Alleen op challenge-3 ben ik nog significant sneller (0.50 s vs 0.80 s op mijn machine). Mogelijk omdat jij voor elke cel alle vier richtingen tweemaal checkt en ik maar eenmaal?

Andere verschillen: jij alloceert grid[2500][2500] statisch wat in theorie een pointer indirectie per lookup moet schelen t.o.v. mijn vector<vector<State>>, maar in de praktijk lijkt het niet veel uit te maken. (Ik zou er nog een 1-dimensionele vector van kunnen maken.)

Wat me nog wel een paar procent winst opleverde was:

C++:

enum State { U, V, B, F };

Vervangen door:

C++:

enum State : char { U, V, B, F };

Anders is 'ie int-sized by default en dat is blijkbaar net wat minder snel (gebruikt sowieso 4x zoveel geheugen als nodig).

[Soultaker]

Wat betreft dag 20: weer niet zo moeilijk.

spoiler:

Ik heb gewoon een breadth-first search geïmplementeerd (voor de hoeveelste keer dit jaar‽) om alle afstanden vanaf het begin en tot aan het einde te berekenen. Dan kun je voor elk paar punten dat max. 20 stappen van elkaar afligt eenvoudig berekenen hoeveel tijd je bespaart t.o.v. het normale kortste pad.

Python code

[FCA]

Voor dag 20 deel 1 had ik een mooie tijd (plaats 738, beste notering dit jaar), met een lelijke oplossing:

spoiler:

Loop over Dijkstra met telkens precies 1 obstakel weggehaald. Omdat er "slechts" 10000 obstakels waren, en mijn kortste pad in ongeveer een milliseconde draaide (+overhead) leverde dit in ~4sec het correcte antwoord op

Dit ging natuurlijk nooit werken voor deel 2

spoiler:

Uiteindelijk wel een oplossing gevonden.
Eerst een hashmap met voor elke open ruimte de afstand tot de oorsprong bij houden, daarna een dubbele loop over de spaces, en als de afstand daartussen <20 is, checken of afstand start + (totale_lengte - afstand_eind) + cheat_lengte <= totale_lengte - 100.

Heb lang lopen frotten om dit goed te krijgen, was eerst begonnen met de start en het einde van een cheat op een obstakel te zetten, maar dat gaat niet werken ("read the problem statement carefully"). En een bunch van off-by-one errors natuurlijk, op alle mogelijke locaties.

Geoptimaliseerde oplossing loopt nu in 55ms, eens kijken of dat nog wat sneller kan.

[Janoz]

pffff

Door een bug en een implementatiefout veel te lang over deel 2 gedaan

spoiler:

Ik zat te laag, maar ik dacht dat dat kwam omdat er uiteindelijk meer stappen (stappen, niet routes) naar eenzelfde punt zijn. Ik ben dus heel lang bezig geweest om mijn algoritme te debuggen waarbij een punt 18 stappen ver ook bij 20 meetelde (19 stappen heen en 1 terug)

Maar uiteindelijk was mijn bug dat ik maar in 1 kwadrant aan het zoeken was en aannam dat een abs van de winst genoeg zou zijn. Uiteindelijk dom alle kanten op gekeken en de abs weggehaald en toen kwamen de juiste antwoorden er uit

[Soultaker]

Extra testdata voor dag 20: aoc-2024-day-20-challenge-1-to-7.zip

De eerste drie zijn bedoelt om de benchmarken, de andere zijn wat “bijzondere” invoer die mijns inziens wel een geldige oplossing heeft. Oplossingen en referentie-tijden (dit kan zeker nog sneller):

$ time pypy3 solve.py < aoc-2024-day-20-challenge-1.txt 
...293
...808

real	0m3.488s
user	0m3.453s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-2.txt 
...956
...982

real	0m31.975s
user	0m31.768s
sys	0m0.143s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-3.txt 
...743
...943

real	5m47.739s
user	5m46.187s
sys	0m0.924s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-4.txt 
...450
...001

real	0m0.915s
user	0m0.880s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-5.txt 
...822
...658

real	0m0.931s
user	0m0.896s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-6.txt 
...387
...613

real	0m1.241s
user	0m1.209s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-7.txt 
...031
...631

real	0m1.264s
user	0m1.245s
sys	0m0.017s

[Robbinb1993]

Soultaker schreef op vrijdag 20 december 2024 @ 10:58:
Extra testdata voor dag 20: aoc-2024-day-20-challenge-1-to-7.zip

De eerste drie zijn bedoelt om de benchmarken, de andere zijn wat “bijzondere” invoer die mijns inziens wel een geldige oplossing heeft. Oplossingen en referentie-tijden (dit kan zeker nog sneller):

$ time pypy3 solve.py < aoc-2024-day-20-challenge-1.txt 
...293
...808

real	0m3.488s
user	0m3.453s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-2.txt 
...956
...982

real	0m31.975s
user	0m31.768s
sys	0m0.143s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-3.txt 
...743
...943

real	5m47.739s
user	5m46.187s
sys	0m0.924s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-4.txt 
...450
...001

real	0m0.915s
user	0m0.880s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-5.txt 
...822
...658

real	0m0.931s
user	0m0.896s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-6.txt 
...387
...613

real	0m1.241s
user	0m1.209s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-7.txt 
...031
...631

real	0m1.264s
user	0m1.245s
sys	0m0.017s

aoc-2024-day-20-challenge-1.txt: 284ms.
aoc-2024-day-20-challenge-2.txt: 2540ms.
aoc-2024-day-20-challenge-3.txt: 27891ms.
aoc-2024-day-20-challenge-4.txt: 67ms.
aoc-2024-day-20-challenge-5.txt: 68ms.
aoc-2024-day-20-challenge-6.txt: 116ms.
aoc-2024-day-20-challenge-7.txt: 119ms.

Antwoorden zijn hetzelfde. Case 3 is traag.

spoiler:

Ik gebruik ook een BFS vanaf het begin en een BFS vanaf het eind. Complexiteit komt neer op O(N * M * 2 * MAX_CHEAT_DIST^2). Aangezien de ruit van eindpunten binnen het bereik een oppervlakte heeft van O(2 * MAX_CHEAT_DIST^2) en we O(N * M) beginpunten aflopen. Ik heb nagedacht of met een sliding window oplossing, waarbij de ruit steeds 1 plek horizontaal of vertical opgeschoven wordt, nog tijdswinst te behalen valt. Maar waarschijnlijk geeft dat meer overhead dan dat het oplevert, vooral omdat we dan nog een binary search of iets soortgelijks moeten doen om afstanden in de ruit te vinden die er voor zorgen dat de afstand >= 100 stappen kleiner wordt. Dit zal pas voordeliger worden als MAX_CHEAT_DIST nog veel groter kan zijn.

https://github.com/Robbin.../blob/main/day20/day20.cc

[ Voor 5% gewijzigd door Robbinb1993 op 20-12-2024 13:38 ]

[FCA]

Soultaker schreef op vrijdag 20 december 2024 @ 10:58:
Extra testdata voor dag 20: aoc-2024-day-20-challenge-1-to-7.zip

De eerste drie zijn bedoelt om de benchmarken, de andere zijn wat “bijzondere” invoer die mijns inziens wel een geldige oplossing heeft. Oplossingen en referentie-tijden (dit kan zeker nog sneller):

$ time pypy3 solve.py < aoc-2024-day-20-challenge-1.txt 
...293
...808

real	0m3.488s
user	0m3.453s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-2.txt 
...956
...982

real	0m31.975s
user	0m31.768s
sys	0m0.143s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-3.txt 
...743
...943

real	5m47.739s
user	5m46.187s
sys	0m0.924s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-4.txt 
...450
...001

real	0m0.915s
user	0m0.880s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-5.txt 
...822
...658

real	0m0.931s
user	0m0.896s
sys	0m0.033s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-6.txt 
...387
...613

real	0m1.241s
user	0m1.209s
sys	0m0.030s

$ time pypy3 solve.py < aoc-2024-day-20-challenge-7.txt 
...031
...631

real	0m1.264s
user	0m1.245s
sys	0m0.017s

Voor deel 1-5 gaat mijn oplossing goed, deel 6 en 7

spoiler:

bevatten doodlopende wegen, ik weet niet of ik dat helemaal strict volgens de invoerbeschrijving vind ("Because there is only a single path from the start to the end").

Deel 5 vond ik dan wel weer een leuke edge case

spoiler:

obstakelvrije stukken die geen onderdeel zijn van de route, niet verbonden zijn met zowel begin als einde

Challenge 1
Day 20 - Part 1 : ..293
        generator: 300ns,
        runner: 31.9039ms

Parsing: 7.0449ms
Day 20 - Part 2 : ..808
        generator: 700ns,
        runner: 596.0102ms

Challenge 2
Parsing: 66.5358ms
Done with initial distance calc
Day 20 - Part 1 : ..956
        generator: 300ns,
        runner: 503.899ms

Parsing: 67.8503ms
Day 20 - Part 2 : ..982
        generator: 800ns,
        runner: 15.3887608s

Challenge 3:
Parsing: 1.1708931s
Done with initial distance calc
Day 20 - Part 1 : ..743
        generator: 2µs,
        runner: 8.3208074s

Parsing: 999.6695ms
Day 20 - Part 2 : ..943
        generator: 1µs,
        runner: 245.5121416s

Wat sneller dus, maar dat kan denk ik vooral verklaart worden door het verschil in gebruikte taal.

[Janoz]

Mijne zijn ook iets sneller, maar de verhouding is hetzelfde dus ik wijt het niet aan het gebruikte algoritme.

4 ging gelijk goed en ik weet om welke aanname 5 gaat. Die was nog wel te fixen, maar 6 (.684, ..466) en 7 (705, ..232krijg ik andere antwoorden. Ik kan zo snel niet verzinnen welke aannames daar gedaan zijn.

[Janoz]

Als we het toch over interpretaties hebben, Eigenlijk vond ik mijn eigen aanname vanochtend niet eens heel raar.

spoiler:

Nergens staat dat een cheat perse het kortste pad zou moeten hebben. Stel, een cheat pad van 18 levert een besparing van 35 stappen op. In mijn opinie van vanochtend is er dan ook een pad van 20 stappen welke een besparing van 33 oplevert. Op het eindpunt even heen en weer stappen.

Voor 14 heb je dan ook 16, 18 en 20 etc etc.


Maar goed, eigenlijk neem je dan niet de kortste route. En dat moest volgens de eerste alinea van de opdracht wel.

[Marcj]

Ik kom er vandaag echt niet uit, ik zal het wel niet helemaal begrijpen. Iemand die kan uitleggen waar ik verkeerd zit?

spoiler:

Bij deel 2 zoek ik paren van plekken die ver uit elkaar liggen op de route, maar dichtbij genoeg op de kaart als je muren negeert. Als ik naar het voorbeeld kijk, vind ik inderdaad de 3 cheats die 76 ps besparen. Maar kijk ik naar 74ps, dan vind ik de volgende 7:

Found cheat: Point(1,3) -> Point(5,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(4,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(3,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(3,8) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(5,7) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(4,7) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(3,7) (74 picoseconds saved)

Volgens de uitleg zijn er maar 4. Kan iemand me uitleggen wat ik mis? Ik zie deze alle 7 als geldige cheats.

[dcm360]

Marcj schreef op vrijdag 20 december 2024 @ 12:59:
Ik kom er vandaag echt niet uit, ik zal het wel niet helemaal begrijpen. Iemand die kan uitleggen waar ik verkeerd zit?

spoiler:

Bij deel 2 zoek ik paren van plekken die ver uit elkaar liggen op de route, maar dichtbij genoeg op de kaart als je muren negeert. Als ik naar het voorbeeld kijk, vind ik inderdaad de 3 cheats die 76 ps besparen. Maar kijk ik naar 74ps, dan vind ik de volgende 7:

Found cheat: Point(1,3) -> Point(5,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(4,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(3,7) (76 picoseconds saved)
Found cheat: Point(1,3) -> Point(3,8) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(5,7) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(4,7) (74 picoseconds saved)
Found cheat: Point(1,2) -> Point(3,7) (74 picoseconds saved)

Volgens de uitleg zijn er maar 4. Kan iemand me uitleggen wat ik mis? Ik zie deze alle 7 als geldige cheats.

spoiler:

De uitleg bedoelt dat er 4 cheats zijn met een exacte besparing van 74. Als je zoekt naar minstens 74, komen de 3 cheats met de besparing van 76 er nog bij.