Advent of Code 2023

[P_Tingen]

MatHack schreef op vrijdag 15 december 2023 @ 14:01:
[...]

spoiler:

@P_Tingen mijn set had ongeveer dezelfde orde van grootte qua cycle/positie. Maar ik zou inderdaad eerst eens met de testset proberen, daar liggen de cycle en positie allebei onder de 10.

Yes! Inmiddels inderdaad met de testset gevalideerd en 14-b in de pocket.

spoiler:

Het was even puzzelen hoe ik obv de patroonlengte en de huidige positie bij het eind kwam, maar door een dump te maken van de historie van de testset kon ik handmatig even pielen om de goede formule te krijgen. Daarna 4 1/2 minuut stampen en voila: het goede antwoord

https://github.com/patric...ter/2023/Day-14/day-14b.p

[joppybt]

P_Tingen schreef op vrijdag 15 december 2023 @ 15:12:
[...]

Yes! Inmiddels inderdaad met de testset gevalideerd en 14-b in de pocket.

spoiler:

Het was even puzzelen hoe ik obv de patroonlengte en de huidige positie bij het eind kwam, maar door een dump te maken van de historie van de testset kon ik handmatig even pielen om de goede formule te krijgen. Daarna 4 1/2 minuut stampen en voila: het goede antwoord

https://github.com/patric...ter/2023/Day-14/day-14b.p

Waarom is dit zo extreem traag?
Ik heb even je code bekeken en qua algoritme doe je niets vreemds. Ik heb zelf vergelijkbare code in JavaScript en zonder enige optimalisatie is deel b in rond 300ms klaar

Is Progress ABL echt zo inefficiënt? Ik begrijp dat het meer op databases gericht is maar dan nog snap ik niet waarom het zo traag is.

[Marcj]

Soultaker schreef op donderdag 14 december 2023 @ 18:42:
Hier nog twee challenges voor dag 14: aoc-2023-day-14-challenge-1-to-2.zip

Correcte antwoorden eindigen op: ...337 (deel 1), ...438 (deel 2) voor de eerste invoer, en ...288 (deel 1), ...651 (deel 2) voor de tweede invoer.

Zelfs m'n C++ oplossing doet hier 6 seconden respectievelijk 6 minuten over.

Ik had wel een idee geïmplementeerd om de complexiteit van O(HWN) (met H, W hoogte en breedte, en N aantal iteraties voordat er een cykel gedecteerd is) terug te brengen naar O(ON) (met O het aantal boulders in de invoer), maar dat bleek voor m'n Python code leek dat niet veel sneller te zijn (tenzij ik expres data sets met extreem weinig boulders genereer, wat een beetje flauw is). Ben benieuwd of iemand een manier weet om dit efficient op te lossen!

@.oisyn ik heb geprobeerd jouw solver te runnen, maar die lijkt een harde limiet van 128 x 128 te hebben, dus die moet sowieso geüpdate worden (weet niet of dat ingewikkeld is).

Leuk deze extra uitdagingen. Mijn recht-toe-recht-aan oplossing in Rust doet er 9 seconden danwel 6,5 minuut over. Op zich best prima dus. Ik denk dat alle memory swaps het traagste deel hiervan zijn, er is vast een betere memory layout hiervoor...

Ik heb wel een leuke oplossing voor een generieke cycle detectie die op een iterator werkt. Makkelijk te gebruiken zo

spoiler:

$ cat ~/Downloads/aoc-2023-day-14-challenge-1-to-2/aoc-2023-day-14-challenge-1.in | target/release/day14
Executing
├── Input parsed in 6,269µs
├── Part 1 calculated in 1,569µs: xxxx337
├── Part 2 calculated in 9,314,062µs: xxxx438
└── Total time: 9,321,962µs

$ cat ~/Downloads/aoc-2023-day-14-challenge-1-to-2/aoc-2023-day-14-challenge-2.in | ../target/release/day14
Executing
├── Input parsed in 3,520µs
├── Part 1 calculated in 3,263µs: xxxxx288
├── Part 2 calculated in 332,606,076µs: xxxxx651
└── Total time: 332,612,896µs

[ Voor 4% gewijzigd door Marcj op 15-12-2023 15:57 ]

[Soultaker]

Marcj schreef op vrijdag 15 december 2023 @ 15:56:
Mijn recht-toe-recht-aan oplossing in Rust doet er 9 seconden danwel 6,5 minuut over.

Heel netjes!

Ik heb wel een leuke oplossing voor een generieke cycle detectie die op een iterator werkt. Makkelijk te gebruiken zo

Er zijn ook cykeldetectiealgoritmen die zonder hashmap werken. In dit geval zou dat waarschijnlijk trager zijn. Soms is het juist sneller, en het kan ook handig zijn als je niet genoeg geheugen hebt om alle vorige toestanden te cachen.

[Marcj]

Soultaker schreef op vrijdag 15 december 2023 @ 19:00:
[...]

Heel netjes!


[...]

Er zijn ook cykeldetectiealgoritmen die zonder hashmap werken. In dit geval zou dat waarschijnlijk trager zijn. Soms is het juist sneller, en het kan ook handig zijn als je niet genoeg geheugen hebt om alle vorige toestanden te cachen.

Grappig genoeg gebruik ik hier als state de hash van de echte state. Die 64-bits waren nauwkeurig genoeg
Maar bedankt, dat algoritme kende ik nog niet!

[ Voor 4% gewijzigd door Marcj op 15-12-2023 19:23 ]

[Soultaker]

.oisyn schreef op donderdag 14 december 2023 @ 22:57:
Wat betreft @Soultaker's testsets, de eerste vindt hij in 2,17s, de tweede in 95,88s.
Heb 'm even gepushed naar een andere branch, day14-alt: https://github.com/oisyn/...y14-alt/day14/src/main.rs

Ik heb m'n Python oplossing geport naar C++ (code) en hij is toch net wat sneller dan jouw Rust code (ongeveer 50% sneller op de officiële testinvoer, en 15% à 25% op mijn eigen testinvoer).

Net zoals jij bereken ik van te voren voor elke positie in het grid wat de dichtstbijzijnde muur is in elk van de 4 richtingen. Maar de truc die ik gebruik is dat ik niet de posities van individuele rotsen bijhoud, maar alleen per muur het aantal rotsen dat aan elke kant ligt.

