Advent of Code 2023

[Varienaja]

Lollig. Nog niemand die het

spoiler:

Wikipedia: Girvan–Newman algorithm

algoritme gebruikt heeft?

[Soultaker]

Gebruikt? Ik had er nog nooit van gehoord

[Varienaja]

Soultaker schreef op maandag 25 december 2023 @ 12:39:
Gebruikt? Ik had er nog nooit van gehoord

Ik natuurlijk ook niet tot vanmorgen.

[.oisyn]

Grappig, de puzzel van vandaag is precies iets waar ik afgelopen tijd op m'n werk mee bezig ben geweest

spoiler:

Namelijk het partitioneren van een graaf in N delen waarbij je de edge cut minimaliseert. Ik gebruik daar een library voor. Zou wel flauw zijn om die gewoon aan te slingeren

Hier trouwens een representatie van het voorbeeld waarin het op het oog direct duidelijk is welke je moet knippen.

[ Voor 43% gewijzigd door .oisyn op 25-12-2023 14:13 ]

[Bolukan]

The End

spoiler: day 25

Ik heb alle bovengenoemde wiki's gevonden en doorgelezen, maar ik snapte het idee maar half en had de energie niet (day 24 nam ook wat tijd) om die rabbit hole te bewandelen.
Dus gezocht naar een short-cut en net als @Remcoder de zwakste schakels opgezocht, verwijderd uit de graph en toen bleken xxx items opeens op distance Infinity te zitten.

Snel de BIG RED BUTTON ingedrukt en de global snow production is hersteld. Eind goed al goed. Fijne feestdagen iedereen.

[Daanoz]

Poeh, was een heftige klus dit jaar. Dankzij de switch naar een andere taal wel eindelijk een keertje de 1 second challenge gehaald . Was even bang dat het niet ging lukken de laatste paar dagen, maar met wat inspiratie links en rechts genoeg kunnen optimaliseren om eronder te blijven.

code:

$ ./target/release/aoc2023 --all | grep "time: "
Day 1 time: 2.16ms (A: 145.67µs, B: 2.02ms)
Day 2 time: 166.42µs (A: 89.33µs, B: 76.96µs)
Day 3 time: 1.23ms (A: 599.38µs, B: 629.79µs)
Day 4 time: 403.46µs (A: 207.13µs, B: 196.33µs)
Day 5 time: 155.67µs (A: 53.79µs, B: 101.79µs)
Day 6 time: 20.98ms (A: 2.21µs, B: 20.97ms)
Day 7 time: 1.33ms (A: 682.71µs, B: 644.46µs)
Day 8 time: 3.68ms (A: 724.21µs, B: 2.95ms)
Day 9 time: 531.46µs (A: 265.17µs, B: 266.13µs)
Day 10 time: 3.33ms (A: 1.35ms, B: 1.98ms)
Day 11 time: 5.14ms (A: 2.64ms, B: 2.49ms)
Day 12 time: 13.96ms (A: 1.35ms, B: 12.62ms)
Day 13 time: 2.13ms (A: 1.07ms, B: 1.07ms)
Day 14 time: 30.19ms (A: 114.63µs, B: 30.07ms)
Day 15 time: 494.54µs (A: 81.25µs, B: 413.25µs)
Day 16 time: 45.76ms (A: 1.60ms, B: 44.16ms)
Day 17 time: 67.23ms (A: 21.94ms, B: 45.28ms)
Day 18 time: 167.00µs (A: 80.88µs, B: 86.13µs)
Day 19 time: 1.04ms (A: 449.67µs, B: 586.75µs)
Day 20 time: 5.28ms (A: 1.04ms, B: 4.24ms)
Day 21 time: 73.45ms (A: 4.86ms, B: 68.59ms)
Day 22 time: 259.93ms (A: 6.26ms, B: 253.67ms)
Day 23 time: 307.94ms (A: 5.17ms, B: 302.78ms)
Day 24 time: 1.39ms (A: 595.58µs, B: 797.17µs)
Day 25 time: 2.99ms (A: 2.99ms, B: 125.00ns)
Total time: 851.07ms

[Friits]

Update: ik heb vanochtend volgens mij te ingewikkeld gedacht... wat denken jullie van de volgende aanpak:

