Advent of Code 2023

[Diderikdm]

Python

Best een mooie oplossing geworden zo

[Creepy]

Vandaag viel weer mee idd.
https://github.com/CodeEn...23/blob/main/days/Day9.go

spoiler:

Voor deel 2 een paar dingetjes moeten omdraaien (first index ipv last pakken en een - ipv een +) maar dat was dan ook alles

[Mugwump]

Creepy schreef op zaterdag 9 december 2023 @ 11:10:
Vandaag viel weer mee idd.
https://github.com/CodeEn...23/blob/main/days/Day9.go

spoiler:

Voor deel 2 een paar dingetjes moeten omdraaien (first index ipv last pakken en een - ipv een +) maar dat was dan ook alles

spoiler:

Of je draait gewoon de lijstjes om.

[gedonie]

Na de lastige puzzel van gisteren wilde ik vandaag er eens goed voor gaan zitten, blijkt de opdracht maar een paar minuten werk te zijn.

Dag 9 in Java.

[Friits]

Soultaker schreef op zaterdag 9 december 2023 @ 09:02:
Okee, omdat hij vandaag zo makkelijk was, hier een iets grotere invoer: aoc-2023-day-09-challenge-1.zip

Ik heb een Python-oplossing die dit in 500 ms uitrekent.

Ik haal in Python 250 ms. Met NumPy zou het waarschijnlijk nog een stuk sneller kunnen.

spoiler:

Pre-computed driehoek van Pascal

[ Voor 20% gewijzigd door Friits op 09-12-2023 12:34 ]

[Friits]

Diderikdm schreef op zaterdag 9 december 2023 @ 11:09:
Python

Best een mooie oplossing geworden zo

spoiler:

Leuk dat je beide antwoorden in één pass berekent! Ik doorloop de hele boel gewoon twee keer: eerst vooruit, daarna achteruit.

Dag 9

[Soultaker]

Friits schreef op zaterdag 9 december 2023 @ 12:32:
Ik haal in Python 250 ms. Met NumPy zou het waarschijnlijk nog een stuk sneller kunnen.

Numpy doet geen bigints voor zover ik weet?

spoiler:

Pre-computed driehoek van Pascal

Nice! Dat had ik ook bedacht/ontdekt.

spoiler:

Je hoeft niet eens te precomputen; je kunt de binomiaalcoëfficienten iteratief genereren, volgens de volgende logica:

nCr(n, k) = n! / k! / (n - k)!

nCr(n, k) / nCr(n, k - 1)
= n! / k! / (n - k)! / (n! / (k - 1)! / (n - (k - 1))!)
= (k - 1)! × (n - (k - 1))! / k! / (n - k)!
= (n - k + 1) / k

→ nCr(n, k) = nCr(n, k - 1) × (n - k + 1) / k

Dan kom je uiteindelijk op een O(N) oplossing uit, wat optimaal is (Python code).

[TrailBlazer]

Vandaag gewoon heel slordig gelezen waardoor ik nog meer dan normaal heb lopen prutsen.

[Friits]

Soultaker schreef op zaterdag 9 december 2023 @ 12:48:
Numpy doet geen bigints voor zover ik weet?

Oh ja... Waarschijnlijk alleen een probleem voor de som aan het einde, maar je krijgt het toch niet meer zo elegant.

spoiler:

Je hoeft niet eens te precomputen; je kunt de binomiaalcoëfficienten iteratief genereren

Klopt, maar ik had aangenomen dat ik de meeste wel een paar keer nodig zou hebben. Jouw code wordt ook wat sneller met een simpele @cache daar.

[FCA]

Soultaker schreef op zaterdag 9 december 2023 @ 12:48:
[...]

Numpy doet geen bigints voor zover ik weet?

Wel met dtype='O' en er gewoon Python ints in stoppen. Snel/efficient is het niet, maar het werkt wel.

[vDorst]

Vandaag was erg makkelijk. Part 2 was ook zo gebeurt.
Begin eindelijk het licht te zien met de nom/winnow parser.

[Tsjilp]

https://github.com/rsids/...2023/blob/main/day9-2.mjs
In javascript, 5.8ms

[SPee]

vDorst schreef op zaterdag 9 december 2023 @ 15:49:
Vandaag was erg makkelijk. Part 2 was ook zo gebeurt.
Begin eindelijk het licht te zien met de nom/winnow parser.

nom was niet eens nodig. Een split_whitespace() en str.parse::<i64>() waren genoeg.
Dan een stack vullen en bij het legen de gevraagde waardes berekenen.
Dus uiteindelijk maar geen aparte methodes voor deel 2 gemaakt.

[KabouterSuper]

Iemand nog bedacht dat je een polynoom kunt maken van een reeks? Dan hoef je alleen de coefficienten te berekenen. En dat kan recursief als je je polynoom handig kiest. Ik denk alleen dat je wat afrondingsverschillen gaat krijgen omdat je met floats moet gaan werken.

[Soultaker]

KabouterSuper schreef op zaterdag 9 december 2023 @ 19:18:
Iemand nog bedacht dat je een polynoom kunt maken van een reeks?

Een polynoom zie ik niet direct, maar

spoiler:

je kunt het antwoord wel schrijven als lineaire combinatie van de invoer, waarbij de coëfficiënten afgeleid zijn van de binomiaalcoëfficiënten (code, uitleg). @Friits had het ook op die manier opgelost.

Daarmee ga je van O(N²) naar O(N) qua complexiteit.

[Friits]

Voor wie het leuk vindt om even te puzzelen, hier mijn NumPy one-liner:

spoiler:

print(abs(sum(np.diff(np.loadtxt('data.txt', int), n=21, prepend=0, append=0))[::-1]))

Deze werkt voor inputs lengte 21. Voor de voorbeeld-data moet je n=21 even vervangen door n=6.

[.oisyn]

KabouterSuper schreef op zaterdag 9 december 2023 @ 19:18:
Iemand nog bedacht dat je een polynoom kunt maken van een reeks? Dan hoef je alleen de coefficienten te berekenen. En dat kan recursief als je je polynoom handig kiest. Ik denk alleen dat je wat afrondingsverschillen gaat krijgen omdat je met floats moet gaan werken.

Waarom moet je met floats gaan werken? Je evalueert altijd op integer posities, en de coefficienten zijn ook altijd integers.

[ Voor 4% gewijzigd door .oisyn op 09-12-2023 22:13 ]

[Daos]

Soultaker schreef op zaterdag 9 december 2023 @ 20:48:
[...]

Een polynoom zie ik niet direct

De voorbeelden zijn deze polynomen:

spoiler:

3x
1/2x^2 + 3/2x + 1
1/3x^3 - x^2 + 11/3x + 10

edit:

.oisyn schreef op zaterdag 9 december 2023 @ 22:13:
de coefficienten zijn ook altijd integers.

Is dus niet waar. Zie mijn voorbeelden hierboven. Volgens mij zijn de coefficienten wel altijd in Q. Je kan rekenen met breuken en dan op het exacte getal uitkomen zonder afrondingsfouten.

[ Voor 40% gewijzigd door Daos op 09-12-2023 23:43 ]

[.oisyn]

Ah ja is ook zo! Volgens mij kun je 'm wel altijd omschrijven naar een polynomiaal met integer coefficienten, die je vervolgens in z'n geheel door een faculteit deelt (specifiek n!, met n de graad van de polynomiaal)

[ Voor 95% gewijzigd door .oisyn op 10-12-2023 03:31 ]

[Soultaker]

gedonie schreef op zaterdag 9 december 2023 @ 11:33:
Na de lastige puzzel van gisteren wilde ik vandaag er eens goed voor gaan zitten, blijkt de opdracht maar een paar minuten werk te zijn.

Nou, dan hoop ik dat je weer vroeg bent opgestaan, want vandaag is het een forse uitdaging.

[MrHaas]

spoiler:

Deel 1 was redelijk evident, gewoon de pijplijn volgen .

Voor deel 2 ben ik langs de pijplijn gaan lopen en houd ik een set bij van punten die aan de linker of rechterkant van de pijplijn liggen. Dat doe ik door voor elke verbinding de richtingsvector naar links en rechts te roteren en de punten waar deze naar wijst (vanuit beide punten in de verbinding, dus je checkt 4 punten per verbinding) toe te voegen aan desbetreffende sets mits deze punten niet in de pijplijn liggen.
Daarna doe ik een floodfill voor beide sets met initial queue van de punten in die set en met boundaries op ([0, max x in pijplijn], [0, max y in pijplijn]). Degene die niet overflowt is de goede set en daarvan pak je de lengte!

Python code: https://github.com/arjand...oc_2023/day10/solution.py

