Advent of Code 2022

[Soultaker]

Voor wie z'n implementatie wil testen, hier nog wat extra invoer: aoc_2022_day23_large.zip.

Antwoorden en referentie-tijden:

$ time python3 solve-numpy-experiment.py < large-1.txt 
***08
**10

5.428s

$ time python3 solve-numpy-experiment.py < large-2.txt 
***66
**26

35.534s

$ time python3 solve-numpy-experiment.py < large-3.txt 
**90
**23

1m3.877s

$ time python3 solve-numpy-experiment.py < large-4.txt 
***37
**64

2m9.684s

$ time python3 solve-numpy-experiment.py < large-5.txt 
***12
***50

5m39.157s

Dat moet sneller kunnen!

[.oisyn]

Soultaker schreef op vrijdag 23 december 2022 @ 21:32:
Ik heb voor de grap dag 23 ook nog met numpy geïmplementeerd (valt nog van alles aan te optimaliseren). Het is conceptueel wel leuk, aangezien je elke simulatie-stap met een constant aantal array-operaties kunt uitvoeren, maar voor de officiële invoer niet heel veel sneller.

Het valt me trouwens tegen dat we nog niet van @.oisyn of andere figuren die ervaring hebben met graphics programming gehoord hebben; de bitmap-aanpak is behoorlijk goed te optimaliseren. B.v. het tellen van buren kan met een convolutie-matrix.

Ik heb het deze week een beetje druk gehad en heb sinds dag 16 eigenlijk helemaal niet meer naar de opdrachten gekeken

[Asgardian28]

Leuke vandaag! Nu relaxed morgen in voor de laatste alweer!

spoiler:

Wel heel veel tijd verloren omdat ik in mn bfs er vanuit ging dat je altijd kon wachten. Klopt natuurlijk niet als er een storm aankomt. Ging daardoor m'n stormberekeningen helemaal checken en uiteindelijk het gelopen pad vergelijken met het voorbeeld. Doh!

[tarlitz]

Inderdaad een leuke vandaag!

spoiler:

Ik heb best lang lopen knoeien om de data in een `numpy` array te lezen, maar ik dacht dat `np.roll` echt ideaal voor dit probleem zou zijn (spoiler, dat is het ook). Toen een BFS gedaan en een set met veilige posities bijgehouden. Deel 2 was simpelweg deel 1 3x aanroepen.

Python

[Remcoder]

spoiler:

Mijn eerste poging met pathfinding werkte goed voor het voorbeeld, maar met de echte input kwam die niet tot een resultaat binnen een acceptabele tijd...

Daarna maar domweg per minuut alle mogelijke posities bij gaan houden, en zodra de exit in de lijst met posities zit ben ik er.

Ik was wel nog even bang voor deel 2, maar die viel reuze mee.

[Marcj]

Ik heb het ook wat druk gehad, maar ondertussen een paar dagen extra gemaakt.
Day 17 in Kotlin
Day 18 in Kotlin
Day 19 in Kotlin
Day 20 in Kotlin
Day 21 in Kotlin

Alleen dag 19 was nog erg interessant en het duurde een tijd voordat ik voldoende optimalisaties in het zoeken had om het snel genoeg te maken.

spoiler:

- Voor de heuristic heb ik gekeken wat het maximale aantal geodes was dat je mogelijk kon produceren. Deze overschat het nog steeds een stuk, maar beter kreeg ik het niet.
- Ik ga nooit meer een bot bouwen als ik al het maximaal aantal productie heb wat ik kan gebruiken van die resource
- Ik ga ook geen bot bouwen als in de vorige ronde ik geen bot heb gebouwd en deze wel kon betalen

Eens kijken wanneer ik de tijd heb voor 22 - 25...

[Varienaja]

Dag 24 in Java.

[Varienaja]

Soultaker schreef op vrijdag 23 december 2022 @ 22:01:
Voor wie z'n implementatie wil testen, hier nog wat extra invoer: aoc_2022_day23_large.zip.
Dat moet sneller kunnen!

Dan heb ik nog flink wat te sleutelen:

large-1.txt 20s
large-2.txt 184s

Verder probeer ik niet eens.

[RefleXion]

Weer erg leuke opdracht vandaag.

spoiler:

Eerst geprobeerd om met een agent alle opties te volgen, dit werkt voor het voorbeeld, maar is veel te traag voor daadwerkelijke puzzel input. Daarom bij gaan houden wat allemaal mogelijk is per tijdspunt. Hierna is deel twee van de puzzel ook een eitje.