Bijvoorbeeld, als je alle boulders naar het noorden verplaatst, dan weet je dat alle rotsen nu ten zuiden van een muur (#) liggen (waarbij je de bovenkant van het grid ook als muur moet tellen). Je kunt de toestand dus karakteriseren als een set van (positie, aantal) paren, waarbij positie de positie naast de muur is, en aantal het aantal boulders. In mijn oplossing gebruik hou ik alleen de posities bij waarbij aantal > 0.

Het voordeel daarvan is dat elk paar van twee integers meerdere rotsen kan representeren. In theorie is je state daardoor kleiner. In de praktijk valt de winst tegen: het aantal muren waar rotsen aan grenzen is vaak ongeveer de helft van het aantal rotsen. Maar toch is het blijkbaar genoeg om een kleine winst mee te behalen.

[.oisyn]

Dat houd ik nu ook al bij.

.edit: hmm, mijn bus kwam eraan, blijkbaar op verzenden gedrukt

Wat ik wilde zeggen is dat ik de rotsen dus op zich wel weg kan doen, want alles volgt uit de state van de hekjes.

[ Voor 78% gewijzigd door .oisyn op 16-12-2023 11:54 ]

[P_Tingen]

joppybt schreef op vrijdag 15 december 2023 @ 15:40:
[...]

Waarom is dit zo extreem traag?
Ik heb even je code bekeken en qua algoritme doe je niets vreemds. Ik heb zelf vergelijkbare code in JavaScript en zonder enige optimalisatie is deel b in rond 300ms klaar

Is Progress ABL echt zo inefficiënt? Ik begrijp dat het meer op databases gericht is maar dan nog snap ik niet waarom het zo traag is.

Ja goeie vraag. Ik denk dat ik de indexen op mijn tabel goed heb. Ik had eerst meerdere (4 stuks) voor verschillende manieren van benaderen, maar de overhead van het bijwerken van die indexen was kennelijk groter dan de winst die het opleverde. Voor "normale" code is het geen issue omdat je in Progress eigenlijk nooit echt performance-dingen doet. Daar waar dat wel zo is, gaat het om databasetoegang en dat is prima in orde

[CrossProd]

Het was weer goed te doen vandaag zonder een slim algoritme. Ik had een lange sessie verwacht vandaag maar dat viel erg mee.

Dag 16 in Swift

spoiler:

De eerste minuut dacht ik het met recursie op te gaan lossen maar bedacht me al snel en gebruik nu een queue met items die de coördinaat en richting bevatten.

[ Voor 59% gewijzigd door CrossProd op 16-12-2023 06:53 ]

[FCA]

Inderdaad, conceptueel niet te moeilijk, maar wel wat implementatiewerk

spoiler:

nieuwe positie + en nieuwe richting op een stack gooien, op basis van de mirror op die positie en de richting van de inkomende beam.
Deel 1 had ik uiteraard een domme manier gedaan: om "loops" te omzeilen gewoon een counter bij te houden, en na 10^7 keer te stoppen. Was goed genoeg voor deel 1, maar ging uiteraard niet werken voor deel 2, dus voor deel 2 een extra set/hashmap aangemaakt waarin de al voorgekomen posities + richtingen werden bijgehouden.
Niet extreem snel, en een lekkere hoeveelheid geneste if-statements (had in ieder geval al wel de bounds-checking + al gedaan checking in een functie gezet), maar het werkt.

[Soultaker]

Dag 16:

spoiler:

Was eigenlijk een search-probleem. Ik heb simpelweg een lookup table gehardcode van (lichtrichting, karakter) → [lijst van nieuwe richtingen]; dat was sneller/makkeliiker dan de daadwerkelijke reflectie implementeren.

Vervolgens kun je een depth-first search (of breadth-first search) doen om alle triples (rij, kolom,
lichtrichting) te vinden, waarbij het voor het antwoord alleen de (rij, kolom) paren telt.

Voor deel 2 heb ik simpelweg hetzelfde algoritme gerunt vanaf elke mogelijk beginpositie. Niet heel efficient (~850 ms met pypy) maar ik kan ook niet zo snel wat beters bedenken.

Python code.

[MatHack]

Relatief simpel inderdaad, nadat...

spoiler:

Ik in het voorbeeld doorhad dat de eerste spiegel al meteen duidelijk maakt dat loops mogelijk zijn.

Voor mijn gevoel kan het nog efficiënter (deel2 is nu ~500ms), maar ik vind het voor nu prima. https://github.com/realma...de.Y2023/Solvers/Day16.cs

PS. Vind het toch altijd leuk/mooi hoe de kalendar langzaam veranderd naarmate je puzels oplost, mooi lava effect vandaag.

[mbe81]

Vandaag was het inderdaad weer goed te doen! Wel een aardige lijst van switch- en if-statements maar deel 2 runt in ca. 30 ms (Go). Dit weekend mijn achterstand inhalen (dag 14 en dag 12 deel 2).

https://github.com/mbe81/advent-of-code/tree/main/2023/day16

[RefleXion]

mbe81 schreef op zaterdag 16 december 2023 @ 08:01:
Vandaag was het inderdaad weer goed te doen! Wel een aardige lijst van switch- en if-statements maar deel 2 runt in ca. 30 ms (Go). Dit weekend mijn achterstand inhalen (dag 14 en dag 12 deel 2).

https://github.com/mbe81/advent-of-code/tree/main/2023/day16

Ik heb de if-statements op de volgende manier omzeild:

spoiler:

DIRECTION_TRANSFORM = { "." : { (1,0 ) : [(1,0 )],
(-1,0) : [(-1,0)],
(0,1 ) : [(0,1 )],
(0,-1) : [(0,-1)]},
"/" : { (1,0 ) : [(0,-1)],
(-1,0) : [(0,1 )],
(0,1 ) : [(-1,0)],
(0,-1) : [(1,0 )]},
"\\": { (1,0 ) : [(0,1 )],
(-1,0) : [(0,-1)],
(0,1 ) : [(1,0 )],
(0,-1) : [(-1,0)]},
"|": { (1,0 ) : [(0,1),(0,-1)],
(-1,0) : [(0,1),(0,-1)],
(0,1 ) : [(0,1 )],
(0,-1) : [(0,-1)]},
"-": { (1,0 ) : [(1 ,0)],
(-1,0) : [(-1,0)],
(0,1 ) : [(1,0),(-1,0)],
(0,-1) : [(1,0),(-1,0)] } }

Dan kun je de waarde uit het veld en de huidige richting invullen en krijg je list met nieuwe richtingen terug.

Daarnaast ook hashmap gebruikt om de combinaties van locatie en richting die al gepasseerd zijn niet opnieuw te volgen.

[ Voor 3% gewijzigd door RefleXion op 16-12-2023 11:28 ]

[MadEgg]

Vandaag weer eens op tijd erbij. Niet zo lastig vandaag. Zo op het eerste gezicht aardig dezelfde aanpak als de andere code die ik hier voorbij zie komen. Vraag me af of er nog veel slimmigheidjes toe zijn te passen.

spoiler:

Het meeste moeite had ik om de beam tracing goed te krijgen, steeds de verkeerde kant op omdat ik steeds bronrichting en doelrichtng in mijn hoofd door elkaar haalde toen ik de logica erin zette. Maar toen de voorbeeldset goed ging, ging de rest ook gelijk goed.

Deel 2 was vrij makkelijk aangezien ik er voor deel 1 al was uitgegaan dat de invalspositie niet vast zou zijn. Alleen de mogelijke startposities even enumereren en gaan een maxBy erop.

Dag 16 - Kotlin

[ Voor 11% gewijzigd door MadEgg op 16-12-2023 11:28 ]

[Diderikdm]

Python dag 16

Niet de meest efficiënte code (~6s), wel snel klaar. Kijk er misschien later nog naar.

spoiler:

Vermoed dat er nog wel winst te halen is uit het vinden van subroutines, bijhouden van steps tot een bepaald punt icm energizement gaf me nog niet de resultaten die ik wilde, maar doe vgm nog wat verkeerd

[arnold_m]

De 'Hot Springs' van dinsdag (dag 12) heb ik pas gisteravond af kunnen maken. Om de fouten uit mijn efficiënte, maar complexe oplossing te halen, heb ik een tweede oplosfunctie geschreven die domweg de mogelijke verdeling telt. Daarmee kon ik de randgevallen waarin het mis ging identificeren en debuggen.

De eenvoudige aanpak bleek voor het eerste deel sneller, maar voor deel twee won de complexe aanpak.
Met 12,5 seconde in Rust voor de gehele opgave ben ik tevreden.

Vanaf woensdag tot en met vandaag vind ik de opgaven een stuk eenvoudiger.

[FrankMennink]

Day 16 in Python

Leuke puzzel vandaag. Redelijk 1 op 1 gecodeerd wat er in de puzzel staat. Draaide in ~1,6s, nog een kleine verbetering gemaakt en nu draait het in ~1s

spoiler:

Als een lichtstraal out of bounds gaat, hoef je het exit-point niet te checken als input, want de energy value is hetzelfde als die van het zojuist gecheckte entry point. deze lijst geef ik terug samen met de energy value en haal ik van de points to check af. Ik ging van 440 checks naar 274 checks, scheelt toch weer runtime

[Soultaker]

FrankMennink schreef op zaterdag 16 december 2023 @ 16:08:

spoiler:

Als een lichtstraal out of bounds gaat, hoef je het exit-point niet te checken als input, want de energy value is hetzelfde als die van het zojuist gecheckte entry point.

Dat is niet 100% correct.

spoiler:

De uitgang heeft een waarde die kleiner dan of gelijk is aan de waarde die je net gevonden hebt; het is niet per se gelijk. Simpel voorbeeld: ".|" als je uiterst links begint bezoek je 2 punten, en eindigt de straal rechts boven/onder. Maar als je boven/onder begint bezoek je maar 1 punt. De conclusie gaat nog wel op: de uitgang hoef je niet meer als ingang te beschouwen.

[FrankMennink]

Soultaker schreef op zaterdag 16 december 2023 @ 17:04:
[...]

Dat is niet 100% correct.

spoiler:

De uitgang heeft een waarde die kleiner dan of gelijk is aan de waarde die je net gevonden hebt; het is niet per se gelijk. Simpel voorbeeld: ".|" als je uiterst links begint bezoek je 2 punten, en eindigt de straal rechts boven/onder. Maar als je boven/onder begint bezoek je maar 1 punt. De conclusie gaat nog wel op: de uitgang hoef je niet meer als ingang te beschouwen.

Daar had ik inderdaad niet aan gedacht, thanks

[Varienaja]

Dag 16 in Java.

Ik had niet van direkt rekening gehouden met lichtstralen die eeuwig rondjes blijven draaien. Maar het was wél een vrolijk gezicht die wild razende lichtstralen in mijn debugscherm te zien bewegen.

[Friits]

Eerlijk gezegd had vandaag wel iets moeilijkers verwacht, vooral deel 2. Maar goed, het was weer een leuke puzzel!

Python, met complexe getallen voor de huidige positie en richting.

[ Voor 4% gewijzigd door Friits op 16-12-2023 19:10 ]

[Soultaker]

Friits schreef op zaterdag 16 december 2023 @ 19:09:
Python, met complexe getallen voor de huidige positie en richting.

Hoe verzin je het, met complexe getallen

spoiler:

Wel interessante observatie dat je bij een splitter onvoorwaardelijk beide kanten op kunt gaan. Dat is niet triviaal en had ik me nog niet geraliseerd. Het is vergelijkbaar met de logica die @FrankMennink hierboven noemde: als je de richting van de laser omkeert, bezoek je een subset van de tegels die je al bezocht had.

[Soultaker]

Fuuu... vandaag eindeloos zitten pielen voor ik door had dat

spoiler:

je niet mag omkeren, alleen een kwartslag naar links of rechts draaien! Achteraf staat het duidelijk in de opgave, maar het is een detail dat je makkelijk over het hoofd kunt zien.

Goed, heb ik wel mooie code geschreven om het optimale pad te reconstrueren en de oplossing te visualiseren.

Deel 2 was natuurlijk een eitje.

[ Voor 30% gewijzigd door Soultaker op 17-12-2023 07:08 ]

[MatHack]

Als je eenmaal deel 1 hebt, dan is (gelukkig) deel 2 inderdaad relatief simpel.

spoiler:

Eerst een tijd met A*/Dijkstra lopen klieren, maar dat ging uiteindelijk toch niet lekker. Als ik het goed heb komt dat door de restrictie van aantal moves, waardoor je eigenlijk een dynamische graaf hebt.

Kwam er wel achter dat mijn oplossing niet werkt voor de tweede testset (die met alleen 9 & 1), maar voor de eerste testset en de echte set werkte deze gelukkig wel.
Komt omdat de paden overlappen in de onderste rij en het pad vanaf start recht naar beneden een lagere heat heeft en deze eerst gezien wordt (en vervolgens in de visited hashset wordt geduwd).
'k heb geen zin om daar een oplossing voor te bedenken, aangezien de andere twee sets wel werken.

https://github.com/realma...de.Y2023/Solvers/Day17.cs

[ Voor 0% gewijzigd door MatHack op 17-12-2023 09:35 . Reden: foutieve opmerking doorstreept ]

[FCA]

Daar ging m'n zondagochtend...
Poog de nummer 2 op de private leaderboard van m'n werk in te halen (liep 7 punten achter), dus dat is weekendbikkelen nu

spoiler:

Vandaag veel te lang over deel 1 gedaan: ik had een simpele Dijkstra geimplementeerd, op een grid waarbij ik een extra "richting" dimensie had geplakt en dan de input + 1,2,3 * de nieuwe richting in de queue gooien.
Alleen deed ik de checking of het wel zin had om verder te gaan niet goed (i.e. de "node visited"): ik checkte op cur_distance <= best_distance_so_far[point, dir], i.p.v. cur_distance < best_distance_so_far[point,dir], waardoor bij de echte uitvoer mijn programma veels-te-veel begon te checken (na een minuut of 2 maar gekilld). De test output draaide wel snel (en correct), dus heel veel lopen graven naar de bug, veel extra test-cases gemaakt, uiteindelijk het issue gevonden.
Uiteindelijk bleek de "bug" bij deel 1 maar een factor 2 in de hoeveelheid rekentijd te schelen, terwijl het bij deel 2 tenminste een factor 100 scheelt.

Deel 2 was een eitje, had alles al ervoor geimplementeerd, gewoon de start en stop condities aanpassen.

[Soultaker]

MatHack schreef op zondag 17 december 2023 @ 08:39:

spoiler:

Eerst een tijd met A*/Dijkstra lopen klieren, maar dat ging uiteindelijk toch niet lekker. Als ik het goed heb komt dat door de restrictie van aantal moves, waardoor je eigenlijk een dynamische graaf hebt.

spoiler:

Het is inderdaad als een graafprobleem te modelleren en dan met Dijkstra's algoritme op te lossen.

Er zijn twee verschillende representaties mogelijk. In de eerste, die ik oorspronkelijk had gekozen, correspondeert een vertex met een tupel (rij, kolom, richting, aantal) waarbij richting de laatstgenomen richting is en aantal het aantal stappen dat je in die richting hebt gezet. Voor elke state heb je dan twee soorten edges: je kunt ofwel in dezelfde richting doorgaan als het aantal dat toestaat, waarbij aantal verhoogd wordt (bijvoorbeeld: (0, 0, oost, 1) -> (0, 1, oost, 2)), of je kunt in een andere richting doorgaan waarbij aantal reset naar 1 (bijvoorbeeld: (0, 1, oost, 2) -> (1, 1, zuid, 1)).

Op die manier heb je ongeveer H×W×4×3 vertices (voor deel 1) of H×W×4×10 vertices (voor deel 2) en max. 3 edges per vertex (want je kunt hooguit vooruit, linksaf, of rechtsaf).

Python code (~4 seconde)

Een efficiëntere variant die ik pas later bedacht had is om de vertices te representeren als (rij, kolom, vorige richting), waarbij je elke keer van richting verandert. Voor iedere vertex heb je dan aparte edges voor 1, 2, of 3 stappen vooruit (bijvoorbeeld: (10, 10, oost) → (11, 10, zuid), (12, 10 zuid), (13, 10, zuid), (9, 10, noord), (8, 10, noord), (7, 10, noord)). Bij deel 2 mag je dan ipv 1 t/m 3 stappen, 4 t/m 10 stappen vooruit.

(Ik zie dat @FCA deze variant gebruikt heeft).

Dat is een efficiëntere graaf omdat het aantal vertices kleiner is (H×W×4), en hoewel het aantal edges per vertex gemiddeld hoger is (max. 4 voor deel 1, max. 14 voor deel 2) is het totaal aantal edges kleiner.

Het helpt hierbij dat in het laatste voorbeeld van deel 2 expliciet wordt gezegd dat je het doel niet in minder dan 4 stappen mag bereiken. Zonder die restrictie zou deze oplossing wat extra werk op het einde nodig hebben.

Python code (~1,4 seconde)

(In beide versies heeft de startpositie nog wat speciale aandacht nodig, omdat er geen vorige richting is.)

[MatHack]

Soultaker schreef op zondag 17 december 2023 @ 09:07:
[...]

spoiler:

Het is inderdaad als een graafprobleem te modelleren en dan met Dijkstra's algoritme op te lossen.

Er zijn twee verschillende representaties mogelijk. In de eerste, die ik oorspronkelijk had gekozen, correspondeert een vertex met een tupel (rij, kolom, richting, aantal) waarbij richting de laatstgenomen richting is en aantal het aantal stappen dat je in die richting hebt gezet. Voor elke state heb je dan twee soorten edges: je kunt ofwel in dezelfde richting doorgaan als het aantal dat toestaat, waarbij aantal verhoogd wordt (bijvoorbeeld: (0, 0, oost, 1) -> (0, 1, oost, 2)), of je kunt in een andere richting doorgaan waarbij aantal reset naar 1 (bijvoorbeeld: (0, 1, oost, 2) -> (1, 1, zuid, 1)).

Op die manier heb je ongeveer H×W×4×3 vertices (voor deel 1) of H×W×4×10 vertices (voor deel 2) en max. 3 edges per vertex (want je kunt hooguit vooruit, linksaf, of rechtsaf).

Python code (~4 seconde)

Een efficiëntere variant die ik pas later bedacht had is om de vertices te representeren als (rij, kolom, vorige richting), waarbij je elke keer van richting verandert. Voor iedere vertex heb je dan aparte edges voor 1, 2, of 3 stappen vooruit (bijvoorbeeld: (10, 10, oost) → (10, 11, zuid), (10, 12, zuid), (10, 13, zuid), (10, 9, noord), (10, 8, noord), (10, 7, noord)). Bij deel 2 mag je dan ipv 1 t/m 3 stappen, 4 t/m 10 stappen vooruit.

(Ik zie dat @FCA deze variant gebruikt heeft).

Dat is een efficiëntere graaf omdat het aantal vertices kleiner is (H×W×4), en hoewel het aantal edges per vertex gemiddeld hoger is (max. 4 voor deel 1, max. 14 voor deel 2) is het totaal aantal edges kleiner.

Het helpt hierbij dat in het laatste voorbeeld van deel 2 expliciet wordt gezegd dat je het doel niet in minder dan 4 stappen mag bereiken. Zonder die restrictie zou deze oplossing wat extra werk op het einde nodig hebben.

Python code (~1,4 seconde)

(In beide versies heeft de startpositie nog wat speciale aandacht nodig, omdat er geen vorige richting is.)

spoiler:

Voor mijn originele poging van A*/Dijkstra had ik alleen de coordinaten gebruikt als state, en dus niet richting + aantal stappen in die richting daar nog bovenop. Als afstand gebruikte ik de heat van de neighbor en ik beperkte de neighbors door met backtracking te bepalen of ik al 3x in de richting was gegaan. Backtracking via de parents-lookup die je ook gebruikt voor het bouwen van het pad, waarschijnlijk ook niet de beste keuze, aangezien deze ook nog kan wijzigen . Voor mijn huidige oplossing kwam ik er dan ook achter dat ik richting + aantal stappen ook nodig had als key voor een seen/visited hashset.

Nu jij dit zo uitlegt en met de kennis die ik ondertussen met mijn andere oplossing heb opgedaan zou Dijkstra inderdaad wel kunnen. Soms zit je gewoon te vast geroest in een oplossingsrichting (zoals alleen maar coordinaten gebruiken in een search-algoritme). Bedankt voor de uitleg!

Nu maar weer verder met puzzels van voorgaande jaren

[mvdnes]

Soultaker schreef op zondag 17 december 2023 @ 09:07:
[...]

spoiler:

Het is inderdaad als een graafprobleem te modelleren en dan met Dijkstra's algoritme op te lossen.

Er zijn twee verschillende representaties mogelijk. In de eerste, die ik oorspronkelijk had gekozen, correspondeert een vertex met een tupel (rij, kolom, richting, aantal) waarbij richting de laatstgenomen richting is en aantal het aantal stappen dat je in die richting hebt gezet. Voor elke state heb je dan twee soorten edges: je kunt ofwel in dezelfde richting doorgaan als het aantal dat toestaat, waarbij aantal verhoogd wordt (bijvoorbeeld: (0, 0, oost, 1) -> (0, 1, oost, 2)), of je kunt in een andere richting doorgaan waarbij aantal reset naar 1 (bijvoorbeeld: (0, 1, oost, 2) -> (1, 1, zuid, 1)).

Op die manier heb je ongeveer H×W×4×3 vertices (voor deel 1) of H×W×4×10 vertices (voor deel 2) en max. 3 edges per vertex (want je kunt hooguit vooruit, linksaf, of rechtsaf).

Python code (~4 seconde)

Een efficiëntere variant die ik pas later bedacht had is om de vertices te representeren als (rij, kolom, vorige richting), waarbij je elke keer van richting verandert. Voor iedere vertex heb je dan aparte edges voor 1, 2, of 3 stappen vooruit (bijvoorbeeld: (10, 10, oost) → (10, 11, zuid), (10, 12, zuid), (10, 13, zuid), (10, 9, noord), (10, 8, noord), (10, 7, noord)). Bij deel 2 mag je dan ipv 1 t/m 3 stappen, 4 t/m 10 stappen vooruit.

(Ik zie dat @FCA deze variant gebruikt heeft).

Dat is een efficiëntere graaf omdat het aantal vertices kleiner is (H×W×4), en hoewel het aantal edges per vertex gemiddeld hoger is (max. 4 voor deel 1, max. 14 voor deel 2) is het totaal aantal edges kleiner.

Het helpt hierbij dat in het laatste voorbeeld van deel 2 expliciet wordt gezegd dat je het doel niet in minder dan 4 stappen mag bereiken. Zonder die restrictie zou deze oplossing wat extra werk op het einde nodig hebben.

Python code (~1,4 seconde)

(In beide versies heeft de startpositie nog wat speciale aandacht nodig, omdat er geen vorige richting is.)

Ah bedankt voor de tip. Hiermee kon ik het een stuk sneller maken!

spoiler:

Het kan zelfs in HxWx2, want je hoeft alleen bij te houden of je van links/rechts komt of van boven/onder.

[Soultaker]

mvdnes schreef op zondag 17 december 2023 @ 10:35:

spoiler:

Het kan zelfs in HxWx2, want je hoeft alleen bij te houden of je van links/rechts komt of van boven/onder.

Slim bedacht! Deze optimalisatie heb ik van je gejat; scheelt toch weer de helft van de oplossingstijd (ik kom nu op ~700 ms in Python).

[MueR]

spoiler:

Vandaag was (zeker nadat er gisteren al even wat pathfinding voorbij kwam) goed te doen. Deel 1 in ~180ms, deel 5 in 525ms) in Go.