/edit: je zou natuurlijk ook al een keer er door heen kunnen lopen om te checken hoeveel hoeken naar rechts en hoeveel naar links gaan zodat je al weet naar welke kant van de pijplijn je moet kijken!

[ Voor 16% gewijzigd door MrHaas op 10-12-2023 09:04 ]

[Mugwump]

Soultaker schreef op zondag 10 december 2023 @ 06:50:
[...]

Nou, dan hoop ik dat je weer vroeg bent opgestaan, want vandaag is het een forse uitdaging.

Inderdaad, net deel 1 gedaan en die was goed te doen.

spoiler:

Afgezien van het feit dat ik wat liep te klooien met windrichtingen en wat nodeloze debugtijd nodig had.

Ik open net deel 2 en dat gaat wel even duren denk ik.

spoiler:

Begon nog wel overzichtelijk, maar dat 'squeezing through' moet ik even goed over na gaan denken.

[Soultaker]

MrHaas schreef op zondag 10 december 2023 @ 08:47:

spoiler:

Deel 1 was redelijk evident, gewoon de pijplijn volgen .

Fuuu... Ik heb deel 1 veel te ingewikkeld gemaakt.

spoiler:

Ik ging er vanuit dat er allerlei aftakkingen mogelijk waren, en dat je de ene cykel in een graaf moest identificeren, dus ik heb allemaal code opgetuigd om doodlopende paden af te kappen die uiteindelijk helemaal niet nodig bleek.

Stom van me dat ik niet eerst gecheckt heb of de eenvoudige aanpak werkt. Dat had me heel veel tijd bespaard.

Voor deel 2

spoiler:

ben ik langs de pijplijn gaan lopen en houd ik een set bij van punten die aan de linker of rechterkant van de pijplijn liggen.

Slim bedacht (en netjes geïmplementeerd ook!). Interssant dat er zoveel verschillende mogelijkheden zijn. Ik had een andere aanpak:

spoiler:

Ik heb het geïmplementeerd met de even-odd rule: vanuit elk punt dat niet op de loop ligt scan je naar boven, en tel je hoeveel muren je tegenkomt. Je moet dan paren van karakters bekijken.
Bijvoorbeeld als je langs "--" of "L-" komt, steek je een muur over, maar als je langs "||" of "JF" komt niet, want dan kun je “tussendoor” glippen. Als het aantal muren dat je zo tegenkomt oneven is, zit je aan de binnenkant van de curve. Python code

En een derde mogelijkheid die ik pas later bedacht had is

spoiler:

dat je ook gewoon het grid kan verdubbelen (van grote H×W naar (2H+1)×(2W+1)). Daarbij introduceer je lege plekken behalve waar nodig om tegels te verbinden. Bijvoorbeeld "JF" wordt "J.F", maar "FJ" wordt "F-J" omdat de F en J verbonden zijn. voorbeeld (op pastebin want pre-tags werken niet in spoiler-tags).

Op het resultaat kun je simpelweg 1 flood fill uitvoeren (vanaf linksboven b.v.) om alle vakjes die aan de buitenkant liggen te identificeren. Wat overblijft is dan de binnenkant. Wel oppassen dat je alleen de oorspronkelijke coördinaten telt.

Misschien is dat nog wel het makkelijkste om te bedenken.

[FCA]

Pfff....

spoiler:

Deel 1 was direct duidelijk, maar wsl niet zo handig geimplementeerd: ik heb gelijk Dijkstra erbij gepakt (altijd goede oefening, Dijkstra from 'scratch'). Kan waarschijnlijk een stukje makkelijker/sneller.
dictionary van pijpelement -> output directions gemaakt, en functie die checkt of een pijpelement compatibel is met de inkomende stroom.

Deel 2 moest ik even goed voor gaan zitten. Uiteindelijk het volgende gedaan:
- achterhalen wat het startpunt voor pijpelement is door de dictionary van pijpelement naar uitgangen van hiervoor te inverteren.
- array met visited uit deel 1 met factor 3 opblazen, en dan de verder uit detailleren met welk pijpelement er in zat. Bijvoorbeeld "F" word [[0,0,0],[0,1,1],[0,1,0]].
- Daarna floodfill vanaf (0,0) in de grote array
- Door oorspronkelijke visited array lopen (voor de floodfill), als deze niet bezocht is checken of het centrale element daarvan in de flood-fill array (3x3 groter dus) ook niet bezocht is, dat is dan een interior.

[ Voor 3% gewijzigd door FCA op 10-12-2023 09:50 ]

[WernerL]

Deel 2 kom ik nog niet helemaal uit.

spoiler:

Voor deel 2 dacht ik eenvoudig een floodFill algorithme te implementeren, maar de requirement "squeezing between pipes is also allowed!" maakt dat een beetje lastig. Ik kom dus op een te hoog getal uit omdat een aantal tiles niet gevuld worden door het algorithme.

Straks maar verder kijken

[MatHack]

Deel 2 moet ik ook nog voltooien, maar hiervoor moet ik deel 1 ook nog herschrijven.

spoiler:

Begonnen met Dijkstra, maar die kreeg ik nog niet lekker aan de praat (omdat het een loop is ipv een pad naar een andere node in de boom). Later maar eens verder naar kijken.
Uiteindelijk heb ik deel 1 met DFS opgelost, waarbij ik bijhoudt welke nodes ik al bezocht heb en de parents van nodes. Op een gegeven moment kom je een node die je al bezocht hebt, dat is dan de verste node en dan kun je het pad teruggeven mbt de parents mapping.
Voor deel 2 heb je het hele pad nodig, dus moet mijn deel 1 omschrijven zodat ik dat terugkrijg.

[ Voor 16% gewijzigd door MatHack op 10-12-2023 11:37 ]

[bakkerjangert]

Pittige opgave vandaag, vooral deel 2.

spoiler:

Voor deel 2 heb ik gebruik gemaakt van de regel dat als je een lijn trekt vanuit een punt en die lijn een oneven aantal keer een omtrek van een figuur snijdt, het punt zich binnen de figuur bevindt. parallelle lijnen zijn vrij eenvoudig op te lossen als je bedenkt dat voor een horizontale lijn naar rechts geldt:

intersection = '|' or 'L-- ... --7' or 'F-- ... --J'.

code in python

Dit schrijvende besef ik me dat het nog makkelijker is om een schuine lijn te trekken (x+1)(y+1). Dan heb je helemaal geen parallelle paden .

[Dido]

Soultaker schreef op zondag 10 december 2023 @ 09:45:

spoiler:

Ik heb het geïmplementeerd met de even-odd rule: vanuit elk punt dat niet op de loop ligt scan je naar boven, en tel je hoeveel muren je tegenkomt. Je moet dan paren van karakters bekijken.
Bijvoorbeeld als je langs "--" of "L-" komt, steek je een muur over, maar als je langs "||" of "JF" komt niet, want dan kun je “tussendoor” glippen. Als het aantal muren dat je zo tegenkomt oneven is, zit je aan de binnenkant van de curve. Python code

spoiler:

Die heb ik ook, maar dan nog simpeler. Alleen horizontaal kijken per regel is al genoeg. Voor alle punten die niet op de lijn liggen check je of er een even of oneven aantal keer een |, J of L links in de regel voorkomen. Oneven betekent dat je binnen zit, even dat je (weer) buiten bent.

Dat heeft wel wat klooien gekost, maar is heul snel als je de punten di eop de lijn liggen uit deel 1 hergebruikt

[Mugwump]

spoiler:

Ik kom er bij deel 2 achter dat er nog ergens een slordigheidje in m'n deel 1 zit.
Ik had netjes een ceil(loop.size / 2) voor deel 1 en dat werkt correct. Alleen nu blijft 1 van de voorbeelden voor deel 2 hangen in oneindige loop, gloeiende gloeiende.

Werken in een taal die ik voor AoC nog niet eerder had gebruikt en het feit dat ik in de 20 jaar sinds m'n studietijd eigenlijk geen serieus algoritmisch werk meer heb gedaan nekt me vandaag wel.

[Soultaker]

bakkerjangert schreef op zondag 10 december 2023 @ 10:33:

spoiler:

Dit schrijvende besef ik me dat het nog makkelijker is om een schuine lijn te trekken (x+1)(y+1). Dan heb je helemaal geen parallelle paden .

Dit had ik ook even overwogen, maar het werkte niet precies zoals gehoopt. Achteraf realiseerde ik me dat het werkt als je

spoiler:

'|', '-', 'J', en 'F' als muren beschouwd, maar 'L' en '7' niet.

[bakkerjangert]

Soultaker schreef op zondag 10 december 2023 @ 10:59:
[...]

Dit had ik ook even overwogen, maar het werkte niet precies zoals gehoopt. Achteraf realiseerde ik me dat het werkt als je