spoiler:

We definiëren de twee componenten als S en (impliciet) G \ S. We willen dat S slechts knopen bevat zodat er exact drie zijden zijn tussen S en G \ S.

De knoop in S met de meeste buren in G \ S hoort waarschijnlijk niet thuis S, dus we verwijderen we deze uit S. Dit herhalen we tot er precies drie zijden zijn tussen de componenten.

Code

Dit werkt op de voorbeeld-input en mijn eigen input, maar het klinkt te mooi (te eenvoudig) om volledig correct te zijn... ziet iemand waar mijn denkfout zit?

[Diderikdm]

Friits schreef op dinsdag 26 december 2023 @ 00:35:
Update: ik heb vanochtend volgens mij te ingewikkeld gedacht... wat denken jullie van de volgende aanpak:

spoiler:

We definiëren de twee componenten als S en (impliciet) G \ S. We willen dat S slechts knopen bevat zodat er exact drie zijden zijn tussen S en G \ S.

De knoop in S met de meeste buren in G \ S hoort waarschijnlijk niet thuis S, dus we verwijderen we deze uit S. Dit herhalen we tot er precies drie zijden zijn tussen de componenten.

Code

Dit werkt op de voorbeeld-input en mijn eigen input, maar het klinkt te mooi (te eenvoudig) om volledig correct te zijn... ziet iemand waar mijn denkfout zit?

Het minimaal aantal buren is 4 (aldus mijn debug, iig zo zou ik het geloven) dus je hebt altijd alsnog een overlap van 3 welke je zou moeten vergelijken op cycles. Lastige is dat zolang je niet prunet op de drie punten welke je wilt alles connected blijft.

[.oisyn]

Day25 in Rust
29381.9µs

spoiler:

Voordat ik het register opentrok met een min-cut algoritme wilde ik eerst zelf wat aankloten. Ik heb een hele vieze oplossing. Voor alle edges check ik hoe lang een loopje minimaal is voor je weer bij dezelfde edge aankomt. Of anders gezegd, het kortste pad van A naar B zonder gebruik te maken van edge AB. Het euvel wil dat zowel in het voorbeeld als in de officiele input, de edges die je door moet knippen een veel langer loopje hebben dan de rest van de edges. Daarna brute-force ik het op volgorde van de loop-grootte, maar die vindt dus in deze datasets direct het antwoord bij de eerste poging.

.edit:

spoiler:

Ah volgens mij precies wat @Remcoder ook doet

[ Voor 10% gewijzigd door .oisyn op 26-12-2023 02:44 ]

[Asgardian28]

Ik heb de afgelopen jaren altijd wat burnout, het is best zwaar als er een paar krakers op een rij tussen zitten. Elk jaar denk ik dit is de laatste keer dat ik voor lb ga, volgend jaar relaxed aan en mooie code schrijven. Maar dan begint het in November toch weer te kriebelen.

[Bolukan]

Ik ben gisteravond door mijn repositories gegaan en heb alles van AOC bij elkaar gezet. Niet elk jaar meegedaan of afgemaakt, maar ik heb bewaard een jaar met C# (2016), met C++ gedraaid op een ESP32 MCU (2019), met Excel (2020) en vorig jaar (maar paar dagen) en dit jaar met Python. Misschien ook eens naar Rust en Go kijken.

[Soultaker]

Friits schreef op dinsdag 26 december 2023 @ 00:35:
Update: ik heb vanochtend volgens mij te ingewikkeld gedacht... wat denken jullie van de volgende aanpak:

spoiler:

We definiëren de twee componenten als S en (impliciet) G \ S. We willen dat S slechts knopen bevat zodat er exact drie zijden zijn tussen S en G \ S.

De knoop in S met de meeste buren in G \ S hoort waarschijnlijk niet thuis S, dus we verwijderen we deze uit S. Dit herhalen we tot er precies drie zijden zijn tussen de componenten.

Code

Dit werkt op de voorbeeld-input en mijn eigen input, maar het klinkt te mooi (te eenvoudig) om volledig correct te zijn... ziet iemand waar mijn denkfout zit?

Interessant idee! Het werkt vast op de officiële invoer die een bepaalde structuur heeft, maar zoals veel greedy algoritmes kan het soms een suboptimale oplossing geven.

