Advent of Code 2022

[Cranzai]

Soultaker schreef op zondag 11 december 2022 @ 20:52:
Okee, een extra uitdaging voor dag 11. Meer apen! Meer artikelen!

aoc_2022_day11_large-1.txt (12 KB), som van de cijfers van de antwoorden: 21, 72.

aoc_2022_day11_large-2.txt (135 KB), som van de cijfers van de antwoorden: 48, 60.

Hint: ik heb de inputs zo ontworpen dat je in principe géén big integer library nodig voor deze problemen (wel 64-bits integers), behalve misschien voor large-2 deel 1, afhankelijk van hoe je het aanpakt.

Nu komt de aap uit de mouw!

[Cranzai]

tarlitz schreef op zondag 11 december 2022 @ 20:53:
[...]


Ja, maar ik ken dijkstra ook helemaal niet. Net als @Cranzai heb ik een scheikunde achtergrond en is advent of code echt de eerste keer dat ik zulk soort algoritmes tegen kom. Laat staan dat ik dat voor een aoc puzzel ga implementeren. Dan gebruik ik een library. Anders worden dat soort opdrachten erg lastig.

Ik vind deze discussie daarom wel extra interessant, want ik sta echt versteld van wat ik allemaal zie qua oplossingen. En blijkbaar komt dit dus wél voorbij in de informatica opleidingen. Dit is goed om te weten voor mijn eigen zelfwaarde 😅

Dat trucje van vandaag zou ik zelf nooit opgekomen zijn als ik het niet vorig jaar ook al tegengekomen was. Dat vind ik ook het leuke van aoc. Zeker met opdrachten als deze leer ik veel van de oplossingen die voorbij komen.

Geloof dat ik vorig jaar Dijkstra nog wel zelf heb weten te implementeren, die informatici/wiskundigen weten hun logica vaak wel elegant te presenteren zodat het redelijk te doen is

en wat je zegt, goed om te weten dat sommige van deze dingetjes geen "normale" kennis zijn haha

[ Voor 4% gewijzigd door Cranzai op 11-12-2022 21:11 ]

[Gropah]

Cranzai schreef op zondag 11 december 2022 @ 21:07:
[...]


Hmmm, dan ben ik dat vak niet tegengekomen, tenzij het een vak in C was? Kan ook zijn dat het de scheikundige technologen waren die dat vak volgden? Die hebben net een ander curriculum

Zelf in de richting theoretische chemie gegaan

Het gaat om imperatief programmeren. En het is volgens mij inderdaad een keuzevak voor iedereen die geen informatica of kunstmatige intelligentie studeert.

[P_Tingen]

Veel van die algoritmes ken ik ook niet. Ik programmeer sinds mijn 15e en ben nu al bijna 30 jaar zelf ontwikkelaar, alleen niet met dit soort algoritmes. Die gebruik je nou eenmaal niet zo snel in een ERP. Ik vind het echter heerlijk om te zien hoe anderen het probleem oplossen, jammer dat er zo weinig uit mijn niche (Progress 4GL) meedoen aan AoC, slechts een handjevol. Ook oplossingen in andere talen vind ik mooi en leerzaam, al is de ene taal wat toegankelijker dan de andere.

[corbosman]

MueR schreef op zondag 11 december 2022 @ 15:11:
Dag 11 in PHP
Deel 2 is wat traag met ~130ms.

Bij mij 90ms in php maar dat kan aan snellere laptop liggen. Blijft traag helaas.

[Jern_97]

Soultaker schreef op zondag 11 december 2022 @ 20:52:
Okee, een extra uitdaging voor dag 11. Meer apen! Meer artikelen!

aoc_2022_day11_large-1.txt (12 KB), som van de cijfers van de antwoorden: 21, 72.

aoc_2022_day11_large-2.txt (135 KB), som van de cijfers van de antwoorden: 48, 60.

Hint: ik heb de inputs zo ontworpen dat je in principe géén big integer library nodig voor deze problemen (wel 64-bits integers), behalve misschien voor large-2 deel 1, afhankelijk van hoe je het aanpakt.

Hiervoor moet je duidelijk wel

spoiler:

least common multiple

gebruiken ipv

spoiler:

gewoon alle divisors te vermenigvuldigen

Net onder de 4s voor input 2. (enkel 64 bit integers)

[HectorMalot]

Soultaker schreef op vrijdag 9 december 2022 @ 14:46:
Nog wat extra grote inputs voor dag 9:

• aoc_2022_day09_large-1.zip (4.4 MB, 1M instructies); antwoorden eindigen op 673 en 518
• aoc_2022_day09_large-2.zip (44 MB, 10M instructies); antwoorden eindigen op 628 en 182

Mijn Python oplossing doet de eerste set in ongeveer 27 seconden. Mijn C++ oplossing (met absl::flat_hash_set) de eerste in ongeveer 5, en de tweede in 68 seconden. Dat kan vast beter

Ook nog gedaan in Go. Mijn eerste simpele oplossing liep op 4 minuten voor de grote set, part 2. Leuk om te optimaliseren met goroutines/channels. Nu naar 40 seconden weten te brengen op apple M1. Code hier

[CMG]

Dag 11 in 2 delen gedaan ivm tijdgebrek (verjaardagfeestje)

Deel 1 ging goed, behalve dat ik een parameter niet overnam in de constructor waardoor mijn mapping niet klopte; wat tijd kwijt geweest met debuggen 😅

Deel 2 ging best ok omdat ik redelijk wist wat ik moest doen (vergelijkbaar met een issue uit vorige jaren); ware het niet dat ik een int overflow niet opmerkte omdat hij zo ver overflowde dat hij een plausiebele positieve waarde terug gaf 🤣

video deel 1 | video deel 2 | c# code

[Soultaker]

Jern_97 schreef op zondag 11 december 2022 @ 22:27:
Net onder de 4s voor input 2. (enkel 64 bit integers)

Nice! Hoe heb je deel 1 aangepakt?

[FrankMennink]

Dag 11 in Python

spoiler:

Redelijke tijd zitten staren op deel 2, met mij nog wel meer lees ik. Had wel door dat het iets met de verschillende delers moest zijn. Na een minuut of 20 eigenlijk at random maar de lcm gepakt van de delers en daar was t goeie antwoord. Zeker gevalletje goed geluk. Deel 2 draait in 3.2s, voor nu goed genoeg. Zeker wel een om laten nog even terug te kijken

[Soultaker]

HectorMalot schreef op zondag 11 december 2022 @ 22:52:
Ook nog gedaan in Go. Mijn eerste simpele oplossing liep op 4 minuten voor de grote set, part 2. Leuk om te optimaliseren met goroutines/channels. Nu naar 40 seconden weten te brengen op apple M1. Code hier

Dit heb je wel leuk aangepakt: elke knoop krijgt z'n eigen thread, en de deduplicatie van posities ook. Jammer dat het nog niet heel snel is (ik had oorspronkelijk ~24s in C++, later ~9s, en @.oisyn heeft het weten te verbeteren tot ~1.5s). Misschien helpt het als je in segment alleen naar de output channel schrijft als de positie daadwerkelijk veranderd is?

Ik snap trouwens ook niet echt waarom counter() de invoer naar de uitvoer kopieert? Waarom schrijft die niet gewoon len(visited) naar de uitvoer wanneer 'ie klaar is?

[CMG]

Soultaker schreef op zondag 11 december 2022 @ 20:52:
Okee, een extra uitdaging voor dag 11. Meer apen! Meer artikelen!

aoc_2022_day11_large-1.txt (12 KB), som van de cijfers van de antwoorden: 21, 72.

aoc_2022_day11_large-2.txt (135 KB), som van de cijfers van de antwoorden: 48, 60.

Hint: ik heb de inputs zo ontworpen dat je in principe géén big integer library nodig voor deze problemen (wel 64-bits integers), behalve misschien voor large-2 deel 1, afhankelijk van hoe je het aanpakt.

Eerste input getest; geen benchmark, maar gewoon Stopwatch 1 run: 1.3s for beide delen

spoiler:

Result: 2683200
LCM: 1375604230
Result: 865971689472
Code runtime: 00:00:01.3066955

2e input ook gerund, loopt 1 minuut 😅 som voor deel 1 is alleen 32 bij mij, niet 48?

spoiler:

Result: 2184004256
LCM: 1250549300
Result: 769335011398221
Code runtime: 00:01:00.3263298