Day 24 (Python)

[user109731]

Dag 24 in JS. Zo'n 170 ms voor deel 1 en 430 ms voor deel 2.

spoiler:

Standaard BFS oplossing. Ik was eerst bang dat ik moest gaan prunen, maar het aantal oude/nieuwe states voor elke iteratie (minuut) is maximaal 25 * 120 (= 3000) dus dat was niet nodig. De positie van de blizzards update ik aan het begin van elke iteratie.

[ Voor 217% gewijzigd door user109731 op 24-12-2022 15:47 ]

[Janoz]

Pff, ik doe nog veel te veel. In 15 seconden heb ik alles ingelezen en een datastructuur gemaakt waarbij ik van elk punt op elk moment in de tijd weet in hoeveel minuten ik bij het begin en in hoeveel minuten ik bij het eind kan komen. Uiteindelijke heen en weer lopen is vervolgens een simpele lookup in een hashmap.

Ben tussendoor af en toe nog ff aan het kijken of ik ook minder kan berekenen..


code

[Soultaker]

Dag 24 oplossing in Python

Ik zie trouwens veel mensen moeilijk doen met het simuleren van blizzards en vervolgens de resultaten te cachen; dat is helemaal niet nodig

spoiler:

je kunt met de originele kaart in vier stappen checken of je op tijdstip `t` op positie (r, c) door een blizzard geraakt wordt; je weet immers dat een blizzard die van rechts komt `t` stappen naar rechts heeft gedaan, dus die moet dan `t` stappen links van jou begonnen zijn, wat betekent dat je alleen van rechts geraakt kan worden als op positie (r, c - t) in de invoer een '>' staat. Dan datzelfde voor elk van de vier richtingen, en een modulo operatie voor de wraparound. (code)

Janoz schreef op zaterdag 24 december 2022 @ 15:52:
Pff, ik doe nog veel te veel. In 15 seconden heb ik alles ingelezen en een datastructuur gemaakt waarbij ik van elk punt op elk moment in de tijd weet in hoeveel minuten ik bij het begin en in hoeveel minuten ik bij het eind kan komen. Uiteindelijke heen en weer lopen is vervolgens een simpele lookup in een hashmap.

Ja, je bent ook knettergek als je de hele graaf expliciet gaat instantiëren terwijl je kunt aanvoelen dat je de meeste nodes waarschijnlijk nooit bezoekt. Heeft je framework geen support voor een breadth-first-search over een impliciete graaf, waarbij je alleen de punten berekent die bezocht worden of gegenereerd worden als buren?

edit:
Ik zie dat je daar inderdaad ondersteuning voor hebt.

Overigens kun je de graaf nog iets kleiner maken door

spoiler:

voor het aantal lagen lcm(height, width) te gebruiken i.p.v. (height * width); scheelt toch weer een factor 5, voor mijn testinvoer tenminste

maar ook dat zou niet nodig moeten zijn. Ik precompute helemaal niets en het loopt binnen 1 seconde.

[ Voor 9% gewijzigd door Soultaker op 24-12-2022 16:25 ]

[user109731]

Soultaker schreef op zaterdag 24 december 2022 @ 16:15:
Dag 24 oplossing in Python

Grappig om te zien dat jij ook hebt gekeken of er verticale blizzards in de start/finish kolom zaten Ik was bang dat dit een instinker was maar gelukkig zat het niet in de invoer.

[Soultaker]

user109731 schreef op zaterdag 24 december 2022 @ 14:38:
Zo'n 170 ms voor deel 1 en 430 ms voor deel 2.

Hoe run jij je code zo snel? Als ik m'n eigen testinput er in copy/paste is 'ie ruim 10 keer zo traag:

$ time node test.js 
Part 1: *** (2106 ms)
Part 2: *** (6173 ms)

real    0m8.483s
user    0m8.721s
sys     0m0.052s

[user109731]

Soultaker schreef op zaterdag 24 december 2022 @ 16:38:
Hoe run jij je code zo snel?

Is dat de laatste versie? Ik had mijn code/post bijgewerkt om de blizzards ook in een Set op te slaan zodat ik ze niet allemaal hoef te doorlopen en dat scheelde behoorlijk.

Dit is op macOS, M1. Nog even gekeken en ik zie < 450 ms voor deel 2 ook in de browser (Chrome en Firefox).

