Advent of Code 2023

[Soultaker]

Thorwing schreef op donderdag 21 december 2023 @ 19:31:
Kijk, dat heb ik dan wel weer, dezelfde oplossing . Haha, maar ik moet ook eerlijk zeggen dat mijn oplossing niet werkt voor jouw 'hele moeilijke case' (elders in de thread) Mijn oplossing gaat er namelijk vanuit dat de set aan punten in de frontier vaker voor kan komen. En bij het vinden van 3 maak ik daar een quadratic formule voor.

Mogelijk zit daar het probleem. Ik doe iets soortgelijks maar ik spendeer iets meer tijd aan het detecteren van een patroon, zonder er van uit te gaan dat het na 3 keer vaststaat.

Hier vind ik helaas ook geen oplossing voor, op stap 5 zit een frontier van 3 punten die daarna nooit meer voorkomt, en daar breekt mijn code op.

Ik kan deze ook niet volledig oplossen. Bruteforcen tot 1000 of 5000 stappen geeft 1072 respectievelijk 5360 als antwoord.

Diderikdm schreef op donderdag 21 december 2023 @ 18:08:
Python dag 21

Mooie compacte oplossing! Hoe kwam je op het idee voor die cykel-detectie?

Een paar implementatie-tips (ik weet niet of je er op zit te wachten maar ik kan het niet laten):

- In plaats van een binary heap kun je voor een breadth-first search beter een deque gebruiken; is aanzienlijk sneller.
- De check if (x, y) in seen kun je beter doen vóór je de state in de queue stopt op regel 25. Is ook sneller.
- De seen-set is eigenlijk de combinatie van de even/odd-set. Je kunt beter 2 sets gebruiken i.p.v. 3.
- De grid dictionary lijkt me niet zo zinnig aangezien 'ie precies dezelfde informatie bevat als data, maar kostbaarder is om te indexeren; simpeler om die achterwege te laten?
- Tenslotte, misschien een persoonlijke voorkeur, maar ik vind dat je hier de tuple assignment syntax een beetje misbruikt:

Python:

ln, steps, cycle, seen, even, odd, n = len(data), 0, [], set(), set(), set(), 26501365

Het is zo lastig te zien welke waarde precies aan welke variabele wordt toegekend (is cycle nu een lege lijst of een set?). Als je al die assignments per se op één regel wil zetten, doe het dan zo:

Python:

ln = len(data); steps = 0; cycle = []; seen = set(); even = set(); odd = set(); n = 26501365

edit:
En dit stukje:

Python:

for x in range(n // (ln * 2)):
    p2 += offset
    offset += increment

Kun je volgens de formule voor driehoeksgetallen omschrijven naar de gesloten vorm:

Python:

x = n // (ln * 2)
p2 += x*offset + x*(x - 1)//2*increment

Als ik die ideëen combineer kom ik op de volgende code: day21.py

[ Voor 6% gewijzigd door Soultaker op 21-12-2023 20:18 ]

[Soultaker]

Asgardian28 schreef op donderdag 21 december 2023 @ 20:00:
Ik ben vandaag 12 uur bezig geweest.

Wow, punten voor toewijding! Ik denk soms dat ik te veel tijd besteed aan AoC maar 12 uur per dag haal ik niet. Ik hoop dat je 'm in die tijd tenminste hebt opgelost!

Samen met Slam Salmon de moeilijkste ooit imo

Slam Salmon Welk probleem was dat?

[Diderikdm]

Soultaker schreef op donderdag 21 december 2023 @ 20:03:
[...]

Mogelijk zit daar het probleem. Ik doe iets soortgelijks maar ik spendeer iets meer tijd aan het detecteren van een patroon, zonder er van uit te gaan dat het na 3 keer vaststaat.


[...]

Ik kan deze ook niet volledig oplossen. Bruteforcen tot 1000 of 5000 stappen geeft 1072 respectievelijk 5360 als antwoord.


[...]

Mooie compacte oplossing! Hoe kwam je op het idee voor die cykel-detectie?

Een paar implementatie-tips (ik weet niet of je er op zit te wachten maar ik kan het niet laten):

- In plaats van een binary heap kun je voor een breadth-first search beter een deque gebruiken; is aanzienlijk sneller.
- De check if (x, y) in seen kun je beter doen vóór je de state in de queue stopt op regel 25. Is ook sneller.
- De seen-set is eigenlijk de combinatie van de even/odd-set. Je kunt beter 2 sets gebruiken i.p.v. 3.
- De grid dictionary lijkt me niet zo zinnig aangezien 'ie precies dezelfde informatie bevat als data, maar kostbaarder is om te indexeren; simpeler om die achterwege te laten?
- Tenslotte, misschien een persoonlijke voorkeur, maar ik vind dat je hier de tuple assignment syntax een beetje misbruikt:

Python:

ln, steps, cycle, seen, even, odd, n = len(data), 0, [], set(), set(), set(), 26501365

Het is zo lastig te zien welke waarde precies aan welke variabele wordt toegekend (is cycle nu een lege lijst of een set?). Als je al die assignments per se op één regel wil zetten, doe het dan zo:

Python:

ln = len(data); steps = 0; cycle = []; seen = set(); even = set(); odd = set(); n = 26501365

Als ik die ideëen combineer kom ik op de volgende code: day21.py

Mooi! Normaal zou ik nog het e.e.a. opschonen voor het posten maar was helemaal klaar met deze dag Tips zijn altijd welkom, no worries! Ben nog aan het leren.

* Deque, goeie! Heb dit eerder gebruikt, maar was er zo niet op gekomen, thanks! Echt aanzienlijk sneller zeg
* seen-set, klopt! Had inderdaad een even/odd set (zonder seen) om te checken, maar had die seen erbij gepropt omdat ik gek werd tijdens debuggen
* grid, goeie, is een tic; gebruik vaak een subset van data in grids om grid.get(x, default) te doen, maar dat bleek hier niet nodig idd
* ;'s gebruik ik nog niet echt, maakt het wel leesbaarder, thanks!

spoiler:

Voor de cycle-detectie; hier kwam ik achter tijdens het debuggen van het voorbeeld. Het viel me op bij het itereren over steps en het printen van even (of odd) dat het verschil tussen step en step + 1 vanaf ongeveer 2/3 volledige breedtes van het grid hetzelfde verschil was als tussen step + 22 (11 x 2 voor voorbeeld) en step + 1 + 22. 2x gridgrootte omdat de ene helft even en de andere helf odd is voordat het patroon herhaalt. Dat bleek voor alle 22 waarden het geval, ongeacht hoe veel grids ik opzij ging. Dat deed me vermoeden dat er een cycle te vinden was. Duurde wel even voor ik die goed had, want alle even steps werkte maar de odds niet

[Soultaker]

Vandaag een niet al te ingewikkelde opgave (gelukkig, na de moeilijke puzzel gisteren).

spoiler: Oplossing dag 22

Eerst bereken ik waar elk blokje valt. Dat doe ik door de blokjes te sorteren op laagste z-cöordinaat, en vervolgens een set bij te houden welk punt in de 3D-ruimte door welk blokje bezet is. Dan kun je voor elk blokje berekenen welke blokjes er direct onder liggen, en zolang het antwoord “geen” is, laat je 'm stapje-voor-stapje vallen totdat hij ofwel op de bodem ligt, of op een of meer andere blokjes rust.

Tijdens dit proces bereken je ook voor ieder blokje: op welke andere blokjes het rust, en welke andere blokjes er op rusten. Dit kun je gebruiken voor zowel deel 1 als deel 2, waar ik gewoon een soort breadth-first search heb gemaakt.

Een aantal implementatie-details kunnen efficiënter, maar voor de officiële testinvoer blijkt dat niet nodig.

edit: ik heb de eerste fase nog geoptimaliseerd naar bijhouden per (x, y) coördinaat wat de hoogste z-waarde is; op die manier kun je in 1 keer berekenen hoe ver het blokje valt i.p.v. dat je 't stapje bij stapje doet.

Python code: 22.py

[ Voor 10% gewijzigd door Soultaker op 22-12-2023 08:17 ]

[FCA]

Leuke opgave vandaag

spoiler:

Eerst sorteren op z-hoogte, 3D array maken, en naar beneden laten vallen tot er iets onder zit. Daarna voor elk blokje nagaan of er 1 of meerdere blokjes direct onder liggen (en natuurlijk checken dat dat niet het blokje zelf is... ).

Deel 2

spoiler:

Graafalgoritmes heb ik niet echt paraat (nooit een Informatica opleiding gedaan), dus dat werd even aanpoten/denken.
Uiteindelijk een beetje lelijk:
- Maak een dict aan waarin voor elk blokje staat waar op welke blokjes die steunt
- voor elk punt in de lijst van blokjes die je niet mag disintegraten van deel 1:
- Ga voor alle blokjes na wat hun "root" blokken zijn (de blokjes die verder nergens meer op steunen), d.m.v. een recursieve functie, en voeg als extra conditie toe dat het blokje wat disintegrated is ook nergens op steunt.
- Als die root blok verzameling voor een specifiek blok alleen bestaat uit het blokje wat je nu hebt gedisintegrate dan valt dit blokje.
- Gooi een memoization op de recursieve functie en klaar is kees

[Asgardian28]

Soultaker schreef op donderdag 21 december 2023 @ 20:18:
[...]

Wow, punten voor toewijding! Ik denk soms dat ik te veel tijd besteed aan AoC maar 12 uur per dag haal ik niet. Ik hoop dat je 'm in die tijd tenminste hebt opgelost!


[...]

Slam Salmon Welk probleem was dat?

Normaal gesproken ben ik ook wel binnen uurtje klaar, maar er zitten van die krakers tussen zoals gisteren. En is soort van erezaak om zonder tips dan toch op te lossen.

Ik heb het uiteindelijk gesimuleerd met 8 verschillende soorten tuinen:
* 4 uiteindes van de diamant (die een x of y coordinaat met een 0 hadden)
* 4 andere tuinen afhankelijk van de cel waar de tuin werd binnengelopen
Deze 8 tuinen hebben een uniek en altijd gelijk groeipatroon en creeren op gezette tijden ook weer unieke en altijd dezelfde nieuwe babytuintjes. Het groeipatroon is gewoon een lijst met hoeveel cellen er bereikbaar zijn sinds de geboorte van de tuin. Als de tuin z'n max bepaald dan stop ik met het groeipatroon (vanaf daar is het zo'n switch geworden)