[Remcoder]

Remcoder schreef op donderdag 14 december 2023 @ 09:15:

spoiler:

En jaaaa, daar is de cycle detectie weer

Ik had alleen een off by one erin zitten waar ik lang naar aan het zoeken was

Ik verwacht trouwens dat we dit weekend pathfinding gaan krijgen.

En zoals verwacht, vandaag inderdaad pathfinding

spoiler:

Het duurde wel even tot ik doorhad hoe ik goed kon onderscheiden welke nodes ik al bezocht had.

Uiteindelijk zoals iedereen hier gezien dat locatie + richting + lengte de onderscheidende factor is.

Daarna nog bij deel 2 tegen een bug aangelopen die blijkbaar ook in mijn deel 1 code zat waardoor dat wat langer duurde, maar daarna werkte alles.

Wel nog een relatief lange runtime, bijna 5 seconden voor deel 2.

[Corniel]

Ik lees hier dat mensen dag 14 in de secondes lopen? Huh? Deel 1 is bij mij orde 100 us, en deel 2 100 ms.

Vandaag (dag 17) lang zitten k#tten doordat ik dácht dat ik de eindconditie (deel twee) voor het bereiken van het target geod had gedaan (dus niet), en dat mijn implementatie voor de voorbeelden (uiteraard?!) werkte.