[ Voor 3% gewijzigd door user109731 op 24-12-2022 16:44 ]

[Janoz]

Soultaker schreef op zaterdag 24 december 2022 @ 16:15:
Ja, je bent ook knettergek als je de hele graaf expliciet gaat instantiëren terwijl je kunt aanvoelen dat je de meeste nodes waarschijnlijk nooit bezoekt.

Klopt, maar ik zat te lang te kutten met mijn initiele oplossing (waarschijnlijk meerdere off by one errors ed) dat ik vervolgens maar eens aan het kijken ben gegaan hoe lang de debiele oplossing duurde. En toen ik alles in 15 sec berekende vond ik het nog niet eens zo heel debiel.

Heeft je framework geen support voor een breadth-first-search over een impliciete graaf, waarbij je alleen de punten berekent die bezocht worden of gegenereerd worden als buren?
edit:
Ik zie dat je daar inderdaad ondersteuning voor hebt.

Overigens kun je de graaf nog iets kleiner maken door

spoiler:

voor het aantal lagen lcm(height, width) te gebruiken i.p.v. (height * width); scheelt toch weer een factor 5, voor mijn testinvoer tenminste

maar ook dat zou niet nodig moeten zijn. Ik precompute helemaal niets en het loopt binnen 1 seconde.

Weet ik, maar voor de puzzelinput maakte dat niet uit.

[Soultaker]

user109731 schreef op zaterdag 24 december 2022 @ 16:43:
Is dat de laatste versie?

Aha, wist niet dat je de code nog geüpdate had. De laatste versie loopt inderdaad vrij rap:

$ time node test.js 
Part 1: *** (314 ms)
Part 2: *** (823 ms)

real    0m1.372s
user    0m1.591s
sys     0m0.051s

Nog wel iets minder snel op mijn laptop dan bij jou, maar het verschil is minder dan een factor 2. edit: kan ook aan de testinvoer liggen natuurlijk.

Overigens lijkt dit topic een soort van verkapte reclame voor Apple's M1 CPU's te zijn. Die blijken verdraait snel te zijn voor een laptop CPU.

[ Voor 8% gewijzigd door Soultaker op 24-12-2022 16:56 ]

[Diderikdm]

Prima dagje vandaag, leuke puzzel! Op naar morgen.

~ 2.5s

Dag 24 - Python

[ Voor 3% gewijzigd door Diderikdm op 24-12-2022 20:12 ]

[Diderikdm]

Fijne afsluiter. Vond het weer een leuk jaar dit jaar!

Dag 25 - Python

[MrHaas]

Yes, leuke afsluiter idd. Fijne dagen en tot volgend jaar allemaal!

[RefleXion]

Laatste dag was mijn inziens wel erg simpel in vergelijking met eerdere puzzels.

Had helaas pas op dag 17 door dat deze puzzels weer online stonden, geen punten verdiend dus de eerste dagen, alles daarna op de dag zelf opgelost en de eerdere puzzels nog voor vandaag in kunnen halen. Veel plezier aan gehad.

Oplossing day 25 (Python)

[ Voor 44% gewijzigd door RefleXion op 25-12-2022 10:59 ]

[Varienaja]

Dag 25 in Java.

Ik ben er nog even voor gaan zitten en heb een oplossing gebouwd die helemaal geen conversie naar decimaal nodig heeft. (hoewel.. de per-macht-van-5 optelling is nog decimaal, maar ik had toch geen zin om die vele mogelijkheden van 1 snafu + nog een safu + een carry in een lookup-table te stoppen. )

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

[tarlitz]

Dag 25 Python

Leuke afsluiter inderdaad! Bedankt iedereen voor het posten van jullie oplossingen! Net als vorig jaar heb ik er weer veel van opgestoken :-)

[Soultaker]

Varienaja schreef op zondag 25 december 2022 @ 11:47:
Dag 25 in Java.

Ik ben er nog even voor gaan zitten en heb een oplossing gebouwd die helemaal geen conversie naar decimaal nodig heeft.

Heb ik ook zo gedaan (de implementatie is ook bijna letterlijk hetzelfde). Blij te zien dat ik niet de enige was die zich realiseerde dat conversie naar integers helemaal niet nodig is; om twee decimale getallen op te tellen ga je ze toch ook niet eerst naar binair omzetten?

Are you trying to tell me I can convert between SNAFUs and decimal numbers?
— No, Neo, I'm telling you, when you're ready, you won't have to.

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