Daarna daarna de niveaus van de diamant over loopen (niveau 0 is enkel de starttuin, niveau 1 is alle uiteindes erbij (+4), niveau 2 is +8, niveau 3 is +12, niveau 4 is +16 etc. Op elk niveau komen er 4 uiteindes bij en de 4 andere tuinen telkens eentje extra. Dan hoef je dus eigenlijk maar 26M keer 8 bewerkingen uit te voeren.

Gelukkig heb ik deze week al vrij genomen

Slam Salmon is dag 2019 dag 22. Met dat spel kaarten dat je heel vaak moet schudden

[Asgardian28]

Voor vandaag ben ik wel tevreden met m'n keuze voor datastructuren

spoiler: spoiler

1) Totaalset met cubes
2) Lijst met blokken, waarbij een blok een set van cubes is
Hiermee was het goed te doen. Voor deel 2 maak je per blokje een kopie van je totaalset en je blokkenlijst, haalt je blokje eruit en simuleer je het vallen

Voor deel twee dacht ik dat het om het maximale aantal blokjes ging, in plaats van de som. Advent of Reading...

[Friits]

Asgardian28 schreef op donderdag 21 december 2023 @ 20:00:
[...]

@Friits Ben jij soms 4HbQ op reddit? Die heeft zo'n beetje dezelfde code. Zo ja, geniale code schrijf je. Zo nee, beter goed gejat dan slecht bedacht zullen we maar zeggen.

Yup, en thanks!

Voor vandaag heb ik NumPy maar uit de kast gehaald: code.

Ik ben niet heel erg thuis in NumPy, dus ik ben benieuwd wat er mooier/sneller/beter kan

[ Voor 64% gewijzigd door Friits op 22-12-2023 09:12 ]

[Varienaja]

Naïeve oplossing. Brute force naar een antwoord in 2,5s.

[Asgardian28]

Friits schreef op vrijdag 22 december 2023 @ 08:43:
[...]

Yup, en thanks!

Voor vandaag heb ik NumPy maar uit de kast gehaald: code.

Ik ben niet heel erg thuis in NumPy, dus ik ben benieuwd wat er mooier/sneller/beter kan

Oe wat gaaf, een levende legende op GoT , ik kijk afgelopen jaren alleen nog maar naar jouw oplossingen om weer wat van Python te leren. Inspirerend!

[Soultaker]

Asgardian28 schreef op vrijdag 22 december 2023 @ 08:31:
Slam Salmon is dag 2019 dag 22. Met dat spel kaarten dat je heel vaak moet schudden.

Ohh, die heet eigenlijk Slam Shuffle vandaar dat ik 'm niet kon vinden met Google. Dat was inderdaad een hele kluif!

[MatHack]

Voor nu vandaag ook maar lekker bruteforce gedaan (duurde ongeveer 30 seconden totaal voor beide delen). Heb al wel gezien met debuggen dat mijn valsimulatie traag is, 'k heb alleen geen zin om daar voor nu verder naar te kijken.

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

[MatHack]

Ik zat nog te kijken naar deel 2 van gisteren (dag 21) en ..

spoiler:

Ik zag dat de echte set inderdaad de X- en Y-as vanaf het beginpunt blanco zijn, maar in de testset is dit niet zo (rocks op elk van de windrichtingen). Wat ik graag zou willen weten is of dit nog uitmaakt in de oplossingsrichting?

[Soultaker]

(Over dag 21:)

MatHack schreef op vrijdag 22 december 2023 @ 10:15:

spoiler:

Ik zag dat de echte set inderdaad de X- en Y-as vanaf het beginpunt blanco zijn, maar in de testset is dit niet zo (rocks op elk van de windrichtingen). Wat ik graag zou willen weten is of dit nog uitmaakt in de oplossingsrichting?

Het is niet strict noodzakelijk, maar die observatie kun je wel gebruiken om tot een relatief eenvoudige oplossing te komen. Het is op zichzelf echter niet genoeg; je moet het met een klein aantal andere observaties combineren.

Zonder te veel weg te geven: je kunt er van uitgaan dat alles wat niet overduidelijk random is met opzet zo gekozen is en bruikbaar is om je oplossing te versimpelen.

Als je niet weet welke observaties je nog meer zou kunnen doen:

spoiler:

plot je rotstuintje eens in een bitmap zodat je het van een grotere afstand kunt bekijken, dan valt je mogelijk iets op.

[ Voor 11% gewijzigd door Soultaker op 22-12-2023 10:31 ]

[CrossProd]

Ik ben 2 uur verloren in part 1 door

spoiler:

een super domme bug bij het zoeken of een brick x verwijderd kon worden. Zodra ik een eerste brick y supported by brick x vond die meer dan 1 support had voegde ik de brick x toe aan bricks die verwijderd konden worden zonder te checken of er nog andere bricks steunde op brick x. Ik had al mijn debugging gefocused op de simulatie maar daar was dus niks mis mee.

Day 22 in Swift

[Marcj]

Ik heb ook eindelijk dag 21 opgelost! Ik heb gevoel de hele tijd achter te lopen

Volgens mij heb ik een iets andere implementatie dan sommigen. Mijn observatie was:

spoiler:

Ik heb eerst de nummers gegenereerd voor zover redelijk te berekenen was. Daarna in een spreadsheet aan het spelen geweest om patronen te herkennen. Toen zag ik bij de echte input dat er een constante 2e afgeleide was als ik alleen naar elke 131ste kijk.... Dit werkt echter alleen op de echte input, bij het voorbeeld werkt dit helemaal niet.

[KabouterSuper]

Vandaag niet mijn beste dag....deel 1 ging nog wel, maar al 6s draaitijd. Deel 2 duurde ongeveer vijf minuten. En dan ook nog slecht geprogrammeerd omdat ik in eerste instantie alleen keek naar de coordinaten. Een blokje dat valt op de plek van een blokje met dezelfde grootte werd daarom niet meegeteld. Ach, morgen weer een dag om het mooi te doen.

[Soultaker]

Marcj schreef op vrijdag 22 december 2023 @ 10:56:
Volgens mij heb ik een iets andere implementatie dan sommigen. Mijn observatie was:

spoiler:

Ik heb eerst de nummers gegenereerd voor zover redelijk te berekenen was. Daarna in een spreadsheet aan het spelen geweest om patronen te herkennen. Toen zag ik bij de echte input dat er een constante 2e afgeleide was als ik alleen naar elke 131ste kijk....

Dit klinkt als dezelfde analyse die @Diderikdm ook gedaan heeft. Slim, ik had het zelf niet zo benadert.

spoiler:

Dit werkt echter alleen op de echte input, bij het voorbeeld werkt dit helemaal niet.

Dit vond ik een van de de nadelen van dit probleem. De voorbeeldinvoer is niet representatief voor de echte invoer; als je dus eerst de voorbeeldinvoer op probeert te lossen (zoals ik vrijwel altijd doe) dan zit je eigenlijk te moeilijk te denken. Persoonlijk vind ik het een beetje flauw maar je kunt ook beargumenteren dat goed naar de invoer kijken onderdeel van het probleem is.

[Asgardian28]

Soultaker schreef op vrijdag 22 december 2023 @ 09:12:
[...]

Ohh, die heet eigenlijk Slam Shuffle vandaar dat ik 'm niet kon vinden met Google. Dat was inderdaad een hele kluif!

Ah haha, foutje bedankt! Slam shuffle idd. Wat een drama was dat! Iets met modular multiplicative inverse en cryptografie

[Remcoder]

Soultaker schreef op vrijdag 22 december 2023 @ 14:02:
[...]

Dit klinkt als dezelfde analyse die @Diderikdm ook gedaan heeft. Slim, ik had het zelf niet zo benadert.


[...]

Dit vond ik een van de de nadelen van dit probleem. De voorbeeldinvoer is niet representatief voor de echte invoer; als je dus eerst de voorbeeldinvoer op probeert te lossen (zoals ik vrijwel altijd doe) dan zit je eigenlijk te moeilijk te denken. Persoonlijk vind ik het een beetje flauw maar je kunt ook beargumenteren dat goed naar de invoer kijken onderdeel van het probleem is.

Mja, dat vond ik ook erg naar aan gister, uiteindelijk heb ik flink door de solutions thread gebrowsed om uiteindelijk iets in elkaar te krassen wat werkt voor de echte input, en blijkbaar voor een paar voorbeeld inputs, maar nog niet voor alle voorbeeld inputs.

Ik probeer altijd mijn oplossing zo te schrijven dat ik er elke willekeurige AoC input aan kan geven, en dat houdt dus ook in de voorbeeld inputs.

Voor dit jaar mis ik nog de puzzel waarbij we een karakters moeten lezen, we hebben tot nu toe alleen nog numerieke antwoorden moeten bepalen. Ik ben benieuwd of die nog komt, ik vind die persoonlijk altijd wel leuk.

[Soultaker]

Remcoder schreef op vrijdag 22 december 2023 @ 14:17:
Ik probeer altijd mijn oplossing zo te schrijven dat ik er elke willekeurige AoC input aan kan geven, en dat houdt dus ook in de voorbeeld inputs.

Ja, dat probeer ik meestal ook.

Mijn oplossing voor Dag 21 werkt (denk ik) wel voor alle mogelijk inputs, onder een paar aannames: de invoer is een vierkant van oneven grootte, en de buitenste rand is leeg. Dit geldt zowel voor de officiële testinvoer als de voorbeeldinvoer.

Voor dit jaar mis ik nog de puzzel waarbij we een karakters moeten lezen, we hebben tot nu toe alleen nog numerieke antwoorden moeten bepalen.

We missen ook nog het implementeer-een-rare-instructie-set probleem dat er meestal bij zit, zoals de IntCode machine van 2019. Misschien komt 'ie nog!

[Remcoder]

Soultaker schreef op vrijdag 22 december 2023 @ 14:26:
[...]
We missen ook nog het implementeer-een-rare-instructie-set probleem dat er meestal bij zit, zoals de IntCode machine van 2019. Misschien komt 'ie nog!

Mmh, ik vond dag 20 wel redelijk in die categorie vallen, vooral omdat je daar voor deel 2 wel echt de input moest analyseren zoals wel vaker gebeurt bij de instructie-set puzzels.

[Soultaker]

Extra testinvoer voor dag 22: aoc-2023-day-22-challenge-1-to-3-r1.zip (let op: r1 bevat een gefixte versie van invoer 1, met dank aan @.oisyn voor het melden!)

Correcte antwoorden modulo 97:

• challenge-1.txt: 67 (deel 1), 7 (deel 2).
• challenge-1-r1.txt: 54 (deel 1), 24 (deel 2).
• challenge-2.txt: 1 (deel 1), 20 (deel 2).
• challenge-3.txt: 85 (deel 1), 83 (deel 2).

Referentietijden in Python: 0,2 s, 1,2 s, 8 s.

[ Voor 32% gewijzigd door Soultaker op 23-12-2023 18:38 ]

[Diderikdm]

Python dag 22

Stilte voor de storm vandaag? Laatste weekend is aanstaande, ben benieuwd.

[Marcj]

Soultaker schreef op vrijdag 22 december 2023 @ 14:26:
[...]

Ja, dat probeer ik meestal ook.

Mijn oplossing voor Dag 21 werkt (denk ik) wel voor alle mogelijk inputs, onder een paar aannames: de invoer is een vierkant van oneven grootte, en de buitenste rand is leeg. Dit geldt zowel voor de officiële testinvoer als de voorbeeldinvoer.


[...]

We missen ook nog het implementeer-een-rare-instructie-set probleem dat er meestal bij zit, zoals de IntCode machine van 2019. Misschien komt 'ie nog!

Dat is wat ik ook altijd probeer, maar deze dag was dus mislukt wat dat betreft. Ik laat nu wel met een check zien dat de invoer niet aan mijn verwachting voldoet en stopt hij dus gewoon.

Het voordeel van mijn oplossing is wel dat hij binnen 50ms runt

[Varienaja]

Soultaker schreef op vrijdag 22 december 2023 @ 14:37:
Extra testinvoer voor dag 22:

• challenge-1.txt: OK 22s 2,6s.
• challenge-2.txt: OK 1070s.
• challenge-3.txt: Geen zin om zo lang te wachten.

Eerst ging mijn oplossing stuk. Er zat nog een domme typefout in. Daarna heb ik de boel versneld door de baksteen met zijn stukje vloer te vergelijken ipv de hele vloer met de baksteen. Daardoor kon ik challenge 1 überhaupt in eindige tijd uitvoeren. Zo te zien valt er nog vééééél meer te optimaliseren. Het schaalt momenteel in ieder geval mooi kl*te met het aantal bakstenen.

[Soultaker]

Remcoder schreef op vrijdag 22 december 2023 @ 14:31:
Mmh, ik vond dag 20 wel redelijk in die categorie vallen, vooral omdat je daar voor deel 2 wel echt de input moest analyseren zoals wel vaker gebeurt bij de instructie-set puzzels.

Ah ja, zou kunnen dat dat dag 20 was. We hebben ook nog maar 2½ dag te gaan dus een hele set van puzzels zoals met IntCode zit er sowieso niet in.

Varienaja schreef op vrijdag 22 december 2023 @ 17:45:

• challenge-1.txt: OK 22s 2,6s.
• challenge-2.txt: OK 1070s.
• challenge-3.txt: Geen zin om zo lang te wachten.

Eerst ging mijn oplossing stuk. Er zat nog een domme typefout in. Daarna heb ik de boel versneld door de baksteen met zijn stukje vloer te vergelijken ipv de hele vloer met de baksteen. Daardoor kon ik challenge 1 überhaupt in eindige tijd uitvoeren. Zo te zien valt er nog vééééél meer te optimaliseren. Het schaalt momenteel in ieder geval mooi kl*te met het aantal bakstenen.