[MatHack]

Corniel schreef op zondag 17 december 2023 @ 12:31:
Ik lees hier dat mensen dag 14 in de secondes lopen? Huh? Deel 1 is bij mij orde 100 us, en deel 2 100 ms.

Vandaag (dag 17) lang zitten k#tten doordat ik dácht dat ik de eindconditie (deel twee) voor het bereiken van het target geod had gedaan (dus niet), en dat mijn implementatie voor de voorbeelden (uiteraard?!) werkte.

Ik vermoed dat voor de mensen die voor dag 14 secondes noemen dit niet gaat over de AoC invoer, maar de invoer die door @Soultaker is gegenereerd

[Diderikdm]

Python dag 17

Prima dagje vandaag! Runt in ~4.5s

spoiler:

kan daar wsl wel wat van af halen door bij part 2 direct 4 stappen door te skippen ivm de restrictie, nu geen zin in..

[Corniel]

MatHack schreef op zondag 17 december 2023 @ 13:17:

Ik vermoed dat voor de mensen die voor dag 14 secondes noemen dit niet gaat over de AoC invoer, maar de invoer die door @Soultaker is gegenereerd

Ik vond het al zo vaag. Ik zal de volgende keer beter lezen.

[Varienaja]

Dag 17 in Java.

Een dag om moedeloos van te worden. Deel 1, voorbeeld ging goed. Voor de echte invoer duurde hel veel te lang. Uiteindelijk @Soultaker 's oplossing nagebouwd en het antwoord in eindige tijd gekregen. Maar het duurt nog steeds meer dan een minuut. Wat ik zie, is dat mijn queue aan mogelijke wegen groeit totaan zowat 600.000 items, terwijl het Python-equivalent niet verder komt dan ongeveer 6000 States in 'todo'.

Opgelost.

[ Voor 4% gewijzigd door Varienaja op 17-12-2023 16:05 ]

[Corniel]

@Varienaja Wilde ik net een suggestie aan de hand doen.

Bij mij stonderen er (net even gekeken) trouwens ca 1000 (deel 1) en 1600 (deel 2) in de queue als ik mijn oplossing terugstuur.

[FrankMennink]

Day 17 in Python

Redelijk lang aan gezeten, paar keer helemaal moeten herschrijven omdat het niet lekker werkte. Uiteindelijk op een vrij vergelijkbare uitkomst gekomen als Soultaker, alleen deed mn code er ~2 seconden over.

spoiler:

Als eerste Dijkstra geimplementeerd en daarna de 3 lengte geprobeerd er in te verwerken, dat ging niet heel lekker. Uiteindelijke oplossing had ik eerst met een deque geimplementeerd. Daarna gezien dat mensen met een heapq werkte. Die geimplementeerd en dat scheelt een slok op n borrel. 170/350 ms voor deel 1 en 2 resp.

[ Voor 12% gewijzigd door FrankMennink op 17-12-2023 21:32 ]

[.oisyn]

Soultaker schreef op zaterdag 16 december 2023 @ 07:06:
Dag 16:

spoiler:

Voor deel 2 heb ik simpelweg hetzelfde algoritme gerunt vanaf elke mogelijk beginpositie. Niet heel efficient (~850 ms met pypy) maar ik kan ook niet zo snel wat beters bedenken.

Python code.

spoiler:

Ik had ook even geen zin in een beter algo, dus ik doe hetzelfde. 39ms in Rust.

Wat ik wel had bedacht is dat paden vanaf splitters altijd gelijk zijn, dus voor alle startposities zou je die data kunnen delen. Je komt alleen niet weg met alleen pad-lengte, want in het overige pad kruis je mogelijk dezelfde tiles.

[Diderikdm]

.oisyn schreef op zondag 17 december 2023 @ 21:41:
[...]

spoiler:

Ik had ook even geen zin in een beter algo, dus ik doe hetzelfde. 39ms in Rust.

Wat ik wel had bedacht is dat paden vanaf splitters altijd gelijk zijn, dus voor alle startposities zou je die data kunnen delen. Je komt alleen niet weg met alleen pad-lengte, want in het overige pad kruis je mogelijk dezelfde tiles.

spoiler:

wat je nog zou kunnen doen, is per loop bijhouden wat de coords en richting is, deze in een collection stoppen en elke keer wanneer je een punt uit deze collectie (incl direction) tegen komt, de run vanaf deze coord stoppen en += loopgrootte/set(coords), zou wsl een hoop schelen.

[Bolukan]

Hi allemaal. Afgelopen twee dagen even de achterstand weggewerkt en 34 antwoorden ingeleverd. Morgen doe ik gewoon met iedereen mee volgens schema.

spoiler: dag 17

Ik heb dubbele vertices gemaakt (horizontaal of verticaal bewogen) en 1 tot 3 lange vertices of 4 tot 10 vertices gebruikt. De heatmap is ook dubbel uitgevoerd en rechtsonder pak ik de laagste.

Sinds paar weken ben ik python gaan gebruiken, ik had het als lastig dialect met dat inspringen als scripting taal genegeerd. Ik programmeer alleen voor de hobby en dat gaat in C voor MCU's. Nu had ik het nodig om radio signalen (SDR) te verwerken. Ik moet zeggen mijn mening over Python is helemaal bijgedraaid.

[.oisyn]

Day16 in Rust
Time spent: 38705.2µs

Day17 in Rust
Time spent: 10530.2µs

[P_Tingen]

Bolukan schreef op zondag 17 december 2023 @ 23:26:
Hi allemaal. Afgelopen twee dagen even de achterstand weggewerkt en 34 antwoorden ingeleverd. Morgen doe ik gewoon met iedereen mee volgens schema.