spoiler:

'|', '-', 'J', en 'F' als muren beschouwd, maar 'L' en '7' niet.

spoiler:

Ligt eraan welke hoek je kiest. stel schuin omhoog:

../ ../
.F .J.
/.. /.. raken de lijn, maar snijden niet en moet je dus niet mee tellen. Analoog voor andere richtingen.

[Soultaker]

bakkerjangert schreef op zondag 10 december 2023 @ 11:14:

spoiler:

Ligt eraan welke hoek je kiest.

spoiler:

Het gaat om de diagonaal (twee opties) niet de hoek (vier opties). Ik ging inderdaad uit van de hoofddiagonaal die jij ook noemde. Voor de antidiagonaal tel je inderdaad L en 7 en laat je F en J achterwege.

spoiler:

raken de lijn, maar snijden niet en moet je dus niet mee tellen.

spoiler:

De manier waarop ik het bekijk is dat je niet het hoekpunt raakt of snijdt, maar er omheen loopt.

Als je parallel aan de hoofddiagonaal naar linksboven loopt en je komt een L-tegel tegen, dan kun je ofwel links ofwel rechts om het hoekpunt lopen. In het eerste geval doorkruis je 0 muren, in het tweede geval 2 muren (eerst de horizontale en dan de verticale); hoe dan ook is het aantal even dus dat maakt voor de pariteit van het totaal aantal muren niet uit, vandaar dat je dat karakter kunt negeren.

Omgekeerd als je b.v. een F-tegel tegenkomt, dan kun je ofwel linksom door de vertikale muur, ofwel rechtsom door de horizontale muur. In elk geval doorkruis je 1 muur.

[ Voor 5% gewijzigd door Soultaker op 10-12-2023 11:48 ]

[Creepy]

Ik ben nu al helemaal klaar met het schrijven van een parser (en pas net begonnen....)

[mbe81]

Creepy schreef op zondag 10 december 2023 @ 11:55:
Ik ben nu al helemaal klaar met het schrijven van een parser (en pas net begonnen....)

Die map had ik inderdaad ook zo geparsed, maar er overheen gelezen dat het om een loop ging. Dus heel veel ingewikkelds gedaan zonder resultaat. Na de lunch maar een nieuwe poging.

[Mugwump]

Nou, deel 2 ook afgekregen.

spoiler:

Ik zat wat vast op m'n implementatie van "canEscapeFromPosition".
Ik had de loop gepakt en daarvan een bounding box gemaakt.
Vervolgens gezocht naar potentiële nesten (lees: aaneengesloten vakjes die geen onderdeel zijn van de loop) in die bounding box
Van elk potentieel nest de buitenste randen gepakt.
Stond nog open hoe ik kon bepalen of ik vanuit 1 van die vakjes van zo'n buitenste rand kon ontsnappen.

Daar was ik echt even de draad kwijt, dus ik heb hier even schaamteloos inspiratie opgedaan. Het idee om het aantal muren (van de loop) te tellen dat je doorkruist als je diagonaal naar linksboven of linksonder gaat gebruikt en dat werkt prima.

[ Voor 3% gewijzigd door Mugwump op 10-12-2023 14:42 ]

[Remcoder]

spoiler:

Het is een aardige berg code geworden, met lichte spaghettification erin, maar ik heb wel een oplossing gevonden

Ik zoek vanaf het startpunt eerst een hoekpunt uit, en dan markeer ik de linkerzijde van de looprichting als "buiten" en ga ik de route lopen tot ik rond ben. Tijdens het lopen markeer ik alle punten aan de linkerzijde als "buiten".

Na het lopen veeg ik de route nog even schoon, zodat de routepunten alleen als routepunt aangemerkt zijn, en niet meer als buitenpunt.

Daarna pak ik alle overgebleven buitenpunten, en vanaf daar doe ik een floodfill.

Daarna tel ik alle buitenpunten en binnenpunten, en ik geef de laagste van de 2 terug. Hier doe ik dus wel een aanname dat er meer punten buiten de loop dan erbinnen liggen.

Aanschouw mijn zonde hier.

[ Voor 9% gewijzigd door Remcoder op 10-12-2023 15:18 ]

[P_Tingen]

** even weer een Dijkstra-update doet

[MadEgg]

spoiler:

Hier kwam mijn cursus computer graphics van pas Niet eens overwogen om een brute force aanpak te proberen hier.

Bij deel 2 kwam ik er wel achter dat het wellicht een goed idee was geweest om het node-type van de S-node vast te leggen. In de uitgebreidere voorbeelden kwam ik erachter dat de data iets minder schoon was doordat er mee dan 2 aangrenzende nodes aan de start-node, dus dat vereiste nog even wat extra checks om de juiste twee buren te kiezen.

Daarna de loop-doorbrekingen tellen om te weten of het ingesloten is of niet.

Code kan nog wel wat netter, maar heb nog meer te doen vandaag Vanavond misschien nog even.

Dag 10 - Kotlin

[ Voor 6% gewijzigd door MadEgg op 10-12-2023 15:39 ]

[Camulos]

Terug naar dag 8.. ik weet niet waarom maar voor Deel 2 had ik gelezen

spoiler:

startnodes die eindigen met xxA of xxB

Dat werkt wel, behalve dat de cycle-lengtes soms gelijk zijn maar de offsets niet.
En dan is ie niet oplosbaar...

gelukkig duurde dit maar een halve dag klooien om beter te leren lezen

[Diderikdm]

Python

schrik niet van mn lambdas

[Creepy]

Deel 1 was vrij snel klaar.

spoiler:

Het is een loop zonder splitsingen en kruisingen. Dus lengte van de loop / 2 is de uitkomst.
Deel 2 ben ik nu druk aan het scannen op buizen waar je tussendoor kan kruipen, maar ergens zit nog een foutje......

[JeroenTheStig]

Nou, dat was een hele bevalling om deel 2 op te lossen. De code is niet om aan te gluren, maar het juiste antwoord kwam er wel uitgerold.

spoiler:

Bij het parsen van het veld heb ik van de route een dubbelgelinkte Node-netwerk gemaakt. Deze kwam van pas om deel 2 op te lossen:

Van iedere node die niet op de route ligt, heb ik berekend hoe vaak de route op dezelfde x-positie aan de linkerkant verticaal doorkruist en aan de rechterkant vertikaal doorkruist. Ditzelfde heb ik gedaan om te kijken hoe vaak de route op dezelfde y-positie aan de bovenkant en onderkant doorkruist.

Een node valt binnen de route indien het aantal doorkruiste lijnen aan iedere zijde van de node een oneven getal is.

De dubbele gelinkte nodes kwamen van pas om het doorkruisen te bereken, ook omdat er meerdere achtereen volgende nodes op dezelfde lijn kunnen liggen als de lijn waarop je het aantal doorkruisingen wilt testen.

Code komt hopelijk later nog, nadat ik de spaghetti en dubbelingen heb weggerefactord

/edit

spoiler:

Lees nu pas de vele verschillende oplossingen hier in dit topic voor deel 2. Ontzettend leuk om te zien wat voor slimme creaties er zijn gemaakt, vooral het diagonaal ipv horizontaal zoeken van doorkruisende 'muren' vind ik best geniaal

[ Voor 11% gewijzigd door JeroenTheStig op 10-12-2023 20:39 ]

[Creepy]

Zo, deel 2 duurde ff ja...

spoiler:

Google nodig gehad om zo de odd/even rule te ontdekken. Daarna veel te lang open prutsen om het correct aantal muren te tellen als je een ray schiet..

https://github.com/CodeEn...3/blob/main/days/Day10.go

[ Voor 16% gewijzigd door Creepy op 10-12-2023 21:21 ]

[.oisyn]

Day10 in Rust

Dat was een leuke .
Time spent: 493.3µs

Relatief simpel op te lossen.

spoiler:

Ik loop over het pad en stop alle offsets (ik werk niet eens met coordinaten, die zijn irrelevant, en de hele textuele buffer staat as-is in geheugen) van niet-horizontale delen in een array, die ik daarna sorteer van klein naar groot.

Vervolgens schrijf ik die lijst met offsets om naar een lijst met borders. Dat is ofwel een verticale border (|), ofwel een span van gelijke richting (F..7 of L..J), ofwel een span met omgekeerde richting (F..J of L..7).

Dan loop ik over de borders. Als ik een span van gelijke richting vind, dan voeg ik de lengte toe aan de area. Vind ik daarentegen een verticale border of een span met omgekeerde richting, dan zoek ik een tweede border, waarbij ik spans met gelijke richting negeer. Wat ik dan in totaal bij de area optel is de lengte van linker-offset van de eerste borde t/m de rechter-offset van de rechter border.