Mee eens. Het equivalent voor Jurassic Jigsaw was dit jaar Day 22: Monkey Map, en ik vond Day 19: Not Enough Minerals ook wel een leuke uitdaging.

[KabouterSuper]

Varienaja schreef op zondag 25 december 2022 @ 11:47:

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

Ik ben dit jaar behoorlijk afgehaakt op de optimalisatie-opgaven (Dijkstra-achtige algo's). Dag 16 deel 2 was echt niet leuk omdat een generieke methode te langzaam bleek. En de helft van de python oplossing op internet die ik bekeken heb (ter inspiratie) gaven bij mij niet eens het goede antwoord. En dag 19 was weer een hel waar je je in bochten moest wringen om je antwoord te krijgen, in de hoop dat je niet te kort door de bocht was gegaan....pfft.

[Asgardian28]

Oe vond het vanochtend toch heel lastig, meer dan uur mee bezig geweest, zag het niet meer.

Maarrrr wel voor het eerst keer op global leaderboard gekomen bij een puzzel! Hoewel dat natuurlijk in het niets valt bij eerste plek op tweakers lb 🤪

Tot volgend jaar!

[Remcoder]

Waarom stoppen als je nog door kan met puzzels van voorgaande jaren?

Op naar de 400 sterren!

Ik moet er nog 54.

[vDorst]

Day25 was leuk.
Jammer dat ik nog niet genoeg sterren heb voor part 2.
Tevens ook geleerd dat in Rust conversie van u64/i64 naar f64 niet op de nette manier, "try_from", kan.
Nu maar cast gebruikt met wat extra check zodat het veilig is.

[Daanoz]

Nog wat statistieken van dit jaar:







Thx @ElkeBxl voor het organiseren dit jaar!

[ElkeBxl]

Leuke grafieken @Daanoz ! Het organiseren was graag gedaan

Ik loop nog achter dit jaar, ben nu pas aan dag 16 aan het starten Ooit krijg ik het af, als ik de tijd vind

[MatHack]

Helaas ergens halverwege flink in de ban van een griepvirus dat ik ergens gratis kreeg... binnenkort maar eens proberen alles af te ronden. Is zeker een leuk event.

[Soultaker]

Voor het geval men zich verveelt deze laatste dagen van het jaar nu er geen dagelijkse nieuwe puzzel meer gepost wordt, wilde ik een reminder plaatsen dat een aantal van mijn custom AOC inputs nog niet opgelost zijn. Van makkelijk naar moeilijk (denk ik):

• Voor Day 23: Unstable Diffusion: alle invoer (vooral een optimalisatie-uitdaging)
• Voor Day 18: Boiling Boulders: alle invoer
• Voor Day 20: Grove Positioning System: large-2 en large-3
• Voor Day 11: Monkey in the Middle: large-2.txt (alleen deel 1) (vooral een wiskundige uitdaging)

Daarnaast zag ik dat @Asgardian28 een blog post met statistieken had gepost: Advent of Code analysis through the years. Leuk om te lezen!

[Asgardian28]

Dank je! Was leuk om eens in de stats te duiken

[sjorsjuhmaniac]

Diderikdm schreef op donderdag 15 december 2022 @ 10:08:
Al was het een bruteforce in 1m19s voor deel 2, wel blij met 9 min tussen part 1 en 2 completion time

Nu tijd om (in ieder geval part 2) te refactoren.
Dag 15 - Python

Mooie oplossing! Voor part 2 zat ik zelf ook aan hetzelfde te denken maar heb hem niet uitgewerkt omdat ik er niet op kwam om te stellen:

spoiler:

https://github.com/Jeroen...09da933d/src/day15.rs#L48
[quote]
its distance must be exactly r+1 from at least 2 sensors
[/quote]

Ik begrijp dat het punt voor meer dan 1 sensor op (>r, >r) moet liggen, maar begrijp niet waarom het precies op (r+1, r+1) moet ligen. Maar waarom kan het punt niet op (r+1, r+2) voor een van de (2) sensoren liggen?
De >r zat namelijk in mijn hoofd. In dat geval is het niet meer zo eenvoudig om de snijpunten te bepalen.

[Diderikdm]

sjorsjuhmaniac schreef op zondag 1 januari 2023 @ 16:15:
[...]


Mooie oplossing! Voor part 2 zat ik zelf ook aan hetzelfde te denken maar heb hem niet uitgewerkt omdat ik er niet op kwam om te stellen:

spoiler:

https://github.com/Jeroen...09da933d/src/day15.rs#L48
[quote]
its distance must be exactly r+1 from at least 2 sensors
[/quote]

Ik begrijp dat het punt voor meer dan 1 sensor op (>r, >r) moet liggen, maar begrijp niet waarom het precies op (r+1, r+1) moet ligen. Maar waarom kan het punt niet op (r+1, r+2) voor een van de (2) sensoren liggen?
De >r zat namelijk in mijn hoofd. In dat geval is het niet meer zo eenvoudig om de snijpunten te bepalen.

Thanks!

spoiler:

De enige reden waarom dit punt op precies (r + 1, r + 1) moet liggen is omdat er precies 1 punt binnen het gegeven vlak (but the distress beacon must have x and y coordinates each no lower than 0 and no larger than 4000000.) niet bedekt wordt door sensor(s) + r (Find the only possible position for the distress beacon. What is its tuning frequency?)

In het geval van (r + 1, r + 2) heb je in het allerbeste geval al twee punten die niet geraakt worden (r + 1, r + 1) en (r + 1, r + 2). Er moet dus een snijpunt zijn van 2+ (r + 1) lijnen om te garanderen dat slechts 1 punt binnen dit vlak niet geraakt wordt door sensor + r. Het punt kan wel op r + 2 van een sensor liggen, al liggen er dan ook meerdere sensors wel op r + 1.

In mijn geval zijn dit 288 snijpunten in de volgende vorm (gesimplificeerd):



Met bovenstaande kun je zelf nog een stapje verder gaan. Om precies 1 leeg punt te vinden, kan je twee evenwijdige lijnen vinden (r en r + 2), en deze checken tegen twee aan deze lijnen kruisende evenwijdige (r en r + 2) lijnen:

[ Voor 19% gewijzigd door Diderikdm op 02-01-2023 10:32 ]

[sjorsjuhmaniac]

Thanks @Diderikdm voor de gedetailleerde uitleg!

Door je laatste opm. wel een nieuwe vraag

spoiler:

Ik kon de betreffende logica van de pallellen lijnen r en r+2 nog niet plaatsen.

Ik heb het gegeven puzzlevoorbeeld met [code]visualize.py[/code] geplot. Daarna heb ik met dezelfde input alleen r en r + 2 geplot.
Groen met r
Blauw met r + 1
Geel met r + 2

Ik zie er nog geen verband tussen
er zijn meerdere posities waar r + 1 voor 2 sensoren waar is waarbij dan ook r en r + 2 dubbelzijdig ...
Het enige wat me wel opvalt is dat de r + 2 lijnen (geel) alleen bij het lege punt elkaar volledig doorkruizen. Bij de omcirkelde punten raken/overlappen ze elkaar wel maar lopen ze op tenminste 1 hoek niet door.

Wat is het verband waar je op doelt?


https://tweakers.net/i/UG...reyXGnHI.png?f=user_large

https://tweakers.net/i/4o...lYzf37gG.png?f=user_large

[ Voor 17% gewijzigd door sjorsjuhmaniac op 02-01-2023 21:51 ]

[.oisyn]

Diderikdm schreef op maandag 2 januari 2023 @ 10:20:

spoiler:

Met bovenstaande kun je zelf nog een stapje verder gaan. Om precies 1 leeg punt te vinden, kan je twee evenwijdige lijnen vinden (r en r + 2), en deze checken tegen twee aan deze lijnen kruisende evenwijdige (r en r + 2) lijnen:

spoiler:

Hiermee maak je het jezelf wel ingewikkelder dan nodig. Want waarom zou je per se kijken naar evenwijdige lijnen r en r+2, als je ook gewoon de lijn r+1 kunt pakken? Twee sensoren met range A en B die precies rA+rB+1 van elkaar afliggen delen zo'n lijn.

[Diderikdm]

sjorsjuhmaniac schreef op maandag 2 januari 2023 @ 21:24:
Thanks @Diderikdm voor de gedetailleerde uitleg!

Door je laatste opm. wel een nieuwe vraag

spoiler:

Ik kon de betreffende logica van de pallellen lijnen r en r+2 nog niet plaatsen.

Ik heb het gegeven puzzlevoorbeeld met [code]visualize.py[/code] geplot. Daarna heb ik met dezelfde input alleen r en r + 2 geplot.
Groen met r
Blauw met r + 1
Geel met r + 2

Ik zie er nog geen verband tussen
er zijn meerdere posities waar r + 1 voor 2 sensoren waar is waarbij dan ook r en r + 2 dubbelzijdig ...
Het enige wat me wel opvalt is dat de r + 2 lijnen (geel) alleen bij het lege punt elkaar volledig doorkruizen. Bij de omcirkelde punten raken/overlappen ze elkaar wel maar lopen ze op tenminste 1 hoek niet door.

Wat is het verband waar je op doelt?


https://tweakers.net/i/UG...reyXGnHI.png?f=user_large

https://tweakers.net/i/4o...lYzf37gG.png?f=user_large

.oisyn schreef op maandag 2 januari 2023 @ 21:54:
[...]

spoiler:

Hiermee maak je het jezelf wel ingewikkelder dan nodig. Want waarom zou je per se kijken naar evenwijdige lijnen r en r+2, als je ook gewoon de lijn r+1 kunt pakken? Twee sensoren met range A en B die precies rA+rB+1 van elkaar afliggen delen zo'n lijn.

Ah yes..

spoiler:

Ik had dit zelf nog niet verder uitgewerkt, maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2), je met de methode van het eerdere voorbeeld nog een stuk sneller (dan alle (r + 1) kruispunten vergelijken t.o.v. alle scanners) tot het antwoord komt. Ik weet nu inderdaad alleen niet of je door de extra vergelijking evenwijdig/niet echt veel runtime opschiet