Je had je code ook kunnen testen op mijn extra testinvoer, daar gaat 'ie op de eerste invoer al mis

spoiler:

Het deel van de logica dat correct is, is: als een knoop v in S meer dan drie verbindingen heeft met knopen in S \ G, dan hoort v niet in S thuis en kun je 'm verwijderen. Het probleem is dat het kan voorkomen dat geen enkele individuele knoop meer dan 3 verbindingen heeft, terwijl het totaal aantal verbindingen tussen S en S \ G nog wel groter dan 3 is, en dan kies je een willekeurige knoop, die mogelijk wel in S moet blijven.

Hier is een concreet tegenvoorbeeld:

a: b c d g
b: c d g
c: d e
d: f
e: f g h
f: g h
g: h

Dat ziet er zo uit:


Het is duidelijk dat de componenten A = {a, b, c, d, e, f, g} en B = {h} zijn. Als je code toevallig begint met het verwijderen van e, f en g zodat S = {a, b, c, d, h} (wat consistent is met de regels), dan zul je vervolgens h willen verwijderen: h heeft immers exact 3 verbindingen met {e, f, g}, terwijl {a, b, c, d} er elk maar 1 hebben. Dan concludeer je ten onrechte dat h niet in S thuishoort, terwijl je juist met S={h} wil eindigen. Wanneer je eenmaal zo'n fout maakt is het onmogelijk die te herstellen.

Grappig genoeg geeft je code op bovenstaande voorbeeld soms wel het goede antwoord, afhankelijk van waar je toevallig begint. Blijkbaar is het een randomized algoritme, omdat in Python de volgorde van elementen in een set() niet alleen ongedefinieerd is, maar actief gerandomized wordt, zodat elke run de volgorde anders is (wat ik me niet gerealiseerd had).

[Friits]

Thanks voor de uitleg. Mijn aanpak leek al te mooi (te eenvoudig) om volledig correct te zijn. Gelukkig werkt 'ie prima op de officiële AoC inputs, en in het uitzonderlijke geval dat 'ie de mist in gaat kan ik 'm gewoon opnieuw draaien. Het is een voor een puzzeltje, niet mission-critical software

Soultaker schreef op dinsdag 26 december 2023 @ 11:10:
omdat in Python de volgorde van elementen in een set() niet alleen ongedefinieerd is, maar actief gerandomized wordt, zodat elke run de volgorde anders is (wat ik me niet gerealiseerd had).

Klopt, dit is er aan de hand:

Elementen worden in een set geplaatst op basis van hun hash. Sinds 3.3 wordt er bij het hashen van strings een seed gebruikt voor security-redenen. Die seed wordt random gekozen wanneer de interpreter opstart.

Je kan dit uitzetten met export PYTHONHASHSEED=0, en dan zal de volgorde ook tussen runs gelijk zijn.

[ Voor 6% gewijzigd door Friits op 26-12-2023 13:12 ]

[Bolukan]

De volgorde van de insert in een set wordt sinds 3.7 vastgehouden en kan met list(set) worden gebruikt.

[Friits]

Weet je het zeker?

code:

>>> s=set()
>>> s.add('a')
>>> s.add('b')
>>> s.add('c')
>>> list(s)
['b', 'c', 'a']

Voor zover ik weet geldt dit alleen voor dictionaries, en niet voor sets.

[ Voor 44% gewijzigd door Friits op 26-12-2023 13:37 ]

[Bolukan]

Je hebt gelijk, ik zat hier fout. Uit de release notes 3.7:
"the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec."

Hoewel mijn output in de juiste 17% valt:

Python:

{'a', 'b', 'c'}

[ Voor 18% gewijzigd door Bolukan op 26-12-2023 23:09 ]

[Corniel]

Ik hèb dat 24 opgelost (niet op de manier die ik wilde), daarom een vraag:

spoiler:

Ik heb 1 paar van hails waarbij zowel de dX, als de dZ gelijk zijn, hebben jullie die ook, of is dat toeval?

[Soultaker]

Corniel schreef op woensdag 27 december 2023 @ 08:26:

spoiler: dag 24

