Advent Of Code 2025

[Reptile209]

Soultaker schreef op zondag 7 december 2025 @ 13:29:
[...]
Dat is letterlijk 21.

spoiler:

Er staat 22 ^ karakters in het grid; de enige met een . erboven is de vijfde op de een na laatste regel, dus 22 - 1 = 21.

Kijk, dat had ik in mijn quick-scan nog niet opgemerkt idd. En meestal worden dat soort zaken juist in het stap-voor-stap voorbeeld uitgewerkt.

[Jelle van Kraaij]

Deel 1 was even goed lezen en nadenken wat ze nou bedoelde en boe is op die 21 komen
Deel 2 stuk langer over gedaan

spoiler:

Recursive zonder caching is niet te doen.
Toen iteratief geprobeerd zonder caching, wel iets sneller, maar duurde nog steeds veel te lang
Dan maar weer alles omgooien naar recursive met caching. Zo dat maakt een enorm verschil
Ik vervang gwn de '^' met de uitgerekende waarde

https://github.com/JellevanKraaij/AoC-2025/tree/main/day07

[Friits]

Leuk puzzeltje vandaag. Mijn oplossing in Python.

Ik vind de puzzels tot nu toe trouwens wel erg makkelijk, zeker gegeven dat we inmiddels over de helft zijn, en het weekend (die waren tijdens eerdere edities altijd moeilijker dan de doordeweekse puzzels). Maar goed, ik vermaak me alsnog prima!

[Jelle van Kraaij]

Friits schreef op zondag 7 december 2025 @ 14:10:
Leuk puzzeltje vandaag. Mijn oplossing in Python.

Ik vind de puzzels tot nu toe trouwens wel erg makkelijk, zeker gegeven dat we inmiddels over de helft zijn, en het weekend (die waren tijdens eerdere edities altijd moeilijker dan de doordeweekse puzzels). Maar goed, ik vermaak me alsnog prima!

PFff sommige mensen kunnen veeel beter puzzelen en python dan mij
Mooi gedaan

@Friits ik snap nu hoe het werkt, heel mooi opgelost!

[ Voor 3% gewijzigd door Jelle van Kraaij op 07-12-2025 14:17 ]

[Friits]

Thanks! Het is gewoon een kwestie van veel doen, denk ik. Ik heb inmiddels alle 500+ sterren, en ben ieder jaar ook actief op het AoC-subforum van Reddit. Daar is iedere dag een thread waarin mensen hun oplossingen plaatsen. Hier is die voor de puzzel van vandaag.

Zeker mijn eerste paar jaren heb ik veel geleerd door het lezen en begrijpen van andere oplossingen. Tegenwoordig deel ik vooral mijn eigen oplossingen, en ontvang ik feedback

[Jelle van Kraaij]