Niet slecht! Ik moest mijn oorspronkelijke oplossing ook aanzienlijk verbeteren om deze problemen op te kunnen lossen (zonder optimalisaties doet 'ie net challenge-1.txt in 1 minuut). Het is ook de bedoeling om je een beetje uit te dagen je oplossing sneller en meer solide te maken, en zoals je terecht opmerkt, zijn er bij dit probleem veel plekken waar je makkelijk veel snelheidswinst kunt behalen. Dat maakt het een leuk probleem naar mijn mening.

[ Voor 16% gewijzigd door Soultaker op 22-12-2023 18:35 ]

[Asgardian28]

We hebben ook nog geen game of life puzzel gehad. Of zou dat dag 25 worden?

[FCA]

Soultaker schreef op vrijdag 22 december 2023 @ 14:37:
Extra testinvoer voor dag 22: aoc-2023-day-22-challenge-1-to-3.zip

Correcte antwoorden modulo 97:

• challenge-1.txt: 67 (deel 1), 7 (deel 2).
• challenge-2.txt: 1 (deel 1), 20 (deel 2).
• challenge-3.txt: 85 (deel 1), 83 (deel 2).

Referentietijden in Python: 0,3 s, 1,7 s, 12 s.

@FCA: werkt jouw oplossing op deze testdata? Hoe snel runt 'ie?

Challenge 1 werkt (nadat ik eerst deel 1 een stuk sneller had gemaakt, niet meer 1 per keer droppen, maar netjes bijhouden hoever je naar beneden kunt vallen en direct daar neer zetten). Had eerst nog een off-by-one error in deel 2 die ik blijkbaar niet triggerde in de officiele invoer. Tijd voor challenge 1 is niet geweldig, 40,4 s.

Challenge 2 gooit een OOM bij het alloceren van de initiele array voor de posities
Misschien ga ik eens van de kerstvakantie wat optimaliseren, maar voor vandaag houd ik het voor gezien, elke dag om 6 uur opstaan bouwt de vermoeidheid aardig op.

Denk dat ik mijn graafalgoritme nog kan verbeteren als ik bijvoorbeeld een topological sort toepas en gelijk afbreek als ik te laag in de graaf zit o.i.d. En natuurlijk een nette DP oplossing, i.p.v. mijn gare memoization (ik besef me nu dat ik de in de memoization key ook de node die ik disintegrate zet, waardoor ik alles opnieuw bereken voor elke disintegrated node... )

[ Voor 13% gewijzigd door FCA op 22-12-2023 20:36 ]

[Soultaker]

Asgardian28 schreef op vrijdag 22 december 2023 @ 20:08:
We hebben ook nog geen game of life puzzel gehad. Of zou dat dag 25 worden?

Dag 25 is meestal relatief simpel (en sowieso maar 1 deel). Maar een cellular automaton zou best kunnen voor morgen of overmogen! Iedereen heeft zijn Hashlife implementatie klaar hoop ik?

FCA schreef op vrijdag 22 december 2023 @ 20:20:
Challenge 1 werkt (nadat ik eerst deel 1 een stuk sneller had gemaakt, niet meer 1 per keer droppen, maar netjes bijhouden hoever je naar beneden kunt vallen en direct daar neer zetten). Had eerst nog een off-by-one error in deel 2 die ik blijkbaar niet triggerde in de officiele invoer. Tijd voor challenge 1 is niet geweldig, 40,4 s.

Challenge 2 gooit een OOM bij het alloceren van de initiele array voor de posities

Ah, jammer. Op basis van je beschrijving vermoedde ik dat je een meer geavanceerd algoritme had geïmplementeerd.

Misschien ga ik eens van de kerstvakantie wat optimaliseren, maar voor vandaag houd ik het voor gezien, elke dag om 6 uur opstaan bouwt de vermoeidheid aardig op.

Ja, ik begin dat ook wel zat te worden Nog een paar dagen doorbikkelen...

[.oisyn]

Day22 in Rust

Superweinig tijd gehad, gelukkig een simpele opdracht.

spoiler:

Mijn implementatie is niet heel efficient. Ik weet dat ik voor deel 2 zou kunnen bijhouden welke stenen er vallen en dan van boven naar onderen kan werken en zo niet steeds dingen opnieuw zou hoeven uitrekenen, maar daar had ik even geen zin in. Wellicht dat ik dat later nog eens implementeer. Ook gebruik ik een fixed size 10x10 grid dus die sets van @Soultaker gaan 'm sowieso niet worden

.edit:

spoiler:

Heh, nu ik de reacties van vandaag teruglees blijkt dat ik het voor deel 1 van meet af aan toch een stuk efficiënter heb geïmplementeerd dan velen hier

[ Voor 23% gewijzigd door .oisyn op 22-12-2023 23:44 ]

[.oisyn]

Soultaker schreef op vrijdag 22 december 2023 @ 14:37:
Extra testinvoer voor dag 22: aoc-2023-day-22-challenge-1-to-3.zip

Correcte antwoorden modulo 97:

• challenge-1.txt: 67 (deel 1), 7 (deel 2).
• challenge-2.txt: 1 (deel 1), 20 (deel 2).
• challenge-3.txt: 85 (deel 1), 83 (deel 2).

Referentietijden in Python: 0,3 s, 1,7 s, 12 s.

@FCA: werkt jouw oplossing op deze testdata? Hoe snel runt 'ie?

Ik heb van mijn statische array even een hashmap gemaakt zodat ik iig je challenges kan runnen, maar ik krijg voor deel 2 de juiste antwoorden, terwijl ik voor deel 1 iets anders krijg (resp. 74 en 2)

spoiler:

Mijn volledige antwoorden voor challenge 1 zijn 3760 en 175572

Running tijd is trouwens 10,9ms en 50,9s

.edit: oh interessant, als ik de sort vervang door een unstable sort dan krijg ik andere antwoorden voor challenge 1.

.edit2: ah, je hebt een foutje in je data. Heb even een test ingebouwd.

code:

bricks ((72, 83, 758), (72, 83, 792)) and ((59, 83, 787), (92, 83, 787)) overlap

.edit3: oh shit dat is bij lange na niet de enige overlap .

code:

bricks ((72, 83, 758), (72, 83, 792)) and ((59, 83, 787), (92, 83, 787)) overlap
bricks ((72, 54, 1848), (72, 54, 1881)) and ((65, 54, 1852), (97, 54, 1852)) overlap
bricks ((72, 53, 2673), (72, 92, 2673)) and ((56, 62, 2673), (99, 62, 2673)) overlap
bricks ((78, 73, 2896), (78, 73, 2942)) and ((78, 62, 2913), (78, 75, 2913)) overlap
bricks ((73, 70, 2912), (73, 93, 2912)) and ((73, 79, 2912), (73, 79, 2900)) overlap
bricks ((56, 80, 5671), (56, 80, 5698)) and ((56, 53, 5684), (56, 103, 5684)) overlap
bricks ((89, 66, 6167), (89, 86, 6167)) and ((65, 78, 6167), (92, 78, 6167)) overlap
bricks ((53, 82, 6293), (53, 82, 6336)) and ((53, 68, 6318), (53, 114, 6318)) overlap
bricks ((60, 63, 7124), (60, 63, 7128)) and ((60, 56, 7125), (60, 71, 7125)) overlap
bricks ((97, 87, 7134), (97, 87, 7180)) and ((97, 59, 7172), (97, 98, 7172)) overlap
bricks ((94, 73, 7241), (94, 73, 7285)) and ((66, 73, 7265), (98, 73, 7265)) overlap
bricks ((87, 73, 7250), (87, 73, 7288)) and ((66, 73, 7265), (98, 73, 7265)) overlap
bricks ((82, 62, 7882), (82, 62, 7901)) and ((82, 60, 7883), (82, 101, 7883)) overlap
bricks ((95, 57, 7916), (95, 106, 7916)) and ((95, 58, 7916), (95, 58, 7931)) overlap
bricks ((89, 78, 8251), (89, 78, 8271)) and ((89, 77, 8263), (89, 97, 8263)) overlap
bricks ((58, 69, 8326), (95, 69, 8326)) and ((63, 69, 8326), (63, 69, 8280)) overlap
bricks ((57, 99, 9362), (57, 99, 9406)) and ((57, 99, 9363), (74, 99, 9363)) overlap
bricks ((89, 65, 10702), (89, 112, 10702)) and ((72, 86, 10702), (98, 86, 10702)) overlap
bricks ((78, 64, 11139), (78, 64, 11163)) and ((78, 51, 11152), (78, 69, 11152)) overlap
bricks ((54, 90, 11493), (54, 90, 11537)) and ((52, 90, 11536), (75, 90, 11536)) overlap
bricks ((85, 52, 12515), (85, 52, 12537)) and ((68, 52, 12532), (85, 52, 12532)) overlap
bricks ((85, 100, 14102), (85, 100, 14134)) and ((67, 100, 14126), (117, 100, 14126)) overlap

Ook heb je heel veel negatieve z-coordinaten er in staan. Dat lijkt me onjuiste data, want de puzzel tekst heeft het erover dat de grond zich op z=0 bevindt, dus dan zouden er stenen door de grond zijn gezakt.

2 en 3 valideren wel volgens mijn check.

.edit4: challenge 2 nu in 18s.

[ Voor 63% gewijzigd door .oisyn op 23-12-2023 02:52 ]

[.oisyn]

BAM, challenge 2 in 168ms. Zit nog wel een bugje in want ik krijg bij de officiele invoer niet het goede antwoord. Volgens mij klopt mijn algoritme in principe, alleen mis ik denk ik ergens een edge case waardoor ik verkeerd tel. Morgen verder.

[Soultaker]

.oisyn schreef op zaterdag 23 december 2023 @ 00:47:
.edit2: ah, je hebt een foutje in je data. Heb even een test ingebouwd.

code:

bricks ((72, 83, 758), (72, 83, 792)) and ((59, 83, 787), (92, 83, 787)) overlap

[..]
Ook heb je heel veel negatieve z-coordinaten er in staan. Dat lijkt me onjuiste data, want de puzzel tekst heeft het erover dat de grond zich op z=0 bevindt, dus dan zouden er stenen door de grond zijn gezakt.

D'oh! Je hebt gelijk, dat was niet mijn bedoeling. Er zat een fout in 1 van de 3 generatoren (elke invoer heeft een andere structuur). Bedankt voor het melden!

Hier is een nieuwe versie: challenge-1-r1.txt. Correcte antwoorden zijn 54 en 24 modulo 97.

[Varienaja]

Lekker niet om 6 uur opgestaan, maar ik lach me een aap: "vind het langste pad".

[FCA]

Pfff...
Deel 1:

spoiler:

Gewoon brute force proberen, recursief met het gelopen pad bijhouden in een set. Werkt niet bijster snel, maar wel goed genoeg. Redelijk snel geimplementeerd, positie < 1000.

Deel 2 was weer een killer voor mij

spoiler:

Brute force vergelijkbaar met deel 1 (maar dus meer toegestane transities) werd hem niet binnen een minuut, dus alternatieven zoeken. Zoals al eerder opgemerkt, graafalgoritmes zijn niet mijn sterkste punt, dus dat schept geen hoge verwachtingen.

Na veel zoeken kom ik erachter dat het waarschijnlijk NP compleet is, dus ik ga zoeken naar speciale eigenschappen van de graaf. Half uurtje prutsen voor ik een fatsoenlijke plaatje van de graaf kan maken (graphviz, pygraphviz en Windows lopen niet lekker samen).
Blijkt dat de graaf uit veel a_1 <-> a_2 <-> ... <-> a_n rijen bestaat. Dat kunnen we versimpelen naar a_1 <-> a_n met gewicht n.

Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:

[ Voor 18% gewijzigd door FCA op 23-12-2023 09:46 ]

[.oisyn]

Soultaker schreef op zaterdag 23 december 2023 @ 08:37:
Hier is een nieuwe versie: challenge-1-r1.txt. Correcte antwoorden zijn 54 en 24 modulo 97.

Are you sure? Ik krijg andere antwoorden (waarvan ik 99,999% zeker ben dat deel 1 iig correct is)

[Soultaker]

.oisyn schreef op zaterdag 23 december 2023 @ 09:35:
Are you sure? Ik krijg andere antwoorden (waarvan ik 99,999% zeker ben dat deel 1 iig correct is)

Ik denk het... Ik gaf het antwoord modulo 97 he, niet simpelweg de laatste twee cijfers.

Check ook of je niets raars doet met whitespace; als ik van pastebin download heb ik Windows newlines in het bestand (maar mogelijk wil jij dat juist).

Probeer anders deze kleinere eerst: small.txt. 100 regels in de invoer. Correcte antwoorden zijn 71 en 251 (exact).

[.oisyn]

86 74 hier

[Soultaker]

.oisyn schreef op zaterdag 23 december 2023 @ 09:53:
86 74 hier

Ok, hier is mijn debug uitvoer. Wijs maar een blok aan dat ik ten onrechte heb gemarkeerd als “NOT safe to remove”

[Soultaker]

FCA schreef op zaterdag 23 december 2023 @ 09:29:

spoiler:

Recursief op de versimpelde graaf blijkt te werken. Nog steeds niet snel (het blijft brute-force), maar de graaf heeft nog maar 36 edges, dan gaat het blijkbaar net (net even gecheckt: 1.262.816 unieke paden om te checken, maar er zijn natuurlijk nog veel meer doodlopende/in zichzelf kerende paden)
BTW: mijn gereduceerde graaf:
[Afbeelding]

Ik was vanochtend ook helemaal niet wakker (nu nog nauwelijks) en heb ontzettend zitten prutsen. Sterker nog, de aanpak die jij beschrijft had ik al bij deel 1 gebruikt (wat natuurlijk volslagen overkill was, dom!) en dan zou je denken: dan was deel 2 zeker makkelijk. Ja, ware het niet dat ik op de een of andere manier bedacht had dat

spoiler:

je elke edge in de graaf maar 1 keer mag bezoeken, maar elke vertex meerdere keren. Dat is een heel ander probleem!

En ook plaatjes gemaakt van de graaf:



(De kleuren geven aan of een vertex een even of oneven aantal buren heeft. Dat heb je nergens voor nodig.)

edit: de plaatjes kloppen niet eens Dit zijn de correcte versies:

Voorbeeld deel 1 / 2:


Officiële invoer deel 1 / 2:

Uiteindelijk hetzelfde gedaan als jij, maar ook een teleurstellende runtime simpelweg vanwege het grote aantal mogelijkheden. Nog even nadenken of dat efficiënter kan. Overigens is het in z'n algemeenheid wel een NP-compleet probleem.

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

[Remcoder]

Soultaker schreef op vrijdag 22 december 2023 @ 20:48:
[...]

Dag 25 is meestal relatief simpel (en sowieso maar 1 deel). Maar een cellular automaton zou best kunnen voor morgen of overmogen! Iedereen heeft zijn Hashlife implementatie klaar hoop ik?

Ik kwam deze observatie tegen dat dag 21 juist de cellular automaton opdracht was. Ik zie best wat die daar bedoelt.

[Asgardian28]

Remcoder schreef op zaterdag 23 december 2023 @ 11:33:
[...]

Ik kwam deze observatie tegen dat dag 21 juist de cellular automaton opdracht was. Ik zie best wat die daar bedoelt.

Ah nice catch.

Ik heb vandaag met 112e mn beste klassering gehaald!

spoiler:

Voor deel 1 nog een off by 1 error, maar voor deel 2 zag ik snel de kruispunten in m'n input, dus voor alle kruispunten & start & einde de afstanden naar alle direct bereikbare andere kruispunten & start & einde bepaald en vervolgens die door de dijkstra heen geknald.

[Soultaker]

Asgardian28 schreef op zaterdag 23 december 2023 @ 12:20:
Ik heb vandaag met 112e mn beste klassering gehaald!

Gefeliciteerd!

spoiler:

Voor deel 1 nog een off by 1 error, maar voor deel 2 zag ik snel de kruispunten in m'n input, dus voor alle kruispunten & start & einde de afstanden naar alle direct bereikbare andere kruispunten & start & einde bepaald en vervolgens die door de dijkstra heen geknald.

Maar dat kan toch helemaal niet?

spoiler:

Dijkstra's algoritme vindt het kórtste pad in een graaf, niet het langste. En nee, je kunt niet simpelweg het element met de grootste afstand uit de set halen in plaats van de kleinste afstand.

Ik zag trouwens dat er in mijn code ook een bug zat, terwijl het antwoord wel klopte (ik miste wat edges). Het zou me niets verbazen als een aantal mensen met een verkeerde oplossing toch toevallig op het goede antwoord terecht kwamen.

(Overigens heb ik 'm nu in ongeveer 8 seconde in Python. Eigenlijk te traag voor m'n smaak maar ik heb niet echt een idee hoe ik het nog sneller moet maken.)

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

[Diderikdm]

Was best snel met p2 vandaag

spoiler:

Omdat ik bij part 1 al de conjunctions relatief aan elkaar had berekend om mee te gaan rekenen.

Maar nu nog ~55s runtime voor p2 ... Dus ik ga er nog even mee stoeien.

Voor wie de huidige staat wil zien:

Python

[Asgardian28]

Soultaker schreef op zaterdag 23 december 2023 @ 12:33:
Maar dat kan toch helemaal niet?

spoiler:

Ownee sorry, het is gewoon dezelfde dfs als deel 1 die je door laat draaien, maar nu met kruispunten ipv cellen.
Een state is (het kruispunt, afgelegde afstand, al bezochte kruispunten)
En als je dan bij je bestemming komt check je of deze beter is dan je maximale afstand tot nu toe

Ik was even in de war omdat je bij weighted edges standaard dijkstra gebruikt.

[Soultaker]

Asgardian28 schreef op zaterdag 23 december 2023 @ 13:05:

spoiler:

Ownee sorry, het is gewoon dezelfde dfs als deel 1 die je door laat draaien, maar nu met kruispunten ipv cellen. Een state is (het kruispunt, afgelegde afstand, al bezochte kruispunten) En als je dan bij je bestemming komt check je of deze beter is dan je maximale afstand tot nu toe

Dat klinkt beter, in de zin dat het het correcte antwoord zou moeten geven, maar vanuit performance oogpunt is het een beetje verdacht. Hoe voorkom je op deze manier dat het aantal states te groot wordt?

Staat je code ergens online trouwens?

[Asgardian28]

Kan kloppen, doet er 2,5 minuut over
https://github.com/jvanel...ong%20Walk/solution.ipynb

[Friits]

Leuke puzzel vandaag! Zoals de meesten hier maak ik een vereenvoudigde graaf. Oplossen kost voor mijn input 15 seconden, maar ik heb geoptimaliseerd voor leesbaarheid, niet performance

Code (Python)

[.oisyn]

Soultaker schreef op zaterdag 23 december 2023 @ 10:11:
[...]

Ok, hier is mijn debug uitvoer. Wijs maar een blok aan dat ik ten onrechte heb gemarkeerd als “NOT safe to remove”

Ah ik zie het al, jij hebt regels als
99,79,139~62,79,139

Waarbij componenten van het eerste coordinaat hoger zijn dan die van het tweede coordinaat. Ik weet niet of dat de bedoeling was? De omschrijving noemt verder niet dat dat verboden is, maar de voorbeeld en de officiele input doet dat nooit. Als ik dat support kom ik ook op 71. Ik vind persoonlijk dat je je input moet fixen

[ Voor 20% gewijzigd door .oisyn op 23-12-2023 13:27 ]

[CrossProd]

Mijn algoritme voor part 2 (dag 23) eindigde maar niet maar ik had wel al het juiste antwoord naar de console geprint dus de twee sterren waren al binnen vanochtend. Nu flink lopen refactoren en het is nu klaar in ~1 seconde met Swift.

spoiler:

Zoals denk ik iedereen eerst het grid omgezet naar een weighted graph. Daarna met DFS alle mogelijke paden bekijken. Kleine optimalisatie is het opslaan van bezochte nodes in een Int met bit flags want er zijn toch maar 36 nodes. Scheelt weer het bijhouden van bv een Set.

BV:
visitedNodes |= (1 << startIndex)

for edge in edges where (visitedNodes & (1 << edge.b)) == 0 { ... }

Dag 23 in Swift

[ Voor 8% gewijzigd door CrossProd op 23-12-2023 13:31 ]

[Remcoder]

Soultaker schreef op zaterdag 23 december 2023 @ 12:33:
[...]

Gefeliciteerd!


[...]

Maar dat kan toch helemaal niet?

spoiler:

Dijkstra's algoritme vindt het kórtste pad in een graaf, niet het langste. En nee, je kunt niet simpelweg het element met de grootste afstand uit de set halen in plaats van de kleinste afstand.

Ik zag trouwens dat er in mijn code ook een bug zat, terwijl het antwoord wel klopte (ik miste wat edges). Het zou me niets verbazen als een aantal mensen met een verkeerde oplossing toch toevallig op het goede antwoord terecht kwamen.

(Overigens heb ik 'm nu in ongeveer 8 seconde in Python. Eigenlijk te traag voor m'n smaak maar ik heb niet echt een idee hoe ik het nog sneller moet maken.)

spoiler:

Bij mijn input werkte het blijkbaar

Ik had gewoon de compareTo van mijn nodes omgedraaid, zodat de sortering in de queue andersom is. Voor de test input gaf die het op 1 na beste resultaat terug, ik runde hem voor de gein maar eens met de echte input, en blijkbaar gaf die daar het goede antwoord terug.

[MatHack]

spoiler:

Had zelf ook al bedacht om de grid naar een graaf te converteren en daardoor gingen deel 1 (beide invoer) + deel 2 (testinvoer) lekker snel. Helaas duurt de echte invoer voor deel 2 lang, maar gaf wel het juiste antwoord.

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

[Soultaker]

Diderikdm schreef op zaterdag 23 december 2023 @ 13:00:
Maar nu nog ~55s runtime voor p2 ... Dus ik ga er nog even mee stoeien.

Voor wie de huidige staat wil zien: Python

Het is in ieder geval correct! Je kunt het nog aanzienlijk sneller maken (spoiler!):

spoiler:

In je huidige oplossing bestaat je state uit (steps, current, seen). Je sorteert seen wat een goed optimalisatie is om het aantal states van O(V × V!) naar O(V × 2^V) te verlagen. Maar je doet nu nog onnodig extra werk omdat je dezelfde combinatie van (current, seen) meerdere keren bezoekt, namelijk élke keer dat je steps verlaagt (wat in de officiële testinvoer gelukkig niet vaak voorkomt).

Om dat sneller te maken moet je het van de andere kant bekijken. Bereken niet hoeveel stappen je nodig hebt om tot current te komen, maar bereken wat de maximale afstand tot het eindpunt is gegeven current en seen.

Asgardian28 schreef op zaterdag 23 december 2023 @ 13:19:
Kan kloppen, doet er 2,5 minuut over
https://github.com/jvanel...ong%20Walk/solution.ipynb

Ah ja, dat verklaart het Bijzonder dat je voor een iteratieve oplossing met een while-loop gekozen hebt in plaats van een simpelere DFS met een recursieve functie. En de ordening van de deque, daar heb je hier niets aan (maar kwaad kan het ook niet). Wel lekker strakke code om de graaf voor deel 2 op te bouwen.

Trouwens wel leuk om te zien dat Github die notebook kan previewen.

CrossProd schreef op zaterdag 23 december 2023 @ 13:30:
Mijn algoritme voor part 2 (dag 23) eindigde maar niet maar ik had wel al het juiste antwoord naar de console geprint dus de twee sterren waren al binnen vanochtend. Nu flink lopen refactoren en het is nu klaar in ~1 seconde met Swift.

spoiler:

Zoals denk ik iedereen eerst het grid omgezet naar een weighted graph. Daarna met DFS alle mogelijke paden bekijken.

Dit klinkt alsof er een bug in je code zit... Als je een DFS zonder optimalisaties doet is het aantal paden O(V!) en dat is toch veel te veel om in 1 seconde te doen? De oplossingen van @Asgardian28 en @Friits hebben dezelfde logica en doen er logischerwijs veel langer over.

[ Voor 18% gewijzigd door Soultaker op 23-12-2023 14:29 ]

[Soultaker]

.oisyn schreef op zaterdag 23 december 2023 @ 13:23:
Ah ik zie het al, jij hebt regels als
99,79,139~62,79,139
Waarbij componenten van het eerste coordinaat hoger zijn dan die van het tweede coordinaat. Ik weet niet of dat de bedoeling was? De omschrijving noemt verder niet dat dat verboden is, maar de voorbeeld en de officiele input doet dat nooit.

Dat was expres, precies omdat het volgens het problem statement kan. De negatieve/overlappende z-coördinaten was onbedoeld.

Ik vind persoonlijk dat je je input moet fixen

Waarom? Jij hebt je code toch al gefixt

Maar je mag ook testinvoer 3 oplossen, die heeft volgens mij geen geïnverteerde coördinaten.

[Remcoder]

Remcoder schreef op zaterdag 23 december 2023 @ 14:08:
[...]

spoiler:

Bij mijn input werkte het blijkbaar

Ik had gewoon de compareTo van mijn nodes omgedraaid, zodat de sortering in de queue andersom is. Voor de test input gaf die het op 1 na beste resultaat terug, ik runde hem voor de gein maar eens met de echte input, en blijkbaar gaf die daar het goede antwoord terug.

spoiler:

Helaas ging diezelfde vlieger niet op voor deel 2, dus toch maar even een nette oplossing gemaakt die voor elke input kan werken.

De efficientie laat te wensen over, voor deel 2 draait die 17 seconden.

Ik bouw eerst een graph op met de kruispunten als nodes, dan bepaal ik elk mogelijk pad dat naar de exit kan leiden, en daarvan geef ik dan de grootste lengte terug.

[Soultaker]

Remcoder schreef op zaterdag 23 december 2023 @ 11:33:
Ik kwam deze observatie tegen dat dag 21 juist de cellular automaton opdracht was. Ik zie best wat die daar bedoelt.

Bedankt voor de link — dit is conceptueel heel cool! (En ook echt met HashLife zoals ik al eerder noemde...) Helaas krijg ik er niet de juiste antwoorden uit voor mijn testdata, maar ik weet niet of dat aan mij code ligt of de zijne. Sowieso is zijn implementatie verdacht traag, terwijl ik zou denken dat er

[CrossProd]

[b]Soultaker schreef op zaterdag 23 december 2023 @ 14:18:
Dit klinkt alsof er een bug in je code zit... Als je een DFS zonder optimalisaties doet is het aantal paden O(V!) en dat is toch veel te veel om in 1 seconde te doen? De oplossingen van @Asgardian28 en @Friits hebben dezelfde logica en doen er logischerwijs veel langer over.

Maar gecompileerde swift code is verwacht ik wel significant sneller dan Python. Zover ik kan zien loop ik alle mogelijke paden door.

Een simpele globale counter geeft aan dat ik de dfs functie 30,580,294 keer uitvoer in die 1 seconde.

[Soultaker]

CrossProd schreef op zaterdag 23 december 2023 @ 16:13:
Maar gecompileerde swift code is verwacht ik wel significant sneller dan Python. Zover ik kan zien loop ik alle mogelijke paden door. Een simpele globale counter geeft aan dat ik de dfs functie 30,580,294 keer uitvoer in die 1 seconde.

Als ik het vergelijk met de code van Friits hier dan wordt search() ~100 miljoen keer gecalled, waarbij 'ie ~29 miljoen keer langs de eerste twee if-statements komt. Dat zit dus ongeveer in de orde van grootte van jouw oplossing. Mischien is Swift gewoon swifter dan ik dacht

[MatHack]

Ik was niet tevreden met mijn oplossing van dag 22, het werkte, maar was supertraag (~30s totaal voor beide antwoorden) en ik wist dat ik die toch zeker nog een stuk kon verbeteren, nou dat is gelukt. Voornamelijk verbetering van datatypes en berekeningen. Nu runnen beide sets in ongeveer 75ms, dat is 400x zo snel. Nu ben ik wel tevreden over mijn oplossing.

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

[CrossProd]

Soultaker schreef op zaterdag 23 december 2023 @ 17:05:
[...]

Als ik het vergelijk met de code van Friits hier dan wordt search() ~100 miljoen keer gecalled, waarbij 'ie ~29 miljoen keer langs de eerste twee if-statements komt. Dat zit dus ongeveer in de orde van grootte van jouw oplossing. Mischien is Swift gewoon swifter dan ik dacht

Bedankt voor deze check!

[Bolukan]

Ik heb veel tijd besteed aan debuggen aan de recursieve functie. Ik ben (python) niet gewend en dat ie alles by reference doorgeeft. Daarom en omdat ik uberhaupt niet goed bezig was, minder goed gevoel overgehouden aan vandaag, terwijl ik qua aanpak goed zat.

spoiler: day 23, part 2

Voor part 1 gelijk de graaf opgezet. De wat lange looptijd van de code voor part 2 lag zo te lezen niet aan mij alleen.
Ik vind 1.262.816 verschillende routes door het doolhof en analyseer daarvoor 30.580.293 stapjes in 70 seconde.

[ Voor 11% gewijzigd door Bolukan op 23-12-2023 18:45 ]

[.oisyn]

Zo, hèhè, eindelijk even tijd gehad om de bug uit mijn day22 algo te halen

Officiele input: 582.3µs

Op @Soultaker's sets:
1: 3,949.0µs
2: 159,689.1µs
3: 244,243.6µs

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.

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.

[ Voor 76% gewijzigd door .oisyn op 23-12-2023 20:36 ]

[jeroenheijmans]

Even tussendoor met een meta-berichtje, niet aan een dag gerelateerd. Voor de liefhebbers heb ik de resultaten van mijn jaarlijkse Advent of Code Survey gepubliceerd, dit jaar 3000+ mensen die 'm hebben ingvuld dus geeft enig beeld van wat men doet en gebruikt.

• Survey resultaten:https://jeroenheijmans.github.io/advent-of-code-surveys/
• Reddit announcement: https://www.reddit.com/r/..._aoc_2023_survey_results/

Met sneak peek van de resultaten hieronder.

spoiler: Multi-select vraag: "anno 2023 what are your thoughts on AI and LLM's for Advent of Code?"

Enjoy! En succes met de laatste puzzels natuurlijk allemaal

[Bolukan]

spoiler: day 23, part 2

Dit verklaart de hoeveelheid routes tussen begin (1) en eind (36)

[ Voor 42% gewijzigd door Bolukan op 23-12-2023 21:51 ]

[.oisyn]

Ik vond dat mijn dag 23 deel 2 er wel erg lang over deed. Ik print ondertussen de tot nu toe langst gevonden route, maar daar was al een tijdje geen update op geweest. Ik doe nog niet aan pruning verder dus ik ging gewoon eens kijken of dat dan het juiste antwoord was.

"Your anwer is too high"

Wait, what?!

Soultaker schreef op zaterdag 23 december 2023 @ 10:23:
Ja, ware het niet dat ik op de een of andere manier bedacht had dat

spoiler:

je elke edge in de graaf maar 1 keer mag bezoeken, maar elke vertex meerdere keren. Dat is een heel ander probleem!

d'Oh! Ik maak dus exact dezelfde fout. Typisch dat dat niet op deel 1 van toepassing is, noch op het voorbeeld.

spoiler:

Inderdaad even niet bedacht dat alle nodes natuurlijk dezelfde tile delen. Je kunt dus niet naar dezelfde node maar dan een ander pad nemen, want die ene tile die alle paden verbindt is al belopen

spoiler:

Mijn graaf for good measure

[ Voor 66% gewijzigd door .oisyn op 24-12-2023 02:04 ]

[.oisyn]

Ik vind het wel goed zo.
Day23 in Rust
Time spent: 2,6s.

[Soultaker]

Dit is wel heel veel wiskunde voor een vroege zondagmorgen. Geometrie nog wel... Ik ben er nog niet uit. Ik neem nog maar een kopje koffie denk ik.

[MatHack]

Pfff... ik heb de juiste wiskunde voor deel 1 (en ik heb al een vermoeden waar deel 2 heen gaat), testinvoer werkt ook prima, maar de echte invoer niet. Gezien de grote nummers en het feit dat er non-integer intersecties kunnen zijn vermoed ik dat het probleem in datatypes zit voor mijn oplossing...

Heb ondertussen al wel een range te pakken voor het juiste antwoord gezien ik ondertussen 2 foute antwoorden heb gegeven, een te hoog, ander te laag.

spoiler:

Die crossings in de past waren de grootste uitdaging tot nu toe, rest was formules overtypen.

[EfBe]

Soultaker schreef op zondag 24 december 2023 @ 07:17:
Dit is wel heel veel wiskunde voor een vroege zondagmorgen. Geometrie nog wel... Ik ben er nog niet uit. Ik neem nog maar een kopje koffie denk ik.

Volgens mij heeft dit SO antwoord de juiste wiskunde: https://stackoverflow.com/a/565282/44991, maar mocht je het niet zien dan wordt deze wel taai inderdaad...

[Soultaker]

EfBe schreef op zondag 24 december 2023 @ 09:26:
Volgens mij heeft dit SO antwoord de juiste wiskunde: https://stackoverflow.com/a/565282/44991, maar mocht je het niet zien dan wordt deze wel taai inderdaad...

Voor deel 1 is dat i.d.d. voldoende maar ik zit vast op deel 2

[MatHack]

Deel 1 ondertussen gelukt, deel 2 was nog erger dan ik had verwacht.

spoiler: deel 1

Had van Wikipedia: Line–line intersection de eerste formule gebruikt (uiteindelijk met doubles), maar kreeg daar het foute antwoord uit. Uiteindelijk de tweede formule gebruikt en daar kwam wel het juiste antwoord uit. Er zat een verschil van 1 tussen de tellingen van formule1 en formule2... zal wel een precisie-verschil in doubles geweest zijn ofzo...

EDIT: Heb ondertussen op reddit gezien dat heel veel mensen externe libraries/websites hebben gebruikt voor deel 2.

[ Voor 10% gewijzigd door MatHack op 24-12-2023 09:56 ]

[Remcoder]

MatHack schreef op zondag 24 december 2023 @ 09:52:
Deel 1 ondertussen gelukt, deel 2 was nog erger dan ik had verwacht.

spoiler: deel 1

Had van Wikipedia: Line–line intersection de eerste formule gebruikt (uiteindelijk met doubles), maar kreeg daar het foute antwoord uit. Uiteindelijk de tweede formule gebruikt en daar kwam wel het juiste antwoord uit. Er zat een verschil van 1 tussen de tellingen van formule1 en formule2... zal wel een precisie-verschil in doubles geweest zijn ofzo...

EDIT: Heb ondertussen op reddit gezien dat heel veel mensen externe libraries/websites hebben gebruikt voor deel 2.

spoiler:

Die eerste formule werkt ook, alleen passen de tussen resultaten niet in een 64 bits getal. Als je die aanpast naar iets wat werkt met grotere getallen krijg je het goede resultaat eruit.

Bij mijn oplossing heb ik dus alles omgebouwd naar BigDecimals, daar krijg ik de goede resultaten uit.

[.oisyn]

Dit wordt zo te zien een makkie. Jammer dat ik wrinig tijd heb vandaag

[MrHaas]

spoiler:

Heb deel 2 ook nog niet, maar ik vermoed dat je iets kan met de punten die dezelfde snelheid in een bepaalde richting hebben, volgens mij kan je daarmee het aantal mogelijke snelheden van de steen die je gooit in een bepaalde richting flink reduceren.

/edit: hiermee is het me inmiddels gelukt om de velocity vector te vinden, nu nog de positie
/edit2: en uiteindelijk gelukt door ook voor het vinden van de initiele positie de parallelen te gebruiken: ik pak de eerste 2 punten die parallel zijn voor x over t en kan tussen die 2 makkelijk dt bepalen door `dx*t1 = vx1 * t1 + x1` en `dx*t2 = vx2 * t2 + x2` op te lossen. Deze dt kan je dan weer gebruiken door mbv y1(t) en y2(t) de daadwerkelijke t te vinden. Uren naar lijnen en snijpunten zitten staren, maar blij dat ik het zonder hints heb kunnen oplossen

[ Voor 58% gewijzigd door MrHaas op 24-12-2023 16:31 ]

[Asgardian28]

spoiler:

Jeeeee wat een kraker weer zeg. Net klaar na 7,5 uur kloooooten

Ik heb heel lang zitten in formules om een vlak te bepalen op basis van twee parallelle lijnen en dan kijken wanneer de andere lijnen hiermee snijden. Voor de testcase werkte dit, maar niet voor het antwoord. Dus dat was een doodlopend spoor. Ook voor het eerst met GPT geprobeerd om dit soort wiskundige ellende uit te vogelen. Dat viel me eigenlijk nog vies tegen, met code die niet werkt e.d.

Om 13:15 kwam ik op het idee om Z3 te gebruiken. En 13:30 had ik het antwoord, in 1x goed. Heel blij mee maakt een hoop van de voorgaande uren goed.

En kwam goed uit want nu snel naar de familie voor kerstdiner.

[Bolukan]

spoiler: day 24, part 2

Zojuist snap ik hoe part 2 te doen. Part 1 verwijst er heel erg goed naar: dat je niet in de tijd moet zoeken maar naar kruispunten tussen 2 lijnen. Alleen de andere lijn van part 2 is nog juist te bepalen. Leuke animaties in de tijd gemaakt van x/y/z.

[MatHack]

Bolukan schreef op zondag 24 december 2023 @ 16:37:

spoiler: day 24, part 2

Zojuist snap ik hoe part 2 te doen. Part 1 verwijst er heel erg goed naar: dat je niet in de tijd moet zoeken maar naar kruispunten tussen 2 lijnen. Alleen de andere lijn van part 2 is nog juist te bepalen. Leuke animaties in de tijd gemaakt van x/y/z.

spoiler: dag 24, deel 2

Hoe bedoel je dat? Ik had al wel gemerkt dat er maar een enkele paren niet kruisen in het eerste deel. Bedoel je dat je nog iets extra's kunt met de paren die je in deel 1 hebt gevonden, want je gebruikt de Z-as niet in deel 1?

[Bolukan]

spoiler:

Waar ik aan denk is dat je 300 lijnen in de tijd kunt tekenen die ergens een lijn die je zoekt doorkruist, waarbij het tijdstip niet belangrijk is (niet belangrijk = per vergelijking anders).
In tegenstelling tot part 1 doe je dat niet tussen die 300 vergelijkingen maar met de onbekende 301e vergelijking, waarvan je de parameters nog niet kent.

[ Voor 68% gewijzigd door Bolukan op 24-12-2023 17:29 ]

[Diderikdm]

spoiler:

Ben deel 2 nog aan het uitwerken, maar volgens mij zou je aan 3 (met verschillende velocities (geen veelvoud van elkaar) lijnen genoeg moeten hebben om hier een raaklijn op te tekenen. De rock moet immers alle hailstones raken, dus zou dat het pad moeten zijn qua velocity voor de rock, daarna zou je met het tijdstip van een lijn van start tot raakpunt terug kunnen redeneren wat de xyz zou moeten zijn op basis van tijd stappen terug op de raaklijn.

[Soultaker]

Ik heb het ook weer even opgepakt. Momenteel ben ik aan het werken met getallen modulo 529233060817505690510304950800612746886167535693661804372887187718111564412284041920041722342379610808287460926855236217917467249455008000. Geen idee of ik brilliant ben of compleet zot; een van de twee in ieder geval

edit: Ik ben brilliant!

[ Voor 5% gewijzigd door Soultaker op 24-12-2023 19:14 ]

[Bolukan]

spoiler: even nadenken

als we de te vinden lijn nummer 0 geven, en de rest 1 tm 300:
1) px_i + t_i * dx_i = px₀ + t_i * dx₀ voor i=1..300 en idem voor y en z

Herschreven tot:
2) px₀ = px_i + t_i * ( dx_i - dx₀ )