Ik heb 1 paar van hails waarbij zowel de dX, als de dZ gelijk zijn, hebben jullie die ook, of is dat toeval?

spoiler: dag 24

Dat was me in mijn invoer ook opgevallen (exact 1 paar), dus mogelijk was dat opzet. Ik kon er verder niet zoveel mee. Heb je het nog ergens voor gebruikt?

[.oisyn]

spoiler: dag24

Ik gebruik dus het gegeven dat sommige paren dezelfde snelheid op een bepaalde as hebben.

Ik zat te denken dat je dezelfde oplossing kunt gebruiken zonder paren van hagels te hebben in de input waarvoor dat geldt, door gebruik te maken van lineaire transformaties.

Bijvoorbeeld, in 2d, stel je hebt een steen met snelheid (0, 1) en een steen met snelheid (1,0). Als je dat transformeert naar een stelsel met als basis-assen (1,0) en (-1, 1), dan worden de snelheden in dit nieuwe stelsel respectievelijk (1,0) en (1,1) en dan heb je dus een paar met gelijke snelheid op de nieuwe x-as.

Je moet alleen wel oppassen dat je geen non-integer antwoorden krijgt. Volgens mij is dat wel op te lossen.

.edit:

spoiler:

Heb even zitten pieken met een online matrix calculator op m'n telefoon. In dit specifieke voorbeeld is de transformatiematrix zijn eigen inverse, dus alle transformaties vallen in Z . Waar je specifiek naar moet kijken is de determinant van de matrix, daar zul je door moeten delen bij het terugtransformeren. Dus de resultaten die je berekent in de getransformeerde ruimte moeten een veelvoud zijn van de determinant.

[ Voor 23% gewijzigd door .oisyn op 27-12-2023 10:15 ]

[Soultaker]

Beetje laten reactie, maar ik had nu pas tijd om deze slimme oplossing goed genoeg te bestuderen dat ik 'm ook volledig begrijp:

.oisyn schreef op zaterdag 23 december 2023 @ 20:03:
Zo, hèhè, eindelijk even tijd gehad om de bug uit mijn day22 algo te halen
[..]

spoiler:

Voor deel 2 doe ik 2 passes.

In de eerste pass bepaal ik welke steen je moet omgooien om een steen te laten vallen. Hierbij heb je gegevens nodig over op welke stenen een steen rust. Ik werk van onder naar boven (stenen gesorteerd op minimale y-waarde). Voor elke steen voeg ik de stenen waar de steen op rust toe aan een max-queue. Dan pop ik steeds een waarde van de max-queue en vervang die met de steen die die steen doet laten vallen (die ik dan al weet, want die zijn lager dus die zijn al aan de beurt geweest). Als er maar 1 entry in de lijst zit, dan valt de steen bij het verwijderen van die ene steen in de lijst. Als we een steen bereiken die nooit kan vallen (omdat hij op de grond staat) met meerdere stenen in de queue, dan kan deze steen ook niet vallen.

Dit is heel slim gevonden en werkt heel goed voor alle drie van mijn testcases, maar het is helaas worst case nog steeds een kwadratisch algoritme.

Als je bijvoorbeeld aan aoc-2023-day-22-challenge-3.txt één regel toevoegt:

1,42,2~7,42,2

Dan gaat de runtime van ~400 ms naar ~7 minuten

Ter vergelijking, mijn snelle oplossing gebaseerd op

spoiler:

lowest common ancestors

runt deel 2 in O(V + E log V) tijd, waarbij V het aantal blokjes in de invoer is, en E het aantal paren van blokjes dat elkaar raakt.

spoiler:

Dan heb ik een lijstje met wanneer elke steen valt. Voor de tweede pass maak ik een nieuw lijstje; hoeveel stenen er vallen bij het omgooien van elke steen. Nu loop van boven naar onderen, waarbij ik steeds 1 + het aantal stenen dat valt bij omgooien van deze steen, optel bij de steen die deze steen doet laten vallen. Het antwoord van deel twee is de som van dit lijstje.

spoiler:

Hier doen we bijna precies hetzelfde, maar net wat anders. We hebben dezelfde informatie berekend: wat bij jou fall_at[x] heet, heet bij mij Parent(x).