Dit geeft de totale area van de hele polygoon. Dan trek ik daar de lengte van het pad van af (die je al nodig had voor deel 1), en dan hou je over alle binnenste tiles.

Het idee achter de borders is als volgt. Elke keer dat je over een rand stapt, ga je van buiten het pad naar binnen het de polygoon en vice versa. Het type borders dat een gebied afsluiten is altijd een verticale border of een span met ongelijke richting. Immers, als je eerst niet in de polygoon zit, en dan een border met gelijke richting tegenkomt, dan zit je daarna nog steeds niet in de polygoon. Alleen de span zelf is dan onderdeel van de polygoon. Zit je al ín de polygoon, dan kun je alle spans met gelijke richting negeren, want je treedt dan niet buiten de polygoon.

Verder werk ik met offsets omdat je nooit een span zal hebben die een begint op de ene regel en eindigt op de volgende regel.

[ Voor 22% gewijzigd door .oisyn op 11-12-2023 01:04 ]

[.oisyn]

Soultaker schreef op zondag 10 december 2023 @ 09:45:
Stom van me dat ik niet eerst gecheckt heb of de eenvoudige aanpak werkt. Dat had me heel veel tijd bespaard.

Of gewoon de opdracht goed had gelezen, dan had je geweten dat er niet eens tekens zijn gedefinieerd voor T-splitsingen. en dat er staat:

Based on the acoustics of the animal's scurrying, you're confident the pipe that contains the animal is one large, continuous loop.

[ Voor 18% gewijzigd door .oisyn op 11-12-2023 01:14 ]

[CrossProd]

Vandaag was goed te doen.

Dag 11 in Swift

spoiler:

Gelukkig had ik de galaxies al direct in een Set gezet dus alleen de coördinaten van de galaxies updaten tijdens de expansie. Voor part 2 hoefde ik alleen de expansion factor te wijzigen.

[Soultaker]

.oisyn schreef op maandag 11 december 2023 @ 01:06:
Of gewoon de opdracht goed had gelezen, dan had je geweten dat er niet eens tekens zijn gedefinieerd voor T-splitsingen

Goed punt, had ik me letterlijk nog niet gerealiseerd Soms vraag ik me af hoe ik het überhaupt voor elkaar krijg om werkende code te schrijven als ik zulke basale dingen mis.

Dag 11 vandaag was niet al te moeilijk.

spoiler:

Ik heb er spijt van dat ik deel 1 opgelost heb met de brute force aanpak (expliciet lege rijen en kolommon invoegen in het grid) in plaats van direct de algemene aanpak (coördinaten naar nieuwe coördinaten vertalen), aangezien op basis van de probleemstelling goed te voorspellen was wat deel 2 zou zijn, en de brute force aanpak niet echt simpeler te implementeren was.

Case in point: ik heb 10 minuten over deel 1 gedaan (maar daar moet je ook het lezen van het probleem bij meetellen), en daarna minder dan 6 minuten over deel 2, terwijl ik m'n code bijna helemaal moest herschrijven.