Toegepast op i=1 en 2:
3) px₁ + t₁ * ( dx₁ - dx₀ ) = px₂ + t₂ * ( dx₂ - dx₀ )
idem voor y en z

Herschreven:
4) ( px₁ - px₂ + t₁ * dx₁ - t₂ * dx₂ ) / ( t₂ - t₁ ) = dx₀

en de rest komt na de kerstnachtdienst

[arnold_m]

MatHack schreef op zondag 24 december 2023 @ 08:29:
Pfff... ik heb de juiste wiskunde voor deel 1 (en ik heb al een vermoeden waar deel 2 heen gaat), testinvoer werkt ook prima, maar de echte invoer niet. Gezien de grote nummers en het feit dat er non-integer intersecties kunnen zijn vermoed ik dat het probleem in datatypes zit voor mijn oplossing...

Heb ondertussen al wel een range te pakken voor het juiste antwoord gezien ik ondertussen 2 foute antwoorden heb gegeven, een te hoog, ander te laag.

spoiler:

Die crossings in de past waren de grootste uitdaging tot nu toe, rest was formules overtypen.

Ik heb er vrij lang over gedaan, maar ik heb een oplosser geprogrammeerd die geen floating-pointgetallen gebruikt.

spoiler:

Bij deel 2 moest ik wel grootste gemene delers bepalen en op tijd variabelen omlaagschalen, omdat mijn algoritme anders overflows produceerde met de i128 van Rust.