[.oisyn]

@Diderikdm

spoiler:

Ik zie niet helemaal hoe jou methode voorkomt dat je snijpunten moet testen op overlap met andere sensoren.

[Diderikdm]

.oisyn schreef op maandag 2 januari 2023 @ 22:57:
@Diderikdm

spoiler:

Ik zie niet helemaal hoe jou methode voorkomt dat je snijpunten moet testen op overlap met andere sensoren.

spoiler:

Ik denk dat ik niet duidelijk genoeg was in mijn uitleg, je zou voor deze selectie ook een vergeliking moeten doen; In bovenstaand geval test je niet álle (r + 1) snijpunten die te vinden zijn zoals in het eerste voorbeeld, maar alleen de snijpunten van de (r + 1) lijnen binnen de evenwijdige (r en r + 2) lijnen. Vermoedelijk hoef je dan niet 200+ snijpunten te vergelijken met alle sensors, maar (naar schatting) onder de 50-100.

[.oisyn]

Diderikdm schreef op dinsdag 3 januari 2023 @ 00:02:
[...]

spoiler:

Ik denk dat ik niet duidelijk genoeg was in mijn uitleg, je zou voor deze selectie ook een vergeliking moeten doen; In bovenstaand geval test je niet álle (r + 1) snijpunten die te vinden zijn zoals in het eerste voorbeeld, maar alleen de snijpunten van de (r + 1) lijnen binnen de evenwijdige (r en r + 2) lijnen. Vermoedelijk hoef je dan niet 200+ snijpunten te vergelijken met alle sensors, maar (naar schatting) onder de 50-100.