[ Voor 9% gewijzigd door CMG op 11-12-2022 23:36 . Reden: spoiler tag fixed ]

[corbosman]

CMG schreef op zondag 11 december 2022 @ 23:32:

2e input ook gerund, loopt 1 minuut 😅 som voor deel 1 is alleen 32 bij mij, niet 48?

Ik heb een ander resultaat bij de 1e, en kom uit op 50,60. Collega van me in andere taal zelfde result als ik en dus ook 50,60 ipv 48,60.

Cor

[_mike_]

Soultaker schreef op zondag 11 december 2022 @ 20:52:

aoc_2022_day11_large-2.txt (135 KB), som van de cijfers van de antwoorden: 48, 60.

Hee, zowel ik (rust) als iemand anders (php) krijgen voor large-2 deel 1 als som van de cijfers 50 ipv 48. heb je een hint waardoor dat zou kunnen komen?

[CMG]

corbosman schreef op zondag 11 december 2022 @ 23:46:
[...]

Ik heb een ander resultaat bij de 1e, en kom uit op 50,60. Collega van me in andere taal zelfde result als ik en dus ook 50,60 ipv 48,60.

Cor

De andere 3 'sommen' komen wel overeen bij mij, dus geen idee. Wel appart dat we allemaal een ander antwoord krijgen bij deel 1 van file 2 😅

[Soultaker]

CMG schreef op zondag 11 december 2022 @ 23:32:
Eerste input getest; geen benchmark, maar gewoon Stopwatch 1 run: 1.3s for beide delen
[..]
2e input ook gerund, loopt 1 minuut 😅 som voor deel 1 is alleen 32 bij mij, niet 48?

De antwoorden voor large-1 (deel 1 & 2) en large-2 deel 2 kloppen, maar large-2 deel 1 niet. Je hebt daar waarschijnlijk een integer overflow

Mijn Python code doet large-1 ook in ongeveer 1s, large-2 in iets meer dan een minuut.

Hint: large-2 deel-1 is het moeilijkste onderdeel van de extra set. Je moet daar wat slims voor verzinnen. Mogelijk helpt het ook om naar de invoerdata te kijken.

[CMG]

Soultaker schreef op zondag 11 december 2022 @ 23:47:
[...]

De antwoorden voor large-1 (deel 1 & 2) en large-2 deel 2 kloppen, maar large-2 deel 1 niet. Je hebt daar waarschijnlijk een integer overflow

Mijn Python code doet large-1 ook in ongeveer 1s, large-2 in iets meer dan een minuut.

Hint: large-2 deel-1 is het moeilijkste onderdeel van de extra set. Je moet daar wat slims voor verzinnen. Mogelijk helpt het ook om naar de invoerdata te kijken.

Voor part 1's deed ik geen LCM omdat het niet nodig was tot nu toe 😅 ik zal eens kijken wat dat nog kan zijn. Net LCM toegevoegd daar en dan kom ik op 51 uit; dus al iets anders (en ook anders dan de andere hier nu ) ik zoek nog ff

[HectorMalot]

Soultaker schreef op zondag 11 december 2022 @ 23:32:
[...]

Dit heb je wel leuk aangepakt: elke knoop krijgt z'n eigen thread, en de deduplicatie van posities ook. Jammer dat het nog niet heel snel is (ik had oorspronkelijk ~24s in C++, later ~9s, en @.oisyn heeft het weten te verbeteren tot ~1.5s). Misschien helpt het als je in segment alleen naar de output channel schrijft als de positie daadwerkelijk veranderd is?

Ik snap trouwens ook niet echt waarom counter() de invoer naar de uitvoer kopieert? Waarom schrijft die niet gewoon len(visited) naar de uitvoer wanneer 'ie klaar is?

Thanks! Counter was 'transparant' zodat ik ook de positie van de 2e knoop (deel 1) bij kon houden en ondertussen de data door kon laten stromen.

Met segment alleen doorzetten bij wijziging gaan er een paar seconden vanaf.

Iets van 60% van de tijd zit nu in het schrijven naar de map[pos]struct{}. Een poor man's implementatie van concurrent writes op de map brengt het tot 19 sec, wel stukken minder leesbaar geworden.

[CMG]

Soultaker schreef op zondag 11 december 2022 @ 23:47:
[...]

De antwoorden voor large-1 (deel 1 & 2) en large-2 deel 2 kloppen, maar large-2 deel 1 niet. Je hebt daar waarschijnlijk een integer overflow

Mijn Python code doet large-1 ook in ongeveer 1s, large-2 in iets meer dan een minuut.

Hint: large-2 deel-1 is het moeilijkste onderdeel van de extra set. Je moet daar wat slims voor verzinnen. Mogelijk helpt het ook om naar de invoerdata te kijken.

Mijn deel 2 code herschreven als een functie die count accepteerd zodat ik 20 en 10k mee kan geven; krijg nu sum van 45 voor het antwoord van deel 1 file 2 🤣

spoiler:

3642484509

Hoe zou het kunnen dat hij 20 niet kan uitrekenen maar 10k wel? 😅 Kan alle state per monkey uitspugen als het helpt, maar vraag me af waar het verschil vandaan komt 😅

[update]

Nog even gekeken; had het doReduction stuk natuurllijk niet meegenomen als parameter. Kom nu ook op 51 uit 🤣

[ Voor 6% gewijzigd door CMG op 12-12-2022 00:08 ]

[Jern_97]

Soultaker schreef op zondag 11 december 2022 @ 23:21:
[...]

Nice! Hoe heb je deel 1 aangepakt?

spoiler:

(value / 3) % (lcm * 3)

Vraag me niet om wiskundig te bewijzen waarom het werkt, maar het werkt wel
Volgens mij heb ik het hoofdstuk over modulair rekenen overgeslagen tijdens mijn opleiding...

https://github.com/Jeroen...22/blob/main/src/day11.rs

[ Voor 24% gewijzigd door Jern_97 op 12-12-2022 00:09 ]

[Soultaker]

CMG schreef op maandag 12 december 2022 @ 00:02:
Hoe zou het kunnen dat hij 20 niet kan uitrekenen maar 10k wel? 😅 Kan alle state per monkey uitspugen als het helpt, maar vraag me af waar het verschil vandaan komt 😅

Hint:

spoiler:

(a + b) % m == ((a % m) + (b % m)) % m

en

spoiler:

(a * b) % m == ((a % m) * (b % m)) % m

maar

spoiler:

(a / b) % m != ((a % m) / (b % m)) % m (tenminste, niet altijd)

Jern_97 schreef op maandag 12 december 2022 @ 00:06:

spoiler:

(value / 3) % (lcm * 3)

Vraag me niet om te bewijzen waarom het werkt, maar het werkt wel

Hier moet ik morgen even over nadenken, want ik weet niet of ik het zo laat nog kan snappen Kun je het volledige antwoord (gespoilerd) posten zodat ik weet dat het klopt?

[Jern_97]

Soultaker schreef op maandag 12 december 2022 @ 00:11:
[...]

Hier moet ik morgen even over nadenken, want ik weet niet of ik het zo laat nog kan snappen Kun je het volledige antwoord (gespoilerd) posten zodat ik weet dat het klopt?

Sommen van de individuele getallen komen overeen, dus zou me verbazen als er iets fout zou zijn:

spoiler:

Part 1: 2683200
Part 2: 865971689472
Time: 77ms

Part 1: 2029629080
Part 2: 769335011398221
Time: 3930ms

[CMG]

Soultaker schreef op maandag 12 december 2022 @ 00:11:
[...]

Hint:

spoiler:

(a + b) % m == ((a % m) + (b % m)) % m

en

spoiler:

(a * b) % m == ((a % m) * (b % m)) % m

maar

spoiler:

(a / b) % m != ((a % m) / (b % m)) % m (tenminste, niet altijd)

[...]

Hier moet ik morgen even over nadenken, want ik weet niet of ik het zo laat nog kan snappen Kun je het volledige antwoord (gespoilerd) posten zodat ik weet dat het klopt?

Jern_97 schreef op maandag 12 december 2022 @ 00:14:
[...]


Sommen van de individuele getallen komen overeen, dus zou me verbazen als er iets fout zou zijn:

spoiler:

Part 1: 2683200
Part 2: 865971689472
Time: 77ms

Part 1: 2029629080
Part 2: 769335011398221
Time: 3930ms

Som van file 2 deel 1 is 38, Soultaker zei dat het 48 moest zijn.