spoiler: dag 17

Ik heb dubbele vertices gemaakt (horizontaal of verticaal bewogen) en 1 tot 3 lange vertices of 4 tot 10 vertices gebruikt. De heatmap is ook dubbel uitgevoerd en rechtsonder pak ik de laagste.

Sinds paar weken ben ik python gaan gebruiken, ik had het als lastig dialect met dat inspringen als scripting taal genegeerd. Ik programmeer alleen voor de hobby en dat gaat in C voor MCU's. Nu had ik het nodig om radio signalen (SDR) te verwerken. Ik moet zeggen mijn mening over Python is helemaal bijgedraaid.

Knap werk als je in twee dagen tijd alle achterstand hebt ingelopen! Ik zit veel te vaak veel te lang vast op een schijnbaar triviaal onderdeeltje om 17 dagen in twee dagen in te lopen

[bakkerjangert]

Gisteren vond ik al lastig al is het gelukt (runt wel in 30 minuten ofzo, maar heb gelukkig wel het juiste antwoord). Deel 2 van vandaag is ook pittig en ben ik nog niet uit.

spoiler:

Deel 1 heb ik opgelost met een shoe-lace berekening, wat verrassend goed werkt als je bedenkt waar de buitenzijde van de figuur loopt. Voor deel 2 heb je echter veel intersecties en dus overlappende delen, nu op zoek naar algoritme om een buitenomtrek te vinden ... Niet dus, dank @Soultaker. Na die bug verholpen te hebben is deel 2 ook gewoon met shoe-lace op te lossen.

[ Voor 9% gewijzigd door bakkerjangert op 18-12-2023 09:41 ]

[MatHack]

Hmm... deel 1 was goed te doen, maar deel 2... Later vandaag nog maar eens over nadenken.

spoiler:

Voor deel 1 gewoon de naïeve oplossing gebouwd en daadwerkelijk de boel uitgewerkt met een bool grid (kleuren boeide toch niet), en vervolgens met flood fill de binnenkant vullen. Werkt binnen 50ms, maar dat gaat gezien de getallen voor deel 2 niet werken. Zal wel iets met een som van oppervlaktes moeten zijn of zo...

[ Voor 18% gewijzigd door MatHack op 18-12-2023 08:49 ]

[Friits]

Leuke puzzel vandaag! Mijn oplossing in Python

spoiler:

Dankzij dag 10 was deze wel erg eenvoudig.

[Soultaker]

Voor mij was vandaag ook niet eenvoudig. Ik heb er 40 minuten over gedaan en relatief veel code moeten schrijven: 18.py. Ik ben dan ook benieuwd of er anderen slimmere/eenvoudigere algoritmes geïmplementeerd hebben.

Voor mensen die nog vast zitten, hier een hint voor deel 1 (geen volledige spoiler):

spoiler:

Kijk nog eens goed naar deel 2 van dag 10.

En een voor deel 2:

spoiler:

Kijk nog eens goed naar deel 2 van dag 11.

Mijn oplossing loopt snel zat (200ms) op de officiële invoer maar eigenlijk is 'ie O(N²) terwijl een O(N log N) algoritme mogelijk moet zijn. Als ik vrije tijd heb zal ik nog eens wat grotere invoer genereren...

[ Voor 21% gewijzigd door Soultaker op 18-12-2023 08:11 ]

[Friits]

Soultaker schreef op maandag 18 december 2023 @ 08:09:
Als ik vrije tijd heb zal ik nog eens wat grotere invoer genereren...

Volgens mij is mijn code gewoon O(n), dus kom maar op

[FCA]

Deel 2 vandaag was letterlijk alle corner- en edge-cases goed behandelen

spoiler:

Deel 1 had ik brute force aangepakt (floodfill van de binnenkant, eerste binnenpunt detecteren door te kijken naar richting van eerste en laatste edge).

Deel 2 wist ik gelukkig nog van de shoelace formule (maar die naam niet, maar goed gewoon zoeken op area of polytope). Maar toen nog bedenken hoe je dat omzet naar het grid. Uiteindelijk bedacht dat je
1. De coordinaten worden de centers van je grid cells
2. Elke edge telt extra mee voor (lengte -1)//2 ( eerst alle lengtes optellen, aan het eind pas door 2 delen i.v.m. afrondfouten/overflow)
3. Elke bocht naar links telt extra mee voor 1/4, elke bocht naar rechts telt mee voor 3/4.
4. Bochten detecteren door vorige richting met huidige te vergelijken (alle cases uitgeschreven, is vast elegante formule voor), en vergeet de bocht aan het begin niet (laatste richting naar eerste richting)

Daar had ik wel even een whiteboard en wat denktijd voor nodig, maar leverde uiteinde het goede antwoord op

[Soultaker]

bakkerjangert schreef op maandag 18 december 2023 @ 07:57:

spoiler:

Deel 1 heb ik opgelost met een shoe-lace berekening, wat verrassend goed werkt als je bedenkt waar de buitenzijde van de figuur loopt. Voor deel 2 heb je echter veel intersecties en dus overlappende delen, nu op zoek naar algoritme om een buitenomtrek te vinden ...

Mogelijke spoiler voor jou:

spoiler:

In de sample data en officiële testinvoer die ik kreeg zitten geen intersecties, ook niet in deel 2. Mogelijk heb je de invoer niet correct geparset?

Friits schreef op maandag 18 december 2023 @ 08:02:
Leuke puzzel vandaag! Mijn oplossing in Python

spoiler:

Dankzij dag 10 was deze wel erg eenvoudig.

Aha, dat is de methode die @bakkerjangert ook noemde. Heel nette oplossing!

spoiler:

Dat is inderdaad O(N) mits er geen overlap in de invoer zit. En heeeel wat simpeler dan mijn aanpak, al zal ik maar zeggen dat die superieur is omdat 'ie ook werkt als er intersecties zijn

[bakkerjangert]

FCA schreef op maandag 18 december 2023 @ 08:46:
Deel 2 vandaag was letterlijk alle corner- en edge-cases goed behandelen

spoiler:

Deel 1 had ik brute force aangepakt (floodfill van de binnenkant, eerste binnenpunt detecteren door te kijken naar richting van eerste en laatste edge).

Deel 2 wist ik gelukkig nog van de shoelace formule (maar die naam niet, maar goed gewoon zoeken op area of polytope). Maar toen nog bedenken hoe je dat omzet naar het grid. Uiteindelijk bedacht dat je
1. De coordinaten worden de centers van je grid cells
2. Elke edge telt extra mee voor (lengte -1)//2 ( eerst alle lengtes optellen, aan het eind pas door 2 delen i.v.m. afrondfouten/overflow)
3. Elke bocht naar links telt extra mee voor 1/4, elke bocht naar rechts telt mee voor 3/4.
4. Bochten detecteren door vorige richting met huidige te vergelijken (alle cases uitgeschreven, is vast elegante formule voor), en vergeet de bocht aan het begin niet (laatste richting naar eerste richting)

Daar had ik wel even een whiteboard en wat denktijd voor nodig, maar leverde uiteinde het goede antwoord op

spoiler:

Volgens mij kunnen die bochten sneller; je hebt een gesloten geheel en daardoor per definitie 4 buitenbochten. Elke binnenbocht wordt weer gecompenseerd door een buitenbocht. Per paar tel je er dan 1/4 + 3/4 = 1 bij op, is gemiddeld 1/2 per bocht (wat hetzelfde is als een recht stuk). Uiteindelijk heb ik de totaal lengte * 1/2 gepakt en daar 1/4 x4 buitenbochten voor de compensatie bij opgeteld.

[bakkerjangert]

@Soultaker Dank, was bij één regel de verwijzing naar pt2 aan te passen . Daarna direct het juiste antwoord. Code in python.

[.oisyn]

Day18 in Rust

spoiler:

Ik heb letterlijk mijn oplossing voor dag10 erbij gepakt. Die is niet zo efficient voor deel 2 omdat hij voor elke y-coordinaat een element toevoegt aan een lijstje. Ik weet wel hoe ik dat beter kan doen maar daar heb ik nu even geen zin in

[Soultaker]

Okee, extra testdata voor dag 18: aoc-2023-day-18-challenge-1-to-3.zip Segmenten bevatten geen overlap, net zoals de officiële testdata. Op invoer 3 na passen de antwoorden in een 63-bits integer.

Correcte antwoorden eindigen op:

1. ..934 en ...39243
2. ...486 en ...72432
3. ...699 en ...37799

Zo, ook maar even de efficiënte oplossing geïmplementeerd: 18-fast.py. Zo moeilijk is het achteraf niet eens; parsen is ingewikkelder dan het oplossen. (Uitleg van het algoritme hier, met spoiler tags)

[ Voor 37% gewijzigd door Soultaker op 18-12-2023 19:36 . Reden: Link naar uitleg toegevoegd ]

[MueR]

Dag 18 in Go.

spoiler:

Ik had bij dag 2 even over de directions heen gelezen waardoor ik even vast zat..

[MueR]

Soultaker schreef op maandag 18 december 2023 @ 10:24:
Okee, extra testdata voor dag 18: aoc-2023-day-18-challenge-1-to-3.zip Segmenten bevatten geen overlap, net zoals de officiële testdata. Op invoer 3 na passen de antwoorden in een 63-bits integer.