[Soultaker]

Zo, dag 23 eindelijk af (Python code). Ik zat al een tijdje in de correcte richting te denken maar de implementatie-details waren nog wel tricky.

Als iemand interesse heeft kan ik (morgen of overmorgen) een gedetailleerde uitleg posten.

MrHaas schreef op zondag 24 december 2023 @ 11:31:

spoiler:

/edit2: en uiteindelijk gelukt door ook voor het vinden van de initiele positie de parallelen te gebruiken: ik pak de eerste 2 punten die parallel zijn voor x over t en kan tussen die 2 makkelijk dt bepalen door `dx*t1 = vx1 * t1 + x1` en `dx*t2 = vx2 * t2 + x2` op te lossen. Deze dt kan je dan weer gebruiken door mbv y1(t) en y2(t) de daadwerkelijke t te vinden. Uren naar lijnen en snijpunten zitten staren, maar blij dat ik het zonder hints heb kunnen oplossen

Oh interessant. Ik heb geen gebruik van gemaakt van dit soort eigenschappen van de invoer. Ik had wel een aantal observaties maar de meeste leken niet heel bruikbaar. Ik moet later nog eens in detail naar je code kijken om te begrijpen wat je precies doet. Op het eerste gezicht is het aanzienlijk simpeler dan mijn aanpak.