Heb alles naar ulong's omgezet; nu kom ik ook op

spoiler:

2029629080

en dus sum 38 (andere had ik al de zelfde uitkomsten)

[Soultaker]

Jern_97 schreef op maandag 12 december 2022 @ 00:14:
Sommen van de individuele getallen komen overeen, dus zou me verbazen als er iets fout zou zijn:

Drie van de vier zijn correct, maar large-2 part 1 niet. De som van de cijfers van jouw antwoord is 38 en niet 48.

Het kan zijn dat mijn antwoord niet klopt maar ik wil dit wel goed beredeneerd zien voordat ik het geloof

CMG schreef op maandag 12 december 2022 @ 00:24:
Som van file 2 deel 1 is 38, Soultaker zei dat het 48 moest zijn.

Dit is juist. 2029629080 is voor zover ik weet incorrect.

[Jern_97]

CMG schreef op maandag 12 december 2022 @ 00:24:
[...]


[...]


Som van file 2 deel 1 is 38, Soultaker zei dat het 48 moest zijn.

Heb alles naar ulong's omgezet; nu kom ik ook op

spoiler:

2029629080

en dus sum 38 (andere had ik al de zelfde uitkomsten)

Oh wow, daar heb ik inderdaad compleet over gekeken... Waarschijnlijk toch fout dan.
Ik beheers de wiskunde erachter te weinig om hier echt op te kunnen rederen...

[ Voor 10% gewijzigd door Jern_97 op 12-12-2022 00:47 ]

[Varienaja]

Thorwing schreef op zondag 11 december 2022 @ 20:39:
Het is alsof je gaat klagen dat je het Dijkstra algoritme niet kent bij een toekomstige opgave (wat zeker gaat komen).

Goedemorgen mijnheer Dijkstra!

Dag 12 in Java.

[Janoz]

Toch eigenlijk nog best wel lang mee bezig geweest omdat het algoritme niet verder kwam bij de echte input. Bleek ik toch een stukje van het verhaal niet helemaal goed gelezen te hebben

[MrHaas]

Mijn oplossing in Python

spoiler:

Bij deel 2 berekende ik initieel voor elk startpunt het path maar daarna aangepast door gewoon de queue te initializeren met alle startpunten.

[CMG]

Soultaker schreef op maandag 12 december 2022 @ 00:29:
[...]

Drie van de vier zijn correct, maar large-2 part 1 niet. De som van de cijfers van jouw antwoord is 38 en niet 48.

Het kan zijn dat mijn antwoord niet klopt maar ik wil dit wel goed beredeneerd zien voordat ik het geloof


[...]

Dit is juist. 2029629080 is voor zover ik weet incorrect.

Is er inmiddels iemand die het wel ‘correct’ heeft?

[Gropah]

Janoz schreef op maandag 12 december 2022 @ 07:20:
Toch eigenlijk nog best wel lang mee bezig geweest omdat het algoritme niet verder kwam bij de echte input. Bleek ik toch een stukje van het verhaal niet helemaal goed gelezen te hebben

Same here En veels te lang geprobeerd het recursief te doen.

Al met al niet zo heel blij met mijn tijd van vandaag, maar wel met de uiteindelijke oplossing die ik heb gemaakt

[Janoz]

Gropah schreef op maandag 12 december 2022 @ 09:00:
[...]


Same here En veels te lang geprobeerd het recursief te doen.

Al met al niet zo heel blij met mijn tijd van vandaag, maar wel met de uiteindelijke oplossing die ik heb gemaakt

Nou, mijn algoritme was keurig in orde, maar mijn geldige stap validatie ging niet goed.

spoiler:

pas na een paar keer lezen drong het door dat ver naar beneden klimmen geen enkel probleem was

[Gropah]

Janoz schreef op maandag 12 december 2022 @ 09:21:
[...]

Nou, mijn algoritme was keurig in orde, maar mijn geldige stap validatie ging niet goed.

spoiler:

pas na een paar keer lezen drong het door dat ver naar beneden klimmen geen enkel probleem was

Haha, ja, die ging bij mij ook verkeerd

[Janoz]

Gelijk maar even de tijd genomen om Dijkstra te refactoren naar een generieke class. Het stomme is dat ik dit al wilde doen toen @TrailBlazer er 6 december over begon. Had vandaag best wat tijd gescheeld kunnen hebben...

[Soultaker]

CMG schreef op maandag 12 december 2022 @ 08:39:
Is er inmiddels iemand die het wel ‘correct’ heeft?

Niet dat ik weet

Varienaja schreef op maandag 12 december 2022 @ 06:53:
Goedemorgen mijnheer Dijkstra!

Technisch is dit een

spoiler:

breadth-first search, waarbij elke stap als 1 telt, niet Dijkstra's algoritme, wat stappen van variabele lengte toestaat.

[armageddon_2k1]

Dag 12 in Kotlin/

Klassiekertje natuurlijk die elk jaar terugkomt. Nu komen mijn generieke helper functies wel erg goed van pas!

Part 2 kan slimmer, maar fuck it

[ Voor 7% gewijzigd door armageddon_2k1 op 12-12-2022 10:17 ]

[Diderikdm]

Deze puzzel zat eraan te komen! Wel even vastgezeten omdat ik nog een verdwaalde:

spoiler:

abs(a - b) ipv (a - b) in mn code had

Voor deel twee gekozen om:

spoiler:

Start en eindpunten om te draaien om zo vanaf E de eerste "a" te vinden

Dag 12 - Python

[MrHaas]

Diderikdm schreef op maandag 12 december 2022 @ 09:49:
Voor deel twee gekozen om:

spoiler:

Start en eindpunten om te draaien om zo vanaf E de eerste "a" te vinden

Ah ja, niet eens aan gedacht!

[tarlitz]

Diderikdm schreef op maandag 12 december 2022 @ 09:49:
Deze puzzel zat eraan te komen! Wel even vastgezeten omdat ik nog een verdwaalde:

spoiler:

abs(a - b) ipv (a - b) in mn code had

Voor deel twee gekozen om:

spoiler:

Start en eindpunten om te draaien om zo vanaf E de eerste "a" te vinden

Dag 12 - Python

Hah, inderdaad grappig omdat het hier gister nog over ging.

spoiler:

Hier heb ik hem lekker weer met networkx opgelost.

[ Voor 69% gewijzigd door tarlitz op 12-12-2022 11:22 ]

[.oisyn]

Janoz schreef op maandag 12 december 2022 @ 07:20:
Toch eigenlijk nog best wel lang mee bezig geweest omdat het algoritme niet verder kwam bij de echte input. Bleek ik toch een stukje van het verhaal niet helemaal goed gelezen te hebben

Ik denk dat ik hetzelfde niet goed gelezen heb

[Janoz]

.oisyn schreef op maandag 12 december 2022 @ 10:08:
[...]


Ik denk dat ik hetzelfde niet goed gelezen heb

@Diderikdm ook

[.oisyn]

Janoz schreef op maandag 12 december 2022 @ 10:09:
[...]

@Diderikdm ook

Dan ik idd ook
Wel jammer, ik gebruikte de \n karakters als boundary, maar dat werkt nu niet meer

.edit:

Time: 778us (load:50us, algo1:83us, algo2:643us)
Part 1: 339
Part 2: 332

Nou kom maar op met die grotere inputs

.edit: visualisatie

[ Voor 50% gewijzigd door .oisyn op 12-12-2022 10:59 ]

[Camulos]

Vandaag was idd een classic - oplossing Day 12 in C#

spoiler: deel1

Breadth-First-Search met een queue, en dan zo veel mogelijk prunen:
* Extra grid met minimale stappen bijhouden (naast de hoogte kaart)
* Voordat je een nieuw vakje toevoegd, ook al checken of er route is geweest met dezelfde (of minder) stappen, dan kun je deze overslaan
* Ben erg blij met de C# Tuples

spoiler: deel2

thnx @Diderikdm voor Endpoint = startpoint !! dat was erg slim, en heb dat ook meteen toegepast

[P_Tingen]

Ik herkende hem van vorig jaar en gelukkig had ik van vorig jaar een paar aantekeningen bewaard zodat ik de code op kon zoeken. Hij zat er vorig jaar nml ook al in, onze Edsger.

Code van vorig jaar is verrassend goed bruikbaar, merkte ik 😎

[Xqlusive]

spoiler:

Deel 2 maar op de brute force methode opgelost... blijkbaar zitten er 1338 a-tjes in, dus dat duurde wel even. Gelukkig wel het juiste antwoord na 20 min wachten

Ik was vooral veel tijd kwijt aan het transformeren van de input naar een graph dict. Hier kan vast iets veel slimmers voor gedaan worden, ik ga dan ook even oplossingen van anderen doorkijken hoe ik hier handiger mee om zou kunnen gaan in de toekomst!

[CMG]

Vandaag zoals zovelen

spoiler:

Dijkstra

maar uit de kast gehaald, al was dat achteraf eigenlijk niet nodig.

Voor deel 2 was het vooral dat je moet inzien dat je

spoiler:

van eind het kortste startpunt moet zoeken ipv alle mogelijke startpunten naar het eind

code post | video

[Soultaker]

.oisyn schreef op maandag 12 december 2022 @ 10:12:
Nou kom maar op met die grotere inputs

Hier is er alvast eentje:

Extra invoer voor dag 12:

• aoc_2022_day12_large-1.zip (13 MB ingepakt, 30 MB uitgepakt)
  Correcte antwoorden modulo 31337: 15519 en 511.
• aoc_2022_day12_zigzag.zip (1 MB uitgepakt, som van de antwoorden is een mooi rond getal).
• aoc_2022_day12_large-2.zip (11 MB ingepakt, 25 MB uitgepakt). Antwoorden modulo 97: 57, 53.

[ Voor 33% gewijzigd door Soultaker op 12-12-2022 13:16 ]

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 11:23:
[...]

Hier is er alvast eentje:

Extra invoer voor dag 12: aoc_2022_day12_large-1.zip (13 MB ingepakt, 30 MB uitgepakt)
Correcte antwoorden modulo 31337: 15519 en 511.

Time: 898.283us (load:21.240us, part1:379.369us, part2:493.550us)

.edit:
Deze is iets beter (zie paar posts naar onderen)

Time: 811.393us (load:19.464us, part1:346.904us, part2:440.852us)

[ Voor 12% gewijzigd door .oisyn op 12-12-2022 11:52 ]

[.oisyn]

CMG schreef op maandag 12 december 2022 @ 11:16:
Voor deel 2 was het vooral dat je moet inzien dat je

spoiler:

van eind het kortste startpunt moet zoeken ipv alle mogelijke startpunten naar het eind

spoiler:

Nou ja, dat 'moet' helemaal niet, maar wat je vooral niet moet doen is het algoritme elke keer opnieuw runnen voor elk startpunt. Als je iets als Dijkstra gebruikt dan kun je ook gewoon beginnen met alle mogelijke startpunten in de queue.

[armageddon_2k1]

.oisyn schreef op maandag 12 december 2022 @ 11:41:
[...]

spoiler:

Nou ja, dat 'moet' helemaal niet, maar wat je vooral niet moet doen is het algoritme elke keer opnieuw runnen voor elk startpunt. Als je iets als Dijkstra gebruikt dan kun je ook gewoon beginnen met alle mogelijke startpunten in de queue.

spoiler:

Nou ja dat moet ook helemaal niet als je gewoon lui bent en je algo performant genoeg is en je weer aan het werk moet

[Jern_97]

.oisyn schreef op maandag 12 december 2022 @ 11:41:
[...]

spoiler:

Nou ja, dat 'moet' helemaal niet, maar wat je vooral niet moet doen is het algoritme elke keer opnieuw runnen voor elk startpunt. Als je iets als Dijkstra gebruikt dan kun je ook gewoon beginnen met alle mogelijke startpunten in de queue.

Maar jouw implementatie gebruikt geen

spoiler:

Dijkstra

veronderstel ik? Ik kan namelijk Soultaker's input niet oplossen in een redelijke tijd met

spoiler:

mijn implementatie (Dijkstra met priority queue).

[.oisyn]

@Jern_97

spoiler:

A*, ik zal eens kijken waar ik op uit kom zonder heuristic

.edit: Time: 854.966us (load:21.536us, part1:368.414us, part2:460.280us)
Wat ik al vermoedde, de heuristic voegt niet heel veel toe met deze datasets. A* zonder heuristic is gewoon Dijkstra

.edit2:

spoiler:

Oh haha het is zelfs sneller zonder heuristic. Blijkbaar is het berekenen van het nog minimaal te zetten stappen meer overhead dan de extra pruning die het geeft

Je gebruikt Rust, toch? Dan zou ik toch je code eens goed nakijken of er niet ergens een domme dure stap in zit

[ Voor 90% gewijzigd door .oisyn op 12-12-2022 11:56 ]

[TrailBlazer]

spoiler:

het verschil tussen mijn task1 en task2 is maar een stap ging wel twijfelen bij mijn invoer

[Soultaker]

Jern_97 schreef op maandag 12 december 2022 @ 11:46:
[...]


Maar jouw implementatie gebruikt geen

spoiler:

Dijkstra

veronderstel ik? Ik kan namelijk Soultaker's input niet oplossen in een redelijke tijd met

spoiler:

mijn implementatie (Dijkstra met priority queue).

In principe moet 'ie wel op te lossen zijn voor de gemiddelde deelnemer.

spoiler:

Een typische oplossing loopt in O(N) tijd (breadth first search) of O(N log N) (sommige implementaties van Dijkstra's algoritme of A*). De invoer is 30 MB groot, dus maximaal 30 miljoen stappen voor O(N), ~600 miljoen voor O(N log N); dat moet in een paar seconden of hooguit een paar minuten lukken. De invoer is alleen niet te doen als je een O(N²) of slechter algoritme geïmplementeerd hebt, maar je moet je best doen om het zo gek te maken

[MatHack]

Dag 12 in C#

Part1 in 542,7683ms
Part2 in 7,147ms

spoiler:

A* voor deel 1 gebruikt, maar dat ging voor deel 2 niet op (omdat je het einde niet weet). Toen maar Dijkstra geïmplementeerd die vanaf E de eerste a vindt. Blijkbaar was ik niet de eerste die eraan dacht om voor deel 2 het begin & eind om te draaien. Nu ik de opmerkingen van @Soultaker lees zie ik in dat breadth-first waarschijnlijk beter werkt (en waarschijnlijk ook sneller te implementeren is), alle afstanden zijn natuurlijk 1

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 12:00:
[...]

In principe moet 'ie wel op te lossen zijn voor de gemiddelde deelnemer.

spoiler:

Een typische oplossing loopt in O(N) tijd (breadth first search) of O(N log N) (sommige implementaties van Dijkstra's algoritme of A*). De invoer is 30 MB groot, dus maximaal 30 miljoen stappen voor O(N), ~600 miljoen voor O(N log N); dat moet in een paar seconden of hooguit een paar minuten lukken. De invoer is alleen niet te doen als je een O(N²) of slechter algoritme geïmplementeerd hebt, maar je moet je best doen om het zo gek te maken

spoiler:

Nu je dat zegt realiseer ik me ineens waar de relatieve traagheid van A* vandaan komt idd. Door de heuristic moet ie de de priority queue updaten, terwijl zonder de heuristic dingen gewoon aan het eind worden toegevoegd. Denk dat ik de hele prio queue er maar uit sloop. En zonder heuristic is van E naar a zoeken voor part2 idd sowieso sneller

[ Voor 57% gewijzigd door .oisyn op 12-12-2022 12:07 ]

[Janoz]

Ik heb de grote inputs nog niet geprobeerd, maar ik zie ook dat mijn dijkstra oplossing 3/4 van de tijd van mijn A* oplossing nodig heeft voor part 1. JE zou dus best nog wel eens gelijk kunnen hebben @.oisyn. Part 2 heeft de helft van de tijd van part 1 nodig. Eerst nog aan het werk, vanmiddag maar eens even loslaten op een grote set. Was vanochtend vooral nog even bezig geweest met het generaliseren van mijn oplossingen zodat ik hem de volgende keer niet weer helemaal uit hoef te schrijven.

[ Voor 6% gewijzigd door Janoz op 12-12-2022 12:33 ]

[Soultaker]

Deze zijn ook leuk om te testen: aoc_2022_day12_zigzag.zip (som van de antwoorden is een mooi rond getal). Deze testset is gemaakt in vim

Overige invoer staat hier.

[ Voor 39% gewijzigd door Soultaker op 12-12-2022 13:18 ]

[.oisyn]

Weird, breadth-first van end naar start is voor de originele input wel een stuk sneller, maar bij Soultaker's set is hij langzamer dan (multi)start naar eind.

[Janoz]

Ik heb het idee dat bij de opdracht er een complete 'canyon' juist om het eindpunt zit (kijk maar naar je animatie, mijn set zag er vergelijkbaar uit qua route). De start->eind oplossing loopt dan eerst helemaal om de canyon heen terwijl de eind->start oplossing er gelijk uitloopt.

[Janoz]

Soultaker schreef op maandag 12 december 2022 @ 12:33:
Deze zijn ook leuk om te testen: aoc_2022_day12_zigzag.zip (som van de antwoorden is een mooi rond getal). Deze testset is gemaakt in vim

Large:

Part 1:
xx99 (A*)
15868 ms
xx99 (Dijkstra met early out)
15500 ms

Part 2:
xx01 (Dijkstra)
12917 ms

[P_Tingen]

Kan iemand mij even bijpraten over de 'snelle' manier van deel 2?
Ik heb het nu brute force opgelost maar dat kan beter

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 12:33:
Deze zijn ook leuk om te testen: aoc_2022_day12_zigzag.zip (som van de antwoorden is een mooi rond getal). Deze testset is gemaakt in vim

Zó weird dit.

Breadth-first start to end

===[ aoc_2022_day12_large-1.txt ]==========
Time: 851.034us (load:20.143us, part1:362.547us, part2:464.218us)
Part 1: 2616490
Part 2: 2507471
Time: 846.207us (load:20.246us, part1:355.083us, part2:466.501us)
Part 1: 2616490
Part 2: 2507471
Time: 829.116us (load:20.921us, part1:348.042us, part2:456.162us)
Part 1: 2616490
Part 2: 2507471

===[ aoc_2022_day12_zigzag-small.txt ]==========
Time: 34.341us (load:1.145us, part1:13.471us, part2:19.468us)
Part 1: 1299999
Part 2: 1200001
Time: 33.687us (load:1.002us, part1:13.486us, part2:19.006us)
Part 1: 1299999
Part 2: 1200001
Time: 33.148us (load:968us, part1:13.216us, part2:18.760us)
Part 1: 1299999
Part 2: 1200001

===[ aoc_2022_day12_zigzag-large.txt ]==========
Time: 348.981us (load:9.855us, part1:132.000us, part2:204.869us)
Part 1: 12999999
Part 2: 12000001
Time: 351.564us (load:11.904us, part1:131.512us, part2:205.897us)
Part 1: 12999999
Part 2: 12000001
Time: 352.076us (load:9.606us, part1:131.771us, part2:208.151us)
Part 1: 12999999
Part 2: 12000001

Breadth-first end-to-start

===[ aoc_2022_day12_large-1.txt ]==========
Time: 1.139.167us (load:8.939us, part1:558.012us, part2:525.917us)
Part 1: 2616490
Part 2: 2507471
Time: 1.177.797us (load:8.882us, part1:618.514us, part2:504.603us)
Part 1: 2616490
Part 2: 2507471
Time: 1.150.206us (load:8.274us, part1:568.276us, part2:529.995us)
Part 1: 2616490
Part 2: 2507471

===[ aoc_2022_day12_zigzag-small.txt ]==========
Time: 35.996us (load:3.726us, part1:16.632us, part2:14.042us)
Part 1: 1299999
Part 2: 1200001
Time: 32.271us (load:579us, part1:15.402us, part2:14.354us)
Part 1: 1299999
Part 2: 1200001
Time: 32.709us (load:588us, part1:15.645us, part2:14.509us)
Part 1: 1299999
Part 2: 1200001

===[ aoc_2022_day12_zigzag-large.txt ]==========
Time: 320.952us (load:5.373us, part1:156.222us, part2:139.690us)
Part 1: 12999999
Part 2: 12000001
Time: 297.476us (load:4.424us, part1:139.182us, part2:134.343us)
Part 1: 12999999
Part 2: 12000001
Time: 317.566us (load:4.950us, part1:152.573us, part2:140.804us)
Part 1: 12999999
Part 2: 12000001

Dan nog even A* met heuristic (start to end)

===[ aoc_2022_day12_large-1.txt ]==========
Time: 883.047us (load:24.840us, part1:379.287us, part2:474.912us)
Part 1: 2616490
Part 2: 2507471
Time: 874.004us (load:20.429us, part1:375.549us, part2:473.952us)
Part 1: 2616490
Part 2: 2507471
Time: 869.125us (load:19.050us, part1:372.695us, part2:473.374us)
Part 1: 2616490
Part 2: 2507471

===[ aoc_2022_day12_zigzag-small.txt ]==========
Time: 35.251us (load:1.113us, part1:13.577us, part2:20.323us)
Part 1: 1299999
Part 2: 1200001
Time: 33.855us (load:1.032us, part1:13.215us, part2:19.352us)
Part 1: 1299999
Part 2: 1200001
Time: 33.649us (load:922us, part1:13.391us, part2:19.135us)
Part 1: 1299999
Part 2: 1200001

===[ aoc_2022_day12_zigzag-large.txt ]==========
Time: 349.931us (load:9.389us, part1:132.433us, part2:205.829us)
Part 1: 12999999
Part 2: 12000001
Time: 349.869us (load:9.551us, part1:132.642us, part2:205.441us)
Part 1: 12999999
Part 2: 12000001
Time: 352.000us (load:10.005us, part1:134.064us, part2:205.283us)
Part 1: 12999999
Part 2: 12000001

[ Voor 17% gewijzigd door .oisyn op 12-12-2022 13:14 ]

[Dricus]

Dag 12 - Kotlin

Met de grote inputs van @Soultaker:

Part 1 (small): 65ms
Part 1 (large): 684ms
Part 2 (small): 135ms
Part 2 (large): 1522ms

Valt me niks tegen.

[Soultaker]

En nog een invoer: aoc_2022_day12_large-2.zip (11 MB ingepakt, 25 MB uitgepakt). Antwoorden modulo 97: 57, 53.

Bij deze zou A* aanzienlijk beter moeten performen dan BFS.

Overige invoer staat hier.

[ Voor 16% gewijzigd door Soultaker op 12-12-2022 13:18 ]

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 13:17:
En nog een invoer: aoc_2022_day12_large-2.zip (11 MB ingepakt, 25 MB uitgepakt). Antwoorden modulo 97: 57, 53.

Bij deze zou A* aanzienlijk beter moeten performen dan BFS.

Overige invoer staat hier.

A*

===[ aoc_2022_day12_large-2.txt ]==========
Time: 5.158.780us (load:19.706us, part1:317.672us, part2:4.818.774us)
Part 1: 5198
Part 2: 4432
Time: 5.006.886us (load:14.184us, part1:305.941us, part2:4.683.876us)
Part 1: 5198
Part 2: 4432
Time: 4.999.955us (load:14.360us, part1:306.110us, part2:4.676.888us)
Part 1: 5198
Part 2: 4432

BFS

===[ aoc_2022_day12_large-2.txt ]==========
Time: 1.783.883us (load:14.495us, part1:447.830us, part2:1.318.757us)
Part 1: 5198
Part 2: 4418
Time: 1.747.664us (load:15.319us, part1:431.931us, part2:1.297.848us)
Part 1: 5198
Part 2: 4418
Time: 1.733.628us (load:14.242us, part1:427.234us, part2:1.289.586us)
Part 1: 5198
Part 2: 4418

Wel voor part1.

.edit: end to start BFS er nog even bij

===[ aoc_2022_day12_large-2.txt ]==========
Time: 1.134.261us (load:5.181us, part1:562.808us, part2:531.497us)
Part 1: 5198
Part 2: 4418
Time: 1.125.123us (load:5.646us, part1:571.547us, part2:514.511us)
Part 1: 5198
Part 2: 4418
Time: 1.136.162us (load:5.666us, part1:562.114us, part2:534.962us)
Part 1: 5198
Part 2: 4418

.edit: hee wacht ik krijg verschillende antwoorden.
De A* is verkeerd zo te zien. Waarschijnlijk is mijn heuristics-functie niet helemaal juist

.edit2: gefixed, en je wordt er niet vrolijk van.

Time: 6.757.915us (load:14.439us, part1:432.501us, part2:6.308.347us)

A* for the lose.

[ Voor 19% gewijzigd door .oisyn op 12-12-2022 13:39 ]

[Dricus]

Dricus schreef op maandag 12 december 2022 @ 13:13:
Dag 12 - Kotlin

Met de grote inputs van @Soultaker:

Part 1 (small): 65ms
Part 1 (large): 684ms
Part 2 (small): 135ms
Part 2 (large): 1522ms

Valt me niks tegen.

Oh, woeps, dat klopte dus niet. Reden dat ze zo "snel" waren, was dat ik bij het parsen van de input geen rekening hield met een laatste newline . Dit zijn de échte cijfers:

Part 1 (small): 614ms
Part 1 (large): 5208ms
Part 2 (small): 673ms
Part 2 (large): 5610ms

[Janoz]

P_Tingen schreef op maandag 12 december 2022 @ 13:01:
Kan iemand mij even bijpraten over de 'snelle' manier van deel 2?
Ik heb het nu brute force opgelost maar dat kan beter

Ligt eigenlijk wel een beetje aan wat je gebruikt hebt voor deel 1 en hoe je deel 2 gebruteforced hebt.

[P_Tingen]

Janoz schreef op maandag 12 december 2022 @ 13:40:
[...]
Ligt eigenlijk wel een beetje aan wat je gebruikt hebt voor deel 1 en hoe je deel 2 gebruteforced hebt.

spoiler:

Voor deel 1 heb ik Dijkstra geïmplementeerd, vervolgens een functie gemaakt met 2 parameters: start en eind. Voor deel 2 loop ik 1 voor 1 door alle locaties met letter 'a': ik reset de afstanden en bereken dan het aantal stappen van dat punt naar het hoogste punt. Onderweg hou ik de kortste afstand bij.

Voor zover je de code kan lezen: https://github.com/patric...ter/2022/Day-12/day-12b.p

[ Voor 9% gewijzigd door P_Tingen op 12-12-2022 13:53 ]

[evanraalte]

Hm, ik zit een beetje vast. Het voorbeeld geeft de juiste output, maar voor mijn input set werkt geeft ie aan dat er geen pad beschikbaar is.. Ik sta wel open voor een hint als iemand het ziet


https://github.com/evanraalte/aoc2022/blob/main/day12.py

spoiler:

Ik genereer gewoon edges met een weight van 1 om vervolgens dijkstra toe te passen. S = 0 en E = 27, de rest zijn gewoon letters van het alfabet als index (startend vanaf 1). Zoveel zou er niet mis moeten kunnen gaan.

Vanavond nog maar even proberen en anders een andere dag weer.

[GladstoneW]

evanraalte schreef op maandag 12 december 2022 @ 13:57:
Hm, ik zit een beetje vast. Het voorbeeld geeft de juiste output, maar voor mijn input set werkt geeft ie aan dat er geen pad beschikbaar is.. Ik sta wel open voor een hint als iemand het ziet


https://github.com/evanraalte/aoc2022/blob/main/day12.py

spoiler:

Ik genereer gewoon edges met een weight van 1 om vervolgens dijkstra toe te passen. S = 0 en E = 27, de rest zijn gewoon letters van het alfabet als index (startend vanaf 1). Zoveel zou er niet mis moeten kunnen gaan.

Vanavond nog maar even proberen en anders een andere dag weer.

Ik zou de derde en vierde alinea van de opdracht nog even goed doorlezen.

spoiler:

[ Voor 5% gewijzigd door GladstoneW op 12-12-2022 14:17 ]

[CMG]

Soultaker schreef op maandag 12 december 2022 @ 11:23:
[...]

Hier is er alvast eentje:

Extra invoer voor dag 12:

• aoc_2022_day12_large-1.zip (13 MB ingepakt, 30 MB uitgepakt)
  Correcte antwoorden modulo 31337: 15519 en 511.
• aoc_2022_day12_zigzag.zip (1 MB uitgepakt, som van de antwoorden is een mooi rond getal).
• aoc_2022_day12_large-2.zip (11 MB ingepakt, 25 MB uitgepakt). Antwoorden modulo 97: 57, 53.

Oof, bijna 5 minuten 🤣

spoiler:

Part 1: 2616490 (% 31337: 15519
Part 2: 2507471 (% 31337: 511
Code runtime: 00:04:43.2451880

[corbosman]

Soultaker schreef op maandag 12 december 2022 @ 11:23:

• aoc_2022_day12_large-1.zip (13 MB ingepakt, 30 MB uitgepakt)
  Correcte antwoorden modulo 31337: 15519 en 511.

php in 20s en 40s voor die large1. Originele in 10ms voor beiden. Tja, het is geen C of Rust

[CMG]

Soultaker schreef op maandag 12 december 2022 @ 12:33:
Deze zijn ook leuk om te testen: aoc_2022_day12_zigzag.zip (som van de antwoorden is een mooi rond getal). Deze testset is gemaakt in vim

Overige invoer staat hier.

Deze wel (redelijk) snel

spoiler:

small
Part 1: 1299999 (% 31337: 15182
Part 2: 1200001 (% 31337: 9195
Code runtime: 00:00:01.0367465

large
Part 1: 12999999 (% 31337: 26481
Part 2: 12000001 (% 31337: 29267
Code runtime: 00:00:09.2312294

[Janoz]

P_Tingen schreef op maandag 12 december 2022 @ 13:52:
[...]

spoiler:

Voor deel 1 heb ik Dijkstra geïmplementeerd, vervolgens een functie gemaakt met 2 parameters: start en eind. Voor deel 2 loop ik 1 voor 1 door alle locaties met letter 'a': ik reset de afstanden en bereken dan het aantal stappen van dat punt naar het hoogste punt. Onderweg hou ik de kortste afstand bij.

Voor zover je de code kan lezen: https://github.com/patric...ter/2022/Day-12/day-12b.p

spoiler:

Ik denk dat in jouw geval het het makkelijkste is om alle a's als startpunt te nemen ipv alleen het startpunt. Ken het taaltje niet exact, maar ik denk dat je een heel eind komt door bij 'init' niet alleen piStart op todo te zetten, maar elke locatie met een 'a'. Om het conceptueel te begrijpen: wat je eigenlijk moet doen is vanuit een viruteel startpunt in 0 stappen naar elke 'a' en dan de korste route naar eind nemen

[evanraalte]

GladstoneW schreef op maandag 12 december 2022 @ 14:11:
[...]


Ik zou de derde en vierde alinea van de opdracht nog even goed doorlezen.

spoiler:

[Afbeelding]

Ik heb je spoiler niet gelezen, maar thanks, volgens mij snap ik wat er mis gaat!

spoiler:

Ik had de aaname gedaan dat je ook climbing gear nodig had om verder naar beneden te abseilen .

[MatHack]

P_Tingen schreef op maandag 12 december 2022 @ 13:52:
[...]

spoiler:

Voor deel 1 heb ik Dijkstra geïmplementeerd, vervolgens een functie gemaakt met 2 parameters: start en eind. Voor deel 2 loop ik 1 voor 1 door alle locaties met letter 'a': ik reset de afstanden en bereken dan het aantal stappen van dat punt naar het hoogste punt. Onderweg hou ik de kortste afstand bij.

Voor zover je de code kan lezen: https://github.com/patric...ter/2022/Day-12/day-12b.p

spoiler:

Conceptueel, zonder te weten of het in jouw oplossing makkelijk te implementeren is:
- Start bij E, vind de 'a' die de kortste route heeft met Dijkstra.
- Houd hierbij rekening dat je height restrictie dus ook is omgedraaid (dus ipv een verschil van 1 of lager is het nu een verschil van -1 of hoger), omdat je van eind naar begin gaat.

[Jern_97]

.oisyn schreef op maandag 12 december 2022 @ 11:47:
@Jern_97
Je gebruikt Rust, toch? Dan zou ik toch je code eens goed nakijken of er niet ergens een domme dure stap in zit

Jup, inderdaad. Had mijn edges gewoon in 1 grote array opgeslagen ipv geindexed per vertex, waardoor hij dus telkens alle edges moest aflopen .

Nu iets meer dan 2s voor de grote input.

[ Voor 17% gewijzigd door Jern_97 op 12-12-2022 16:07 ]

[TrailBlazer]

evanraalte schreef op maandag 12 december 2022 @ 13:57:
Hm, ik zit een beetje vast. Het voorbeeld geeft de juiste output, maar voor mijn input set werkt geeft ie aan dat er geen pad beschikbaar is.. Ik sta wel open voor een hint als iemand het ziet


https://github.com/evanraalte/aoc2022/blob/main/day12.py

spoiler:

Ik genereer gewoon edges met een weight van 1 om vervolgens dijkstra toe te passen. S = 0 en E = 27, de rest zijn gewoon letters van het alfabet als index (startend vanaf 1). Zoveel zou er niet mis moeten kunnen gaan.

Vanavond nog maar even proberen en anders een andere dag weer.

Je maakt volgens mij de fout die velen maakten.

spoiler:

Naar beneden mag met grotere stappen dan 1

[evanraalte]

TrailBlazer schreef op maandag 12 december 2022 @ 14:34:
[...]

Je maakt volgens mij de fout die velen maakten.

spoiler:

Naar beneden mag met grotere stappen dan 1

spoiler:

Jep, leren lezen Ondertussen A en B gefixt!

[corbosman]

Soultaker schreef op maandag 12 december 2022 @ 09:43:
[...]

Niet dat ik weet

Kan je wellicht echt de spoiler geven? Ik zie het echt niet. Zowel ik in php als vriend in rust (100% gegarandeerd geen overflows) krijgen 50,60 ipv 48,60.

Cor

[P_Tingen]

Janoz schreef op maandag 12 december 2022 @ 14:14:
[...]

spoiler:

Ik denk dat in jouw geval het het makkelijkste is om alle a's als startpunt te nemen ipv alleen het startpunt. Ken het taaltje niet exact, maar ik denk dat je een heel eind komt door bij 'init' niet alleen piStart op todo te zetten, maar elke locatie met een 'a'. Om het conceptueel te begrijpen: wat je eigenlijk moet doen is vanuit een viruteel startpunt in 0 stappen naar elke 'a' en dan de korste route naar eind nemen

Dank! Dat hielp inderdaad behoorlijk. Deel 2 is nu zelfs sneller dan deel 1 (363 vs 314 ms)
Aardig beter dan mijn brute-force die er 6 minuten over deed.

[Soultaker]

corbosman schreef op maandag 12 december 2022 @ 14:44:
Kan je wellicht echt de spoiler geven? Ik zie het echt niet. Zowel ik in php als vriend in rust (100% gegarandeerd geen overflows) krijgen 50,60 ipv 48,60.

Share je code eens? Ik vermoed dat je iets doet wat niet klopt.

[corbosman]

Soultaker schreef op maandag 12 december 2022 @ 14:56:
[...]

Share je code eens? Ik vermoed dat je iets doet wat niet klopt.

code

[Soultaker]

.oisyn schreef op maandag 12 december 2022 @ 13:22:
A* for the lose.

Ik behaal er bij deel 2 toch wel enige winst mee:

$ time ./solve bfs < aoc_2022_day12_large-2.txt 
8626088 points expanded
21498527 points expanded
5198
4418
Total time:    2,038,436 us
  Parsing:       372,933 us
  Solving 1:     482,455 us
  Solving 2:   1,183,046 us

$ ./solve astar < aoc_2022_day12_large-2.txt 
2107492 points expanded
8896482 points expanded
5198
4418
Total time:    1,146,795 us
  Parsing:       375,659 us
  Solving 1:     167,745 us
  Solving 2:     603,391 us

en m'n baseline qua solve tijden lijkt ook net iets lager te liggen dan bij jou (parsen heb ik nog niet aan gewerkt), dus het is niet alsof A* alleen sneller lijkt omdat m'n BFS traag zou zijn. Het verschil in tijd-per-punt valt ook erg mee: ~50 ns/punt voor BFS vs ~75 ns/punt voor A*.

[Soultaker]

corbosman schreef op maandag 12 december 2022 @ 14:59:
code

Je probleem zit hier.

Probeer deze input maar eens. Correct antwoord voor deel 1 is: 58 × 60 = 3480.

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 15:08:
[...]

Ik behaal er bij deel 2 toch wel enige winst mee:

$ time ./solve bfs < aoc_2022_day12_large-2.txt 
8626088 points expanded
21498527 points expanded
5198
4418
Total time:    2,038,436 us
  Parsing:       372,933 us
  Solving 1:     482,455 us
  Solving 2:   1,183,046 us

$ ./solve astar < aoc_2022_day12_large-2.txt 
2107492 points expanded
8896482 points expanded
5198
4418
Total time:    1,146,795 us
  Parsing:       375,659 us
  Solving 1:     167,745 us
  Solving 2:     603,391 us

en m'n baseline qua solve tijden lijkt ook net iets lager te liggen dan bij jou (parsen heb ik nog niet aan gewerkt), dus het is niet alsof A* alleen sneller lijkt omdat m'n BFS traag zou zijn. Het verschil in tijd-per-punt valt ook erg mee: ~50 ns/punt voor BFS vs ~75 ns/punt voor A*.

Vanavond maar eens profilen dan. Het is vast iets heel doms

.edit: ah. @Soultaker, wat betekent "n points expanded" in jouw output? Is dat zeg maar hoe vaak je een item uit de queue trekt?
Ik kom daar op 95.245.329, een factor 8,5x dat van jou voor part2 in large-2.txt.

En ik neem aan dat je heuristic iets is als: max(absDeltaX + absDeltaY, toHeight - fromHeight)?

.edit: zo hallo, anders geef ik echt compleet verkeerde data aan mijn heuristic functie (van oude naar adjacent cell, ipv van adjacent cell naar einde)

Visited 2149188 cells
Visited 9171396 cells
Time: 984.731us (load:14.304us, part1:122.298us, part2:845.388us)

Maar ik zie nog steeds dat ik sommige cells meerdere keren in de queue stop (dan vind ik een kortere weg naar dezelfde cell). Volgens mij zou dat nooit moeten gebeuren als je heuristic gegarandeerd niet over-estimate, toch?

[ Voor 27% gewijzigd door .oisyn op 12-12-2022 17:28 ]

[corbosman]

Soultaker schreef op maandag 12 december 2022 @ 15:28:
[...]

Je probleem zit hier.

Probeer deze input maar eens. Correct antwoord voor deel 1 is: 58 × 60 = 3480.

Ok, ik denk dat ik snap wat je bedoelt. Volgorde moet iets anders. Maar nu heb ik correcte puzzel antwoord, correcte 3480 output van je kleine bestand, maar large-2 deel 1 is nog steeds fout

spoiler:

2703011818

(31 ipv 48). deel 2 klopt wel, 60. Vaag.

[.oisyn]

Aarrgh GVD kut-VS. Waarom gooit hij de undo-geschiedenis weg na een merge?! @@%@%@ Al mijn changes weg.

[ Voor 11% gewijzigd door .oisyn op 12-12-2022 17:20 ]

[Soultaker]

.oisyn schreef op maandag 12 december 2022 @ 15:31:
@Soultaker, wat betekent "n points expanded" in jouw output? Is dat zeg maar hoe vaak je een item uit de queue trekt?

Ja, dat precies.

En ik neem aan dat je heuristic iets is als: max(absDeltaX + absDeltaY, toHeight - fromHeight)?

Ik gebruikte alleen de Manhattan distance (absDeltaX + absDeltaY).

Maar ik denk dat bij dit probleem tie-breaking veel uitmaakt. Ik heb twee implementaties, de ene bezoekt minder punten en de andere is sneller. Iets wat mij hielp om minder punten te bezoeken is dit:

spoiler:

De prioriteit is de som van de afstand tot een punt plus de geschatte afstand tot het doel, waarbij A* vereist dat die schatting optimistisch is (i.e., de werkelijk afstand niet óverschat). Als die som voor twee punten gelijk is, dan bezoek ik eerst het punt met de hogere afstand. Immers, de schatting is optimistisch, en de afgelegde afstand is realistisch.

Maar ik zie nog steeds dat ik sommige cells meerdere keren in de queue stop (dan vind ik een kortere weg naar dezelfde cell). Volgens mij zou dat nooit moeten gebeuren.

Dit kan met Dijkstra/A* juist wel.
Een voorbeeld:

E..
zz.
aaA
aza
aSa

Je moet via de hoofdletter A om van S naar E te gaan. Je A* algoritme zal geneigd zijn om heuristisch eerst naar links te zoeken (immers dan blijf je dichter bij E) terwijl rechtsom korter is. Het kan dan zijn dat je eerst vindt dat de afstand to A=5, en daarna pas de afstand tot A=3.

Vandaar dat de theoretische implementatie van Dijkstra ook een decrease-priority operatie gebruikt om de prioriteit van een element te verlagen. Een binary heap ondersteunt die operatie in principe, maar in de praktijk is het vaak simpeler/sneller om een element gewoon meerdere keren in de queue te gooien, mits je er voor zorgt dat je 'm maar één keer verwerkt.

[Soultaker]

corbosman schreef op maandag 12 december 2022 @ 16:34:
Ok, ik denk dat ik snap wat je bedoelt. Volgorde moet iets anders. Maar nu heb ik correcte puzzel antwoord, correcte 3480 output van je kleine bestand, maar large-2 deel 1 is nog steeds fout

spoiler:

2703011818

(31 ipv 48). deel 2 klopt wel, 60. Vaag.

Het is niet met één simpele operatie te fixen, ik wilde met m'n testset alleen het probleem demonstreren. Om het fundamentele probleem op te lossen moet je verder doordenken.

Het is niet zo gek dat je meer moeite hebt met deel 1 dan deel 2; het probleem zit 'm in de deling, die je bij deel 2 niet gebruikt. Zie ook mijn hints hier.

Als je er niet uitkomt, maak je geen zorgen: het is een behoorlijk ingewikkeld probleem en niemand anders heeft het tot nu toe op weten te lossen

[ Voor 5% gewijzigd door Soultaker op 12-12-2022 17:53 ]

[FrankMennink]

Dag 12 in Python

Veel langer dan me lief is bezig geweest met herinneren hoe ik ook alweer een

spoiler:

BFS

implementeer. Daarna nog een lange tijd aan het vloeken geweest tot ik alinea 3 opnieuw las. Daarna vloeide alles er binnen een paar minuten uit

spoiler:

Ik had start op -1 gezet en het eind op 26, in plaats van 0 en 25 resp. waardoor ik verkeerde antwoorden kreeg

[TrailBlazer]

FrankMennink schreef op maandag 12 december 2022 @ 18:03:
Dag 12 in Python

Veel langer dan me lief is bezig geweest met herinneren hoe ik ook alweer een

spoiler:

BFS

implementeer. Daarna nog een lange tijd aan het vloeken geweest tot ik alinea 3 opnieuw las. Daarna vloeide alles er binnen een paar minuten uit

spoiler:

Ik had start op -1 gezet en het eind op 26, in plaats van 0 en 25 resp. waardoor ik verkeerde antwoorden kreeg

spoiler:

De meeste mensen hadden niet gelezen dat je oneindig verder naar beneden mag. Daar ben je in ieder geval niet in getrapt.

[Creepy]

Ik heb nog geen oplossing, heb de boel even doorgelezen en verwacht ik ik met

spoiler:

Dijkstra

of desnoods

spoiler:

a * oid

aan de slag moet. Ik begin echt lui te worden, ben net begonnen, en ga alweer wat anders doen
Waarschijnlijk morgen wat meer tijd, dan dit alsnog doen..

[TrailBlazer]

Python-Dag 12
niks speciaals gedaan.

spoiler:

deel 2 opgelost door hem reverse te doen. Uit de tree van deel2 kan je ook deel1 halen dus de graph voor deel 1 er maar uitgehaald. De elven kunnen in mijn geval wel enorme einden omhoog springen maar slechts een naar benden.

[Cranzai]

Na vorig jaar voor het eerste het bekende algoritme tegen gekomen te zijn vandaag voor het eerst succesvol een eigen O(N2) implementatie geschreven (aan hand van een tutorial weliswaar maar aangepast voor een grid)

[.oisyn]

Soultaker schreef op maandag 12 december 2022 @ 17:49:
Maar ik denk dat bij dit probleem tie-breaking veel uitmaakt. Ik heb twee implementaties, de ene bezoekt minder punten en de andere is sneller.

Dit kan met Dijkstra/A* juist wel.

Ah right. Ik zat dan even specifiek te denken aan het geval van een grid met manhatten distance heuristic. Immers, voor elke stap die je zet komt er 1 bij, en gaat er hooguit 1 af vanwege de verminderde afstand. De prioriteitswaardes die je dus steeds uitrekent zijn monotoon toenemend.

Als ik even de getallen in je voorbeeld zet (dus afgelegde afstand + manhattan distance naar het einde):

E77
zz7
57A
5z7
5S7

Dan krijgt de A via de node links van hem een prioriteit van 9, terwijl hij via de rechterkant 7 blijft. Mijn redenatie was dus, A kan nooit eerder op een slechter pad worden afgehandeld.

Het probleem is echter dat de naastliggende cell op de verkeerde weg minimaal dezelfde prioriteit meekrijgt als die op de goede weg, en dus eerder kan zijn. En het is die cell die de distance van die A al invult en hem toevoegt aan de queue. Door de kortste paden eerst te doen in de prio-queue voorkom je dit probleem. Als ik dat implementeer gaat het aantal visited cells ook wel naar beneden (komst zelfs nog iets onder de jouwe), maar de tijd gaat daarentegen wel echt hard omhoog, van 850ms naar iets als 1.1s. Zelfs als ik de prioriteit slim encodeer in een enkele uint64.

Ik snap niet zo goed waarom het nou zo traag is. Pakweg 50% van de tijd zit ie in priority_queue::pop().

.edit: ok als ik de structure die in de prio queue zit 8 bytes maak ipv 16 bytes gaat ie naar 750ms. Verder heb ik gemeten dat er maximaal 172181 elementen in de queue staan op enig moment voor large2 part2. Dat is nou ook weer niet zo schrikbarend veel. Ik snap nog steeds niet hoe jij op die 600ms komt met je langzamere CPU

[ Voor 9% gewijzigd door .oisyn op 12-12-2022 23:32 ]

[Creepy]

Ok, wel lui, maar het jeukte me toch iets teveel. Dus dag 12 ook weer klaar.

spoiler:

BFS was genoeg, zoals anderen ook al opgemerkt hadden.

https://github.com/CodeEn...er/aoc/aoc2022/Day12.java

Bij de large input doet part 1 er bijna een seconde (0.95) over en part 2 net iets meer (1.3). Snel genoeg voor een eerste poging

Edit2: en als ik de JVM optimizer ook aan de slag laat gaan dan gaat er nog 3 tienden vanaf. 0.68 en 1.07 secs.

[ Voor 32% gewijzigd door Creepy op 12-12-2022 23:14 ]

[The Fox NL]

Creepy schreef op zondag 11 december 2022 @ 12:58:
Dag 11 ook weer af. Dat was wel ff nadenken voor deel 2

spoiler:

Eerst lopen rommelen met de modulo van de deler van de huidige monkey, maar dat werkte logischerwijs niet. Daarna nog even gedacht aan de deler van de monkey waar het naar toe moet. Duurde even voordat ik op de oplossing uitkwam om alle delers maar met elkaar te vermenigvuldigen en zo maar 1 getal te hebben voor de modulo.

Dat had ik op den duur ook uitgevogeld, maar toen was mijn oplossing nog niet goed.

spoiler:

Ik moest mijn teller voor het aantal controleerde items wijzigen van int naar long... Elke AdventOfCode editie trap ik er weer in.

[corbosman]

Soultaker schreef op maandag 12 december 2022 @ 17:52:

Het is niet zo gek dat je meer moeite hebt met deel 1 dan deel 2; het probleem zit 'm in de deling, die je bij deel 2 niet gebruikt. Zie ook mijn hints hier.

Als je er niet uitkomt, maak je geen zorgen: het is een behoorlijk ingewikkeld probleem en niemand anders heeft het tot nu toe op weten te lossen

Het is een lastige idd. Even een vraagje, Het is toch niet dat je 3 aan de LCM berekening moet toevoegen right? Want dat levert ook niet het goede antwoord op.

[.oisyn]

.oisyn schreef op maandag 12 december 2022 @ 22:59:
.edit: ok als ik de structure die in de prio queue zit 8 bytes maak ipv 16 bytes gaat ie naar 750ms. Verder heb ik gemeten dat er maximaal 172181 elementen in de queue staan op enig moment voor large2 part2. Dat is nou ook weer niet zo schrikbarend veel. Ik snap nog steeds niet hoe jij op die 600ms komt met je langzamere CPU

Weg met die std::priority_queue dan maar, en vervangen met een hash map van int naar vector. O(1) insertions en deletions. Aangezien die priorities toch monotoom toenemend zijn en enorm bij elkaar liggen, kan ik ze net zo goed direct indexeren. Large-2 part-2 nu in 220ms . Alleen jammer genoeg wel performance degradatie bij de andere inputs