spoiler:

Maar dan mis je de kern van mijn post. Namelijk, als je eerst naar paren van sensoren kijkt en alleen die paren pakt die rA+rB+1 uit elkaar liggen, dan hou je nog maar een handjevol potentiele lijnen over.

[Diderikdm]

.oisyn schreef op dinsdag 3 januari 2023 @ 00:04:
[...]

spoiler:

Maar dan mis je de kern van mijn post. Namelijk, als je eerst naar paren van sensoren kijkt en alleen die paren pakt die rA+rB+1 uit elkaar liggen, dan hou je nog maar een handjevol potentiele lijnen over.

spoiler:

Right, het is exact de conclusie van wat ik bedoel alleen beter uitgewerkt

[quote]maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2)[/quote]

^ Welke natuurlijk overlappen.

[Janoz]

Aangezien de AoC afgelopen is lijkt het me niet meer perse noodzakelijk om alles in spoiler tags te zetten. Vanaf nu mogen wat mij betreft de discussies gewoon open gevoerd worden. Komt de leesbaarheid van het topic ook ten goede.

[sjorsjuhmaniac]

Diderikdm schreef op maandag 2 januari 2023 @ 22:53:
[...]


[...]


Ah yes..

Ik had dit zelf nog niet verder uitgewerkt, maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2), je met de methode van het eerdere voorbeeld nog een stuk sneller (dan alle (r + 1) kruispunten vergelijken t.o.v. alle scanners) tot het antwoord komt. Ik weet nu inderdaad alleen niet of je door de extra vergelijking evenwijdig/niet echt veel runtime opschiet