.oisyn schreef op zondag 24 december 2023 @ 11:10:
Dit wordt zo te zien een makkie. Jammer dat ik wrinig tijd heb vandaag

Grappig genoeg is het wel een beetje jouw vakgebied. Ik denk dus dat je met deel 1 relatief weinig moeite zal hebben. (Voor deel 2 durf ik het niet te zeggen.)

Bolukan schreef op zondag 24 december 2023 @ 19:05:

spoiler: even nadenken

Herschreven:
4) ( px₁ - px₂ + t₁ * dx₁ - t₂ * dx₂ ) / ( t₂ - t₁ ) = dx₀

en de rest komt na de kerstnachtdienst

Ik had op enig moment dezelfde vergelijking opgesteld, maar

spoiler:

het probleem is dat de deling de vergelijking niet-lineair maakt, en dan wordt het heel moeilijk oplossen. Mogelijk moet je dus in een andere richting denken.

arnold_m schreef op zondag 24 december 2023 @ 20:07:
Ik heb er vrij lang over gedaan, maar ik heb een oplosser geprogrammeerd die geen floating-pointgetallen gebruikt.

Zelfde hier; 100% integer arithmetic, wat bij deel 1 al nodig was. Gelukkig maakt Python dit erg makkelijk. 128-bits integers waren niet voldoende voor mijn oplossing.

[.oisyn]

Soultaker schreef op zondag 24 december 2023 @ 20:13:Grappig genoeg is het wel een beetje jouw vakgebied. Ik denk dus dat je met deel 1 relatief weinig moeite zal hebben. (Voor deel 2 durf ik het niet te zeggen.)

Daarom. Lijnintersecties tik ik uit het hoofd in . Volgens mij kun je ook wel bepalen of het intersectiepunt in het vierkant ligt zonder het uit te rekenen.

Jammer dat ik deel 2 nog niet kan inzien.

[MatHack]

Uiteindelijk heb ik voor deel 2 een implementatie gejat van iemand op reddit die het zonder allerlei externe libraries heeft geïmplementeerd (en waarvan ik ook begreep wat er gebeurde). Dit is toch echt veel wiskunde en dan is voor mij de lol op een gegeven moment er wel vanaf, omdat het niet echt een programmeer puzzel is. De oplossing werkt alleen voor de echte set, niet voor de testset.
Ik begrijp de oplossing wel, maar was er zelf niet opgekomen.

spoiler:

Eerst de snelheid van de steen bepalen door te zoeken naar punten met gelijke snelheid op de verschillende assen, als zelfde snelheid dan moeten ze een bepaalde afstand van elkaar liggen (modulo berekening). Als je dit voor alle drie dimensies hebt gedaan kun je met twee willekeurige punten uitrekenen wat de start positie is.

[FCA]

Pfff...
Ga later nog maar eens kijken naar de andere oplossingen, wat ik gemist heb, ben er even klaar mee.

spoiler:

Deel 1 inderdaad goed te doen. Deel 2 daarentegen....
Eerst met wat geprutst 3 vergelijkingen met 3 onbekenden, alleen niet lineair (inhomogeen bilinear), door in te zien dat als A_12 = (H_1 + t_1 V_1) - (H_2 + t_2 V_2) en A_13 = (H_1 + t_1 V_1) - (H_3 + t_3 V_3) parallel zijn (wat ze moeten zijn, anders kan er geen steen door alle 3 heen), dan krijg je uit crossproduct(A_12, A_13) = 0,
3 vergelijkingen met 3 onbekenden (de t_1, t_2 en t_3).
Alleen niet-lineair...
Eerst brute-force geprobeerd, maar dat ging hem niet worden.
Toen ingezien dat je t_3 uit t_1 en t_2 kunt bepalen, maar ook een brute-force search over t_1 en t_2 ging hem niet worden.
Toen met veel gepruts een vergelijking voor t_3 en t_2 uit t_1 kunnen bepalen (Sylvester matrices en resultant polynomials...). Maar ook een brute-force over t_1 alleen ging hem niet worden.

Er is een mogelijkheid om t_1 ook direct te bepalen, maar na talloze vellen papier volgekladderd te hebben kwam ik tot de conclusie dat dat een 6e graads polynoom zou worden. Die gaan we niet proberen op te lossen (hoewel ik vermoed dat er wel een mooie algebraische oplossing zou zijn, gezien het feit dat de oplossing in integers uitgedrukt kon worden).

Ook nog geprobeerd: de oplossing benaderen door een gradient descent search. Werkt niet, door de grote getallen gaat het niet convergeren.

Toen maar sympy erbij gepakt: oorspronkelijke vergelijking erin stoppen, fout antwoord krijgen
Toen alle numpy (cross products e.d.) vervangen door bare python, en alles opnieuw uitrekenen. Nu een vergelijking waarin t3 een onbekende bleef: er is blijkbaar nog een vrijheidsgraad over. Nu met sympy de resulterende 2 vergelijkingen (een voor t1 in termen van t3, een voor t2 in termen van t3) diophantisch oplossen (dus alleen integers...). Eindelijk de oplossing, maar door het gebruik van Sympy niet echt voldoening
Wel nog even gecheckt, mijn methode met 1 variable brute force werkte correct als ik rond de goede waarde zoek, maar ja, brute force naar ~60 miljard gaat hem niet worden.

spoiler:

Zie nu (op reddit) dat ik het om had kunnen schrijven naar 6 lineaire vergelijkingen met 6 onbekenden... dat had ik wel kunnen oplossen
Ik ben te geintrigeerd door moeilijke oplossingen blijkbaar.
Andere mogelijkheid was blijkbaar brute-force op snelheden van de steen, dat is natuurlijk flauw dat dat werkt

[ Voor 7% gewijzigd door FCA op 24-12-2023 22:44 ]

[Bolukan]

"You have completed day 24 !"

[.oisyn]

Zo, in een keer goed, maar ik heb wel 2 uur zitten debuggen voor een stom foutje
day24 in Rust
Time spent: 26533.6µs

Deel 2 was wel even pittig ja. Deel 1 had ik in 15 minuten ingetypt