Ja, eens! Tijdens mijn opleiding (CODAM) was aoc altijd het leukste, dan kon je met iedereen om je heen competitie doen, elkaar helpen en ideeën uitwisselen.
Nu ben ik de enige dev in mijn bedrijf, dus dit jaar voor het eerst een beetje online aan het kijken.
Daarom ben ik hier (;
Grootste lol vind ik het gewoon oplossen en hoe dat is maakt me niet zoveel uit.
Maar daarna kijken hoe mensen het 10x korter of sneller hebben geschreven is altijd zeer interessant.

[Gropah]

Soultaker schreef op zondag 7 december 2025 @ 13:25:
[...]

Huh? Het is toch gewoon

spoiler:

het aantal splitters (^) dat door een lichtstraal (|) geraakt wordt

? Op wat voor antwoord kom je uit op het voorbeeld dat niet klopt met de tekst (en blijkbaar wel met je code, aangezien je het toch hebt weten op te lossen?)

En dat was het stukje wat ik mistte

spoiler:

Ik had dus niet gezien dat er een splitser niet geraakt werd, dus zat mij af te vragen waarom niet 22/aantal splitsers.

Maar goed, uiteindelijk heeft mij dat niet tegengehouden om de goeie oplossing te implementeren

[Marcj]

Vandaag kreeg ik het voor elkaar om deel 1 niet goed te begrijpen en per ongeluk de oplossing voor deel 2 alvast te schrijven. Was al verbaasd dat ik memoization voor deel 1 nodig had. Nou ja, maakte de rest wel vrij makkelijk

[FCA]

Friits schreef op zondag 7 december 2025 @ 14:10:
Leuk puzzeltje vandaag. Mijn oplossing in Python.

Ik vind de puzzels tot nu toe trouwens wel erg makkelijk, zeker gegeven dat we inmiddels over de helft zijn, en het weekend (die waren tijdens eerdere edities altijd moeilijker dan de doordeweekse puzzels). Maar goed, ik vermaak me alsnog prima!

Het werkt goed op de data die AOC je geeft (en is kort en bondig en elegant), maar er zijn wat edge cases waar dit niet goed gaat (hoe erg dat is hangt er vanaf wat voor purist je bent natuurlijk):

spoiler:

Als je 2 beams naaast elkaar hebt die alle 2 een splitter op dezelfde rij tegenkomen, en als je een splitter op de eerste of laatste kolom hebt

Sowieso zijn er de eerste dagen natuurlijk qua complexiteit in de data geen "worst-case" scenario's.

Het verhaal over weekenden die moeilijker zijn doet elk jaar de ronde, maar ik heb het niet zo in de statistieken kunnen terugvinden. Als ik bijvoorbeeld kijk naar https://github.com/jwoLon...-ov-file#completion-times dan zitten de extra moeilijke dagen door de hele week verspreid.

Wat betreft de moeilijkheidsgraad dit jaar, het enige wat ik terug kan vinden is https://www.reddit.com/r/...&utm_content=share_button van 2 maanden terug, waar hij zegt te proberen het hele spectrum te bestrijken, zonder beginners te ontmoedigen. Ik ga er dus vanuit dat het nu snel moeilijker gaat worden...

[Janoz]

Wat ik voor vandaag voor deel 1 gedaan had maakte deel 2 vervolgens ook best simpel.

spoiler:

Voor deel 1 las ik gewoon per regel de input en hield ik in een set de x locaties van de beams bij. Stond er op die regel een splitter dan ging het totaal aantal 1 omhoog en voegde ik aan de set x+1 en x-1 toe. Zat er geen splitser dan werd gewoon x in de nieuwe set gedaan.

Voor deel 2 hoefde ik alleen de set te vervangen door een hasmap met hoeveel realiteiten er voor die x positie waren. Het toevoegen aan de set hoefde ik alleen te vervangen door het bij elkaar optellen van het aantal realiteiten.

https://github.com/Janoz-NL/advent-of-code/blob/master/y2025/src/main/java/com/janoz/aoc/y2025/day7/Day7.java#L23

[Friits]

@FCA Haha, ik ben totaal geen purist, en ook geen snelheidsduivel. Randgevallen (die niet in mijn input zitten) of efficiëntie interesseren me niet. If it works, it works.

Ik probeer wel altijd een compact stukje code (<15 LoC) af te leveren. De meeste dagen zo eenvoudig mogelijk (en daardoor goed te begrijpen), maar soms ga ik helemaal los met NumPy, functools, of itertools.

Dat van die weekenden is wel iets dat ik me denk te kunnen herinneren uit eerdere jaren, zeker anno IntCode. Die statistieken geven alleen maar aan hoe snel de eerste honderd oplossers waren, en dat is natuurlijk niet echt representatief voor de gehele populatie van oplossers.

Maar goed, ik ben benieuwd wat we nog gaan krijgen. Ik hoop op nog een mooi doolhof-based puzzel, en iets waarin we een simpel spel moeten simuleren. En in de tweede helft bepalen wat de score is na ronde 10¹⁰⁰

Ik ben wel blij met slechts twaalf dagen AoC, want rond de twaalfde komt meestal ook de AIVD kerstpuzzel uit. Die periode van overlap tussen AoC en AIVD was niet goed voor m'n nachtrust en/of sociaal leven

[RayNbow]

Ik durf mijn brouwsel voor vandaag niet te tonen. Zeer inefficiënt in elkaar geflanst...

1. Lees grid in.
2. Definieer een oneindige lijst waarin herhaaldelijk een stapfunctie wordt toegepast op het grid. De stapfunctie neemt dus als invoer een heel grid en produceert een nieuw heel grid.
3. Pak vanwege hoe m'n stapfunctie werkt het (aantal rijen x 2)e grid uit de lijst.
4. Gebruik daarvan de laatste rij om het antwoord te bepalen.

...maar het werkt.

[KabouterSuper]

Friits schreef op zondag 7 december 2025 @ 18:27:
@FCA
Dat van die weekenden is wel iets dat ik me denk te kunnen herinneren uit eerdere jaren, zeker anno IntCode.

Ik kan me ook een weekend-opdracht herinneren met 8-bit cijfers (a la wekkerradio) en een opdracht met het verrijden van auto's. Was het niet moeilijker, dan was het in elk geval afwijkend.

Ik ben wel blij met slechts twaalf dagen AoC, want rond de twaalfde komt meestal ook de AIVD kerstpuzzel uit. Die periode van overlap tussen AoC en AIVD was niet goed voor m'n nachtrust en/of sociaal leven

Jij doet dus ook mee mee de aivd kerstpuzzel, leuk! Ik heb vorig jaar als volwassene de juniorpuzzel gedaan, maar vanwege AoC ben ik pas in Januari begonnen. Ik heb het zelfs ingezonden (natuurlijk netjes gemeld dat ik geen junior ben). Ik was trots dat ik 9e of 10e geworden was, maar er waren dus wel een handvol 15-jarige snotneuzen beter dan ik.

[fruitschaal2]

Vandaag weer een leuke puzzel. Eerste oplossing was snel gevonden. Voor deel 2 heb ik ook het eerste deel herschreven van een set naar een hashmap, zodat beide delen in1 keer opgelost kunnen worden.

Mijn oplossing: https://topaz.github.io/p...WGnyh1hKGJBUyT/i11//NRiGP

[jeroenheijmans]

Hoi Tweakers! Naast zelf meedoen (TypeScript repo) bouw ik een AoC browser extension (leuk om wat screenshots voorbij te zien komen hierboven! ), en run ik elk jaar de community 'survey' voor Advent of Code.

Mocht je dat leuk vinden kun je er wat meer over lezen op Reddit, of de survey gewoon even invullen als je dat nog niet al gedaan hebt: https://forms.gle/TAgtXYskwDXDtQms6

Survey sluit op of vlak na de 12e, en kort daarna komen de resultaten bij de vorige jaren op: https://jeroenheijmans.github.io/advent-of-code-surveys/

En: veel plezier met de puzzels natuurlijk!

[Soultaker]

Het begint langzaam aan iets moeilijker te worden. Ik had mazzel dat ik vorig jaar

spoiler: dag 8

een Disjoint Set datastructuur geïmplementeerd had (disjointset.py). Niet om puzzels op te lossen, maar om extra data te genereren (die data structuur is behulpzaam om random doolhoven te genereren, bijvoorbeeld).

Die code kon ik vandaag dus mooi hergebruiken, en dan is de oplossing eigenlijk relatief eenvoudig: 08.py

Ik had wel een trage start bij deel 1, want ik had bij de voorbeeldinvoer de verkeerde interpretatie:

spoiler:

Ik telde de componenten nadat de eerste 10 connecties gemaakt waren (waarbij ik paren van punten die al in hetzelfde component zaten oversloeg), terwijl de bedoeling was om simpelweg de eerste 10 paren te verwerken (ongeacht of ze nieuwe verbindingen vormen of niet).

Dan krijg je een off-by-one error bij de voorbeeldinvoer. Ik had pas door wat er mis ging toen ik me realiseerde dat de officiële invoer precies 1000 punten bevat, en dan kun je natuurlijk nooit 1000 verbindingen maken (maximaal 999).

[Soultaker]

jeroenheijmans schreef op zondag 7 december 2025 @ 22:27:
Hoi Tweakers! Naast zelf meedoen (TypeScript repo) bouw ik een AoC browser extension (leuk om wat screenshots voorbij te zien komen hierboven! ), en run ik elk jaar de community 'survey' voor Advent of Code.

De extension is erg handig! Vooral naar de tabel met tijden kijk ik vaak. Eigenlijk raar dat dat niet standaard in het leaderboard zit (je hebt wel je eigen “personal times” op een aparte pagina, maar het is juist leuk om te vergelijken met de concurrentie). De grafieken vind ik wat minder inzichtelijk.

Ik heb de survey ook ingevuld. Ben benieuwd hoe de attitudes over AI veranderen. Dat is nogal een polariserend onderwerp.

[Janoz]

Soultaker schreef op maandag 8 december 2025 @ 06:50:
Het begint langzaam aan iets moeilijker te worden. Ik had mazzel dat ik vorig jaar...

spoiler:

Mijn connected sets implementatie die ik al had was helaas puur op 2d grids geimplementeerd, dus eigenlijk had ik daar niet zo vel aan. Gelukkig kon ik sommige datastructuren wel hergebruiken.

spoiler:

Voor vandaag was ik even bang dat de permutatie van al die verbindingen te groot zou gaan worden, maar dat bleek mee te vallen. 10000 verbindingen valt naturlijk ook nog best mee.

Uiteindelijk heb ik net geen 2 seconden nodig voor 1 en 2

Soultaker schreef op maandag 8 december 2025 @ 07:03:
Ik heb de survey ook ingevuld. Ben benieuwd hoe de attitudes over AI veranderen. Dat is nogal een polariserend onderwerp.

Huh? Volgens mij zaten er dit jaar helemaal geen vragen over AI in de survey

[ Voor 18% gewijzigd door Janoz op 08-12-2025 08:17 ]

[bakkerjangert]

Mijn implementatie in python. Deel 1 was ik langer mee bezig dan deel 2. Door de opzet van deel 1 was deel 2 één extra check in de loop toevoegen.

[Friits]

Oei, op het leaderboard loopt Soultaker iedere dag iets verder op mij uit! Misschien toch maar om 5u45 opstaan om alvast een pot koffie te zetten.

Hier mijn Python-code voor vandaag.

[Soultaker]

Janoz schreef op maandag 8 december 2025 @ 08:15:
Huh? Volgens mij zaten er dit jaar helemaal geen vragen over AI in de survey

Oh, je hebt gelijk. Ik keek naar de resultaten van vorige jaren. Wel jammer want juist als je elk jaar dezelfde vraag stelt kun je verandering in sentiment tracken (zo zie je bijvoorbeeld dat JavaScript terrein verliest aan TypeScript).

Friits schreef op maandag 8 december 2025 @ 09:25:
Oei, op het leaderboard loopt Soultaker iedere dag iets verder op mij uit!

In het verleden verloor ik vooral punten op de latere dagen, wanneer de problemen moeilijker worden. Bijvoorbeeld 23, 24, 25 in 2023, en 21, 23, 24 in 2024.

Misschien toch maar om 5u45 opstaan om alvast een pot koffie te zetten.

Koffie zetten doe ik ook altijd. Mag dat eigenlijk wel, of is dat illegale doping voor programmeurs?

[Eupeodes]

Soultaker schreef op maandag 8 december 2025 @ 10:08:
[...]

Koffie zetten doe ik ook altijd. Mag dat eigenlijk wel, of is dat illegale doping voor programmeurs?

is het doping of brandstof?

A programmer is an organism that converts caffeine into code

[HannoOttens]

Vandaag was een leuke uitdaging! Tevreden met de snelheid van mijn oplossing. Draait in ~160ms (80ms voor beide delen).

https://github.com/HannoO...master/2025/day08/main.go

spoiler:

Verbonden circuits hou ik bij in een array met volgnummertjes. Die beginnen allemaal op nul en zijn groter dan nul als ze deel zijn van een circuit.

[ Voor 3% gewijzigd door HannoOttens op 08-12-2025 12:25 ]

[Janoz]

Friits schreef op maandag 8 december 2025 @ 09:25:
Misschien toch maar om 5u45 opstaan om alvast een pot koffie te zetten.

Ik zet er niet mijn wekker voor. Maar ik wordt wel eens vroeg wakker, en in december ga ik er dan (even) uit. In het weekend even naar beneden, puzzel doen en weer lekker mijn bed in kruipen, en door de week hangt het af van hoe snel ik de puzzel af heb.

Vanochtend was ik pas om 6:20 beneden. Ik denk niet dat mijn wederhelft heel gelukkig wordt wanneer ik half december elke dag een wekker zet

[Jelle van Kraaij]

Zo was voor mij wel ongeveer het limiet, hopelijk lukt morgen nog...
part2 was wel zo klaar daarintegen, opzet kon ongeveer gelijk blijven
Eerst lang zelf geprobeerd, maar op een gegeven moment wel een beetje inspiratie opgedaan.

spoiler:

Idee om eerst alle combinaties uit te rekenen maakte het verschil, daarna kon ik het zelf wel weer verder bedenken

https://github.com/Jellev...25/blob/main/day08/run.py

[ Voor 86% gewijzigd door Jelle van Kraaij op 08-12-2025 15:27 ]

[Jelle van Kraaij]

Friits schreef op maandag 8 december 2025 @ 09:25:
Oei, op het leaderboard loopt Soultaker iedere dag iets verder op mij uit! Misschien toch maar om 5u45 opstaan om alvast een pot koffie te zetten.

Hier mijn Python-code voor vandaag.

Friits je hebt wel weer een ongelooflijk korte, elegante oplossing vergeleken met mij chapeau

[FCA]

Vandaag flink lopen prutsen.

spoiler:

Detecteren hoe en wat we konden mergen was een flinke struggle. Uiteindelijk voor deel 1 eerst een hele langzame strategie gevonden (hele tijd door de lijst heen gaan en checken of we iets mergen), later voor deel 2 in de trein een goede manier gevonden. Lijkt erg op wat Friits had gedaan, maar uiteraard minder kort en elegant.

Eerst nog wel wat langzaam, maar nu deel 1 in 11ms en deel 2 in 28ms. Wel veruit de langzaamste (na optimalisaties) tot nu toe, maar je blijft natuurlijk zitten met een O(n^2) algoritme voor het bereken van de afstanden, nog geen idee of je dat nog zou kunnen optimaliseren.

edit: met nog wat micro-optimalisaties naar 4ms en 21.9ms respectievelijk. Meeste tijd zit dus niet in de afstanden berekenen, maar in de code daarna.

Ik zie nu dat er speciale algoritmes voor bestaan (disjoint-set data structuren). Dag 13 dan maar

[ Voor 16% gewijzigd door FCA op 08-12-2025 20:55 ]

[jeroenheijmans]

De extension is erg handig! ... De grafieken vind ik wat minder inzichtelijk.

Thanks! En mee eens, ik gebruik zelf vooral ook de mediallespiegel (want: leuk!) en de delta-tijden (want: interessanter voor beetje 'competitie' in NL tijdzone).

Huh? Volgens mij zaten er dit jaar helemaal geen vragen over AI in de survey

Correct! Het was tijd voor iets nieuws (en de vraag riep erg veel negativiteit op in de "Other..." antwoorden), dus dit jaar zijn de vragen over welke "emoties" je ervaart tijdens het puzzelen nieuw!

[FCA]

Deel 1 was mijn snelste solve tijd tot nu toe, deel 2...

spoiler:

Blijkt dat het in Rust "snel genoeg" is om door alle randen van een rechthoek heen te lopen en te checken (met een precomputed min max tabel) of die binnen de groene randen valt. Slechts 10s rekentijd op de laptop
Wel veel zitten prutsrn met verschillende conventies voor x en y

Nu al wel een snellere oplossing bedacht: alleen de randen checken op posities waar er veranderingen in de min en max x en y posities van de groene randen zitten.

Wel goed voor de positie op het leaderboard op m'n werk, blijkbaar zijn er veel mensen die geometrie lastig vinden.

[P_Tingen]

Vraagje over dag 8, deel 2. Het is me weer eens niet duidelijk

spoiler:

Er staat:

Continue connecting the closest unconnected pairs of junction boxes together until they're all in the same circuit.

Maar betekent dat ook dat ik niet meer slechts de top-1000 van kortste connections moet maken, maar juist alle connections moet gebruiken?

 
Pff, soms heeft AoC meer met tekstverklaren te maken dan met programmeren

[FCA]

P_Tingen schreef op dinsdag 9 december 2025 @ 08:59:
Vraagje over dag 8, deel 2. Het is me weer eens niet duidelijk

spoiler:

Er staat:

Continue connecting the closest unconnected pairs of junction boxes together until they're all in the same circuit.

Maar betekent dat ook dat ik niet meer slechts de top-1000 van kortste connections moet maken, maar juist alle connections moet gebruiken?

 
Pff, soms heeft AoC meer met tekstverklaren te maken dan met programmeren

Ja, maar wel nog steeds in volgorde van klein naar groot.

[P_Tingen]

FCA schreef op dinsdag 9 december 2025 @ 09:06:
[...]
Ja, maar wel nog steeds in volgorde van klein naar groot.

Dank u!

[Friits]

@P_Tingen http://www.adventofrealizingicantread.com is niet voor niets geregistreerd

Dit is wat ik vandaag in elkaar heb geknutseld. Niet al te snel (0.6 seconden), maar goed genoeg voor mij.

[ Voor 203% gewijzigd door Friits op 09-12-2025 12:00 ]

[Marcj]

Vandaag was interessant. Deel 1 was heel snel opgelost, maar deel 2 ging ik eerst helemaal de verkeerde kant mee op. Uiteindelijk nu in mijn pauze maar afgemaakt en de uiteindelijke oplossing is vrij kort nog.

spoiler:

Wel een nieuwe functie moeten implementeren om te controleren of een lijn een vierkant doorkruist. Maar toen ik dat had, ging deze ook vrij snel.

Nu loopt deze ook binnen 10ms, waar ik wel blij mee ben.

Voor de grap ook nog een visualisatie gemaakt van de output. Nu snap ik de input ineens veel beter

spoiler:

[ Voor 30% gewijzigd door Marcj op 09-12-2025 13:12 ]

[Soultaker]

Volgens mij doen jullie allemaal maar wat, zolang het juiste antwoord er uit rolt, ook al is het algoritme zo lek als een mandje

Case in point:

Friits schreef op dinsdag 9 december 2025 @ 09:37:
Dit is wat ik vandaag in elkaar heb geknutseld. Niet al te snel (0.6 seconden), maar goed genoeg voor mij.

Prachtige code, maar faalt op zoiets simpels als:

1,1
9,1
9,9
7,9
7,3
3,3
3,9
1,9

(Correcte antwoord: 27, niet 81.)

Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

[HannoOttens]

@Soultaker Oef, ook bij mij komt door een incorrecte oplossing uit.. 35 in plaats van de inderdaad correcte 27. Leuke edge case die ik nog niet had bedacht!

Blijft moeilijk om echt een sluitend algoritme te bedenken. Doe het graag zonder te zoeken op vergelijkbare problemen. Dan kom ik er toch vaak achter dat mijn kennis te kort schiet.

[P_Tingen]

Soultaker schreef op dinsdag 9 december 2025 @ 13:17:
Volgens mij doen jullie allemaal maar wat, zolang het juiste antwoord er uit rolt, ook al is het algoritme zo lek als een mandje

Case in point:

[...]

Prachtige code, maar faalt op zoiets simpels als:

1,1
9,1
9,9
7,9
7,3
3,3
3,9
1,9

(Correcte antwoord: 27, niet 81.)

Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

Voor welk deel is dit, A of B?

[bakkerjangert]

Deel 1 appeltje eitje, deel 2 daar in tegen veel mee lopen prutsen. Nog niet optimaal met een handmatige aanpassing die benodigd is mijn code en traag voor deel 2. Maar wel correct, in ieder geval voor mijn input.

[MatHack]

P_Tingen schreef op dinsdag 9 december 2025 @ 15:18:
[...]

Voor welk deel is dit, A of B?

9B, deel A is supersimpel.

[Thorwing]

Vandaag beetje heen en weer gestruggled met een algoritme. Ik begon met het idee dat AWT mij kon helpen vandaag, maar kreeg dat niet werkend. Toen voor de sterren van vandaag nog even algoritme bedacht die natuurlijk werkt voor de opgave, maar vervolgens niet voor de gekke voorbeelden zoals mensen hier aangeven. Toen dat eenmaal werkte weer terug naar AWT en low and behold, het werkte.

Is het valsspelen? Wellicht...

Kotlin:

object Day9 : AdventOfCode({
    val coordinates: List<Pair<Int, Int>> = input
        .lines()
        .map { it.split(",").map(String::toInt).let { (x, y) -> y to x } }

    val polygon: Polygon = coordinates.fold(Polygon()) { acc, (y, x) -> acc.apply { addPoint(x, y) } }

    val rectangles: List<Rectangle2D> = coordinates.flatMapIndexed { row, (p1y, p1x) ->
        coordinates.drop(row + 1).map { (p2y, p2x) ->
            Rectangle2D.Double(
                minOf(p1x, p2x).toDouble(),
                minOf(p1y, p2y).toDouble(),
                (p2x - p1x).absoluteValue.toDouble(),
                (p2y - p1y).absoluteValue.toDouble()
            )
        }
    }

    fun Rectangle2D.size() = ((width + 1) * (height + 1)).toLong()

    part1 {
        rectangles.maxOf(Rectangle2D::size)
    }

    part2 {
        rectangles.filter(polygon::contains).maxOf(Rectangle2D::size)
    }
})

[Janoz]

Soultaker schreef op dinsdag 9 december 2025 @ 13:17:
Volgens mij doen jullie allemaal maar wat, zolang het juiste antwoord er uit rolt, ook al is het algoritme zo lek als een mandje

Case in point:

[...]

Prachtige code, maar faalt op zoiets simpels als:

1,1
9,1
9,9
7,9
7,3
3,3
3,9
1,9

(Correcte antwoord: 27, niet 81.)

Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

Yup, ik krijg ook 35. Maar mijn aaname dat cutouts kleiner zouden zijn dan de grootste oppervlakte was voor de puzzel input juist .

Wel mooi om te zien wat de JIT kan. Als ik mijn oplossing 2x achter elkaar draai is de tweede keer meer dan 2x zo snel.

In 0m 0s 59ms 447875ns
In 0m 0s 25ms 812333ns

edit: Hmm, misschien is het nog wel een grappige uitdaging om een BSP te implementeren zodat ook het voorbeeld van @Soultaker goed gaat.

[ Voor 7% gewijzigd door Janoz op 09-12-2025 16:13 ]

[Marcj]

Soultaker schreef op dinsdag 9 december 2025 @ 13:17:
Volgens mij doen jullie allemaal maar wat, zolang het juiste antwoord er uit rolt, ook al is het algoritme zo lek als een mandje
...
Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

Nou ja, lek. Ik heb aannames gedaan over de vorm. Maar jouw voorbeeld heb ik wel even toegevoegd en ook een oplossing gevonden zodat ik niet een gebied vind die geheen buiten de vorm zit. Wel maak ik nu nog de aanname dat de poly opgeschreven staat met de klok mee. Als je dat omdraait werkt die nog steeds niet

Ook mijn check of een lijn door een gebied kruist is niet fool-proof, maar goed genoeg voor deze vormen.

Ook nog een optimalisatie gevonden, waardoor veel sneller ongeldige gebieden uitgesloten worden.

spoiler:

Sorteren van de lijnen op lengte helpt enorm, omdat je eerst de langste lijnen bekijkt of ze kruizen. En die hebben de hoogste kans.

[Soultaker]

Thorwing schreef op dinsdag 9 december 2025 @ 15:48:
Vandaag beetje heen en weer gestruggled met een algoritme. Ik begon met het idee dat AWT mij kon helpen vandaag, maar kreeg dat niet werkend. Toen voor de sterren van vandaag nog even algoritme bedacht die natuurlijk werkt voor de opgave, maar vervolgens niet voor de gekke voorbeelden zoals mensen hier aangeven. Toen dat eenmaal werkte weer terug naar AWT en low and behold, het werkte.

Is het valsspelen? Wellicht...

Ik zag dat Apparaat9 op het leaderboard (wie is dat hier?) ook een bestaande polygon intersection library gebruikt had: day_09.py

Ergens een beetje flauw, aan de andere kant: don't hate te player, hate the game.

Marcj schreef op dinsdag 9 december 2025 @ 17:02:
Nou ja, lek. Ik heb aannames gedaan over de vorm.

Fair enough, dat hoort ook een beetje bij Advent of Code, en ik heb zelf natuurlijk ook bepaalde aannamen gedaan. Toch is het nuttig om ten minste na te denken over welke voorwaarden je vereist, anders snap je eigenlijk je eigen code niet.

[Friits]

Soultaker schreef op dinsdag 9 december 2025 @ 13:17:
[...]
Prachtige code, maar faalt op zoiets simpels als:

Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

Guilty as charged, maar voor mij is het analyseren van de input en vervolgens gebruik (kunnen) maken van bepaalde eigenschappen, onderdeel van de puzzel. In mijn ogen niets dubieus aan, maar ik snap jouw perspectief. Ieder z'n ding

[P_Tingen]

Zelf vind ik het vooral leuk om te zien hoe anderen het probleem aanpakken en deel van de lol is ook om - als ik de oplossing eenmaal heb - nog eea bij te schaven.
Helaas zijn er weinig Progress 4gl ontwikkelaars die meedoen, maar ook door naar oplossingen te kijken in andere talen leer ik bij.

Wat me wel opvalt is dat ik in Progress echt heel veel zelf moet doen waar in andere talen een library voor is.

You lucky Bastards!

[Soultaker]

Ik zal in plaats van alleen maar te zeuren over de oplossingen van anderen ook eens mijn eigen oplossingsaanpak posten, dan kunnen anderen voor de verandering over mij zeuren.

Ten eerste de oplossing die ik vanmorgen gebruikt heb om het antwoord te vinden, en die wellicht het meest eenvoudig te begrijpen is: (spoilers zijn voor deel 2; deel 1 is zo simpel dat ik 'm niet uit hoef te leggen)

spoiler:

Je kunt de lijnstukken intekenen op een 2D grid. Als je zorgt dat er 1 cel ruimte omheen zit, dan kun je met een flood fill algoritme de cellen aan de buitenkant vinden. De overgebleven ongemarkeerde cellen zijn dan per definitie de binnenkant.

Dit werkt prima voor de voorbeeldinvoer, maar de officiële invoer is ongeveer 100,000 × 100,000 pixels groot, en als je dat expliciet in een 2D grid stopt, heb je ongeveer 10 GB geheugen nodig (1 byte per pixel) of tenminste 1,25 GB (1 bit per pixel).

Om het efficiënter te maken, comprimeer ik de coordinaten. Dit is een bekende truc die ook wel eerder langs gekomen is, bijvoorbeeld: dag 22 van 2021.

Voor wie niet bekend is met dit principe: het idee is dat alleen de coördinaten die daadwerkelijk in de invoer voorkomen relevant zijn, en dat je de ruimte daartussen kunt comprimeren tot 1 cel.

Zie bijvoorbeeld figuur 1 hier (externe link omdat spoiler tags de formatting verpesten).

De x-coordinaten in de invoer zijn: 3, 8, 10, 12. Dat betekent dat kolommen 1-2 en 4-7 in het grid identiek zijn, dus kun je samennemen, zoals te zien is in figuur 2.

Hetzelfde principe kun je toepassen op de rijen. In de voorbeelinvoer levert dat niets op, maar in de officiële invoer wel.

Het aantal rijen en kolommen dat overblijft is proportioneel aan het aantal coördinaten in de invoer. Als n het aantal regels in de invoer is, dan is de tijdcomplexiteit van het algoritme O(n⁴): n²/2 rechthoeken, en een grid van hooguit (2n)×(2n) pixels. In de praktijk is het sneller omdat de meeste rechthoeken ofwel een relatief klein deel van het gecomprimeerde grid beslaan, ofwel snel verworpen kunnen worden wanneer er een cel gevonden is die buiten de figuur ligt.

Code: 09.py

---

Dan nog een andere aanpak. Je kunt in plaats van een bitmap de invoer ook zien als polygoon, en dan voor elke mogelijke rechthoek kijken of hij 100% overlapt met die polygoon.

spoiler:

Het probleem hiermee is dat de figuur die beschreven wordt in de invoer een rand heeft met een dikte van 1, maar om de polygoon logica te implementeren wil je eigenlijk alleen de buitenranden van de figuur hebben, zodat de hele figuur strict binnen de polygoon ligt,

Je moet dus eerst de omtrek van die polygoon inclusief de rand vinden. Zie figuur 3 voor een voorbeeld.

De coordinaten in de invoer: 7,1 11,1 11,7 9,7 9,5 2,5 2,3 7,3

Worden dan hoekpunten van de polygoon: 7,1 12,1 12,8 9,8 9,6 2,6 2,3 7,3

Ik had wat moeite om te bedenken wanneer je precies wel of niet 1 op moet tellen bij de coordinaten. Ik heb uiteindelijk gewoon alle 8 situaties met de hand uitgeschreven (vier if-statements hier). Als iemand een simpelere/nettere manier weet om dit te doen hou ik me aanbevolen.

Op dit punt heb ik een simpele polygoon zónder rand. Om vervolgens te detecteren of een rechthoek volledig overlapt, heb ik gebruik gemaakt van de shoelace formula waarbij de coordinaten geclampt worden tot de rechthoek. Deze truc werkt echt alleen voor een rechthoek waarvan de randen parallel lopen aan de assen maar aangezien dat bij dit probleem toevallig zo is, is een ingewikkelder polygoonintersectiealgoritme niet nodig.

Code: 09-alt.py

In theorie zou de tweede oplossing sneller moeten zijn: O(n³) in plaats van O(n⁴). In de praktijk is het ook iets sneller maar het verschil is niet heel groot (1,1s vs 2,5s met PyPy; 11s vs 15s zonder).

[Jelle van Kraaij]

Ik ben niet verder gekomen dan part1, part2 is wel over mijn puzzellimiet.
Gisteren vondt ik part2 nog maar net te doen, vandaag was ik hoopvol door makkelijke part1 maar helaas
https://github.com/Jellev.../blob/main/day09/part1.py
Terug naar mijn usual business, embedded werk, praten met 4g/LTE modems...

[ Voor 38% gewijzigd door Jelle van Kraaij op 09-12-2025 20:44 ]

[Friits]

Ik heb zojuist trouwens wat optimalisaties gedaan en de uitvoertijd teruggebracht van 0.6 naar 0.06 seconden! Nog steeds houdt 'ie geen rekening met alle "randgevallen" van @Soultaker, maar het werkt prima voor mijn puzzel-input. And that's good enough for me!

spoiler:

Optimalisatie 1: Sorteer de "rode" rechthoeken aflopend op oppervlakte. Dan kan je stoppen zodra je je eerste "geldige" rechthoek hebt gevonden. Eventuele andere geldige rechthoeken zijn namelijk sowieso kleiner.

Optimalisatie 2: Sorteer de "groene" lijnen aflopend op lengte. We zoeken voor iedere "rode" rechthoek namelijk naar een lijn die de rechthoek doorsnijdt, en daarmee ongeldig maakt. Hoe eerder we zo'n lijn vinden, hoe sneller we door kunnen om de volgende rechthoek te testen.

Als je de puzzel-input hebt bekeken, weet je waarom deze optimalisatie een groot verschil maakt. En ook in het algemeen geldt: hoe langer de lijn, hoe groter de kans dat 'ie een willekeurige rechthoek doorsnijdt.

[ Voor 67% gewijzigd door Friits op 09-12-2025 22:05 ]

[Soultaker]

Gefeliciteerd @Friits, je was me vandaag te snel af! En eigenlijk heb ik het probleem nog steeds niet helemaal opgelost.

Voor deel 1

spoiler:

heb ik gewoon een breadth-first search geschreven. Alle combinaties van knoppen proberen had ook gekund (essentiële observatie: elke knop wordt hooguit 1 keer ingedrukt, want 2 keer drukken is equivalent aan 0 keer drukken, dus kun je gewoon alle 2^k varianten proberen).

Python code: 10A.py

Voor deel 2

spoiler:

probeerde ik eerst de aanpak van deel 1 te generaliseren. Dat was wat naïef van me, maar het leek me zo'n logische extensie van deel 1 dat het wel haast de bedoeling moest zijn. Niet dus: het aantal mogelijkheden is veel te groot.

Ik heb zelfs even snel A* in elkaar gehackt met een simpele heuristiek, maar ook dat hielp niet (genoeg) om problemen binnen een redelijke tijd op te lossen.

Daarna heb ik zitten kijken of ik bepaalde kenmerken van de invoer kon gebruiken; bij sommige invoeren heb je b.v. dat 1 energie-meter maar door 2 knoppen beïnvloed wordt. Dan kun je eerst alle combinaties van die twee knoppen proberen en dan heb je een simpeler probleem om recursief op te lossen. Maar helaas waren er ook invoerregels waarbij dat niet geldt.

Uiteindelijk heb ik een beetje flauw het probleem aan scipy.optimize. linprog gegeven, om ieder geval de ster binnen te halen.

Python code: 10B-scipy.py

Maar ik vind dat eigenlijk geen “echte” oplossing. Vandaag nog maar even nadenken over een betere aanpak. Ben benieuwd of iemand anders iets slimmers bedacht heeft!

[Friits]

@Soultaker: ik heb vandaag ook gewoon een ILP-solver geïmporteerd, want het her-implementeren daarvan is not my idea of fun.

Ik heb wel even geëxperimenteerd met een local search, maar dat kreeg ik (nog) nét niet lekker werkend.

[ Voor 103% gewijzigd door Friits op 10-12-2025 12:49 ]

[Janoz]

Ik dacht gisteren al dat we nog geen pathfinding hadden gehad. Deel 1 opgelost met BFS en daarna Dijkstra (omdat ik die toch al geimplementeerd had), en ja, deel 2....

Nog wat lopen aanklooien met A* maar ik heb uiteindelijk ook maar de handoek in de ring gegooid.
Het voelt inderdaad heel erg als vals spelen, maar toch Z3 in mijn oplossing gehangen.

[Corniel]

Ik heb vandaag ook maar Z3 in de strijd gegooid...

spoiler:

Ik kreeg met een priority queue de voorbeelden wel snel opgelost. IK heb nog geprobeerd om op basis van het aantal bits in de buttons die eerst maximaal te doen, maar het schoot totaal niet op als je tot meer dan 200 kliks moet komen...

[Janoz]

Soultaker schreef op dinsdag 9 december 2025 @ 13:17:
Volgens mij doen jullie allemaal maar wat, zolang het juiste antwoord er uit rolt, ook al is het algoritme zo lek als een mandje

Case in point:

[...]

Prachtige code, maar faalt op zoiets simpels als:

1,1
9,1
9,9
7,9
7,3
3,3
3,9
1,9

(Correcte antwoord: 27, niet 81.)

Sommige van de andere oplossingen die ik langs zien komen zijn net zo dubieus.

Met een kleine aanpassing die nauwelijks invloed op de totale performance heeft kan ik nu ook zien wanneer een oplossing volledig buiten de tegels valt

https://github.com/Janoz-...edf721582c6369929e056d229

Runtime van de exhte opdrachten is nog steeds 25ish ms

[Marcj]

Vandaag was wel een uitdaging, maar ik heb een oplossing.

spoiler:

Het komt er op neer dat ik een "poor-mans" trage linear solver heb gemaakt, met wat aannames op deze input.

Op het moment doet hij er echter wel 4 minuten over om tot een resultaat te komen. Ik hoop dat ik nog wat optimalisaties vind om het behoorlijk te versnellen.

[Soultaker]

Okee, ik heb toch nog een redelijke oplossing voor dag 10 weten te verzinnen zonder het gebruik van externe solvers als scipy: 10B.py

spoiler:

Het idee is dat je net zoals met de ILP oplossing het probleem formuleert als systeem van lineaire vergelijkingen. De variabelen daarin zijn het aantal keer dat je op elke knop drukt, en de joltage waarden zijn de uitkomst. Met Gauss-Jordan eliminatie kun je ofwel direct een oplossing vinden, of een aantal vrije variabelen identificeren waarvan de andere variabelen afhankelijk zijn. Omdat die vrije variabele niet-negatieve gehele getallen moeten zijn, waarvan het maximum berekenbaar is, kun je alle mogelijkheden voor de vrije variabelen proberen, en dan de andere variabelen afleiden. Het antwoord is dan het minimum van alle mogelijke oplossingen.

Dit draait in < 2 seconde met PyPy (12 seconde met CPython). Veel trager dan met SciPy die waarschijnlijk intern wat slimmers doet, maar het is in ieder geval een zelfbedachte oplossing.

Respect voor @Marcj die als eerste een eigen oplossing bedacht had

[Friits]

@Soultaker Wat gaaf

Drie kleine suggesties:

Je kan (voor mijn input) minstens 30% snelheidswinst behalen door if answer > best_answer: break toe te voegen rond regel 90. Het heeft in dat geval immers geen zin om verder te rekenen.

Verder vind ik je met Fraction() erg elegant, maar volgens mij beroerd voor je performance.

Tot slot is je implementatie van GenerateVariableAssignments() mooi gevonden, maar het doet niets meer dan product(*map(range, bounds)) toch? Ik heb het niet gebenchmarkt, maar wellicht kan je daar ook nog wat winnen.

Ondanks deze kleine puntjes: echt heel erg cool!

[Soultaker]

Dag 11 was een eitje, zeker vergeleken met gisteren.

spoiler:

functools.cache to the rescue!

Python code: 11.py

Visualisatie van mijn testinvoer:

spoiler:

De testinvoer had trouwens nog veel gemener kunnen zijn. Misschien dat ik nog even een extra challenge maak als ik tijd over heb. Eerst even de comment van Friits hierboven lezen...

[Friits]

Schattig puzzeltje vandaag. Niet helemaal wat ik verwacht had op de één-na-laatste dag, maar dan ik nog wat tijd besteden aan m'n ILP-solver.

Hier m'n code voor vandaag.

[ Voor 27% gewijzigd door Friits op 11-12-2025 07:09 ]

[Soultaker]

Friits schreef op woensdag 10 december 2025 @ 21:05:
Je kan (voor mijn input) minstens 30% snelheidswinst behalen door if answer > best_answer: break toe te voegen rond regel 90. Het heeft in dat geval immers geen zin om verder te rekenen.

Direct na answer += val bedoel je? Dat lijkt op mijn invoer niet veel uit te maken (of eerder iets trager te zijn: van 1,8s naar 1,9s).

Misschien is daar wel iets te halen: voor elke vrije variabele weet je of 'ie positief of negatief correleert met de som die je wil optimaliseren, dus als je de assignments aan de vrije variabelen genereert zodat de som nondecreasing is, dan hoef je per assignment alleen maar te checken of de afhankelijke variabelen nonnegative integers zijn. De eerste geldige oplossing is dan direct het minimum.

Maar dat maakt het wel weer complexer, en dan moet ik de product() die ik er op jouw suggestie hieronder heb toegevoegd er weer uitslopen. Misschien kom ik er nog op terug.

Verder vind ik je met Fraction() erg elegant, maar volgens mij beroerd voor je performance.

Ja, heb je helemaal gelijk in. Ik laat 't voor het mooie maar staan, anders moet ik op allerlei plekken abs(x) < eps gaan introduceren om te checken of een getal 0 of een integer is, wat ik nogal lelijk vind. Maar ik denk dat je wel verklaart waarom de professionele libraries met floats werken zelfs als het om puur-integer problemen gaat.

Tot slot is je implementatie van GenerateVariableAssignments() mooi gevonden, maar het doet niets meer dan product(*map(range, bounds)) toch?

Ah ja, ik vermoedde al dat er zoiets bestond maar ik kon er niet op komen. Ik heb het aangepast Qua performance maakt het wederom niet veel verschil (ik denk dat het meeste werk in de binnenste lus verricht wordt) maar waarom het wiel opnieuw uitvinden...

Bedankt voor alle tips!

[Friits]

Soultaker schreef op donderdag 11 december 2025 @ 07:37:
Direct na answer += val bedoel je? Dat lijkt op mijn invoer niet veel uit te maken (of eerder iets trager te zijn: van 1,8s naar 1,9s).

Daar ja. Ik had getest met CPython. Met PyPy is het verschil inderdaad veel kleiner (2,2s naar 2,0s).

Bedankt voor alle tips!

Graag gedaan. Ik weet nooit of ongevraagde feedback gewaardeerd wordt, maar dit was al zo'n gaaf stukje code dat ik het niet kon laten om het (i.i.g. voor mezelf) nog iets mooier te maken.

En een functie van 10 regels vervangen door een itertools one-liner is natuurlijk een imperatief. Op jouw manier is 'ie zelfs nog iets mooier.

[Marcj]

Ik had hetzelfde, vandaag voelde dan wel relatief eenvoudig. Was ook begonnen net al @Soultaker om eerst een visualisatie te doen met graphviz. Die zorgt al voor behoorlijk wat inzicht.

Daarna was de implementatie heel erg simpel.

Soultaker schreef op woensdag 10 december 2025 @ 19:09:
...
Respect voor @Marcj die als eerste een eigen oplossing bedacht had

Dank je! Ik wist dat hij niet efficient was, maar je hebt wel herinneringen nu terug gebracht van wiskunde op de universiteit 20 jaar terug

Als ik tijd vind wil ik nog wel even kijken of ik ook zoiets kan doen in Rust en hoeveel sneller dat kan

[ Voor 7% gewijzigd door Marcj op 11-12-2025 10:20 ]

[Soultaker]

Omdat vandaag wel erg makkelijk was, hier een extra challenge voor dag 11:
aoc-2025-day-11-challenge-1.zip

Correcte antwoorden eindigen op: ...826 (deel 1) en ...545 (deel 2).

Antwoorden passen in een 64-bit integer maar mogelijk niet in een double precision float.

[KabouterSuper]

Vandaag was erg goed te doen.

spoiler:

als je de lru_cache tenminste groot genoeg zet aangezien de default grootte te klein was bij mij

Ik heb nu maar 19 punten meer dan mijn dochter en dat op de een-na-laatste dag. Dat wordt morgen dus vroeg opstaan om de winst te verzilveren.

[Janoz]

Soultaker schreef op donderdag 11 december 2025 @ 10:41:
Omdat vandaag wel erg makkelijk was, hier een extra challenge voor dag 11:
aoc-2025-day-11-challenge-1.zip

Correcte antwoorden eindigen op: ...826 (deel 1) en ...545 (deel 2).

Antwoorden passen in een 64-bit integer maar mogelijk niet in een double precision float.

Uiteraard een stack overflow .

Toch niet stiekem cycles in gedaan?

[Marcj]

Soultaker schreef op donderdag 11 december 2025 @ 10:41:
Omdat vandaag wel erg makkelijk was, hier een extra challenge voor dag 11:
aoc-2025-day-11-challenge-1.zip

Correcte antwoorden eindigen op: ...826 (deel 1) en ...545 (deel 2).

Antwoorden passen in een 64-bit integer maar mogelijk niet in een double precision float.

Er zitten hier cycles in en daar had ik eerst geen rekening mee gehouden. Maar na een kleine aanpassing is deze ook goed te doen. Zelfde antwoorden in enkele milliseconden.

Technisch gezien zijn er een oneindig aantal paden mogelijk als er een cycle in zit

[ Voor 6% gewijzigd door Marcj op 11-12-2025 14:32 ]

[FCA]

Ik heb (na meer dan een dag) eindelijk een oplossing voor dag 10 deel 2, zonder externe libraries, en zonder spoilers te lezen (en ik kan eindelijk weer veilig dit forum en de subreddit bezoeken).
Pffff....

spoiler:

Eerst integer gauss reductie, om zoveel mogelijk dingen vast te leggen. Dat had ik gisteren al geimplementeerd, maar toen kwam het toetje dus nog, door de overgebleven mogelijkheden itereren en de kleinste vinden. Hiervoor Bézout gebruikt, wat nog een crime was vanwege allerlei randgevallen met negatieve coefficienten etc.
Uiteindelijk vandaag de goede oplossing eruit gekregen. Mijn Bézout implementatie kan nog wel iets beter als ik 3 of meer coefficienten overhoud, maar verder wel tevreden uiteindelijk. Solve tijd is om te huilen natuurlijk, maar ik zie niet hoe je dit handiger doet zonder externe libraries (ja, herimplementeren van de methoden daarin natuurlijk, ga maar typen...)
Rekentijd is nu 12s, kan nog wel wat sneller denk ik, heb niet echt geoptimaliseerd voor snelheid nog.

[ Voor 5% gewijzigd door FCA op 11-12-2025 15:56 ]

[KabouterSuper]

Marcj schreef op donderdag 11 december 2025 @ 14:32:
[...]
Technisch gezien zijn er een oneindig aantal paden mogelijk als er een cycle in zit

Tenzij een pad klemloopt in een oneindige rotonde en dus nooit bij out uitkomen. Ik kap een pad af als deze langer dan het aantal elementen is. Het zou mooier zijn om het hele pad mee te geven in de recursie om cycles te detecteren, maar dat vindt de cache waarschijnlijk niet leuk.

[P_Tingen]

Dag 11: deel 1 was nog niet zo ingewikkeld en die had ik dan ook vrij snel voor elkaar.
Voor deel 2 heb ik me wel even zitten schamen....

spoiler:

De initiele oplossing die ik had was een kleine variatie op die van deel 1. Die had ik al recursief opgelost en het enige wat ik erbij had gemaakt was een historie van bezochte nodes. Het idee was om - als ik een uitgang had gevonden - in die lijst te kijken of dac en fft bezocht waren.

Ik vermoed dat het uiteindelijk wel gewerkt zou hebben, maar als je programma niet binnen een paar seconden met een antwoord terugkomt, weet je dat je genaaid bent door in de val getrapt bent van Eric.

Vervolgens dus flink zitten zoeken hoe ik dit nu op moest lossen en heb uiteindelijk maar gespiekt op Reddit.
Daar zag ik dat ik 'gewoon' mijn functie moest cachen. En het beschamende is, dat ik dat JUIST in mijn werk ook regelmatig toepas om bepaalde programma's sneller te maken. Zucht.

Uiteindelijk was de aanpassing dan ook simpel en draait het programma in 30ms
en ja, voor een taal als Progress is dat snel

https://github.com/patric...ter/2025/Day-11/day-11b.p

Ok, nou nog even nadenken hoe ik dag-10 aan ga pakken....

[Janoz]

Vanochtend heb ik deel 1 gewoon bij deel 2 gebruikt.

spoiler:

Voor deel 1 had ik een nrOfPaths(start, end) met een cache. Voor deel twee deed ik gewoon een nrOfPaths(dac, ftt) en een nrOfPaths(ftt,dac). Omdat er geen cycles in zitten (Wat ik itt tot @Soultaker een randvoorwaarde vind ) is 1 van beide 0. Op basis daarvan bepaalde ik nog een srv->dac/ftt en een ftt/dac->out en vermenigvuldigde ik alle drie met elkaar

[bakkerjangert]

Vandaag behoorlijk lopen klooien, maar uiteindelijk een mooie oplossing voor deel 2 gevonden zonder cache te gebruiken. Mijn code in python.

spoiler:

Het kwartje viel toen ik besefte dat enkel het aantal paden wordt gevraagd, niet hoe lang de individuele paden eigenlijk zijn.

[RayNbow]

Voor challenge 11 heb ik voor beide puzzles bijna dezelfde code. Gezien ik de code nog niet heb opgeschoond of van degelijk commentaar heb voorzien, deel ik alleen m'n aanpak in Haskell:

spoiler:

Ik maak eerst een omgekeerde mapping aan (Map String [String]), zodat ik voor elke node weet welke andere nodes ernaar verwijzen.

Vervolgens maak ik een "spreadsheet" aan (Map String (Map String (Int -> Int))). Deze spreadsheet bevat voor de cel "you" de functie const 1. Elke andere cel, bijv. de cel "ddd", bevat een functie die de geëvalueerde spreadsheet ontvangt als argument en daarin de cellen opzoekt van nodes die naar "ddd" verwijzen, bijv. "bbb" en "ccc". De waarden van de cellen worden opgeteld en dat wordt de waarde voor cel "ddd".

Voor deel 1 is het dan simpelweg de spreadsheet evalueren met loeb en de waarde van cel "out" uitlezen.

Voor deel 2 maak ik een vergelijkbare spreadsheet. Hierbij is "svr" de cel die een constante functie krijgt, maar i.p.v. dart deze de waarde 1 retourneert, retourneert hij vier getallen: [1,0,0,0]. Deze vier getallen representeren respectievelijk het aantal paden die niet langs "dac" en "fft" gaan, het aantal paden dat door "dac" gaat, het aantal paden dat door "fft" gaat en het aantal paden die zowel door "dac" en "fft" gaan.
De functies voor de overige cellen doen iets vergelijkbaars als voorheen, maar in plaats van een enkele som worden er nu 4 sommen berekend. De cellen "dac" en "fft" doen hetzelfde, maar voegen als extra stap wat sommen samen. Stel bijv. dat de "dac" cel alle inkomende waarden heeft opgesomd tot [3,0,0,0]. Dan wordt de uiteindelijke waarde voor de "dac" cel [0,3,0,0].

[FCA]

spoiler:

Dag 12 WTF? Jammer dat deze oplossing mogelijk was, maar aangezien de algemene oplossing van https://en.wikipedia.org/wiki/Bin_packing_problem NP-compleet gaat het met deze aantallen niets anders worden.
Naar de input kijken, valt patroon op, quick check of het werkt, ja dus...

[Soultaker]

spoiler:

Wat een fakeout vandaag zeg.

Ik had m'n rotatie en translatie-code al geschreven en getest. Ik zat al te overwegen of ik het met dynamic programming zou kunnen oplossen, of dat ik het als SAT probleem zou kunnen formuleren en aan een externe solver voeren op dezelfde manier als dag 10. En dan... blijkt het allemaal niet nodig te zijn. Nou ja.

Wel jammer want ik had wel zin in een programmeerprobleem, en dat was het niet echt.

In de geest van @Friits mijn minimale oplossing voor vandaag (of als oneliner).

[Janoz]

Same here

spoiler:

Ik was toch maar naïef begonnen aan een bruteforce implementatie zodat iklater wel kon kijken waar ik wat kon optimaliseren. Die deed echteral best lang over de voorbeelden. Ik had al een simpele check toegevoegd voor wat sowieso ging passen. bleek die inderdaad al voldoende te zijn...

[Friits]

Soultaker schreef op vrijdag 12 december 2025 @ 06:56:
[spoiler]
In de geest van @Friits mijn minimale oplossing voor vandaag (of als oneliner).

Haha mooi, dat is inderdaad bijna identiek aan mijn oplossing van vandaag.

[KabouterSuper]

spoiler:

Ik heb een iets subtielere fake-versie geimplementeerd waarin ik check of het aantal hekjes past in de rechthoek (ik ga er dus vanuit dat de puzzelstukjes zonder gaten aan elkaar geplakt kunnen worden). Bij mijn data levert dat hetzelfde antwoord op als de versie hierboven (eerst gepost door @Soultaker ) waarbij je veronderstelt dat elk puzzelstukje 8 hekjes heeft.

Anyway, op naar de AIVD-kerstpuzzel!

[bakkerjangert]

KabouterSuper schreef op vrijdag 12 december 2025 @ 08:26:

spoiler:

Ik heb een iets subtielere fake-versie geimplementeerd waarin ik check of het aantal hekjes past in de rechthoek (ik ga er dus vanuit dat de puzzelstukjes zonder gaten aan elkaar geplakt kunnen worden). Bij mijn data levert dat hetzelfde antwoord op als de versie hierboven (eerst gepost door @Soultaker ) waarbij je veronderstelt dat elk puzzelstukje 8 hekjes heeft.

Anyway, op naar de AIVD-kerstpuzzel!

Mijn code in python die ongeveer het zelfde doet maar net op een andere manier.

spoiler:

Ik gebruik een variant hierop met 3 counters; 1 die telt als het zeker niet past (totale hekjes > hxb), 1 die telt als het zeker past (blokken van 3x3 passen binnen de rechthoek) of als beide niet voldoen 1 die telt of het misschien past. Die 3e teller levert verrassend genoeg 0 op, dus hoef je niet verder te analyseren.

[P_Tingen]

Nou, nog ergens 3 sterren weg zien te plukken en mijn AoC is compleet. Ben eerlijk gezegd nog nooit zover gekomen als dit jaar. Wel jammer dat Eric er niet voor gekozen heeft om de puzzels in twee dagen vrij te geven, dus deel 1 en deel 2 in 2 dagen. Dan zou je voor elke dag een ster kunnen geven en leek het nog een beetje op voorgaande edities. Nu is het wel kort.

spoiler:

Deze laatste vond ik wel een beetje sneaky. Hoe kom je tot de aanname dat alle plekjes bezet zijn, is dat een gok die toevallig goed uitpakt of kun je dat beredeneren aan de hand van de vorm van de shapes?

[Friits]

@P_Tingen: Het is een aanname die werkt voor de puzzel-inputs. Ik kwam er zelf zo achter:

spoiler:

Polyomino-packing is een moeilijk probleem, dus ik wilde het opdelen in sub-problemen. Stap één daarbij is om te controleren of een sub-probleem óf triviaal is, óf onmogelijk. In beide gevallen kan je namelijk stoppen met zoeken. Nou bleek dat iedere input-regel al voldeed aan één van die eisen, dus dat zijn we eigenlijk klaar.

Je kan dan nog wel de rest van de code schrijven, maar die zal voor de puzzel-input toch nooit worden uitgevoerd.

[Hagdos]

Soultaker schreef op woensdag 10 december 2025 @ 19:09:
Okee, ik heb toch nog een redelijke oplossing voor dag 10 weten te verzinnen zonder het gebruik van externe solvers als scipy: 10B.py

spoiler:

Het idee is dat je net zoals met de ILP oplossing het probleem formuleert als systeem van lineaire vergelijkingen. De variabelen daarin zijn het aantal keer dat je op elke knop drukt, en de joltage waarden zijn de uitkomst. Met Gauss-Jordan eliminatie kun je ofwel direct een oplossing vinden, of een aantal vrije variabelen identificeren waarvan de andere variabelen afhankelijk zijn. Omdat die vrije variabele niet-negatieve gehele getallen moeten zijn, waarvan het maximum berekenbaar is, kun je alle mogelijkheden voor de vrije variabelen proberen, en dan de andere variabelen afleiden. Het antwoord is dan het minimum van alle mogelijke oplossingen.

Dit draait in < 2 seconde met PyPy (12 seconde met CPython). Veel trager dan met SciPy die waarschijnlijk intern wat slimmers doet, maar het is in ieder geval een zelfbedachte oplossing.

Respect voor @Marcj die als eerste een eigen oplossing bedacht had

Bedankt voor deze opmerking! Ik zat al op dit pad (was te koppig om een solver te gebruiken, heb zelfs geen Numpy gebruikt), maar mijn oplossing leek alsnog veel te traag.
Heb met wat optimalizaties van zowel algoritme als gewoon code het een stuk sneller gekregen. Lost het nu op in minder dan 8 seconden in gewoon python.

(1.2 seconden in Pypy, moet dat toch eens beter gaan integreren in mijn workflow).
Ik denk dat ik dag 12 maar voor morgen bewaar

https://github.com/Hagdos...2025/Day%2010/Day%2010.py

[Corniel]

[quote]Soultaker schreef op vrijdag 12 december 2025 @ 06:56:

spoiler:

Wat een fakeout vandaag zeg.

Ik had m'n rotatie en translatie-code al geschreven en getest. Ik zat al te overwegen of ik het met dynamic programming zou kunnen oplossen, of dat ik het als SAT probleem zou kunnen formuleren en aan een externe solver voeren op dezelfde manier als dag 10. En dan... blijkt het allemaal niet nodig te zijn. Nou ja.

Wel jammer want ik had wel zin in een programmeerprobleem, en dat was het niet echt.

Dit was ook min of meer mijn ervaring van vandaag...

[P_Tingen]

Friits schreef op vrijdag 12 december 2025 @ 10:04:
@P_Tingen: Het is een aanname die werkt voor de puzzel-inputs. Ik kwam er zelf zo achter:

spoiler:

Polyomino-packing is een moeilijk probleem, dus ik wilde het opdelen in sub-problemen. Stap één daarbij is om te controleren of een sub-probleem óf triviaal is, óf onmogelijk. In beide gevallen kan je namelijk stoppen met zoeken. Nou bleek dat iedere input-regel al voldeed aan één van die eisen, dus dat zijn we eigenlijk klaar.

Je kan dan nog wel de rest van de code schrijven, maar die zal voor de puzzel-input toch nooit worden uitgevoerd.

Je uitleg is nog iets te abstract voor mij helaas. Kun je het nog simpeler uitleggen?

[Marcj]

spoiler:

Zelfde hier, zag een beetje tegenop toen ik vanmorgen de puzzel las. Maar andere jaren was de laatste puzzel altijd vrij makkelijk, dus dacht eerst wat verder te analyseren. Ik ging eerst kijken hoeveel puzzels sowieso wel en niet zouden passen en daar zat al niet zoveel meer tussen. Met nog ietsje meer aannames (dat ik 3/4 van de lege ruimte tussen de 9x9 blokken kan opvullen), kwam ik ook al het met juiste antwoord.
Ik klaag niet in ieder geval, dacht vanmorgen nog dat ik een NP-complete probleem moet proberen met heuristieken moest gaan oplossen. Blijken de heuristieken een stuk makkelijker dan eerste gedacht

[Friits]

P_Tingen schreef op vrijdag 12 december 2025 @ 11:22:
Je uitleg is nog iets te abstract voor mij helaas. Kun je het nog simpeler uitleggen?

Uiteraard!

Een puzzeltje bestaat uit:

• een aantal pakketjes (voor het gemak even allemaal maximaal 3 × 3 groot), en
• een H × B ruimte om ze in te passen.

Voor zo'n puzzel zijn er drie mogelijkheden:

1. De ruimte is groot genoeg om ze allemaal simpelweg naast (en onder) elkaar neer te leggen. Als we vier pakketjes van maximaal 3×3 hebben en een ruimte van 6×6, dan past dat sowieso.
2. De ruimte is zeker te klein om ze allemaal neer te leggen. Als we vier pakketjes van grootte 8 in een ruimte van 5×6 moeten leggen, dan past dat niet. De pakketjes nemen minstens 4×8=32 "vakjes" in, maar de ruimte is slechts 5×6=30 groot. Dan hoef je niet eens te gaan puzzelen, dat past nooit.
3. De ruimte is in principe groot genoeg om ze neer te leggen, maar niet op de triviale manier. In dit geval moet je dus echt gaan puzzelen.

Maar situatie 3 kwam niet voor in de puzzel-input, dus is het voldoende om voor iedere regel te checken of je met situatie 1 of 2 te maken hebt. Is het niet 1, dan is het 2, of vice versa.

[ Voor 3% gewijzigd door Friits op 12-12-2025 14:06 ]

[Friits]

Update over dag 10 (de machines met lampjes): ik heb een oplossing zonder LP (dus ook geen Gauss en co). De aanpak komt uit deze post op Reddit, en het wordt daar erg netjes uitgelegd.

Mijn code lost beide delen op in 0.6 0.25 seconden met de standaard Python interpreter. Het kan misschien nog sneller door bepaalde lijsten van booleans te representeren als integers en met bitmasks te werken, maar dat is niet mijn specialiteit en ik wilde het ook een beetje leesbaar houden

[ Voor 81% gewijzigd door Friits op 12-12-2025 17:01 ]

[P_Tingen]

Friits schreef op vrijdag 12 december 2025 @ 13:21:
[...]

Uiteraard!

Een puzzeltje bestaat uit:

• een aantal pakketjes (voor het gemak even allemaal maximaal 3 × 3 groot), en
• een H × B ruimte om ze in te passen.

Voor zo'n puzzel zijn er drie mogelijkheden:

1. De ruimte is groot genoeg om ze allemaal simpelweg naast (en onder) elkaar neer te leggen. Als we vier pakketjes van maximaal 3×3 hebben en een ruimte van 6×6, dan past dat sowieso.
2. De ruimte is zeker te klein om ze allemaal neer te leggen. Als we vier pakketjes van grootte 8 in een ruimte van 5×6 moeten leggen, dan past dat niet. De pakketjes nemen minstens 4×8=32 "vakjes" in, maar de ruimte is slechts 5×6=30 groot. Dan hoef je niet eens te gaan puzzelen, dat past nooit.
3. De ruimte is in principe groot genoeg om ze neer te leggen, maar niet op de triviale manier. In dit geval moet je dus echt gaan puzzelen.

Maar situatie 3 kwam niet voor in de puzzel-input, dus is het voldoende om voor iedere regel te checken of je met situatie 1 of 2 te maken hebt. Is het niet 1, dan is het 2, of vice versa.

Damn, inderdaad voldoet alles aan mogelijkheid 1. Ik heb mijn data in Excel geladen en daar met twee formules het antwoord ook uit kunnen krijgen.

Overigens zie ik nu ook waar ik in eerste instantie fout ging. Ik las weer eens niet goed en had de opgave andersom geïnterpreteerd, dus niet: hoeveel kadootjes passen er WEL, maar hoeveel passen er NIET. Dus mijn initiele berekening was min of meer goed, maar ik had het verkeerde deel. Tot nu snapte ik nog niet goed waarom het uiteindelijk werkte, maar nu dus wel. Tnx!

[FCA]

Voor dag 12 zie ik trouwens dat bij mij niet voor alle input ik een blok van 3x3 kan nemen, dan worden er enkele afgekeurd die blijkbaar wel kunnen.

[MatHack]

FCA schreef op vrijdag 12 december 2025 @ 19:30:
Voor dag 12 zie ik trouwens dat bij mij niet voor alle input ik een blok van 3x3 kan nemen, dan worden er enkele afgekeurd die blijkbaar wel kunnen.

Ja, de testdata bijvoorbeeld

[Soultaker]

FCA schreef op vrijdag 12 december 2025 @ 19:30:
Voor dag 12 zie ik trouwens dat bij mij niet voor alle input ik een blok van 3x3 kan nemen, dan worden er enkele afgekeurd die blijkbaar wel kunnen.

Weet je het zeker? Zou je deze code eens kunnen draaien op jouw invoer? Die zou een debugregel moeten printen als er een regel van je invoer bestaat die niet eenvoudig op te lossen is. Lijkt me sterk dat jij de enige bent met zo'n geval in je invoer

(Alleen de echte testinvoer, de voorbeeldinvoer heeft inderdaad 1 geval die je niet zo op kunt lossen, puur om je te misleiden.)

[FCA]

Soultaker schreef op zaterdag 13 december 2025 @ 07:04:
[...]

Weet je het zeker? Zou je deze code eens kunnen draaien op jouw invoer? Die zou een debugregel moeten printen als er een regel van je invoer bestaat die niet eenvoudig op te lossen is. Lijkt me sterk dat jij de enige bent met zo'n geval in je invoer

(Alleen de echte testinvoer, de voorbeeldinvoer heeft inderdaad 1 geval die je niet zo op kunt lossen, puur om je te misleiden.)

Ah, ik zie het al, een off-by one error.

spoiler:

Ik heb een aantal gevallen waar het aantal 3x3 blokjes precies pastte, en eerder checkte ik op (lengte * breedte) > 9* # cadeautjes, en het had natuurlijk lengte * breedte >= 9* #cadeautjes moeten zijn (naast het feit dat de nette oplossing natuurlijk integer deling door 3 van elke zijde is... Het is een wonder dat ik uberhaupt opgaves kan oplossen met dit soort blindheden

[Hagdos]

FCA schreef op zaterdag 13 december 2025 @ 09:10:
[...]

Ah, ik zie het al, een off-by one error.

spoiler:

Ik heb een aantal gevallen waar het aantal 3x3 blokjes precies pastte, en eerder checkte ik op (lengte * breedte) > 9* # cadeautjes, en het had natuurlijk lengte * breedte >= 9* #cadeautjes moeten zijn (naast het feit dat de nette oplossing natuurlijk integer deling door 3 van elke zijde is... Het is een wonder dat ik uberhaupt opgaves kan oplossen met dit soort blindheden

Ik heb een half uur geleden exact dezelfde fout gemaakt Wel zelf gevonden, maar beschamend lang mee bezig geweest.

[Soultaker]

Overigens wie in een post-AoC/pre-Kerstmis dip zit, kan ook nog de challenge van Infi (een van de sponsors van AoC) doen: https://aoc.infi.nl/2025

[FCA]

Nou, nu is het ook echt klaar voor mij. Afgelopen 2 dagen nog even zitten optimaliseren, en nu draait alles mooi onder de 1 sec in totaal. Uiteindelijk op ong 161ms, waarbij alle opgaven onderdeel 1 en 2 apart worden gedraaid (dus parsing en eventuele preprocessing ook niet gedeeld). De langstdurende oplossing is opgave 10 deel 2, die doet er ong 40ms over om tot een oplossing te komen. De snelste is dag 2. Deel 1 doet ie in ong. 8 microseconde, deel 2 in 16 microseconde .
Afgelopen dagen vooral dag 2, dag 8, dag 9 en dag 10 geoptimaliseerd.
Dag 2:

spoiler:

Ik hoefde me uiteindelijk niet in de Mobius functie in te lezen. Je kunt het ook beredeneren wanneer je dubbele gaat tegenkomen:
Je moet kijken naar de priemfactorisatie van het aantal digits. Zit daar een priemfactor 2x of meer in hoef je die uberhaupt niet mee te tellen. Verder moet je het aantal priemfactoren tellen: is dat even tel je die mee, is dat oneven dan moet je die negatief meetellen, om dubbeltelling te compenseren.

Edit: ik zie nu dat dat precies de Mobiusfunctie bepaald (nou ja, -1x de functie), maar dat maakt het mysterieuzer klinkender dan het is.

Dag 8:

spoiler:

De disjoint set datastructuur geimplementeerd. Uiteindelijk maar marginaal sneller (18ms vs 20ms) dan mijn oorspronkelijke versie waarbij ik in een bitset bijhield welke punten er in zaten. Grappig genoeg was een niet-triviale speedup (nou ja, ~13ms van 18 naar 5) voor deel 1 om niet alles te sorteren, maar een select te doen.

Dag 9:

spoiler:

Met behulp van een flood-fill en een 2d prefix sum hoef je alleen maar de hoekpunten te checken, en als je de coordinaten goed comprimeert, krijg je een oplossing die als O(k^2) schaalt, met k het aantal punten in de invoer.

Dag 10:

spoiler:

Een oplossing op basis van de bifurcaties
Als je vantevoren voor alle even/oneven combinaties de knopdrukken voorrekent, draait het nu in 40ms voor mij.

Uiteindelijk best tevreden met hoe het ging. Op werk uiteindelijk als 2e geeindigd, ondanks de moeilijkheden van dag 10 (maar daar was ik dus niet de enige in). Was blij dat ik de parsers van vorig jaar ter inspiratie had, en weinig gestruggeld met Rust dingen (in tegenstelling tot vorig jaar, heb dus wel wat bijgeleerd blijkbaar).

De moeilijkheidsgraad ging wel snel omhoog vanaf dag 7 vond ik. Aan de andere kant vind ik het wel weer mooi geweest, moet nog genoeg doen voor werk voor de kerst.
Dank aan iedereen voor de competitie en de mooie codekunstwerkjes, en @Soultaker voor de extra moeilijke opdrachten

[Soultaker]

FCA schreef op zondag 14 december 2025 @ 20:41:
Dag 2:

spoiler:

Je moet kijken naar de priemfactorisatie van het aantal digits. Zit daar een priemfactor 2x of meer in hoef je die uberhaupt niet mee te tellen. Verder moet je het aantal priemfactoren tellen: is dat even tel je die mee, is dat oneven dan moet je die negatief meetellen, om dubbeltelling te compenseren.

Top dat je het zelf hebt weten op te lossen! Voor de duidelijkheid: het is de priemfactorisatie van het aantal herhalingen (rep in je code) waar het om gaat, niet het aantal cijfers dat herhaald wordt (digits) of het totaal aantal cijfers. Dat is wat het zo verwarrend maakt.

Achteraf is het wel logisch, en als je de kwadraten van priemgetallen hebt geëlimineerd, is de rest feitelijk een toepassing van het inclusion-exclusion principle.

(Mogelijk kan je implementatie iets eenvoudiger: de special casing rond invalid_check_start ziet er een beetje verdacht uit.)

Dag 8:

spoiler:

De disjoint set datastructuur geimplementeerd. Uiteindelijk maar marginaal sneller (18ms vs 20ms) dan mijn oorspronkelijke versie waarbij ik in een bitset bijhield welke punten er in zaten. Grappig genoeg was een niet-triviale speedup (nou ja, ~13ms van 18 naar 5) voor deel 1 om niet alles te sorteren, maar een select te doen.

Dit had je vast zelf al bedacht, maar dat komt het genereren en sorteren van alle paren van punten O(n² log n) tijd kost, terwijl zelfs de meest naïeve implementatiie van disjoint sets (waarbij je simpelweg de hele array doorloopt om de ene set naar de andere te herlabelen) nog in O(n²) loopt, dus het optimaliseren van het tweede deel levert theoretisch geen fundamentale verbetering op. Die optimalisatie levert pas wat op als je ook het eerste deel efficiënter maakt, maar dat is veel moeilijker.

Dat was de reden dat ik voor deze dag uiteindelijk geen extra challenge had gepost; ik kon geen data sets genereren waarop het verschil tussen naïeve en slimme oplossingen voldoende groot was.

Dag 9:

spoiler:

Met behulp van een flood-fill en een 2d prefix sum hoef je alleen maar de hoekpunten te checken, en als je de coordinaten goed comprimeert, krijg je een oplossing die als O(k^2) schaalt, met k het aantal punten in de invoer.

Mooi gevonden met die prefix sum!

Zit nog wel een bugje in je implementatie. Bijvoorbeeld op deze invoer:

2,1
4,1
4,4
1,4
1,2
2,2

zou 12 het antwoord moeten zijn bij deel 2.

spoiler: hint

off by 1

Was blij dat ik de parsers van vorig jaar ter inspiratie had, en weinig gestruggeld met Rust dingen (in tegenstelling tot vorig jaar, heb dus wel wat bijgeleerd blijkbaar).

Qua parsing was dit jaar ook wel echt eenvoudiger; ik heb niet één keer een reguliere expressie hoeven gebruiken.

Overigens vind ik jouw Rust code erg goed leesbaar, terwijl ik eigenlijk geen Rust kan. Dus wat mij betreft ben je goed bezig.

De moeilijkheidsgraad ging wel snel omhoog vanaf dag 7 vond ik. Aan de andere kant vind ik het wel weer mooi geweest, moet nog genoeg doen voor werk voor de kerst.

De interessante algoritmes komen vaak pas na een paar dagen, en zijn vaak voor de officiële invoeren helemaal niet nodig; dag 10 was de uitzondering op de regel. Persoonlijk zou ik het wel leuk vinden als de opgaven wat moeilijker waren, met wat meer tijd ertussen om er goed over na te denken, maar dat is eigenlijk het tegenovergestelde van de “advent”-formule natuurlijk.

[FCA]

Soultaker schreef op maandag 15 december 2025 @ 14:27:
[...]

Top dat je het zelf hebt weten op te lossen! Voor de duidelijkheid: het is de priemfactorisatie van het aantal herhalingen (rep in je code) waar het om gaat, niet het aantal cijfers dat herhaald wordt (digits) of het totaal aantal cijfers. Dat is wat het zo verwarrend maakt.

Inderdaad, draaide wat dingen om in de uitleg...

(Mogelijk kan je implementatie iets eenvoudiger: de special casing rond invalid_check_start ziet er een beetje verdacht uit.)

Ik heb er nog over zitten denken, maar het is de eenvoudigste oplossing denk ik om de 2 gevallen goed te doen:
1. Je komt precies uit op een rand van je interval (invalid_check_start * factor = start_id),
2. Of niet, en dan zit je precies 1 te laag. De while loop is wat lelijk, komt nog uit een eerdere versie
Ik vind het nu elegant genoeg in ieder geval

[...]

Dit had je vast zelf al bedacht, maar dat komt het genereren en sorteren van alle paren van punten O(n² log n) tijd kost, terwijl zelfs de meest naïeve implementatiie van disjoint sets (waarbij je simpelweg de hele array doorloopt om de ene set naar de andere te herlabelen) nog in O(n²) loopt, dus het optimaliseren van het tweede deel levert theoretisch geen fundamentale verbetering op. Die optimalisatie levert pas wat op als je ook het eerste deel efficiënter maakt, maar dat is veel moeilijker.

Dat was de reden dat ik voor deze dag uiteindelijk geen extra challenge had gepost; ik kon geen data sets genereren waarop het verschil tussen naïeve en slimme oplossingen voldoende groot was.

Inderdaad, het wordt gedomineerd door de sortering. Ik zie trouwens zo 1,2,3 geen oplossing die dat wegneemt, misschien een k-d tree structuur, maar hoe merge je punten dan? Of een minimum spanning tree, en dan het langste element daaruit kiezen? Is dat gegarandeerd de goede? Hmm... interessant.

[...]

Mooi gevonden met die prefix sum!

Zit nog wel een bugje in je implementatie. Bijvoorbeeld op deze invoer:

2,1
4,1
4,4
1,4
1,2
2,2

zou 12 het antwoord moeten zijn bij deel 2.

spoiler: hint

off by 1

Niet alleen een off-by-one (4 stuks wel te verstaan), maar ook nog een omdraaiing van onder en boven (of ze heffen elkaar een soort van op natuurlijk, maar dan is de naamgeving van de variabelen wel onhandig gekozen). Oops
De prefix sum tip had ik trouwens ergens van reddit geplukt.

[...]

Qua parsing was dit jaar ook wel echt eenvoudiger; ik heb niet één keer een reguliere expressie hoeven gebruiken.

Overigens vind ik jouw Rust code erg goed leesbaar, terwijl ik eigenlijk geen Rust kan. Dus wat mij betreft ben je goed bezig.

Dank. Ik ben dan ook eigenlijk een Python programmeur, dus mijn Rust code heeft waarschijnlijk een hoop Pythonisms erin nog, en niet veel Rust

[...]

De interessante algoritmes komen vaak pas na een paar dagen, en zijn vaak voor de officiële invoeren helemaal niet nodig; dag 10 was de uitzondering op de regel. Persoonlijk zou ik het wel leuk vinden als de opgaven wat moeilijker waren, met wat meer tijd ertussen om er goed over na te denken, maar dat is eigenlijk het tegenovergestelde van de “advent”-formule natuurlijk.

Aan de ene kant wel, aan de andere kant gaat de competitieve kant in mij met mij aan de haal. Na vorig jaar mocht ik van mijn vrouw niet meer de dagen voor Kerst aan aoc werken, omdat dat de kerstsfeer verpestte

[P_Tingen]

FCA schreef op maandag 15 december 2025 @ 20:56:
Na vorig jaar mocht ik van mijn vrouw niet meer de dagen voor Kerst aan aoc werken, omdat dat de kerstsfeer verpestte

Hier ook wel blij dat AoC dit jaar maar 12 dagen is, al is het dan niet omdat de competitiedrang met me aan de haal gaat. Ik merk dat het makkelijker is om vol te houden (no shit, Sherlock). Voorgaande jaren merkte ik wel dat - zeker de laatste dagen voor kerst - een opgave was om tijd te vinden. Dan ook nog dubbele tijd nodig eigenlijk omdat de opgaves dan meestal wat pittiger zijn

[Friits]

Ja, ik ben ook blij met de twaalf dagen. Had vooraf gedacht dat ik het jammer zou vinden (AoC is leuk, en minder AoC is dus minder leuk), maar vind het wel mooi zo. Klaar voordat de traditionele AoC-vermoeidheid toeslaat, en nu alle tijd voor de AIVD kerstpuzzel. Ik heb m'n eerste anagrammen-bruteforcers, next-level-sudoku-solver en Enigma-machine-variant alweer geïmplementeerd

[Soultaker]

FCA schreef op maandag 15 december 2025 @ 20:56:
Ik heb er nog over zitten denken, maar het is de eenvoudigste oplossing denk ik om de 2 gevallen goed te doen:
1. Je komt precies uit op een rand van je interval (invalid_check_start * factor = start_id),
2. Of niet, en dan zit je precies 1 te laag. De while loop is wat lelijk, komt nog uit een eerdere versie

Ik denk dat je gelijk hebt.

De truc die ik in gedachten had was dat als je een functie f(a, b) hebt die de opties in range [a, b] telt, dat je die kunt herschrijven als f(0, b) - f(0, a - 1), wat vaak het voordeel heeft dat de logica versimpeld wordt omdat je alleen met de bovengrens te maken hebt. In dit geval helpt het niet veel, want zelfs als a=0, dan zit je nog met de ondergrens van 10^{digits - 1} aangezien je geen leading zeros mag hebben.

Het enige wat ik nog kon bedenken is om de gedeelde logica van deel 1 en deel 2 af te splitsen in een aparte functie: https://pastebin.com/p5NxBkRe Het is mijns inziens wel ietsje leesbaarder maar geen fundamentele verbetering. Doe ermee wat je wil.

Inderdaad, het wordt gedomineerd door de sortering. Ik zie trouwens zo 1,2,3 geen oplossing die dat wegneemt, misschien een k-d tree structuur, maar hoe merge je punten dan? Of een minimum spanning tree, en dan het langste element daaruit kiezen? Is dat gegarandeerd de goede? Hmm... interessant.

Het is nog niet zo eenvoudig om een fundamentele verbetering te verzinnen. Zelfs als je met een of andere 3D data structuur efficiënt nabijgelegen punten kunt vinden, moet je worst case nog steeds O(n²) van die paren genereren, en een overhead van O(log n) per paar is het minste wat je kunt verwachten.

Bij de officiële invoer is de graaf verbonden nadat ~1% van de edges doorlopen is. In dat geval kan incrementeel genereren van paren een voordeel hebben. Maar ik had ook testinvoeren gegenereerd waarbij je ongeveer 50% van de paren moet doorlopen; dan heb je het dus over ~n²/4 paren = O(n²) paren.

Om die gevallen efficiënter te maken heb je een datastructuur nodig die al verbonden paren daadwerkelijk kan overslaan, maar daar kon ik geen goed idee voor bedenken.

Overigens nu we het over geometrie hebben, valt me op dat we @.oisyn sinds November niet meer gezien hebben in dit topic.

[.oisyn]

Klopt, ik heb amper tijd gehad en toen ik te ver achter liep kon ik ook de zin niet echt opbrengen .

Ik ga in de kerstvakantie even knallen. Denk ik. No promises

[Marcj]

Nou, ik zat nog met dag 10 in mijn hoofd, die moest wel een stuk sneller kunnen. Eerst was ik ook bezig met lineaire algebra (dank @Soultaker voor het voorbeeld), maar ik had echt moeite om dit goed en snel te laten werken. Uiteindelijk werkte het wel redelijk, maar liep nog tegen een edge-case aan om op te lossen.

Toen bedacht ik me een manier om met binaire getallen het probleem steeds op te delen en een stuk deel 1 te hergebruiken. (Ik kom er nu achter dat dit waarschijnlijk ook de bedoelde manier is en er op Reddit van alles over geschreven is). Deze implementatie was veel simpler, beter te begrijpen en had al snel een oplossing die in ~20ms liep.

Maar ja, toen bedacht ik me dat ik alle joltages ook als een SIMD vector kon representeren van 16 u16 getallen (er zitten geen grotere problemen in gelukkig). Nu kon ik dingen helemaal snel laten lopen, door ook switches te combineren tot een SIMD vector.

Hoe dan ook, mijn oplossing van nu heeft deze output:

code:

❯ : target/release/day10
Executing
 ├── Input parsed in 173µs
 ├── Part 1 calculated in 419µs: 425
 ├── Part 2 calculated in 3,036µs: 15883
 └── Total time: 3,740µs

Uhm, ik denk dat ik wel klaar ben voor nu. Toch eens een tijdje gespendeerd aan technische details waar ik anders nooit mijn tijd in zou steken. Maar het is toch ongelooflijk hoe snel computers eigenlijk geworden zijn

Dit alles op mijn macBook Pro van 4 jaar oud met een M1 processor