Aah yes, ik snap nu wat je bedoelde

[Marcj]

Marcj schreef op dinsdag 20 december 2022 @ 18:19:
...

Day 16 from day16.txt:
    Part 1: 1923 in 0,027 seconds
    Part 2: 2594 in 0,045 seconds
Full run in 0,111 seconds

Day 16 from day16_big-1.txt:
    Part 1: 117949 in 0,230 seconds
    Part 2: 125937 in 0,357 seconds
Full run in 0,631 seconds

Day 16 from day16_big-2.txt:
    Part 1: 113928 in 0,267 seconds
    Part 2: 130572 in 0,348 seconds
Full run in 0,678 seconds

Day 16 from day16_big-3.txt:
    Part 1: 132860 in 0,166 seconds
    Part 2: 140630 in 0,294 seconds
Full run in 0,507 seconds

Day 16 from day16_big-4.txt:
    Part 1: 137838 in 0,403 seconds
    Part 2: 141648 in 0,443 seconds
Full run in 0,894 seconds

Day 16 from day16_big-5.txt:
    Part 1: 148452 in 5,716 seconds
    Part 2: 166998 in 7,024 seconds
Full run in 12,787 seconds

Day 16 from day16_big-6.txt:
    Part 1: 158683 in 6,397 seconds
    Part 2: 181585 in 63,713 seconds
Full run in 70,157 seconds

Day 16 from day16_big-7.txt:
    Part 1: 58361 in 0,004 seconds
    Part 2: 52131 in 0,003 seconds
Full run in 0,097 seconds

...

Ik ben de laatste tijd met Rust bezig geweest om toch eens een taal te leren die wat dichter op de machine zat. Hiermee kan ik de meeste runtimes met ongeveer een factor 4 - 6 versnellen. Wat resultaten voor deze use-case, ik vond het leuk om dag 16 opnieuw te implementeren.

$ target/release/day16 < 2022/big_inputs/day16_big-1.txt
Executing
 ├── Input parsed in 706µs
 ├── Part 1 calculated in 76,496µs: 117949
 ├── Part 2 calculated in 117,812µs: 125937
 └── Total time: 195,060µs

$ target/release/day16 < 2022/big_inputs/day16_big-2.txt
Executing
 ├── Input parsed in 1,057µs
 ├── Part 1 calculated in 92,986µs: 113928
 ├── Part 2 calculated in 77,699µs: 130572
 └── Total time: 171,778µs

$ target/release/day16 < 2022/big_inputs/day16_big-3.txt
Executing
 ├── Input parsed in 637µs
 ├── Part 1 calculated in 71,237µs: 132860
 ├── Part 2 calculated in 100,572µs: 140630
 └── Total time: 172,493µs

$ target/release/day16 < 2022/big_inputs/day16_big-4.txt
Executing
 ├── Input parsed in 647µs
 ├── Part 1 calculated in 112,746µs: 137838
 ├── Part 2 calculated in 161,786µs: 141648
 └── Total time: 275,218µs

$ target/release/day16 < 2022/big_inputs/day16_big-5.txt
Executing
 ├── Input parsed in 684µs
 ├── Part 1 calculated in 1,742,271µs: 148452
 ├── Part 2 calculated in 2,056,727µs: 166998
 └── Total time: 3,799,795µs

$ target/release/day16 < 2022/big_inputs/day16_big-6.txt
Executing
 ├── Input parsed in 1,069µs
 ├── Part 1 calculated in 2,139,708µs: 158683
 ├── Part 2 calculated in 6,206,188µs: 181585
 └── Total time: 8,347,046µs

$ target/release/day16 < 2022/big_inputs/day16_big-7.txt
Executing
 ├── Input parsed in 2,799µs
 ├── Part 1 calculated in 50µs: 58361
 ├── Part 2 calculated in 99µs: 52131
 └── Total time: 2,972µs

Of het waard is? Ik vind de Kotlin versie wel een stuk leesbaarder, maar de Rust versie kun je wel dingen doen die dichter op de hardware zitten en nog behoorlijk wat performance vinden...

ps. Deze code is gerund op een M1 macBook Pro