spoiler:

Ik heb het uiteindelijk opgelost door voor paren van stenen die op een as dezelfde snelheid hebben een verzameling van mogelijke snelheden (de delers van de afstand tussen die stenen op die as, relatief aan hun snelheid) bepaald, die ik uiteindelijk wegstreep tegen de mogelijke snelheden bij andere paren.

Blijkt dat je voor de officiele input maar 1 mogelijkheid per as overhoud, maar voor het voorbeeld is dat niet zo, dus ik heb het generiek geimplementeerd waarbij hij ze gewoon probeert. Met een snelheid op 1 as de twee snijpunten op een andere as bepaald om op zo'n manier op te lossen voor positie en snelheden op alle assen. En dan kijken of dat de juiste oplossing is voor alle stenen.

spoiler:

Ah ik zie dat meer mensen voor die oplossing hebben gekozen
Deel 2 gewoon in i64. Ik had even geen zin om over deel 1 na te denken dus daar wel even een i128 gebruikt.

[ Voor 9% gewijzigd door .oisyn op 25-12-2023 04:28 ]

[Asgardian28]

Nou dat was het weer mensen, ik vond het een moeilijk jaar! Vooral dag 21 en 24... Maar ze waren allemaal interessant. En vandaag een leuke om het af te sluiten.

spoiler:

Ik had gelukkig een graaf visualisatie functie gemaakt, die kon ik nu mooi gebruiken.
Maar goed ook, want op reddit blijkt dat veel mensen min cut methode hebben gebruikt, had ik nog nooit van gehoord.

[Soultaker]

Fijne kerstdagen allemaal!

Dag 25:

spoiler: Oplossing voor dag 25

Eerst probeerde ik 'm gewoon te brute forcen: voor elke drie edges een depth-first search om de componenten te detecteren. Dat was natuurlijk veel te traag. Toen had ik code geschreven om cliques te detecteren en samen te trekken. Dat werkte uitstekend op de voorbeeldinvoer, maar de officiële invoer blijkt geen cliques groter dan 3 te hebben, dus dat bleek verspilde tijd.

Uiteindelijk heb ik het Ford-Fulkerson algoritme maar geïmplementeerd om de minimum cut in de graaf te vinden. Probleem is dat je een start- en een eindvertex moet hebben in aparte componenten, anders vind je de minimum cut niet. Ik heb dat simpelweg opgelost door in een while-loop random twee vertices te kiezen. Als de componenten ongeveer even groot zijn is de kans dat je twee goede vertices hebt ongeveer 50%. Vraag me af of dat slimmer kan.

Python code: 25-minimal.py (~150 ms) (of 25.py voor een iets leesbaardere versie).

spoiler: Alternatieve aanpak

Het viel me op dat ik het antwoord ook zonder algoritme kan vinden. Als ik de invoer converteer naar GraphViz formaat en open met Qt Visual Graph Editor, dan zijn de twee helften duidelijk te zien.



Je kunt dan simpelweg op de kritieke edges klikken om de eindpunten te identificeren, en de vertices selecteren om te zien hoe groot de componenten zijn. Het verbaasde me enigszins dat QVGE geen moeite heeft met zulke grote bestanden.

edit:
neato maakt er ook een “mooi” plaatje van:


De edges binnen de componenten zijn een grote warboel maar de drie kritieke edges tússen de componenten zijn duidelijk herkenbaar, en dat is precies de informatie die je nodig hebt Jammer dat ik dit niet meteen geprobeerd had. Had me een heleboel tijd gescheeld (al had ik het probleem ook nog écht op willen lossen).

[ Voor 12% gewijzigd door Soultaker op 25-12-2023 14:45 ]

[FCA]

Dat was hem dan. Ik vond hem voor dag 25 best een pittige eigenlijk. Wel snel gedaan, gelukje.

spoiler:

Ik had ooit (voor programmeerwedstrijden in het verleden) Edmonds-Karp voor max-flow geimplementeerd, dus een 2e keer (en nu in Python) ging redelijk soepel.

Min-cut uit de max flow halen, door over source en target te loopen, en dan stoppen zodra er 1 van 3 is gevonden.
Complexiteit wijs beetje dubieus (O(V^3 E^2)) door de loop over source en target, maar je kunt gelukkig stoppen zodra je de edges hebt gevonden.
Daarna nog connected components inkleuren met een queue.

Ik merk dat ik wel een beetje klaar met AoC was. Vooral dag 21 en 24, waarin ik vast bleef zitten in een oplossingsrichting die weliswaar mogelijk was, maar een veel simpelere (werkend althans op de gegeven input) ook beter was, waren eigenlijk niet leuk. Volgend jaar een andere aanpak kiezen (andere taal eens, om kennis daarvan uit te diepen?) en zeker niet meer in de weekenden om 6 uur beginnen.

[H34H]

Ik heb nog niet in gepost in dit topic, maar wel veel interesse gevolgd. Voor mij was dit het derde jaar dat ik meedeed en voor het eerst dat ik er redelijk soepel doorheen fietste. Dank voor al jullie inzichten! Ik heb uiteindelijk niet alle sterren binnen geharkt, maar wel weer enorm veel geleerd. Speciale shoutout naar @Soultaker , je zou docent moeten worden.

Fijne dagen allemaal!

[Remcoder]

Ik heb ook weer alle sterren binnen gehaald.

spoiler:

Vandaag opgelost op basis van de aanname dat edges die gecut moeten worden ertoe leiden dat de afstand tussen die 2 nodes het grootste wordt.

Ik probeer dus elke edge te snijden en daarna de nieuwe afstand tussen die 2 nodes te bepalen.

De edges die de grootste afstand opleveren moeten dan doorgesneden worden.

Daarna pak ik van de eerste edge beide nodes en bepaal per node welke nodes er allemaal bij horen. Van die 2 sets geef ik dan het formaat terug.

Het werkt niet voor elke willekeurige graaf, maar voor de AoC inputs wel.

[P_Tingen]

Kudos voor iedereen die alles heeft binnengehengeld. Ik merk dat mijn ervaring met allerlei bedrijfs- en productiesystemen iets heel anders is dan al dit soort problemen. Gebrek aan kennis daarvan en tijdgebrek hebben er voor gezorgd dat ik tot 33 ben gekomen. Toch blij dat ik weer heb meegedaan met een taal die voor heel veel problemen veel minder geschikt is dan anderen die ik hier zie. Als ik zie dat ik 200 regels nodig heb en iemand in python dat in 12 regels doet dan vind ik dat knap werk! Op naar AoC2024!

[MrHaas]

spoiler:

Ik heb https://en.wikipedia.org/wiki/Karger%27s_algorithm gebruikt, beetje slechte implementatie dus hij doet er ruim een minuut over, maar hey, het doel heiligt de middelen.

[Friits]

P_Tingen schreef op maandag 25 december 2023 @ 10:35:
Kudos voor iedereen die alles heeft binnengehengeld. Ik merk dat mijn ervaring met allerlei bedrijfs- en productiesystemen iets heel anders is dan al dit soort problemen. Gebrek aan kennis daarvan en tijdgebrek hebben er voor gezorgd dat ik tot 33 ben gekomen. Toch blij dat ik weer heb meegedaan met een taal die voor heel veel problemen veel minder geschikt is dan anderen die ik hier zie. Als ik zie dat ik 200 regels nodig heb en iemand in python dat in 12 regels doet dan vind ik dat knap werk! Op naar AoC2024!

Haha, ik ben juist onder de indruk van iedereen die de puzzels in "serieuze" talen oplost, en zich druk moet maken over types, overflows en allerlei andere zaken, en heel veel meer (foutloze) regels code moet schrijven.

Bijvoorbeeld gisteren: vergeleken met de code van .oisyn voelen mijn 20 regels Python een beetje als Lego

Tot slot nog mijn code voor vandaag, met iets wat lijkt op Karger's.

[Asgardian28]

Soultaker schreef op maandag 25 december 2023 @ 08:26:
Fijne kerstdagen allemaal!

Dag 25:

spoiler: Alternatieve aanpak

Het viel me op dat ik het antwoord ook zonder algoritme kan vinden. Als ik de invoer converteer naar GraphViz formaat en open met Qt Visual Graph Editor, dan zijn de twee helften duidelijk te zien.

[Afbeelding] [Afbeelding]

Je kunt dan simpelweg op de kritieke edges klikken om de eindpunten te identificeren, en de vertices selecteren om te zien hoe groot de componenten zijn. Het verbaasde me enigszins dat QVGE geen moeite heeft met zulke grote bestanden.

spoiler:

Je kan ook networkx met graphviz gebruiken, uiteindelijk is het dan zo'n soort regel om te visualiseren
nx.nx_agraph.graphviz_layout(G,prog='neato', args ='')

Dan krijg je zoiets https://github.com/jvanel...nowverload/solution.ipynb

[ Voor 10% gewijzigd door Asgardian28 op 25-12-2023 11:27 ]

[MatHack]

Pfff... ik had een simpele verwacht vandaag, maar dat was dus niet zo.
Moet zeggen dat ik @FCA's mening wel deel met dat ik er ook wel een beetje klaar mee ben.

spoiler:

Na een kleine zoektocht op internet eerst maar Wikipedia: Stoer–Wagner algorithm geïmplementeerd, maar mijn implementatie gaf het foute antwoord. Geen idee waarom, maar toen maar Wikipedia: Karger's algorithm gepakt met een check op 3 cuts.

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

[Soultaker]

MrHaas schreef op maandag 25 december 2023 @ 11:15:

spoiler:

Ik heb https://en.wikipedia.org/wiki/Karger%27s_algorithm gebruikt, beetje slechte implementatie dus hij doet er ruim een minuut over, maar hey, het doel heiligt de middelen.

spoiler:

Leuk, die kende ik nog niet! Interessant om te zien dat zowel dit als mijn compleet andere algoritme allebei gebruik maken van randomization.

MatHack schreef op maandag 25 december 2023 @ 12:15:
Moet zeggen dat ik @FCA's mening wel deel met dat ik er ook wel een beetje klaar mee ben.

Ik ben vooral ontzettend klaar met het “vroeg opstaan” aspect van de competitie

---

Voor het geval iemand toch nog tijd over heeft vandaag, of misschien morgen teleurgesteld is dat er geen nieuw probleem is om op te lossen, hier wat extra testinvoer voor dag 25:
aoc-2023-day-25-challenge-1-to-4.zip

Correcte antwoorden eindigen op: ..16144, ..05408, ..80480 en ..41796.