fall_at[x] = Parent(x) = y zodat y het hoogstgelegen bokje is dat blokje x doet vallen. Deze relatie is logischerwijs transitief (als x valt wanneer y valt, en y valt wanneer z valt, dan valt x ook wanneer z valt). Je kunt het dus zien als een boomstructuur (vandaar Parent()) en dan is het antwoord op deel 2 simpelweg het aantal paren (x, y) in de boom zodat y een voorouder is van x.

Om dat aantal paren te berekenen neem jij de som van de groottes van de deelbomen (i.e., als ik dit blokje weghaal, hoeveel hogergelegen blokjes vallen er dan) wat je berekent door bij de bladeren te beginnen en dan naar beneden te werken. Ik bereken juist de som van de diepten van de knooppunten (i.e., hoeveel lagergelegen blokjes kunnen de val van dit blokje veroorzaken). Het loopt beide in O(N) tijd. Het praktische voordeel van de bottom up approach is dat je maar één pass nodig hebt. Wat niet wil zeggen dat het ook sneller is natuurlijk.

[KabouterSuper]

.oisyn schreef op woensdag 27 december 2023 @ 10:02:

spoiler: dag24

Ik gebruik dus het gegeven dat sommige paren dezelfde snelheid op een bepaalde as hebben.

Ik zat te denken dat je dezelfde oplossing kunt gebruiken zonder paren van hagels te hebben in de input waarvoor dat geldt, door gebruik te maken van lineaire transformaties.

Bijvoorbeeld, in 2d, stel je hebt een steen met snelheid (0, 1) en een steen met snelheid (1,0). Als je dat transformeert naar een stelsel met als basis-assen (1,0) en (-1, 1), dan worden de snelheden in dit nieuwe stelsel respectievelijk (1,0) en (1,1) en dan heb je dus een paar met gelijke snelheid op de nieuwe x-as.

Je moet alleen wel oppassen dat je geen non-integer antwoorden krijgt. Volgens mij is dat wel op te lossen.

.edit:

spoiler:

Heb even zitten pieken met een online matrix calculator op m'n telefoon. In dit specifieke voorbeeld is de transformatiematrix zijn eigen inverse, dus alle transformaties vallen in Z . Waar je specifiek naar moet kijken is de determinant van de matrix, daar zul je door moeten delen bij het terugtransformeren. Dus de resultaten die je berekent in de getransformeerde ruimte moeten een veelvoud zijn van de determinant.

Ik vermoed dat je met deze analyse 98% van je publiek kwijt bent. Maar ik snap waar je naartoe wil. Ik weet niet of het goed komt met de non-integer getallen. Maar dat is een kwestie van proberen. Dat in dit specifieke voorbeeld de inverse de matrix zelf is, is wel bijzonder. Dat betekent dat er ergens een 0° of 180° hoek in zit (het is een transformatiematrix). Ik zou trouwens vooral bezorgd zijn over determinant=0; dit moet je dan apart gaan afvangen.
Ik heb trouwens vooral gewerkt met QR decomposities, eigenvectoren en eigenwaarden. Maar dat lijkt in deze opgave niet de goede aanpak te zijn.

[.oisyn]

KabouterSuper schreef op woensdag 27 december 2023 @ 11:05:
[...]

Ik zou trouwens vooral bezorgd zijn over determinant=0; dit moet je dan apart gaan afvangen.

Dan is er geen inverse en is er een rij of kolom de 0-vector of zijn de assen lineair afhankelijk, dus dat wil je sowieso vermijden

[Corniel]

Soultaker schreef op woensdag 27 december 2023 @ 09:19:

spoiler: dag 24

Dat was me in mijn invoer ook opgevallen (exact 1 paar), dus mogelijk was dat opzet. Ik kon er verder niet zoveel mee. Heb je het nog ergens voor gebruikt?

spoiler:

Nee, ik heb - uiteindelijk - Z3 ingezet, maar ik ben daar niet trots op. Het voelt als valsspelen.

[Marcj]

Na 3 dagen worstelen is dag 24 me ook eindelijk gelukt! Ik wilde het perse zonder hints van hier halen, en het is eindelijk gelukt. Volgens mij ben ik wel tot een aantal vergelijkbare conclusies gekomen als anderen hier. Mijn observaties waarmee het lukte:

spoiler:

1) Je kunt de assen afzonderlijk verkennen om de snelheid te bepalen van de steen die je moet gooien.
2) Ik ging ervan uit dat de snelheid vrij laag zou zijn. Per as zoek ik een paar hagelstenen met dezelfde snelheid op die as. Hiermee test ik elke mogelijk snelheid, aangezien het verschil in snelheden deelbaar moet zijn door het verschil in positie. Deze stap gaat gelukkig vrij vlot.
3) Er is op 1 van de assen 1 hagelsteen met dezelfde snelheid als de snelheid van de steen. Deze kan ik gebruiken om de positie op 1 as alvast te bepalen (is dezelfde positie als die hagelsteen namelijk).
4) Daarna pak ik een hagelsteen met een snelheid die anders is op alle assen. Deze kan ik gebruiken om te bepalen in verhouden to de hagelsteen in stap 3 wat de tijd is waarop de botsing plaats vind.
5) Die tijd kan ik vervolgens gebruiken om terug te rekenen wat de startpositie van de steeds was

Wat een werk zeg...

In verhouding daartoe was dag 25 vrij eenvoudig.

spoiler:

Ik heb blijkbaar een variant gebruikt van een bekend algoritme, waarbij je een heel aantal kortste routes verkent en kijkt welke paden het meeste gebruikt worden. Als je genoeg paden hebt verkend zijn de 3 toppers hiervan duidelijk de split tussen de 2 helften.
Je hoeft trouwens maar een klein deel van de nodes te verkennen hiervoor (ongeveer de wortel van het aantal nodes) om toch al resultaat te krijgen.

[bakkerjangert]

Pfff, eindelijk klaar. Dag 24 deel 2 kostte me wel wat moeite, uiteindelijke opgelost door het geheel om te schrijven naar een lineaire vergelijking met 4 onbekenden.

spoiler:

Deel 1:
Simpel genoeg omschrijven naar een formaat y = ax + b en de snijpunten berekenen. Zie comments in de code voor de uitwerking.

Deel 2:
Starten met 6 onbekenden van de steen. Uitwerken en oplossen in x-y vlak totdat een lineaire vergelijking met 4 onbekenden ontstaat. Deze heb ik opgelost met Numpy. Gelukkig heeft float64 van numpy genoeg precisie, al kom ik niet exact op ....,0 antwoorden. Zelfde aanpak herhalen voor x-z vlak en alle waarden zijn bekend.

Voor de geïnteresseerde hieronder de uitwerkingsstappen, ook te vinden in mijn code.

# Stone X, Y, Z, VX, VY, VZ UPPER = unknowns
# Hail x, y, z, vx, vy, vz lower = knowns
#
# Step 1: Collision of 1 hail with Stone
# X + VX.t1 = x + vx.t1
# t1.VX – t1.vx = x – X
# t1(VX – vx) = (x – X)
# t1 = (x – X)/(VX – vx) Same equations for y and z
# t1 = (y – Y)/(VY – vy)
# t1 = (z – Z)/(VZ – vz)
#
# Step 2: equation in x and y
# (x – X)/(VX – vx) = (y – Y)/(VY – vy)
# (x – X).(VY – vy) = (y – Y).(VX – vx)
# x.VY – x.vy – X.VY + X.vy = y.VX – y.vx – Y.VX + Y.vx
# Y.VX - X.VY = y.VX – y.vx + Y.vx – x.VY + x.vy – X.vy
#
# Note how left-hand side is independent of hail
#
# Step 3: add in another hail, lets say hail[i] and hail[j]
# yi.VX – yi.vxi + Y.vxi – xi.VY + xi.vyi – X.vyi = yj.VX – yj.vxj + Y.vxj – xj.VY + xj.vyj – X.vyj
# X(vyj – vyi) + Y(vxi – vxj) + VX(yi – yj) + VY(xj – xi) = yi.vxi - xi.vyi – yj.vxj + xj.vyj
#
# Note how this is just a linear equation with 4 unknowns
#
# Step 4: Solve Linear equation with 4 unknowns
# Solve with Linear Algebra (Numpy in this case) using multiple lines
#
# Step 5: replace y for z and redo calculation