Correcte antwoorden eindigen op:

1. ..934 en ...39243
2. ...486 en ...72432
3. ...699 en ...37799

Zo, ook maar even de efficiënte oplossing geïmplementeerd: 18-fast.py. Zo moeilijk is het achteraf niet eens; parsen is ingewikkelder dan het oplossen.

Hehe, mijn deel 1 oplossing klopt hier wel mee.. deel 2 ga ik de negatieven in, dus ergens een bugje.

[bakkerjangert]

Inmiddels werkt mijn code ook voor de grote invoer. Kwestie van het eind antwoord met floor division uitrekenen in plaats van decimalen.

[DutchFakeTuber]

Vandaag was een stuk makkelijker vergeleken met de vorige dagen:

spoiler:

Ik heb de Shoelace Formula plus Picks' Theorem gebruikt om de punten binnen de perken te bepalen.
Daarna de grenzen opgeteld door abs(vorige[rij]-huidige[rij]) + abs(vorige[kolom]-huidige[kolom]) uit te voeren op elke coördinaat.

[MueR]

MueR schreef op maandag 18 december 2023 @ 11:02:
[...]

Hehe, mijn deel 1 oplossing klopt hier wel mee.. deel 2 ga ik de negatieven in, dus ergens een bugje.

En fixed.. Voor de grotere input 1 2.2ms & 2.1ms respectievelijk, voor input 2 2.3&2.6ms (waarvan 2.2 ms input parsing)

[Bolukan]

Soultaker schreef op maandag 18 december 2023 @ 10:24:
Correcte antwoorden eindigen op:

1. ..934 en ...39243
2. ...486 en ...72432
3. ...699 en ...37799

Ik zit nog vast op deel 2. Mijn antwoorden zijn:
...39264
...72544
...35552
Ik lijk in de buurt te zitten, maar ergens een foutje... Het voorbeeld gaat wel goed. PS:Mss overflows: dat de berekening deels in float gaat.

[ Voor 10% gewijzigd door Bolukan op 18-12-2023 12:43 ]

[MadEgg]

Vandaag weer een makkelijke nadat ik veel en veel te lang bezig geweest was met die van gister.

spoiler:

Die van dag 10 kwam goed van pas inderdaad. Eerst gewoon het pad bewandelen aan de hand van de instructies, dat was simpel en ook voor deel 2 prima te doen. Duurt paar seconden maar soit. De flood fill ging prima met de inside/outside bepaling, per rij en dan sommeren. Met als verschil dat nu de randen wel meetellen natuurlijk.

Snelheid is acceptabel, 20 seconden voor beide delen. De meeste tijd zit in het "uitgraven" van de randen bij het volgen van de instructies.

Dag 18 - Kotlin

[ Voor 11% gewijzigd door MadEgg op 18-12-2023 12:19 ]

[Bolukan]

spoiler: day 18

# **354636 not good = + line/2+1
# **354636 is good

Gewoon de eerste keer verkeerd geplakt??

[torx]

DutchFakeTuber schreef op maandag 18 december 2023 @ 11:15:
Vandaag was een stuk makkelijker vergeleken met de vorige dagen:

spoiler:

Ik heb de Shoelace Formula plus Picks' Theorem gebruikt om de punten binnen de perken te bepalen.
Daarna de grenzen opgeteld door abs(vorige[rij]-huidige[rij]) + abs(vorige[kolom]-huidige[kolom]) uit te voeren op elke coördinaat.

Blijkbaar heb ik hetzelfde gedaan.

spoiler:

Om de area te bepalen voor deel 2 heb ik moeten zoeken en kwam ook op de shoelace formula uit. De randen erbij op te tellen leeg ik mij eenvoudig, maar uiteindelijk kwam ik uit op de helft van de edges plus 1. Leek mij foutgevoelig, maar tot mijn verbazing werkte het op mijn invoer. En nu kom ik er dus achter dat het pick's theorem is

Mijn graafplattegronden:

spoiler:

[P_Tingen]

^%$@^!#$!@ Ik kom niet uit deel 18a wat doe ik fout?

spoiler:

Ik heb de code van dag 10b erbij gehaald maar ook dan lukt het me niet met de odd/even rule.

Stel dat ik zo'n patroon heb:

Dan loop ik per regel er zo doorheen:

- inside := false
- do x = 1 to 7:
- als grid[x] <> grid[x - 1] dan inside = not inside
- als (grid[x] = "#") of (grid[x] = " " en inside = true) dan count++
- end

Dit gaat met de 1e regel goed, maar met de 2e niet. Waar ga ik fout?

[MadEgg]

P_Tingen schreef op maandag 18 december 2023 @ 14:45:
^%$@^!#$!@ Ik kom niet uit deel 18a wat doe ik fout?

spoiler:

Ik heb de code van dag 10b erbij gehaald maar ook dan lukt het me niet met de odd/even rule.

Stel dat ik zo'n patroon heb:
[Afbeelding]
Dan loop ik per regel er zo doorheen:

- inside := false
- do x = 1 to 7:
- als grid[x] <> grid[x - 1] dan inside = not inside
- als (grid[x] = "#") of (grid[x] = " " en inside = true) dan count++
- end

Dit gaat met de 1e regel goed, maar met de 2e niet. Waar ga ik fout?

spoiler:

Op regel 2 krijg je 4 x achter elkaar een state change van inside = !inside, eerst van " " naar "#"en daarna weer terug. En dan dat nog een keer. Binnenin zal je inside dus false zijn, en tel je hem niet mee. Je moet alleen switchen als je een "#" tegenkomt. En dat is voor dit voorbeeld. Je hebt nog iets extra nodig als het geen rechthoek is

[.oisyn]

@P_Tingen Je derde puntje gaat natuurlijk mis. Je flipt daar inside aan de binnenkant van het vierkant, maar dat moet helemaal niet. Het is ook erg lastig op deze manier, want je maakt geen onderscheid tussen horizontale en verticale edges.

[ Voor 7% gewijzigd door .oisyn op 18-12-2023 14:52 ]

[P_Tingen]

Ja ik snap waar het mis gaat, ik zie alleen niet hoe het goed zou moeten gaan

[P_Tingen]

Of moet ik mijn plattegrond opbouwen met 7 J F en L ipv X tekens?

[Soultaker]

@P_Tingen Ik was sowieso van plan om nog een gedetailleerde uitleg te posten voor deel 2 voor de mensen die daar moeite mee hebben. Ik wilde daar eigenlijk nog even mee wachten omdat er nog best veel mensen op het leaderboard alleen deel 1 hebben opgelost, en het is moeilijk in te schatten hoeveel daarvan nog op eigen kracht het probleem willen oplossen.

@.oisyn wat vind jij ervan als moderator? Kan ik wat spoilers posten of beter nog even wachten?

[MadEgg]

P_Tingen schreef op maandag 18 december 2023 @ 14:56:
Ja ik snap waar het mis gaat, ik zie alleen niet hoe het goed zou moeten gaan

Ik gebruik hetzelfde algoritme. Als je inspiratie wilt dan kun je mijn code bekijken in: MadEgg in "Advent of Code 2023"

spoiler:

Of een korte tip: je kunt ook naar naburige tiles kijken. Tenzij je de hele outline wilt herschrijven maar dat lijkt me niet de meest ideale aanpak

[.oisyn]

Soultaker schreef op maandag 18 december 2023 @ 14:58:
@.oisyn wat vind jij ervan als moderator? Kan ik wat spoilers posten of beter nog even wachten?

Misschien nog even wachten tot vanavond? Al is de kern al wel al gepost geloof ik

[.oisyn]

spoiler:

God zeg wat heb ik zitten kutten. De "shoelace" methode gebruikte ik ook, heb ik ook een paar keer nodig gehad in mijn werk, al wist ik niet dat die zo heette . Maar hier heb je dus discrete tiles, en ik kreeg dat maar niet goed. Ik probeerde helemaal uit te werken met verschillende sets van ofwel 3 opeenvolgende vertices (bochten) ofwel 4 opeenvolgende vertices om een opgaande of neergaande rand dan wel of niet mee te tellen, maar ik kwam er niet uit.

Het stomme was, helemaal in het begin heb ik wel gewoon een keer breedte*hoogte gepakt met het idee dat ik dan de binnenkant had, en dat ik dan alleen maar de helft van de rand erbij op hoefde te tellen. Maar ik zat er daarmee 1 naast dus het leek me meer geluk dan wijsheid.

Uiteindelijk was dat wel de truc, zoals meerderen hier ook hebben geimplementeerd, en ben er inmiddels ook wel wachter waar die +1 vandaan komt . Ik had het gewoon meteen op papier moeten uittekenen.

Time spent: 187.2µs

[ Voor 4% gewijzigd door .oisyn op 18-12-2023 15:16 ]

[FrankMennink]

Day 18 in Python

Had vandaag een hint nodig, collega kwam met de volgende omschrijving:

spoiler:

Start picking at your shoelaces

Gelukkig ging daar mee een lampje branden en rolde mn solution er redelijk snel uit. Deel 2 kon daarmee ook vrij simpel worden doorgezet. Beide delen draaien in 0.4 ms per stuk

spoiler:

Oplossing is een combinatie van Shoelace formula en Pick's Theorem om daarmee het aantal punten binnen de loop te bepalen, daarna nog de loop punten zelf erbij optellen voor de oplossing

[Dricus]

Soultaker schreef op maandag 18 december 2023 @ 08:09:
Voor mij was vandaag ook niet eenvoudig. Ik heb er 40 minuten over gedaan en relatief veel code moeten schrijven: 18.py. Ik ben dan ook benieuwd of er anderen slimmere/eenvoudigere algoritmes geïmplementeerd hebben.

Ik heb voor dag 10 en 18 het volgende gebruikt:

spoiler:

Wikipedia: Shoelace formula en Wikipedia: Pick's theorem

Edit: Oh, ik ben scheel... Anderen hadden deze hint ook al gegeven...

[ Voor 5% gewijzigd door Dricus op 18-12-2023 15:38 ]

[Diderikdm]

Python dag 18

spoiler:

Natuurlijk werkte mn flood fill algo van part 1 niet voor part 2 . Zoals anderen ook uiteindelijk Shoelace + pick geïmplementeerd.

[Remcoder]

spoiler:

Wat ik alleen niet snap aan de toepassing van het pick theorem, volgens wikipedia is de formule i + (b / 2) - 1.

Terwijl ik voor zover ik kan zien vrijwel iedereen juist +1 doet, ook in mijn geval was dat de oplossing.

Waar komt dat verschil vandaan?

[FrankMennink]

Remcoder schreef op maandag 18 december 2023 @ 16:57:

spoiler:

Wat ik alleen niet snap aan de toepassing van het pick theorem, volgens wikipedia is de formule i + (b / 2) - 1.

Terwijl ik voor zover ik kan zien vrijwel iedereen juist +1 doet, ook in mijn geval was dat de oplossing.

Waar komt dat verschil vandaan?

spoiler:

de formule is A = i + (b/2) - 1, maar we weten b en A al, we willen juist i weten. Vandaar de i = A - (b/2) + 1

[MatHack]

Ik had voor deel 2 van vandaag toch echt de hints van iedereen hier nodig, waarvoor dank, want dat is onbekende wiskunde voor mij. Verder had ik dezelfde vraag als @Remcoder en die is ondertussen beantwoord.

https://github.com/realma...de.Y2023/Solvers/Day18.cs

[Soultaker]

Okee, het is technisch avond, dus voor mensen die het interessant vinden post ik een aantal hints/uitleg voor deel 2 van dag 18. Ja, je kunt het antwoord ook gewoon van Wikipedia halen, maar het is leuker als je ook begrijpt waarom het werkt. Ik heb meerdere spoilers gemaakt zodat je kunt stoppen met lezen als je het vanaf een bepaald punt verder zelf wil oplossen.

spoiler:

Als je de instructies in de invoer vertaalt naar een polygoon, dan kun je het antwoord berekenen met een simpele formule. Ik illustreer het aan de hand van een voorbeeld: R 3, D 1, R 1, D 2, L 4, U 3.
Zie de afbeelding hier:



Bij deel 1 kun je het pad tekenen in een pixel grid en dan eenvoudig tellen: er liggen 14 pixels op de rand (donkergrijs) en 5 pixels binnenin (lichtgrijs), dus het antwoord is 14 + 5 = 19. Maar pixels tellen is niet zo efficiënt als de coördinaten groot zijn, zoals bij deel 2.

spoiler:

In plaats van te kijken naar pixels, kun je het pad ook zien als een polygoon, waarvan de hoekpunten in het midden van de pixels liggen.

Het voordeel van deze representatie is dat het voor het berekenen van het oppervlak niet uitmaakt hoe groot de coördinaten zijn; alleen hoeveel hoekpunten er zijn, en dat aantal is redelijk beperkt: het aantal regels in de invoer.

De rode polygoon heeft een oppervlak van precies 11 vakjes, wat je in dit voorbeeld makkelijk met de hand kunt tellen, en in je code o.a. met de shoelace formula kunt berekenen. 11 is minder dan het werkelijke antwoord (19), en dat komt natuurlijk omdat je het deel van de rand dat buiten de polygoon valt niet hebt meegeteld. Iets preciezer: je hebt ongeveer de helft van de rand niet meegeteld (maar niet exact!) Daar moet je dus nog wat op verzinnen.

spoiler:

Om te compenseren voor de rand, kun je de helft van de lengte van elk lijnstuk bij het antwoord optellen (de helft, omdat je alleen het deel van de rand buiten de polygoon telt). Dat zijn de groene gebieden in het plaatje hieronder:



De omtrek is 14, de helft is 7. 11 + 7 = 18, en dat is nog net geen 19. Dat komt doordat je hier de zwarte vierkantjes (a, b, d, e, f) die ook op de rand liggen nog niet meegeteld hebt, en het gele vierkantje (c) juist dubbel geteld hebt (als onderdeel van lijnstuk (4,1)-(4,2) én (4,2)-(5,2)). Daar moet je ook nog voor compenseren.

spoiler:

Voor elk convex (naar binnen klappend) hoekpunt mis je een stukje van de rand met oppervlak 0,5 × 0,5 = 0,25, en voor elk concaaf (naar buiten klappend) hoekpunt tel je een gebied van 0,25 dubbel.

spoiler:

Dat kun je compenseren met een factor 0,25×(aantal convexe hoekpunten) - 0,25×(aantal concave hoekpunten). Je kunt die expliciet tellen, maar dat is niet eens nodig.

spoiler:

Het aantal convexe hoekpunten is altijd 4 meer dan het aantal concave hoekpunten. Dat kun je zo inzien: als je met de klok mee rond de polygoon loopt, sla je precies vier keer vaker rechtsaf dan linksaf. Dat komt omdat je in dezelfde oriëntatie eindigt als je begint, dus de totale rotatie moet sowieso een veelvoud van 360 zijn, en aangezien het hier om een simpele polygoon gaat (i.e., zonder zelf-intersectie) is het precies 360, niet meer of minder. Kortom, je moet netto precies 4 hoeken van 90 graden maken. 4×0,25 = 1.

Conclusie:

spoiler:

Als je bovenstaande informatie combineert is het antwoord simpelweg: oppervlak van de polygoon + (omtrek van de polygoon)/2 + 1.

En ja, dat is inderdaad precies dezelfde formule als in Pick's theorem maar die hóef je dus niet te kennen om het antwoord af te leiden voor dit probleem.

Wie z'n algoritme wil testen verwijs ik door naar mijn extra testinvoer voor dit probleem.

[.oisyn]

FrankMennink schreef op maandag 18 december 2023 @ 17:00:
[...]

spoiler:

de formule is A = i + (b/2) - 1, maar we weten b en A al, we willen juist i weten. Vandaar de i = A - (b/2) + 1

Nee, je wil b+i weten
A = de totale oppervlakte
i = het aantal interne integer punten
b = het aantal integer punten op de boundary.

Neem als voorbeeld een vierkant van (0,0) naar (3,3).
i = 4, b = 12, A = 9, maar het antwoord dat we zoeken is 16, en dat is geen van deze variabelen. Nou ja, b+i dus, zoals ik al zei.

A = i + b/2 - 1
i = A - b/2 + 1
b+i = A - b/2 + 1 + b = A + b/2 + 1

[Remcoder]

Soultaker schreef op maandag 18 december 2023 @ 10:24:
Okee, extra testdata voor dag 18: aoc-2023-day-18-challenge-1-to-3.zip Segmenten bevatten geen overlap, net zoals de officiële testdata. Op invoer 3 na passen de antwoorden in een 63-bits integer.

Correcte antwoorden eindigen op:

1. ..934 en ...39243
2. ...486 en ...72432
3. ...699 en ...37799

Zo, ook maar even de efficiënte oplossing geïmplementeerd: 18-fast.py. Zo moeilijk is het achteraf niet eens; parsen is ingewikkelder dan het oplossen.

Mmh, ik heb zitten spelen met jouw inputs, en, omdat je een 63 bits integer verwacht heb ik maar gelijk alles omgebouwd naar longs. Ook daarbij ging het resultaat negatief, dus daarna maar omgebouwd naar BigIntegers, en ook dan krijg ik negatieve resultaten. Terwijl mijn implementatie voor zover ik kan zien gewoon hetzelfde is als alle andere implementaties. Ik heb er zelfs een O(N) implementatie van weten te maken die op de officiele AoC invoer correcte resultaten geeft, en ook correcte resultaten voor deel 1 met jouw invoer, maar met deel 2 gaan ze negatief.

De performance valt me dan wel weer reuze mee, zelfs met de grootste testset krijg ik een resultaat binnen een 200 milliseconden

--edit--

Ok, gevonden, ik had gemist dat @Soultaker een abs deed op de uitkomst van het berekenen van de area. Blijkbaar kan dat dus negatief worden, en is dat een bekend gevolg van het toepassen van de formule...

[ Voor 6% gewijzigd door Remcoder op 18-12-2023 19:49 ]

[Soultaker]

Remcoder schreef op maandag 18 december 2023 @ 19:32:
Mmh, ik heb zitten spelen met jouw inputs, en, omdat je een 63 bits integer verwacht heb ik maar gelijk alles omgebouwd naar longs. Ook daarbij ging het resultaat negatief, dus daarna maar omgebouwd naar BigIntegers, en ook dan krijg ik negatieve resultaten.