Enfin, uiteindelijk is het niet zo ingewikkeld. Oplossing in Python. De Python accumulate functie komt hier goed van pas (al kun je 'm natuurlijk ook eenvoudig zelf implementeren).

Ik denk dat @Friits zich weer kan uitleven door de code te minimaliseren. Daar leent de logica zich wel voor.

[FCA]

spoiler:

same here, deel 1 met wat gepruts opgelost op een brute force manier. Toen deel 2 dat niet mogelijk bleek, even een minuutje nagedacht, en een simpelere, elegante algemene oplossing (gewoon bijhouden welke rijen/kolommen leeg zijn, en dan over de oorspronkelijke melkwegposities lopen, en bij de posities optellen hoeveel rijen/kolommen er leeg zijn tot die positie). Als ik dat direct had gedaan was.ik waarschijnlijk eerder klaar geweest, zowel met deel 1 als deel 2, i.p.v. lopen hannesen met numpy append, arrays met grootte 0 x iets, reshapen, de hele rataplan.

[Mschamp]

spoiler:

fout ingeschat wat deel 2 ging zijn: ik was voorbereid op de kortse afstand om alle galaxies te bezoeken. Viel op zich nog mee vandaag

[Mugwump]

FCA schreef op maandag 11 december 2023 @ 07:29:

spoiler:

same here, deel 1 met wat gepruts opgelost op een brute force manier. Toen deel 2 dat niet mogelijk bleek, even een minuutje nagedacht, en een simpelere, elegante algemene oplossing (gewoon bijhouden welke rijen/kolommen leeg zijn, en dan over de oorspronkelijke melkwegposities lopen, en bij de posities optellen hoeveel rijen/kolommen er leeg zijn tot die positie). Als ik dat direct had gedaan was.ik waarschijnlijk eerder klaar geweest, zowel met deel 1 als deel 2, i.p.v. lopen hannesen met numpy append, arrays met grootte 0 x iets, reshapen, de hele rataplan.

spoiler:

Ik heb hetzelfde gedaan met lege rijen / kolommen en dan gewoon (x2 - x1) + (y2 - y1) + emptyrows.intersect(x1<..<x2).count en emptycolumns.intersect(y1<..<y2).count.

Dacht in deel twee simpelweg beide intersect counts met de expansionfactor kunnen te vermenigvuldigen, maar dat levert nog niet het gewenste resultaat. In de trein maar even kijken of ik de oorzaak kan vinden zo.

[Soultaker]

Mschamp schreef op maandag 11 december 2023 @ 07:34:

spoiler:

ik was voorbereid op de kortse afstand om alle galaxies te bezoeken. Viel op zich nog mee vandaag

Je weet dat dit een praktisch onmogelijk probleem is?

[Dido]

spoiler:

Yup, brute force was leuk voor deel 1, maar voor deel 2 de expand toch maar aangepast door de galaxy-coordinaten aan te passen ipv het universum op te blazen.
Waar ik van baal is dat ik een bug introduceerde met mijn expansionrate, die voor deel 1 natuurlijk niet 1 was, maar 2

Mschamp schreef op maandag 11 december 2023 @ 07:34:

spoiler:

fout ingeschat wat deel 2 ging zijn: ik was voorbereid op de kortse afstand om alle galaxies te bezoeken. Viel op zich nog mee vandaag

En je bent al boilerplate aan het schrijven om ergens komende week het halting problem op te lossen?

[ Voor 38% gewijzigd door Dido op 11-12-2023 07:40 ]

[Mugwump]

spoiler:

hmm ergens een off by 1 en het helpt ook wel om Longs ipv Ints te gebruiken. Ook goeiemorgen.

[Dido]

Mugwump schreef op maandag 11 december 2023 @ 07:40:

spoiler:

hmm ergens een off by 1 en het helpt ook wel om Longs ipv Ints te gebruiken. Ook goeiemorgen.

Zie de edit hier, van dik een week geleden
Dido in "Advent of Code 2023"
Bijna les 1 van AoC, maar niet getreurd, ik denk dat iedereen er wel eens in is getrapt. Sommigen ieder jaar opnieuw

[ Voor 16% gewijzigd door Dido op 11-12-2023 07:45 ]

[Friits]

Soultaker schreef op maandag 11 december 2023 @ 06:44:
Ik denk dat @Friits zich weer kan uitleven door de code te minimaliseren.

Yep!

Eigenlijk gelijk aan jouw implementatie, modulo een klein dimensioneel handigheidje.

[ Voor 6% gewijzigd door Friits op 11-12-2023 07:51 ]

[Soultaker]

Extra uitdaging voor dag 11: aoc-2023-day-11-challenge-3.zip. Laatste vijf cijfers van de antwoorden:

aoc-2023-day-11-challenge-1.in:
...77330
...13428

aoc-2023-day-11-challenge-2.in:
...58190
...20490

aoc-2023-day-11-challenge-3.in:
...72698
...83738

Hint: voor de grootste invoerbestanden heb je een efficiënte oplossing nodig. Als mensen interesse hebben kan ik (later) uitleggen hoe dat moet, voor wie er zelf niet uitkomt, want het is een techniek die wel vaker van pas komt, en dus nuttig is om te leren.

edit:
Uitleg hier: snel-met-uitleg.py (spoilers!)

[ Voor 10% gewijzigd door Soultaker op 11-12-2023 20:21 . Reden: Uitleg toegevoegd ]

[Mugwump]

Dido schreef op maandag 11 december 2023 @ 07:44:
[...]

Zie de edit hier, van dik een week geleden
Dido in "Advent of Code 2023"
Bijna les 1 van AoC, maar niet getreurd, ik denk dat iedereen er wel eens in is getrapt. Sommigen ieder jaar opnieuw

spoiler:

Ja in m'n hoofd zou het in een int passen, maar dat was wat optimistisch.
De off-by komt natuurlijk omdat je de eerste lege rij al meetelt in je afstand, dus de vermenigvuldiging is emptyrows (expansionfactor - 1) en de expansionfactor voor part 1 is eigenlijk 2.

[MatHack]

Na gisteren was dit weer een puzzel die relatief simpel was (als je geen fouten maakt).

spoiler:

Voor deel 1 had ik een oplossing gekozen die daadwerkelijk de punten erbij voegde (naar mijn idee sneller geïmplementeerd dan het alternatief). Dat ging in deel 2 natuurlijk niet werken, dus toen toch maar omgebouwd naar rekenen met coordinaten. Daar ging wat tijd inzitten.
En dan moet je goed nadenken dat vervangen met 1.000.000 regels natuurlijk betekent dat je 999.999 regels erbij doet...

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

[Dido]

MatHack schreef op maandag 11 december 2023 @ 08:08:

spoiler:

En dan moet je goed nadenken dat vervangen met 1.000.000 regels natuurlijk betekent dat je 999.999 regels erbij doet...

Of je bedenkt dat 1 regel toevoegen hetzelfde is als een regel vervangen door 2 regels.
Die 10, 100, 1000000 uit deel 2 komen dan overeen een 2, en niet een 1 in deel 1

[MatHack]

Dido schreef op maandag 11 december 2023 @ 08:17:
[...]


[...]

Ja, maar dan moest ik meer in mijn code aanpassen dan ergens een -1

[Mugwump]

MatHack schreef op maandag 11 december 2023 @ 08:18:
[...]


Ja, maar dan moest ik meer in mijn code aanpassen dan ergens een -1

spoiler:

Gewoon empty x (expansionfactor - 1) lost dat op.
Voor deel 1 geef ik solve(2) mee, voor deel 2 solve(1000000)

[KabouterSuper]

Net deel 2 van dag 10 (gisteren) afgerond. Ik heb een flood-en-fill algoritme gemaakt, wat verbazend goed werkte.

spoiler:

Ik heb mijn array wel drie keer zo groot moeten maken om te zorgen dat er gelekt kan worden langs randen. Maar het werkt als een zonnetje.

Ik vond het een leuke opdracht!

Nu door met dag 11.

[Diderikdm]

Python

Runt in ~.5s. Heb het gevoel dat dit sneller kan?

[Soultaker]

Friits schreef op maandag 11 december 2023 @ 07:47:
Yep!

Eigenlijk gelijk aan jouw implementatie, modulo een klein dimensioneel handigheidje.

Nice! Als performance minder belangrijk is kun je 'm zo nog aanzienlijk korter maken, en heb je ook de imports niet meer nodig.

[TrailBlazer]

spoiler:

uiteraard verkeerd begonnen door een matrix te maken voor deel1. Je kon er op wachten dat je daarvoor werd afgestraft in deel2.
uiteindelijk wel die matrix gehouden om de lege rijen/kolommen bij te houden en dan de nieuwe posities mee uit te rekenen voor deel 2.
Ook ik heb even lopen kijken waar die one off nou vandaan kwam.

[MatHack]

Ik kijk nog eens met een frisse blik naar de opdracht van gisteren (dag 10) en zie nu pas dat:

spoiler:

Voor het bepalen van een loop ik veels te moeilijk heb gedacht, er zijn helemaal geen aftakkingen in dat pad, zelfs niet vanaf de S... Dan is het vinden van de loop simpel, ik dacht weer veel te moeilijk aan T of + splitsingen...

[Dido]

MatHack schreef op maandag 11 december 2023 @ 13:11:
Ik kijk nog eens met een frisse blik naar de opdracht van gisteren (dag 10) en zie nu pas dat:

spoiler:

Voor het bepalen van een pad ik veels te moeilijk heb gedacht, er zijn helemaal geen aftakkingen in dat pad, zelfs niet vanaf de S... Dan is het vinden van de loop simpel, ik dacht weer veel te moeilijk aan T of + splitsingen...

Je bent de enige niet

[.oisyn]

The amount of Dijkstra mentions in this topic is TOO DAMN HIGH.

[Mugwump]

.oisyn schreef op maandag 11 december 2023 @ 13:39:
The amount of Dijkstra mentions in this topic is TOO DAMN HIGH.

Heeft die geen only-path algoritme bedacht dan?

[Friits]

Soultaker schreef op maandag 11 december 2023 @ 10:54:
[...]

Nice! Als performance minder belangrijk is kun je 'm zo nog aanzienlijk korter maken, en heb je ook de imports niet meer nodig.

Zelf had ik nog dit idee, maar ik vind die van jou mooier!

[eheijnen]

Friits schreef op maandag 11 december 2023 @ 15:50:
[...]




Zelf had ik nog dit idee, maar ik vind die van jou mooier!

Hoe snel draait ie?

[Friits]

Milliseconden.

En duidelijk sneller dan mijn "normale" oplossing.

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

[Soultaker]

Soultaker schreef op maandag 11 december 2023 @ 07:59:
Extra uitdaging voor dag 11: aoc-2023-day-11-challenge-3.zip.

Bumpje. Heeft iemand deze data nog geprobeerd op te lossen?

[MadEgg]

Soultaker schreef op maandag 11 december 2023 @ 17:17:
[...]
Bumpje. Heeft iemand deze data nog geprobeerd op te lossen?

Ik Maar alleen deel 1 lukt. Het aantal combinaties van deel 2 en deel 3 is veel te groot. Ik heb de verwerkingstijd van mijn algoritme nog met een factor 10 kunnen verkleinen maar dan is het nog steeds niet te doen, dus ik heb een ander algoritme nodig.

[ Voor 3% gewijzigd door MadEgg op 11-12-2023 17:22 ]

[Kazu]

Leuke puzzel vandaag! Oplossing in Rust.

spoiler:

Deel 1 was zo gedaan. Aangezien ik geen zin had om moeilijk te doen heb ik gewoon de map benaderd als matrix, dus bij het inlezen al meteen de lege rij gedubbeld, daarna getransponeerd en nog een keer de lege rijen gedubbeld.

Bij deel 2 was het natuurlijk te verwachten dat dit niet houdbaar was, dus daarna de inhoud van de matrix omgeschreven naar een struct zodat ik bij kon houden of ze onderdeel waren van een lege rij. Het uitrekenen van de lengte is daarna simpel. Ik heb voor deel 2 vooral wat extra moeite gestoken om de tweedimensionale vector om te schrijven naar een ArrayVec, zodat ik de empty cell lookups tenminste in constante tijd kon doen.

Runtime is 175ms. Heb het idee dat het nog wel een stuk efficiënter kan, maar ik vind het wel goed zo.

[DataGhost]

Kazu schreef op maandag 11 december 2023 @ 17:25:
Leuke puzzel vandaag! Oplossing in Rust.

spoiler:

Deel 1 was zo gedaan. Aangezien ik geen zin had om moeilijk te doen heb ik gewoon de map benaderd als matrix, dus bij het inlezen al meteen de lege rij gedubbeld, daarna getransponeerd en nog een keer de lege rijen gedubbeld.

Bij deel 2 was het natuurlijk te verwachten dat dit niet houdbaar was, dus daarna de inhoud van de matrix omgeschreven naar een struct zodat ik bij kon houden of ze onderdeel waren van een lege rij. Het uitrekenen van de lengte is daarna simpel. Ik heb voor deel 2 vooral wat extra moeite gestoken om de tweedimensionale vector om te schrijven naar een ArrayVec, zodat ik de empty cell lookups tenminste in constante tijd kon doen.

Runtime is 175ms. Heb het idee dat het nog wel een stuk efficiënter kan, maar ik vind het wel goed zo.

Ik gebruik bij dit soort problemen altijd gewoon een

spoiler:

set met coordinaten

. Deel twee was daarom een oneliner, enkel een aanpassing in 1 variabele.

[ Voor 3% gewijzigd door DataGhost op 11-12-2023 17:40 ]

[MatHack]

Soultaker schreef op maandag 11 december 2023 @ 17:17:
[...]

Bumpje. Heeft iemand deze data nog geprobeerd op te lossen?

Ja, zelfde uitkomst als @MadEgg (daarna moest ik weer voor studie bezig), ik ben wel benieuwd naar je uitleg voor een betere/snellere oplossing.

[ Voor 6% gewijzigd door MatHack op 11-12-2023 17:34 ]

[WernerL]

Gisteren enorm lopen prutsen met deel 2. Uiteindelijk ben ik weer naar plan A terug gegaan.

spoiler:

Het flood-fill algoritme, alleen dit keer eerst resizen zoals andere mensen ook hebben gedaan. Ook achter gekomen dat dit algoritme niet echt lekker werkt met recursie dus moeten herschrijven naar een stack en toen kwam er een goed antwoord uitrollen.

En replacement voor S hardcoded erin geknalt, geen zin meer om daar een functie voor te schrijven.

Het even-odd principe ook proberen toe te passen maar om een of andere reden kwam daar bij mij geen correct uitwoord uit. Waarschijnlijk deed ik iets heel doms fout.

https://github.com/Werner.../blob/main/day10/day10.ts
Nu eens naar dag 11 kijken.

[ Voor 21% gewijzigd door WernerL op 11-12-2023 17:48 ]

[FCA]

Soultaker schreef op maandag 11 december 2023 @ 07:59:
Extra uitdaging voor dag 11: aoc-2023-day-11-challenge-3.zip. Laatste vijf cijfers van de antwoorden:

aoc-2023-day-11-challenge-1.in:
...77330
...13428

aoc-2023-day-11-challenge-2.in:
...58190
...20490

aoc-2023-day-11-challenge-3.in:
...72698
...83738

Hint: voor de grootste invoerbestanden heb je een efficiënte oplossing nodig. Als mensen interesse hebben kan ik (later) uitleggen hoe dat moet, voor wie er zelf niet uitkomt, want het is een techniek die wel vaker van pas komt, en dus nuttig is om te leren.

code
Hmm... ben wel benieuwd wat er bij deel 3 nog efficienter kan. Heb nu een O(n log n) algoritme volgens mij (met n het aantal galaxies) algoritme, zie wel een mogelijkheid om er een O(n) algoritme van te maken, maar heel veel zou dat niet mogen schelen?

challenge 1: 0.233s (deel 1+2 samen)
challenge 2: 2.721s (deel 1+2 samen)
challenge 3: deel 1 alleen 1m6.781s. Deel 2 geeft een integer overflow, in Python
challenge 3: deel 2 alleen 1m7.378s
Integer overflow kwam omdat ik de parsing in numpy deed, en hij dus de locaties van de galaxies dus nog numpy integers gebruikte, i.p.v. python integers.

code:

[s]solution_a.py:56: RuntimeWarning: overflow encountered in scalar add[/s]

update na wat benchmarking: De sortering die ik nodig heb is inderdaad de "bottleneck". Ik zie wel hoe het anders kan, maar dan moet ik de parsen veranderen, en daar heb ik nu even geen zin in
Maar leuke uitdaging, even goed nadenken over hoe het nog efficienter kan

[ Voor 18% gewijzigd door FCA op 11-12-2023 20:11 ]

[arnold_m]

Soultaker schreef op maandag 11 december 2023 @ 07:59:
Extra uitdaging voor dag 11: aoc-2023-day-11-challenge-3.zip. Laatste vijf cijfers van de antwoorden:

aoc-2023-day-11-challenge-1.in:
...77330
...13428

aoc-2023-day-11-challenge-2.in:
...58190
...20490

aoc-2023-day-11-challenge-3.in:
...72698
...83738

Hint: voor de grootste invoerbestanden heb je een efficiënte oplossing nodig. Als mensen interesse hebben kan ik (later) uitleggen hoe dat moet, voor wie er zelf niet uitkomt, want het is een techniek die wel vaker van pas komt, en dus nuttig is om te leren.

Leuke uitdaging. Ik heb mijn programmaatje nog wat verder geoptimaliseerd en krijg het antwoord op de derde opgave in ongeveer 0,3 seconde met Rust.

[Soultaker]

MatHack schreef op maandag 11 december 2023 @ 17:34:
Ja, zelfde uitkomst als @MadEgg (daarna moest ik weer voor studie bezig), ik ben wel benieuwd naar je uitleg voor een betere/snellere oplossing.

Hier een O(N) oplossing met (veel) uitleg: snel-met-uitleg.py (spoilers, obviously).

14 regels code, 114 regels commentaar Ik hoop dat het duidelijk is hoe het werkt; als er nog vragen zijn, laat dan maar weten.

spoiler:

De twee technieken die vaker bruikbaar zijn, zijn het opsplitsen van de berekening in x- en y-coördinaten apart, en het berekenen van de afstanden tussen alle paren van coördinaten in lineaire i.p.v. kwadratische tijd.

FCA schreef op maandag 11 december 2023 @ 19:39:
Hmm... ben wel benieuwd wat er bij deel 3 nog efficienter kan.

Ik heb een O(N) algoritme geïmplementeerd. De gewone versie draait in ongeveer 1.5 seconde, maar dat is >90% parsen. Ik heb een versie die parsen in numpy doet (maar de berekening niet, vanwege integer overlow, zoals je opmerkte) en die doet deel 3 in ~250 ms. Er valt dus nog wel wat te optimaliseren

De logica van de drie data sets was:

1. Deel 1 is nog te brute forcen.
2. Deel 2 vereist een efficiënte oplossing, maar 64-bit integers volstaan (b.v. NumPy of Java zonder BigInts).
3. Deel 3 is groter dan deel 2 en vereist bigints of tenminste 128-bit integers.

Maar leuke uitdaging, even goed nadenken over hoe het nog efficienter kan

Denk er nog even over na, dan kom je er waarschijnlijk wel uit! Zoniet, zie dan de link hierboven.

arnold_m schreef op maandag 11 december 2023 @ 20:08:
Leuke uitdaging. Ik heb mijn programmaatje nog wat verder geoptimaliseerd en krijg het antwoord op de derde opgave in ongeveer 0,3 seconde met Rust.

Heel goed! De eerste echt efficiënte oplossing denk ik.

[Creepy]

Dat viel weer mee vandaag: https://github.com/CodeEn...3/blob/main/days/Day11.go

spoiler:

Gelijk gaan rekenen met coordinaten en los bijhouden welke rijen en colommen nog moeten expanderen. Dat controleren voor alle rijen en colommen tussen de beide galaxies en klaar. Deel 2 was dan ook een formaliteit.

Het kan nog optimaler door slimmer bij te houden wat er moet expanderen maar dit was al goed genoeg

[MatHack]

Soultaker schreef op maandag 11 december 2023 @ 20:20:
[...]


Hier een O(N) oplossing met (veel) uitleg: snel-met-uitleg.py (spoilers, obviously).

14 regels code, 114 regels commentaar Ik hoop dat het duidelijk is hoe het werkt; als er nog vragen zijn, laat dan maar weten.

spoiler:

De twee technieken die vaker bruikbaar zijn, zijn het opsplitsen van de berekening in x- en y-coördinaten apart, en het berekenen van de afstanden tussen alle paren van coördinaten in lineaire i.p.v. kwadratische tijd.

Bedankt, goed uitgelegd, ik snap het helemaal, maar ik was hier zelf niet opgekomen. Ik heb de meeste van deze zaken wel tijdens een van mijn studies gehad (deels zelfs recentelijk), maar doe in de praktijk hier nauwelijks iets mee, en dan zakt het weg. En zeker het combineren van een aantal zaken was ik niet opgekomen. Dat is deels ook waarom ik AoC zo leuk vind, heb je toch nog een keer wat aan de kennis, en je leert toch nog steeds iets bij .

[FCA]

Soultaker schreef op maandag 11 december 2023 @ 20:20:
[...]


Hier een O(N) oplossing met (veel) uitleg: snel-met-uitleg.py (spoilers, obviously).

14 regels code, 114 regels commentaar Ik hoop dat het duidelijk is hoe het werkt; als er nog vragen zijn, laat dan maar weten.

spoiler:

De twee technieken die vaker bruikbaar zijn, zijn het opsplitsen van de berekening in x- en y-coördinaten apart, en het berekenen van de afstanden tussen alle paren van coördinaten in lineaire i.p.v. kwadratische tijd.

[...]

Ik heb een O(N) algoritme geïmplementeerd. De gewone versie draait in ongeveer 1.5 seconde, maar dat is >90% parsen. Ik heb een versie die parsen in numpy doet (maar de berekening niet, vanwege integer overlow, zoals je opmerkte) en die doet deel 3 in ~250 ms. Er valt dus nog wel wat te optimaliseren

Grappig, ik had een net iets andere aanpak bedacht:

spoiler:

inderdaad opslitsen in x en y, en dan een sliding window: begin met de som van alles alle elementen min de eerste, daarna pop je de eerste eruit, en trek je de lengte van de overgebleven lijst+1 eraf, maal het verschil tussen de eerste en 2e element. De ordening is O(n log n), maar volgens mij krijg je dat bij het parsen for free. Volgens is er trouwens ook een relatie tussen de oplossing van deel 1 en deel 2, waarmee je deel 2 direct zou kunnen berekenen als je deel 1 weet.

[.oisyn]

day11 in Rust
Time spent: 304.5µs 91.0µs

[ Voor 11% gewijzigd door .oisyn op 11-12-2023 22:39 ]

[MadEgg]

Soultaker schreef op maandag 11 december 2023 @ 20:20:
[...]


Hier een O(N) oplossing met (veel) uitleg: snel-met-uitleg.py (spoilers, obviously).

14 regels code, 114 regels commentaar Ik hoop dat het duidelijk is hoe het werkt; als er nog vragen zijn, laat dan maar weten.

spoiler:

De twee technieken die vaker bruikbaar zijn, zijn het opsplitsen van de berekening in x- en y-coördinaten apart, en het berekenen van de afstanden tussen alle paren van coördinaten in lineaire i.p.v. kwadratische tijd.

Nice! Ik heb 'm in Kotlin geimplementeerd. Maar voor de grootste dataset moet ik wel uitwijken naar BigIntegers, dat komt de performance alsnog niet ten goede. Doet er alsnog 5.6 seconde over, maar stuk beter dan de urenlange versie eerder waar nog niet eens een antwoord uitkwam

Ik denk niet dat ik snel tot deze oplossing was gekomen. Misschien als ervoor betaald werd

[ Voor 4% gewijzigd door MadEgg op 11-12-2023 22:36 ]

[DizzyVacation]

Soultaker schreef op maandag 11 december 2023 @ 20:20:
[...]


Hier een O(N) oplossing met (veel) uitleg: snel-met-uitleg.py (spoilers, obviously).

14 regels code, 114 regels commentaar Ik hoop dat het duidelijk is hoe het werkt; als er nog vragen zijn, laat dan maar weten.

spoiler:

De twee technieken die vaker bruikbaar zijn, zijn het opsplitsen van de berekening in x- en y-coördinaten apart, en het berekenen van de afstanden tussen alle paren van coördinaten in lineaire i.p.v. kwadratische tijd.

[...]

Ik heb een O(N) algoritme geïmplementeerd. De gewone versie draait in ongeveer 1.5 seconde, maar dat is >90% parsen. Ik heb een versie die parsen in numpy doet (maar de berekening niet, vanwege integer overlow, zoals je opmerkte) en die doet deel 3 in ~250 ms. Er valt dus nog wel wat te optimaliseren

De logica van de drie data sets was:

1. Deel 1 is nog te brute forcen.
2. Deel 2 vereist een efficiënte oplossing, maar 64-bit integers volstaan (b.v. NumPy of Java zonder BigInts).
3. Deel 3 is groter dan deel 2 en vereist bigints of tenminste 128-bit integers.

[...]

Denk er nog even over na, dan kom je er waarschijnlijk wel uit! Zoniet, zie dan de link hierboven.


[...]

Heel goed! De eerste echt efficiënte oplossing denk ik.

Na initieel de voor de hand liggende aanpak kwam ik ook op zoiets uit.

spoiler:

Alleen transleer ik geen coördinaten maar bereken ze aan de hand van de afstand tussen 2 opeenvolgende galaxy coördinaten.
if steps > 0: distance = (steps - 1) * expansion * path_count + path_count

Dat zijn nogal wat loops in jouw versie die daarvoor nodig zijn, mijn versie is een factor 3 sneller met de challenge 3 file.

[.oisyn]

Soultaker schreef op maandag 11 december 2023 @ 07:59:
Extra uitdaging voor dag 11: aoc-2023-day-11-challenge-3.zip. Laatste vijf cijfers van de antwoorden:

aoc-2023-day-11-challenge-1.in:
...77330
...13428

aoc-2023-day-11-challenge-2.in:
...58190
...20490

aoc-2023-day-11-challenge-3.in:
...72698
...83738

Hint: voor de grootste invoerbestanden heb je een efficiënte oplossing nodig. Als mensen interesse hebben kan ik (later) uitleggen hoe dat moet, voor wie er zelf niet uitkomt, want het is een techniek die wel vaker van pas komt, en dus nuttig is om te leren.

edit:
Uitleg hier: snel-met-uitleg.py (spoilers!)

resp. 394µs, 7,1ms en 171,5ms

[MueR]

Eigenlijk vind ik dat we @Soultaker wel een applausje mogen geven voor zijn dagelijkse extra inputs om het moeilijker te maken danwel onze oplossingen te testen, maar ook voor dit soort dingen.

Alle oplossingen die door iedereen worden gedeeld kunnen anderen helpen om betere programmeurs te worden, maar dit soort dingen steken er imo wel met kop en schouders bovenuit. Ook al is het python...

[.oisyn]

Helemaal mee eens, al zou ik @Soultaker wel willen vragen wat langer te wachten met dit soort uitleg zodat iedereen een kans krijgt om er een plasje over te doen

.edit: oh wacht ik keek verkeerd, de uitleg is pas 's avonds gepost. Dan heb ik niets gezegd

[ Voor 22% gewijzigd door .oisyn op 12-12-2023 01:48 ]

[Soultaker]

Woei! Nummer 8 op het leaderboard van vandaag!

spoiler:

Deze keer hielp het om gelijk de efficiënte oplossing te implementeren onder de aanname dat deel 2 hetzelfde zou zijn als deel 1, alleen dan met grotere invoer.

[Varienaja]

Soultaker schreef op dinsdag 12 december 2023 @ 06:13:
Woei! Nummer 8 op het leaderboard van vandaag!

Goed man! Ik heb ellendig lang zitten klooien met het bitfucking voor deel A. Nachtjes overslaan doet de concentratie geen goed.

[MatHack]

Pff... mijn tijd voor vanochtend is op, maar ik ben nog niet eens voorbij deel 1 van vandaag Ik heb wel een oplossing die werkt voor de testset (in 300 ms, wat naar mijn mening al te veel is), maar de performance met de echte set is om te huilen.

spoiler:

Eerste oplossing was door de groepen te vinden die corrupt waren en dan matching te doen met de gegeven cijfers, maar naar een deel van deze oplossing geschreven te hebben liep ik tegen problemen aan met de herkenning van welke groep wat is, etc.

Tweede oplossing (werkend voor testset) is door te bepalen hoeveel # en . ik moet zetten op de plekken van de ? en vervolgens alle permutaties van deze set van ? en . bepalen. Voor elke permutatie vervang ik vervolgens de Xde ? met Xde teken uit de permutatie en test hierna of dit een valide oplossing is voor de gegeven cijfers.

Ik snap dat je # en . ook als 1 en 0 kunt zien en dat dus als binaire getallen gezien kunnen worden, maar ik zie nog niet in hoe me dit kan helpen bij de oplossing.

[MrHaas]

Soultaker schreef op dinsdag 12 december 2023 @ 06:13:
Woei! Nummer 8 op het leaderboard van vandaag!

spoiler:

Deze keer hielp het om gelijk de efficiënte oplossing te implementeren onder de aanname dat deel 2 hetzelfde zou zijn als deel 1, alleen dan met grotere invoer.

Netjes!

spoiler:

Ik heb het zelf vandaag met dynamic programming opgelost wat ook direct werkte op deel 2, maar er zijn ws wel betere/snellere methodes:
https://github.com/arjand...oc_2023/day12/solution.py

[Mugwump]

Pff ik had gehoopt op een makkie want ik werd wakker met knallende koppijn, moest nog even een productierelease doen en ben best druk vandaag. De paracetamol begint zo langzamerhand te werken, dus zo maar even een frisse blik op werpen.

spoiler:

Ik begin wel met domweg alle permutaties berekenen en filteren op geldigheid. Dat zal vast niet performen, maar premature optimizations enzo.

[.oisyn]

Zo, sloeg ik daar een verkeerde weg in, zeg. Wat nogal dom is, want ik heb een keer een nonogram solver gemaakt
Time spent: 35920.6µs

Good enough .

MatHack schreef op dinsdag 12 december 2023 @ 08:41:
Pff... mijn tijd voor vanochtend is op, maar ik ben nog niet eens voorbij deel 1 van vandaag Ik heb wel een oplossing die werkt voor de testset (in 300 ms, wat naar mijn mening al te veel is), maar de performance met de echte set is om te huilen.

spoiler:

Eerste oplossing was door de groepen te vinden die corrupt waren en dan matching te doen met de gegeven cijfers, maar naar een deel van deze oplossing geschreven te hebben liep ik tegen problemen aan met de herkenning van welke groep wat is, etc.

Tweede oplossing (werkend voor testset) is door te bepalen hoeveel # en . ik moet zetten op de plekken van de ? en vervolgens alle permutaties van deze set van ? en . bepalen. Voor elke permutatie vervang ik vervolgens de Xde ? met Xde teken uit de permutatie en test hierna of dit een valide oplossing is voor de gegeven cijfers.

Ik snap dat je # en . ook als 1 en 0 kunt zien en dat dus als binaire getallen gezien kunnen worden, maar ik zie nog niet in hoe me dit kan helpen bij de oplossing.

spoiler:

^^ dit dus. Het probleem met het testen van permutaties is dat je zo enorm veel werk dubbel loopt te doen. Bijvoorbeeld, als de eerste zowel op plek 0 als op plek 1 past, en voor de rest heb je in beide gevallen N dezelfde valide permutaties, dan doorloop je dus 2*N permutaties, terwijl die 2e N voor de rest exact identiek zijn aan de eerste N. En ik kan je alvast vertellen dat het antwoord voor deel 2 niet in een u32 past

[ Voor 6% gewijzigd door .oisyn op 12-12-2023 12:27 ]

[P_Tingen]

[dag 10]
Nog een nabrander van dag 10. In totaal drie of vier keer helemaal herschreven, maar uiteindelijk gehaald dankzij een tip van een collega.

spoiler:

Ik gebruik de van-links-naar-rechts scanmethode maar zat eerst verkeerd omdat ik vergeten was alle elementen uit het grid te verwijderen die niet onderdeel van de pipe zijn. Dat vertroebelt je uitkomst nogal namelijk

[dag 11]
Bij deel 1 had ik al een vermoeden waar deel 2 heen zou gaan (sleutelwoord: galaxy) dus ik had daar maar een wat nette richting gekozen. Goede keuze, want deel 2 was toen een fluitje van een cent.

[dag 12]
tijd is op.....

[Soultaker]

Dag 11:

FCA schreef op maandag 11 december 2023 @ 21:40:
[...]

spoiler:

Volgens is er trouwens ook een relatie tussen de oplossing van deel 1 en deel 2, waarmee je deel 2 direct zou kunnen berekenen als je deel 1 weet.

Oh dit is eigenlijk een heel goede observatie! Dat ik had ik me helemaal niet geraliseerd. Je kunt inderdaad het volgende doen:

spoiler:

x = antwoord zonder expansion
y = antwoord met expansion van 1 naar 2 (deel 1 van het probleem)
z = antwoord met expansion van 1 naar 1000000 (deel 2 van het probleem)

Dan geldt: z = x + (y - x)*999999

Dus als je deel 1 hebt opgelost (zelfs met brute force) kun je het antwoord voor deel 2 eenvoudig berekenen, zonder een regel nieuwe code te hoeven schrijven!

DizzyVacation schreef op maandag 11 december 2023 @ 22:56:
Na initieel de voor de hand liggende aanpak kwam ik ook op zoiets uit.

spoiler:

Alleen transleer ik geen coördinaten maar bereken ze aan de hand van de afstand tussen 2 opeenvolgende galaxy coördinaten.
if steps > 0: distance = (steps - 1) * expansion * path_count + path_count

Dat zijn nogal wat loops in jouw versie die daarvoor nodig zijn, mijn versie is een factor 3 sneller met de challenge 3 file.

Er zijn een aantal variaties op het thema mogelijk. De code die ik postte was vooral ontworpen om zo eenvoudig mogelijk te begrijpen te zijn, niet per se het snelste om uit te voeren.

De eerste versie die ik schreef is deze: fast.py. Die berekent eerst het aantal sterrenstelsels per rij en kolom. De daadwerkelijke berekening in SolveAxis() combineert het vertalen van coördinaten met het sommeren van afstanden, en loopt in O(N), dus O(H + W) voor de rijen én kolommen. Maar omdat het parsen van de invoer noodzakelijkerwijs O(HW) kost, domineert dat de rekentijd voor grote invoer.

Ik heb ook nog een versie die het parsen (het O(HW) deel) met numpy doet wat het geheel behoorlijk sneller maakt: fast-numpy.py.

MueR schreef op dinsdag 12 december 2023 @ 00:03:
Eigenlijk vind ik dat we @Soultaker wel een applausje mogen geven voor zijn dagelijkse extra inputs om het moeilijker te maken danwel onze oplossingen te testen, maar ook voor dit soort dingen.

Bedankt! Fijn om te horen dat het gewaardeerd wordt! Al heb ik dit jaar niet zoveel custom inputs gepost als vorig jaar. (Ik merkte dat mensen afhaken wanneer ze té ingewikkeld worden.)

Ook al is het python...

HEE! Dat is wel onze nationale programmeertaal hè!

[ Voor 16% gewijzigd door Soultaker op 12-12-2023 12:23 ]

[Soultaker]

Dag 12:

Ik denk dat een hoop mensen dit probleem lastig zullen vinden.

MrHaas schreef op dinsdag 12 december 2023 @ 08:42:

spoiler:

Ik heb het zelf vandaag met dynamic programming opgelost wat ook direct werkte op deel 2, maar er zijn ws wel betere/snellere methodes:
https://github.com/arjand...oc_2023/day12/solution.py

Ik heb in essentie hetzelfde gedaan. (Python code). Voor mensen die zich afvragen hoe dit werkt:

spoiler:

Het idee is dat je de mogelijke strings recursief kunt construeren. Je begint met een lege string. Dan voeg je ofwel een enkele '.' toe (wat kan als het patroon met '.' of '?' begint), of een fragment "###." waarbij het aantal hekjes overeenkomt met het volgende getal in de lijst (wat kan als het patroon uit hekjes/vraagtekens gevolgd door een punt/vraagteken bestaat). En dan zo door tot je het eind van het patroon en de lijst getallen bereikt hebt.

Er is één randgeval: aan het eind van de string hoef je geen punt toe te voegen (je kunt eindigen met "###", het hoeft niet "###." te zijn). Ik heb dat opgelost door simpelweg een '.' aan het einde van het patroon toe te voegen, wat voor voor het aantal oplossingen niet uit maakt.

Op elk moment heb je twee opties om tussen te kiezen ("." of "###."). Daardoor draait het algoritme in O(N + M + 2^Q) tijd per regel, waarbij N de lengte van het patroon is, M het aantal getallen, en Q het aantal vraagtekens in het patroon. Dit werkt goed genoeg voor deel 1, aangezien het maximaal aantal vraagtekens in een patroon 18 is (2¹⁸ = 262.144, wat niet enorm veel is voor een computer).

Voor deel 2 is de factor 2^Q problematisch (18×5 = 90, 2⁹⁰ = 1.237.940.039.285.380.274.899.124.224 wat ietsje pietsje groter is dan je redelijkerwijs kunt bruteforcen). Maar dat is eenvoudig op te lossen met memoization, wat is wat de @cache decorator in Python doet. De Calc() functie heeft twee argumenten: i, de positie in het patroon, en j, de positie in de lijst met getallen, en retourneert het aantal mogelijkheden om het patroon vanaf positie i in te vullen met de getallen vanaf positie j. Het aantal unieke aanroepen is dus hooguit NM, ongeacht het aantal vraagtekens (Q).

De werkelijke complexiteit is iets hoger dan O(NM) omdat de implementatie zelf niet in constante tijd loopt, maar close enough voor de officiële testdata die niet belachelijk groot is.

[ Voor 5% gewijzigd door Soultaker op 12-12-2023 12:58 ]

[FrankMennink]

Even inhalen:

Day 9 in Python

Dacht hier eerst veel te moeilijk over

spoiler:

ik probeerde een polynomiale functie op te stellen, daar is mijn wiskunde absoluut niet sterk genoeg voor bleek wel. Daarna maar de naieve approach gepakt en gewoon domweg geimplementeerd wat er gevraagd werd. Dat bleek ruim voldoende

Day 10 in Python

Leuke puzzel, had voor deel 2 wel de hint nodig

spoiler:

dat je alleen maar de muren |,L,J (en S als S origineel een van die drie is) aan de linker kant hoefde te tellen, oneven = in en even = uit

Day 11 in Python

Ben wel blij dat ik deze gelijk op de juiste manier (

spoiler:

alleen een lijst met galaxies bijhouden en daar de expansion op uitvoeren

) heb gedaan, daarna was deel 2 alleen de expansie factor aanpassen en het antwoord rolde er uit.

spoiler:

Uiteraard ook tegen de 1000000 vs 999999 aangelopen, off-by-1 errors Had wel al zo'n vermoeden dus kostte me een minuutje of te verifieren en dan wachten op de AoC cooldown

Day 12 in Python

Het kan vast mooier, beter, sneller etc maar deel 2 runt in onder 400ms, dus ik ben tevreden voor nu. Ik blijf dit topic wel in de gaten houden voor wat de rest er van maakt

spoiler:

functools cache