spoiler:

De meeste formules voor het berekenen van het oppervlakte van een polygoon berekenen een signed area: een getal wat positief is als de hoekpunten van de polygoon met de klok mee lopen, en negatief als ze tegen de klok in lopen.

(Dit is ook handig om te bepalen welke kant een polygoon op draait, wat veel nuttige toepassingen heeft.)

Als je alleen het oppervlakte wil berekenen moet je de absolute waarde nemen, zoals ik in mijn code ook doe met abs().

Remcoder schreef op maandag 18 december 2023 @ 19:32:
De performance valt me dan wel weer reuze mee, zelfs met de grootste testset krijg ik een resultaat binnen een 200 milliseconden

Niet slecht! Het klopt inderdaad dat als je de O(N) oplossing geïmplementeerd hebt, de rekentijd grotendeels aan het parsen van de invoer besteedt wordt.

Ik heb daarom ook geen supergrote invoer gegenereerd; het voegt als benchmark weinig toe, want als de invoer 10x zo groot is is je solver waarschijnlijk exact 10x zo traag.

[.oisyn]

3530.9µs voor Soultaker-3 hier

[Soultaker]

.oisyn schreef op maandag 18 december 2023 @ 20:09:
3530.9µs voor Soultaker-3 hier

Linkje naar de code die heel mooi en kort maar nog steeds leesbaar is. Ik neem aan dat dit nu >95% parse-tijd is want het aantal rekenkundige operaties per regel is minimaal (rond de 8 ofzo? waarschijnlijk iets meer op CPU-niveau voor 128-bit integers, maar dan nog).

[P_Tingen]

Leuk, al die tips voor deel 2, maar ondertussen zit ik nog steeds met deel 1 te worstelen.

spoiler:

Ik heb het tekendeel omgeschreven zodat ik nu een vorm teken met de letters uit dag 10 en vervolgens laat ik daar ook de code van 10b op los met de odd/even rule. Test klopt, maar echte data nog niet.

Enige tips zijn welkom. En dan bij voorkeur iets duidelijker dan "zie mijn code op github"

[Bolukan]

spoiler: P_Tingen

Je wilt niet flooden of met polygon rekenen, maar wanden tellen.
Je zou bij het tegenkomen van de eerste wand, de regel erboven en eronder kunnen bekijken (een moet genoeg zijn!), waar de wand vandaan komt. En bij de laatste wand kijken waar ie heen gaat. Als ze allebei dezelfde kant op komen/gaan, verandert er niets qua aantal wanden:

     x                              x
-->  x   -->  xxxxxxx   -->  xxxxxxxx
     x        x     x        x

[ Voor 14% gewijzigd door Bolukan op 18-12-2023 21:10 ]

[P_Tingen]

spoiler:

@Bolukan tel je dan wanden van links naar rechts of van boven naar beneden?

[.oisyn]

Bolukan schreef op maandag 18 december 2023 @ 21:05:

spoiler: P_Tingen

Je wilt niet flooden of met polygon rekenen, maar wanden tellen.
Je zou bij het tegenkomen van de eerste wand, de regel erboven en eronder kunnen bekijken (een moet genoeg zijn!), waar de wand vandaan komt. En bij de laatste wand kijken waar ie heen gaat. Als ze allebei dezelfde kant op komen/gaan, verandert er niets qua aantal wanden:

     x                              x
-->  x   -->  xxxxxxx   -->  xxxxxxxx
     x        x     x        x

Je moet wel rekening houden met het feit dat als je je datastructuur echt op deze manier opzet, dat je ofwel extra ruimte moet houden tussen wanden, ofwel met meerdere waardes moet werken die de richting aangeven, omdat je anders nooit het onderscheid kunt maken tussen een lange horizontale muur en meerdere muren die naast elkaar lopen.

[Bolukan]

spoiler: P_Tingen

Ik tel geen wanden, maar als je van links naar rechts gaat (zeg maar de chars van een regel), dan moet je naar de regel erboven (zelfde positie) en/of regel eronder (zelfde positie) kijken.

@.oisyn Ik heb vastgesteld door inzoomen op een grafische weergave van mijn trenches, dat de opgave altijd ruimte heeft tussen 2 trenches ... Je hebt verder gelijk, maar P_Tingen kan ze verder ....

[ Voor 37% gewijzigd door Bolukan op 18-12-2023 21:17 ]

[.oisyn]

@Bolukan flauw

[Bolukan]

Ik heb echt ingezoomd met allerlei ranges in excel, omdat mijn antwoord niet klopte en ik op zoek ging naar een anomolie.... Bleek het toch mijn knip/plak vaardigheid

[P_Tingen]

Ik geloof het wel. Gaat niet meer lukken vandaag.
Mocht iemand nog inspiratie hebben om te zien waar ik het verkloot: dag 18a, outline hier

[.oisyn]

Soultaker schreef op maandag 18 december 2023 @ 20:48:
Ik neem aan dat dit nu >95% parse-tijd is want het aantal rekenkundige operaties per regel is minimaal (rond de 8 ofzo? waarschijnlijk iets meer op CPU-niveau voor 128-bit integers, maar dan nog).

Waarschijnlijk wel ja.

[mvdnes]

spoiler:

Ik heb deel b met coordinate compression opgelost, met een gewone floodfill om de binnenkant te bepalen. Voor de input op AoC werkte dat prima.
Shoelace formule kende ik nog niet, daar moet ik mij maar eens in gaan verdiepen voor komende jaren.

[Soultaker]

mvdnes schreef op maandag 18 december 2023 @ 21:41:

spoiler:

Ik heb deel b met coordinate compression opgelost, met een gewone floodfill om de binnenkant te bepalen.

Heb ik ook gedaan (voor de officiële score).

spoiler:

Shoelace formule kende ik nog niet, daar moet ik mij maar eens in gaan verdiepen voor komende jaren.

spoiler:

Zowel de Shoelace formula als Pick's theorem waren mij in theorie bekend maar ik had er echt niet aan gedacht aangezien ik ze in de afgelopen 10+ jaar nooit ergens voor nodig heb gehad. Overigens vind ik de Trapezoid formula veel eenvoudiger te begrijpen.

[MadEgg]

P_Tingen schreef op maandag 18 december 2023 @ 21:26:
Ik geloof het wel. Gaat niet meer lukken vandaag.
Mocht iemand nog inspiratie hebben om te zien waar ik het verkloot: dag 18a, outline hier

Je start ziet er zo uit:

code:

     |
     |
-----J
|
|
|
L--------7

Je start ziet er zo uit. De hoek begint met `-` en daarom zal je `J` niet geteld worden als doorgang van de rand omdat `iDir` niet op 1 gezet wordt. Het startpunt gaat niet goed bij de omzetting naar J7LF.

spoiler:

Als je kijkt of er op `pos(iCol, iRow - 1)` een gat zit weet je ook dat er een doorgang is. Dan hoef je de omzetting naar J7LF ook niet te doen, en het iDir gebeuren heb je dan ook niet nodig.

[MatHack]

P_Tingen schreef op maandag 18 december 2023 @ 21:00:
Leuk, al die tips voor deel 2, maar ondertussen zit ik nog steeds met deel 1 te worstelen.

Je kunt deel 1 op precies dezelfde manier doen als deel 2 hoor, dus al die tips zouden daar bij moeten helpen.

[MueR]

Soultaker schreef op maandag 18 december 2023 @ 21:45:

spoiler:

Zowel de Shoelace formula als Pick's theorem waren mij in theorie bekend maar ik had er echt niet aan gedacht aangezien ik ze in de afgelopen 10+ jaar nooit ergens voor nodig heb gehad. Overigens vind ik de Trapezoid formula veel eenvoudiger te begrijpen.

spoiler:

Dat is natuurlijk ook wel een beetje het idee van AoC, van die "nutteloze" dingen weer even naar voren halen. Ik heb het ook met shoelace + pick opgelost, moest wel even googlen voordat ik op de juiste oplossing (en termen) kwam.

[.oisyn]

.oisyn schreef op zondag 17 december 2023 @ 21:41:
[...]

spoiler:

Ik had ook even geen zin in een beter algo, dus ik doe hetzelfde. 39ms in Rust.

Wat ik wel had bedacht is dat paden vanaf splitters altijd gelijk zijn, dus voor alle startposities zou je die data kunnen delen. Je komt alleen niet weg met alleen pad-lengte, want in het overige pad kruis je mogelijk dezelfde tiles.

Day 16 even gerevisit, maar dat bood niet echt soelaas. Als ik alle paden cache dan kom ik op 49ms, ipv 39ms alles brute force uitrekenen. Ik heb het niet nagemeten maar ik gok overhead van allerlei geheugenallocaties.

Wat ik nu doe is voor alle eindpunten (en dus beginpunten) en splitters, de paden cachen naar de volgende eindpunten danwel splitters, en zo'n pad is dan een lijstje met tiles. Voor een volledig gecachede laserstraal moet ik dan nog wel recursief al die dingen aflopen, en de paden in een set gooien om te kijken hoeveel unieke tiles ik raak.

Je kunt het nog verder optimaliseren door de totale paden te cachen, maar dat is nog best complex met alle mogelijke loops die je onderweg tegenkomt, dus daar had ik geen zin meer in.