Advent of Code 2022

[Soultaker]

.oisyn schreef op maandag 12 december 2022 @ 22:59:
Dan krijgt de A via de node links van hem een prioriteit van 9, terwijl hij via de rechterkant 7 blijft. Mijn redenatie was dus, A kan nooit eerder op een slechter pad worden afgehandeld.

Het klopt dat zodra je A expand je de optimale afstand hebt. Dat is zo mits je een permissive heuristic gebruikt, zoals A* vereist. (Je kunt overigens een non-permissive heuristic gebruiken, maar dan moet je punten meer dan eens evalueren. Dit kan een gunstige trade-off zijn voor sommige problemen, maar de heuristiek die jij beschreef is permissive.)

Dat betekent niet dat een punt maar 1 keer in de queue terecht kan komen. Hier is nog een voorbeeld:

Saaa...
aaaa..E

Het is hopelijk duidelijk dat alle a's dezelfde prioriteit krijgen (7). Dat betekent dat de volgorde waarin je de a's bezoekt niet vast staat: je zou eerst naar rechts kunnen gaan, of eerst naar onder. Stel dat je eerst naar onder gaat, en daarna pas naar rechts, dan bezoek je eerst de volgende drie nodes:

SPQa...
123R..E

De nodes met labels 1, 2, 3, zijn bezocht en hebben afstand 1, 2, 3. P, Q, R zitten allen in de queue. Maar punt q heeft een prioriteit 9: afstand 4 + heuristiek 5. De afstand is 4 omdat 'ie gezien is vanuit het punt met afstand 3. In realiteit heeft het kortste pad lengte 2, maar om dat te beseffen moet je nog punt P bezoeken, en dat heb je nog niet gedaan. Zodra je punt P bezoek realiseer je je dat de afstand tot Q slechts 2 is, en de afstand plus heuristiek wordt dan verlaagd van 9 naar 7 (afstand 2 + heuristiek 5). Op dat moment zit Q dus twee keer in de priority queue: met prioriteit 9 en 7. Als je de oude entry niet verwijdert bezoek je 'm eerst met prioriteit 7 (correct) en daarna met prioriteit 9.

Nogmaals, dit “probleem” heb je niet als je eerst de bestaande entry uit je priority queue verwijderd of de prioriteit verlaagd, maar de meeste implementaties doen dat niet omdat het in de praktijk meestal trager is dan ze laten zitten en negeren wanneer je ze uit de queue haalt (en b.v. de std::priority_queue in C++ heeft geen ondersteuning voor het verlagen van prioriteiten (of verhogen, want C++ is een max-priority queue)).

[Soultaker]

corbosman schreef op maandag 12 december 2022 @ 23:48:
Het is een lastige idd. Even een vraagje, Het is toch niet dat je 3 aan de LCM berekening moet toevoegen right? Want dat levert ook niet het goede antwoord op.

Ik denk dat ik 'm té moeilijk gemaakt heb. Het klopt dat de LCM simpelweg met 3 vermenigvuldigen niet volstaat.

[.oisyn]

Soultaker schreef op dinsdag 13 december 2022 @ 00:48:
Dat betekent niet dat een punt maar 1 keer in de queue terecht kan komen.

Dat zei ik toch allang

Btw, .oisyn in "Advent of Code 2022"

[ Voor 13% gewijzigd door .oisyn op 13-12-2022 00:50 ]

[MrHaas]

Dag 13 in Python

spoiler:

Input parsen was eitje in Python met `eval`.
In deel 1 gelukkig al direct een comparor functie gemaakt, dus deel 2 was zo goed als alleen een simpele sort. Helaas zat er nog klein bugje in waardoor hij in sommige gevallen te vroeg 0 returnde (wat geen probleem was in deel 1) dus heeft me toch nog bijna kwartier gekost.

[Dricus]

Dag 13 - Kotlin

We worden wel verwend gisteren en vandaag, met de AoC classics .

[Cranzai]

Dricus schreef op dinsdag 13 december 2022 @ 08:58:
Dag 13 - Kotlin

We worden wel verwend gisteren en vandaag, met de AoC classics .

Instant flashbacks naar de snailfish numbers, mijn waterloo van vorig jaar.
Als ik me niet vergis is dit jaar minder erg, wellicht dat ik na vandaag dan ook die van vorig jaar op kan lossen

[Diderikdm]

Veel parsen vandaag, kan nog wel wat schaven aan mn oplossing denk ik

spoiler:

Custom sort gebruikt en is nog niet echt efficient ivm toevoegen brackets etc bij elke compare

Dag 13 - Python

[FrankMennink]

Dag 13 in Python

Was blij verrast dat voor beide delen mn eerste submission correct was. Waarschijnlijk niet optimaal wat ik gemaakt heb maar deel 2 draait in 135ms dus voor nu goed genoeg. Later maar kijken wat iedereen gedaan heeft om daarvan te leren

[RangedNeedles]

Hmm, de testinput van vandaag werkt en na er al eens volledig te zijn door gelopen ziet alles er oké uit maar voor de echte input kom ik een te laag resultaat uit. Waarschijnlijk een speciaal gevalletje of zo dat ik mis.

Ik was nu, aangezien m'n resultaat te laag is, de laatste lijnen in m'n input aan het doorlopen, maar dat gaat ook zo tergend traag. Niemand die nog wat edge cases heeft staan toevallig?

[Basje]

RangedNeedles schreef op dinsdag 13 december 2022 @ 11:04:
Niemand die nog wat edge cases heeft staan toevallig?

Heb de puzzel nog niet opgelost, maar het viel me in ieder geval op dat je werkelijke input ook

spoiler:

getallen bevat die groter zijn dan 9

.

[Janoz]

RangedNeedles schreef op dinsdag 13 december 2022 @ 11:04:
Hmm, de testinput van vandaag werkt en na er al eens volledig te zijn door gelopen ziet alles er oké uit maar voor de echte input kom ik een te laag resultaat uit. Waarschijnlijk een speciaal gevalletje of zo dat ik mis.

Ik was nu, aangezien m'n resultaat te laag is, de laatste lijnen in m'n input aan het doorlopen, maar dat gaat ook zo tergend traag. Niemand die nog wat edge cases heeft staan toevallig?

Ik had hetzelfde issue. Vervolgens heb ik een methode gemaakt die het omgekeerde van het parsen deed. Van de datastructuur die ik van een regel had gemaakt weer terug gaan naar die regel. Vervolgens elke regel afgedrukt die niet hetzelfde terug kwam. Op die manier heb ik nog 2 foutjes er uit kunnen halen die geen invloed hadden op de testinput, maar wel op de uiteindelijke input.

[ Voor 3% gewijzigd door Janoz op 13-12-2022 11:18 ]

[RangedNeedles]

Basje schreef op dinsdag 13 december 2022 @ 11:16:
[...]

Heb de puzzel nog niet opgelost, maar het viel me in ieder geval op dat je werkelijke input ook

spoiler:

getallen bevat die groter zijn dan 9

.

Klopt, maar dat zou het niet mogen zijn, dat had ik ook gespot. Net zoals dat

spoiler:

het getal nul ook kan voorkomen. Misschien niet in elke taal een probleem, maar dit geeft in JS wel een falsy value terwijl het wel gewoon een valide getal is

Janoz schreef op dinsdag 13 december 2022 @ 11:17:
[...]

Ik had hetzelfde issue. Vervolgens heb ik een methode gemaakt die het omgekeerde van het parsen deed. Van de datastructuur die ik van een regel had gemaakt weer terug gaan naar die regel. Vervolgens elke regel afgedrukt die niet hetzelfde terug kwam. Op die manier heb ik nog 2 foutjes er uit kunnen halen die geen invloed hadden op de testinput, maar wel op de uiteindelijke input.

Mm, maar ik was lui en heb het laten parsen

[MatHack]

Dag 13 in C#

spoiler:

Custom Compare functies geïmplementeerd icm polymorphism, deel 2 ging daardoor redelijk snel, maar man-o-man, het is duidelijk een tijd geleden dat ik custom compares heb gemaakt , duurde langer dan ik dacht.

[Visitor.q]

Ik heb een paar dagen achterstand moeten inlopen, want ik zat tot gisteren helemaal vast op dag 09 deel 2. Ik merk een weerstand bij mezelf om gewoon pragmatisch alle cases apart te beschrijven en wilde een generieke case formuleren op basis van de positie vectoren, maar de precieze regels had ik niet helemaal scherp. Bijvoorbeeld voor een stap U:

code:

......
......
......
....H.
4321..  (4 covers 5, 6, 7, 8, 9, s)

......
......
....H.
.4321.
5.....  (5 covers 6, 7, 8, 9, s)

Waarom zouden 2+3+4 hier niet een stapje naar rechts doen? Ze zaten immers niet diagonaal tov '1' toen de stap begon. Maar blijkbaar moet je tail 2 evalueren als je tail 1 al binnen de stap verplaatst hebt.

Uiteindelijk toch een generieke regel gevonden die schandalig eenvoudig is, achteraf:

spoiler:

dist = snake[lead] - snake[tail]
if np.linalg.norm(dist) >= 1.5:
move = dist.copy()
move[dist==2]=1
move[dist==-2]=-1
snake[tail] += move

Day10 was goed te doen, leuk om te doen en een fijne opsteker om weer eens iets in een lunchpauze te kunnen bouwen. Day11 heb ik nu net klaar, en ik zag in eerste instantie op tegen het parsen maar uiteindelijk is het huzarenstukje waarop ik wel trots ben juist daarin, namelijk dat

spoiler:

ik bij het initialiseren van de Class Monkey een lambda functie aanmaak voor de operation:

self.inspect = lambda old: eval(operation)

waarbij operation dus gewoon een string literal uit de input file is. Dat scheelde me een hoop if-else gehannes bij het parsen om de plus, keer en kwadraat te interpreteren.

Ik had deze trouwens niet klaar gekregen zonder hint over o.a. die CRT regel. Ik wilde eerst met gmpy grote integers gaan gebruiken maar dat werd helemaal niks

[Marcj]

Day 13 in Kotlin

Ik ben blij dat ik voor deze implementatie-richting heb gekozen voor deel 1, waardoor deel 2 wel heel eenvoudig was te doen. Ik ben alleen veel te lang bezig geweest met het parsen netjes en leesbaar krijgen.

[Remcoder]

spoiler:

Voor deel 2 komt er bij mijn code een andere sortering uit dan het voorbeeld, maar de elementen die van belang zijn komen op de juiste plekken terecht en daardoor vind ik dus toch het juiste antwoord.

Dus, task failed succesfully?

Ik ben op zich wel nieuwsgierig waardoor dat komt, maar ik ben blij dat ik beide sterren weer heb.

[Litpho]

De afgelopen twee dagen waren wat rommelig. Gisteren vooral aan het reizen geweest en 's avonds proberen om A* zelf te implementeren was niet succesvol. Vanochtend dag 13 parsen en Ord/PartialOrd implementeren gaf voldoende goede moed om dag 12 dan maar met een library op te lossen (dat zou ik in productiecode ook doen met "solved problems" als een A* algoritme).

[KabouterSuper]

Remcoder schreef op dinsdag 13 december 2022 @ 13:28:

spoiler:

Voor deel 2 komt er bij mijn code een andere sortering uit dan het voorbeeld, maar de elementen die van belang zijn komen op de juiste plekken terecht en daardoor vind ik dus toch het juiste antwoord.

Dus, task failed succesfully?

Ik ben op zich wel nieuwsgierig waardoor dat komt, maar ik ben blij dat ik beide sterren weer heb.

Heb je een voorbeeld? Ik kan me in theorie voorstellen dat je ergens een 'draw' krijgt, maar die ben ik niet tegengekomen in mijn dataset.

[Soultaker]

Dag 13 in Python. Ik heb het heel simpel gehouden:

spoiler:

json.loads() gebruiken om de invoer te “parsen”, en nieuwe lijst creëren om getallen met lijsten te vergelijken

.

.oisyn schreef op dinsdag 13 december 2022 @ 00:24:
Weg met die std::priority_queue dan maar, en vervangen met een hash map van int naar vector. O(1) insertions en deletions. Aangezien die priorities toch monotoom toenemend zijn en enorm bij elkaar liggen, kan ik ze net zo goed direct indexeren. Large-2 part-2 nu in 220ms . Alleen jammer genoeg wel performance degradatie bij de andere inputs

Heel netjes! Maar waarom een hash map als de keys in een klein bereik liggen? Ik heb gewoon een vector van vectors gemaakt (de buitenste voor de prioriteiten, de binnenste voor de punten met dezelfde prioriteit).

[ Voor 56% gewijzigd door Soultaker op 13-12-2022 14:07 ]

[Remcoder]

KabouterSuper schreef op dinsdag 13 december 2022 @ 13:45:
[...]

Heb je een voorbeeld? Ik kan me in theorie voorstellen dat je ergens een 'draw' krijgt, maar die ben ik niet tegengekomen in mijn dataset.

spoiler:

Voor de voorbeeldinput vindt mijn code onderstaande sortering, zoals je ziet staan een paar elementen op een andere positie, maar de divider packets komen op de juiste plek terecht.

[]
[[]]
[[[]]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[[1],4]
[[1],[2,3,4]]
[1,1,3,1,1]
[1,1,5,1,1]
[1,[2,[3,[4,[5,6,0]]]],8,9]
[[2]]
[3]
[[4,4],4,4,4]
[[4,4],4,4]
[[6]]
[7,7,7]
[7,7,7,7]
[[8,7,6]]
[9]

[MrHaas]

Remcoder schreef op dinsdag 13 december 2022 @ 14:11:
[...]

spoiler:

[[1],4]
[[1],[2,3,4]]

[1] wordt vergeleken met [1]
1 wordt vergeleken met 1
4 wordt vergeleken met [2,3,4], niet zelfde type dus
[4] wordt vergelekent met [2,3,4]
4 wordt vergeleken met 2
2 wordt daarna vergeleken met 4 en daar stopt de evaluatie.

[Soultaker]

Remcoder schreef op dinsdag 13 december 2022 @ 14:11:

spoiler:

Voor de voorbeeldinput vindt mijn code onderstaande sortering, zoals je ziet staan een paar elementen op een andere positie, maar de divider packets komen op de juiste plek terecht.

Grote spoiler voor Dag 13 deel 2:

spoiler:

je hoeft voor deel 2 helemaal niet te sorteren, je hoeft alleen te tellen hoeveel elementen kleiner zijn dan [[2]] en hoeveel kleiner dan [[6]], zie b.v. deze code. De onderlinge ordening van de lijsten maakt voor het antwoord niet uit.

[evanraalte]

Soultaker schreef op dinsdag 13 december 2022 @ 14:17:
[...]

Grote spoiler voor Dag 13 deel 2:

spoiler:

je hoeft voor deel 2 helemaal niet te sorteren, je hoeft alleen te tellen hoeveel elementen kleiner zijn dan [[4]] en hoeveel kleiner dan [[6]], zie b.v. deze code. De onderlinge ordening van de lijsten maakt voor het antwoord niet uit.

spoiler:

Kan, maar als je een 2 items kan vergelijken, dan ben je (in elk geval in python) al heel dicht bij het bouwen van een custom sort key.

[KabouterSuper]

Soultaker schreef op dinsdag 13 december 2022 @ 14:17:
[...]

Grote spoiler voor Dag 13 deel 2:

spoiler:

je hoeft voor deel 2 helemaal niet te sorteren, je hoeft alleen te tellen hoeveel elementen kleiner zijn dan [[4]] en hoeveel kleiner dan [[6]], zie b.v. deze code. De onderlinge ordening van de lijsten maakt voor het antwoord niet uit.

spoiler:

Mooie oplossing. Ik ben vandaag gewoon heel lui geweest en heb de array ingelezen met eval (deel 1) en in deel 2 alles gesorteerd met de gymles sortering.

[gedonie]

Ben veel te lang bezig geweest om de compare methode goed te schrijven. Maar uiteindelijk alsnog opgelost. Dag 13 in Java

[corbosman]

php in 2ms voor beide delen.

spoiler:

De parser is super simpel als je een json decoder gebruikt.

[Janoz]

Soultaker schreef op dinsdag 13 december 2022 @ 14:17:
[...]

Grote spoiler voor Dag 13 deel 2:

spoiler:

je hoeft voor deel 2 helemaal niet te sorteren, je hoeft alleen te tellen hoeveel elementen kleiner zijn dan [[4]] en hoeveel kleiner dan [[6]], zie b.v. deze code. De onderlinge ordening van de lijsten maakt voor het antwoord niet uit.

Zoiets ;)

[Remcoder]

Remcoder schreef op dinsdag 13 december 2022 @ 14:11:
[...]

spoiler:

Voor de voorbeeldinput vindt mijn code onderstaande sortering, zoals je ziet staan een paar elementen op een andere positie, maar de divider packets komen op de juiste plek terecht.

[]
[[]]
[[[]]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[[1],4]
[[1],[2,3,4]]
[1,1,3,1,1]
[1,1,5,1,1]
[1,[2,[3,[4,[5,6,0]]]],8,9]
[[2]]
[3]
[[4,4],4,4,4]
[[4,4],4,4]
[[6]]
[7,7,7]
[7,7,7,7]
[[8,7,6]]
[9]

spoiler:

Ik denk wel dat ik weet waarom mijn sortering niet goed werkt, en dat is omdat mijn CompareTo niet reversible is.

left.compareTo(right) en right.compareTo(left) geven niet altijd het omgekeerde resultaat terug. Dan krijg je een andere sortering uiteindelijk.

Gelukkig zijn de divider packages zo gekozen dat het geen probleem vormt bij de uiteindelijke positionering van deze packages.

[Marcj]

Soultaker schreef op dinsdag 13 december 2022 @ 14:17:
[...]

Grote spoiler voor Dag 13 deel 2:

spoiler:

je hoeft voor deel 2 helemaal niet te sorteren, je hoeft alleen te tellen hoeveel elementen kleiner zijn dan [[4]] en hoeveel kleiner dan [[6]], zie b.v. deze code. De onderlinge ordening van de lijsten maakt voor het antwoord niet uit.

Dat ik daar niet aan gedacht heb, dat maakt het nog veel simpeler!

[_mike_]

Rust

Draait in 1.18ms. Meeste tijd kwijt in de parser (690 µs). Ook geprobeerd met serde_json en simd_json, maar die zijn veel trager: rond de 3ms om te parsen. Zelfs als ik de hele input als 1 grote array aan simd_json voer, wordt het niet sneller. Op een macbook 2020 met een 2GHz quad-core i5.

[.oisyn]

Soultaker schreef op dinsdag 13 december 2022 @ 14:06:
Dag 13 in Python. Ik heb het heel simpel gehouden:

spoiler:

json.loads() gebruiken om de invoer te “parsen”, en nieuwe lijst creëren om getallen met lijsten te vergelijken

.


[...]

Heel netjes! Maar waarom een hash map als de keys in een klein bereik liggen? Ik heb gewoon een vector van vectors gemaakt (de buitenste voor de prioriteiten, de binnenste voor de punten met dezelfde prioriteit).

Gek, ik heb helemaal geen hash map gebruikt . Het was een std::deque. Het was denk ik al laat

[Varienaja]

Vanmorgen was ik niet direkt goed wakker. Parsertje bouwen (jaloerse blik naar de .eval() talen) duurde veels te lang. Het sorteren wou ik te elegant implementeren. Kostte ook veel tijd om goed te krijgen, dus ik heb het over een andere boeg gegooid en heb de Engelse specificatie 1:1 in Java omgezet, en ziedaar: het draait.

Dag 13 in Java.

[DataGhost]

Varienaja schreef op dinsdag 13 december 2022 @ 17:20:
Vanmorgen was ik niet direkt goed wakker. Parsertje bouwen (jaloerse blik naar de .eval() talen) duurde veels te lang. Het sorteren wou ik te elegant implementeren. Kostte ook veel tijd om goed te krijgen, dus ik heb het over een andere boeg gegooid en heb de Engelse specificatie 1:1 in Java omgezet, en ziedaar: het draait.

Dag 13 in Java.

Mja deel van deze opdrachten is imo ook standaardcode die allang geschreven is hergebruiken, zodat je niet onnodig met parsen bezig bent tenzij dat expliciet de doel van de opgave is. Ook voor Java kan je gewoon library-functies gebruiken om

spoiler:

json

te parsen.

[Soultaker]

Twee extra grote sets voor dag 13: aoc_2022_day13_large.zip (10 MB zip file, 30 MB elk uitgepakt).

Ter referentie:

$ time pypy3 solve.py < aoc_2022_day13_large-1.txt 
***73
***02

real 0m4.516s
user 0m4.215s
sys 0m0.270s

$ time pypy3 solve.py < aoc_2022_day13_large-2.txt 
******370
******840

real 0m2.963s
user 0m2.660s
sys 0m0.259s

Ik moest een eigen parser schrijven (code) hiervoor want json.loads() trok het niet meer. Het bleek nog veel sneller te zijn ook

[ Voor 4% gewijzigd door Soultaker op 13-12-2022 19:55 . Reden: Antwoorden gefixt. ]

[Soultaker]

Janoz schreef op dinsdag 13 december 2022 @ 15:03:
Zoiets ;)

Ik vind je code erg netjes (maar wel erg verbose, in typische Java stijl), ook b.v. de introductie van een ListOrInt class. Maar wat ik niet begrijp is

spoiler:

waarom je Queues gebruikt in de implementatie van compare()? Nu doe je een heleboel extra werk met de recursieve constructie van nieuwe ArrayDeques en singletons, terwijl je alleen maar van links naar rechts door de lijsten loopt.

edit:
Ik zou zoiets doen. OK, je alloceert nog steeds iterators, maar dat zou je weg kunnen optimaliseren wanneer je alle lists als ArrayList declareert. Je zou ook ListOrInt zelf iterable kunnen maken.

[ Voor 20% gewijzigd door Soultaker op 13-12-2022 18:47 ]

[Varienaja]

DataGhost schreef op dinsdag 13 december 2022 @ 17:40:
Ook voor Java kan je gewoon library-functies gebruiken om...

Ohja kijk aan. Dat scheelt weer 20 regels code.

Grote inputs (met verdacht andere antwoorden voor part 1 als @Soultaker )

aoc_2022_day13_large-1.txt
Solution 13a: ***73
Solution 13b: ***02
1) 2,5s (1,6s met eigen parser)
2) 38s (36s met eigen parser)

aoc_2022_day13_large-2.txt
Solution 13a: ******370
Solution 13b: ******840
1) 2,1s (1,3s met eigen parser)
2) 5,7s (3,9s met eigen parser)

[ Voor 45% gewijzigd door Varienaja op 13-12-2022 20:19 ]

[Janoz]

Soultaker schreef op dinsdag 13 december 2022 @ 18:09:
[...]

Ik vind je code erg netjes (maar wel erg verbose, in typische Java stijl), ook b.v. de introductie van een ListOrInt class. Maar wat ik niet begrijp is

spoiler:

waarom je Queues gebruikt in de implementatie van compare()? Nu doe je een heleboel extra werk met de recursieve constructie van nieuwe ArrayDeques en singletons, terwijl je alleen maar van links naar rechts door de lijsten loopt.

Tja, 's ochtends begin ik met de 'make it work' en daarna komt de 'make it nice'. Juist conceptueel vond ik makkelijker te behappen met recursie, dus zo was mijn eerste implementatie. Aangezien dat meer dan snel genoeg was ben ik er niet verder mee gegaan. Ik ben juist bezig geweest om de algoritmen van gisteren verder uit te breiden en generaliseren zodat ik ze in de toekomst gelijk uit mijn gereedschapskist kan trekken (had ik vorig jaar al moeten doen met dag 15)

Gelijk ook nog even wat timings los gelaten op de verschillende algo's:

code:

-- Part 1 --
aStar        : 490
In 52ms
BFS          : 490
In 18ms
Dijkstra     : 490
In 31ms
-- Part 2 --
BFS          : 488
In 10ms
BFS rev      : 488
In 5ms
Dijkstra     : 488
In 10ms
Dijkstra rev : 488
In 7ms

[ Voor 12% gewijzigd door Janoz op 13-12-2022 18:53 ]

[Soultaker]

Varienaja schreef op dinsdag 13 december 2022 @ 18:20:
Ohja kijk aan. Dat scheelt weer 20 regels code.

Grote inputs (met verdacht andere antwoorden voor part 1 als @Soultaker )

Oei! Er zat een bug in m'n handgeschreven parser code. Jouw antwoorden zijn correct (ik zal m'n comment ook updaten).

[corbosman]

Soultaker schreef op dinsdag 13 december 2022 @ 00:49:
[...]

Ik denk dat ik 'm té moeilijk gemaakt heb. Het klopt dat de LCM simpelweg met 3 vermenigvuldigen niet volstaat.

Heeft het te maken met de modular multiplicative inverse?

[Soultaker]

corbosman schreef op dinsdag 13 december 2022 @ 21:24:
Heeft het te maken met de modular multiplicative inverse?

Ja, dat is een stukje van de puzzel! (Maar nog niet de hele oplossing.)

[HectorMalot]

Soultaker schreef op dinsdag 13 december 2022 @ 17:53:
Twee extra grote sets voor dag 13: aoc_2022_day13_large.zip (10 MB zip file, 30 MB elk uitgepakt).

Ter referentie:

$ time pypy3 solve.py < aoc_2022_day13_large-1.txt 
***73
***02

real 0m4.516s
user 0m4.215s
sys 0m0.270s

$ time pypy3 solve.py < aoc_2022_day13_large-2.txt 
******370
******840

real 0m2.963s
user 0m2.660s
sys 0m0.259s

Ik moest een eigen parser schrijven (code) hiervoor want json.loads() trok het niet meer. Het bleek nog veel sneller te zijn ook

Thx, beide net onder de seconde (950ms). Wel jaloers op 'eval() en you're done' opties hier, mijn parser is een stuk lelijker. Code

[.oisyn]

Hmm als ik er < tekens tussen zet kan ik het bijna linea reacta aan KolQ voeren Het enige wat dan fout gaat is een compare tussen een list en een int

[corbosman]

Soultaker schreef op dinsdag 13 december 2022 @ 23:26:
[...]

Ja, dat is een stukje van de puzzel! (Maar nog niet de hele oplossing.)

Ja daar waren we ook al achter maar we komen er nog niet uit. Om slapeloze nachten te vermijden zou een harde spoiler wel helpen.

[Soultaker]

corbosman schreef op woensdag 14 december 2022 @ 00:05:
Ja daar waren we ook al achter maar we komen er nog niet uit. Om slapeloze nachten te vermijden zou een harde spoiler wel helpen.

Het moet wel een uitdaging blijven hè! Overigens is er ook een redelijke oplossing mogelijk zonder modular inverse (die is voor mij wel iets trager, ongeveer 40 seconden in Python).

[MueR]

Goed, ik heb even voor dag 12 de handdoek in de ring gegooid. Met de test input werkt alles prachtig (ook als ik extra points op de map toevoeg), met de echte input voor geen meter

[ Voor 13% gewijzigd door MueR op 14-12-2022 01:15 ]

[Soultaker]

MueR schreef op woensdag 14 december 2022 @ 01:10:
Goed, ik heb even voor dag 12 de handdoek in de ring gegooid. Met de test input werkt alles prachtig, met de echte input voor geen meter

Heb je in de probleembeschrijving de zin gelezen die tussen haakjes staat?

Als dat niet je probleem is, en je wil een hint, moet je een link naar je code posten

[MueR]

Soultaker schreef op woensdag 14 december 2022 @ 01:19:
[...]

Heb je in de probleembeschrijving de zin gelezen die tussen haakjes staat?

Als dat niet je probleem is, en je wil een hint, moet je een link naar je code posten

Yeah, die heb ik gelezen. Zoals gezegd, m'n code vind bij de test input het helemaal prima, maar bij deel 2 ging het mis, en nu werkt zelfs deel 1 niet meer met echte input (test prima though). Code hier

[.oisyn]

Soultaker schreef op dinsdag 13 december 2022 @ 17:53:
Twee extra grote sets voor dag 13: aoc_2022_day13_large.zip (10 MB zip file, 30 MB elk uitgepakt).

Ter referentie:

$ time pypy3 solve.py < aoc_2022_day13_large-1.txt 
***73
***02

real 0m4.516s
user 0m4.215s
sys 0m0.270s

$ time pypy3 solve.py < aoc_2022_day13_large-2.txt 
******370
******840

real 0m2.963s
user 0m2.660s
sys 0m0.259s

Ik moest een eigen parser schrijven (code) hiervoor want json.loads() trok het niet meer. Het bleek nog veel sneller te zijn ook

===[ input.txt ]==========
Time: 61us (load:37us, algo:23us)
5760
===[ aoc_2022_day13_large-1.txt ]==========
Time: 32,953us (load:38us, algo:32,915us)
***73
===[ aoc_2022_day13_large-2.txt ]==========
Time: 26,056us (load:58us, algo:25,997us)
***370

Part2 moet ik nog maken

Wel even een shoutout naar @timvisee, ik had een bugje in mijn parser die niet naar voren kwam in de example en heb die van hem even gebruikt om te kijken welk paar ik speciifek fout had

[ Voor 8% gewijzigd door .oisyn op 14-12-2022 02:15 ]

[Soultaker]

MueR schreef op woensdag 14 december 2022 @ 01:24:
Yeah, die heb ik gelezen. Zoals gezegd, m'n code vind bij de test input het helemaal prima, maar bij deel 2 ging het mis, en nu werkt zelfs deel 1 niet meer met echte input (test prima though). Code hier

Ik heb het niet helemaal doorgespit maar twee dingen vielen me op.

Het eerste is dat je als heuristiek voor A* de Euclidean distance tussen punten gebruikt (sqrt((x1 - x2)² + (y1 - y2)²), wat eigenlijk de Manhattan distance zou moeten zijn (abs(x1 - x2) + abs(y1 - y2)). Maar dat zou geen foute antwoorden op moeten leveren, aangezien de Euclidean distance altijd minder is dan de Manhattan distance, dus blijft de schatting permissive.

Het tweede is dat je in calculateRealCost() de hoogte van het veld als cost lijkt terug te geven? Maar de cost van een stap is altijd 1 (vandaar dat BFS ook werkt ipv A*), onafhankelijk van de hoogte waar je naartoe stapt.

.oisyn schreef op woensdag 14 december 2022 @ 01:33:

===[ input.txt ]==========
Time: 61us (load:37us, algo:23us)
5760
===[ aoc_2022_day13_large-1.txt ]==========
Time: 32,953us (load:38us, algo:32,915us)
***73
===[ aoc_2022_day13_large-2.txt ]==========
Time: 26,056us (load:58us, algo:25,997us)
***370

Nice, load > algo is altijd jammer, al verbaasd het me eerlijk gezegd niet. Ik heb specifiek geprobeerd om invoer te genereren waarbij je een groot deel van de waarden inhoudelijk moet vergelijken, maar het blijft natuurlijk lineair in de invoer, en de probleembeschrijving laat helaas niet veel meer creatieve invoer toe.

[.oisyn]

Part2 toegevoegd, de tijden worden niet significant anders (komt vooral omdat die dividers zo kort zijn dat je het antwoord al na een paar checks weet)

spoiler:

===[ aoc_2022_day13_large-1.txt ]==========
Time: 32,646us (load:36us, algo:32,610us)
Part 1: 22673
Part 2: 80802

===[ aoc_2022_day13_large-2.txt ]==========
Time: 26,543us (load:44us, algo:26,498us)
Part 1: 226645370
Part 2: 801677840

[ Voor 46% gewijzigd door .oisyn op 14-12-2022 01:59 ]

[corbosman]

Soultaker schreef op dinsdag 13 december 2022 @ 17:53:
Twee extra grote sets voor dag 13: aoc_2022_day13_large.zip (10 MB zip file, 30 MB elk uitgepakt).

Ter referentie:

$ time pypy3 solve.py < aoc_2022_day13_large-1.txt 
***73
***02

real 0m4.516s
user 0m4.215s
sys 0m0.270s

$ time pypy3 solve.py < aoc_2022_day13_large-2.txt 
******370
******840

real 0m2.963s
user 0m2.660s
sys 0m0.259s

Ik moest een eigen parser schrijven (code) hiervoor want json.loads() trok het niet meer. Het bleek nog veel sneller te zijn ook

large-2, 4s en 24s. large-1 lukt me niet want php's json parser vindt het geen valid json. Ook paar online parsers geprobeerd. Maar wellicht is dat expres

[.oisyn]

corbosman schreef op woensdag 14 december 2022 @ 02:02:
[...]


large-2, 4s en 24s. large-1 lukt me niet want php's json parser vindt het geen valid json. Ook paar online parsers geprobeerd. Maar wellicht is dat expres

Wel gek, ik zie niet in hoe je hierme data die incompatible is met json kan genereren. Weet je waar de fout zit?
Misschien is de nesting gewoon te diep

[ Voor 5% gewijzigd door .oisyn op 14-12-2022 02:07 ]

[.oisyn]

Leuk feitje, kijken of een regel "kleiner" is dan [[2]] of [[6]] kan met een regex

spoiler:

resp. \[+[01]?\] en \[+[0-5]?\]

[.oisyn]

@Soultaker Ik zie dat de paren voor jouw grotere sets wel redelijk identiek zijn kwa string. Misschien een idee om wat willekeurige nestings toe te voegen voor de afzonderlijke getallen. Want 2 matcht immers met [[[[[[[2]]]]]]].

[Janoz]

Zo, dag 14 viel mij enorm mee. Waarschijnlijk ook omdat ik nog wel wat datastructuren van vorig jaar had liggen.

spoiler:

Blijkbaar was de naïve benadering ook voor deel 2 snel zat en heb ik niet veel slimmigheden hoeven doen, maar dat zal vast ook wel komen omdat ik al een slim 2D grid had liggen

[bakkerjangert]

Leuke opdracht vandaag, lekker met zand spelen En inderdaad goed te doen.

spoiler:

Ik heb een enkele optimalisatie voor part 2 toegevoegd, door ook verticale wanden te plaatsen en er daarna de driehoeken aan de zijkanten met een eenvoudige formule bij te tellen.

[Janoz]

Oh, dat is op zich wel slim, dat zijn er nogal wat. De enige optimalisatie voor deel 2 die ik gedaan heb is

spoiler:

gewoon verder gaan met waar ik bij deel 1 gebleven was. De eerste 500+ korrels vallen immers hetzelfde

[Gropah]

Het was prima te doen. Als ik niet dom was geweest was ie binnen een uur af geweest.

spoiler:

Ik was alleen zo dom om altijd de laatste waarde in de min/max te stoppen, ipv alleen als ie daadwerkelijk groter was. De example input werkt dan wel, omdat de 2e lijn de onderste lijn is en de volledige breedte doet. Maar de daadwerkelijke output natuurlijk niet.

[eheijnen]

Graag wat assistentie bij dag 13...

Ik vraag me af hoe deze stelling uit de case past bij onderstaande elementen uit de input sample.

If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.

code:

== Pair 2 ==
- Compare [[1],[2,3,4]] vs [[1],4]
  - Compare [1] vs [1]
    - Compare 1 vs 1
  - Compare [2,3,4] vs 4
    - Mixed types; convert right to [4] and retry comparison
    - Compare [2,3,4] vs [4]
      - Compare 2 vs 4
        - Left side is smaller, so inputs are in the right order

Hier word alleen de 2 vergeleken terwijl de stelling zegt: "if the right list runs out of items first, the inputs are not in the right order." Maar pair 2 word goedgekeurd.

Zie ik nou iets over het hoofd of....

[ElkeBxl]

Ik loop zwaar achter dit jaar (life happens), gisterenavond dag 7 in Rust opgelost. Volgende 2 weken heb ik congé dus kan ik dan wel inhaalpoging doen

Ook de lijst in de topicstart weer aangevuld. Als iemand mij gestuurd zou hebben die er nog niet in staat, let me know! Ik denk dat ik wel iedereen heb toegevoegd en beantwoord

[.oisyn]

@eheijnen 2 wordt toch eerst vergeleken met 4? compare the first value of each list, then the second value, and so on. 2 is kleiner dan 4, dus [2,3,4] is kleiner dan [4].

[bakkerjangert]

eheijnen schreef op woensdag 14 december 2022 @ 08:06:
Graag wat assistentie bij dag 13...

Ik vraag me af hoe deze stelling uit de case past bij onderstaande elementen uit de input sample.

If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.

code:

== Pair 2 ==
- Compare [[1],[2,3,4]] vs [[1],4]
  - Compare [1] vs [1]
    - Compare 1 vs 1
  - Compare [2,3,4] vs 4
    - Mixed types; convert right to [4] and retry comparison
    - Compare [2,3,4] vs [4]
      - Compare 2 vs 4
        - Left side is smaller, so inputs are in the right order

Hier word alleen de 2 vergeleken terwijl de stelling zegt: "if the right list runs out of items first, the inputs are not in the right order." Maar pair 2 word goedgekeurd.

Zie ik nou iets over het hoofd of....

spoiler:

Volgens mij gaat het om de toevoeging 'runs out of items'. In dit geval zijn er nog items om te vergelijken en worden de ints vergeleken, waarmee aan de eerst beschreven voorwaarde voldaan wordt. Voorwaarde twee kan alleen een win of verlies opleveren als een van beide een lege list is. Anders doorgaan met vergelijken van de items in de list.

[eheijnen]

.oisyn schreef op woensdag 14 december 2022 @ 08:12:
@eheijnen 2 wordt toch eerst vergeleken met 4? compare the first value of each list, then the second value, and so on. 2 is kleiner dan 4, dus [2,3,4] is kleiner dan [4].

4 word geconverteerd naar een list [4] met 1 element met waarde 4
dan wordt er vergeleken: Compare [2,3,4] vs [4]

En kom je bij de volgende waarde uit en blijkt het array links langer te zijn...

[ Voor 9% gewijzigd door eheijnen op 14-12-2022 08:15 ]

[.oisyn]

eheijnen schreef op woensdag 14 december 2022 @ 08:14:
[...]

4 word geconverteerd naar een list [4] met 1 element met waarde 4
dan wordt er vergeleken: Compare [2,3,4] vs [4]

En kom je bij de volgende waarde uit en blijkt het array links langer te zijn...

Maar je komt niet bij de volgende waarde want 2<4

[eheijnen]

@.oisyn & @bakkerjangert
Ja, ik heb het nu gezien...
Thanks!!

[MatHack]

MueR schreef op woensdag 14 december 2022 @ 01:24:
[...]

Yeah, die heb ik gelezen. Zoals gezegd, m'n code vind bij de test input het helemaal prima, maar bij deel 2 ging het mis, en nu werkt zelfs deel 1 niet meer met echte input (test prima though). Code hier

Volgens mij zit het probleem hier, wat doet die abs() daar? Het grote verschil tussen de testcases & de echte input is sprongen naar beneden (dus groter dan -1), maar die vis je er nu uit. De testcase heeft altijd keurig stappen van 1, 0 of -1, dus dan werkt je abs() wel

EDIT: Daarnaast heb kans dat de S = 0/E = 27 je ook nog nekt, volgens mij kun je in jouw oplossing nu niet van y naar E en van S naar b, terwijl dat wel mogelijk moet zijn.

[ Voor 9% gewijzigd door MatHack op 14-12-2022 08:46 . Reden: nog extra dingetje bedacht ]

[Janoz]

@MueR : GladstoneW in "Advent of Code 2022"

[Litpho]

Rust. Dag 14 viel na twee drukke dagen wel mee. Het is vast slimmer te doen, maar code schrijven die je volgend jaar nog kan lezen is zijn eigen beloning .

https://github.com/litpho...ob/main/day14/src/main.rs

[MrHaas]

spoiler:

Eerst ook op de naieve manier gedaan en gewoon zand naar beneden laten vallen tot het blijft plakken. Runde nog in 500ms voor deel 2. Daarna maar ff omgeschreven naar DFS, kunnen we die ook weer afstrepen voor dit jaar . Voor het bepalen van collisions heb ik alle punten in set gegooid, dus dat is denk ik ik ook nog wel te verbeteren door gewoon collisions met de lijnen te vinden.

[CMG]

Dag 13 was een ramp voor mij gisteren, vandaag was leuk om te doen 😊

code | video

[CMG]

Soultaker schreef op dinsdag 13 december 2022 @ 17:53:
Twee extra grote sets voor dag 13: aoc_2022_day13_large.zip (10 MB zip file, 30 MB elk uitgepakt).

Ter referentie:

$ time pypy3 solve.py < aoc_2022_day13_large-1.txt 
***73
***02

real 0m4.516s
user 0m4.215s
sys 0m0.270s

$ time pypy3 solve.py < aoc_2022_day13_large-2.txt 
******370
******840

real 0m2.963s
user 0m2.660s
sys 0m0.259s

Ik moest een eigen parser schrijven (code) hiervoor want json.loads() trok het niet meer. Het bleek nog veel sneller te zijn ook

Had al een eigen parser geschreven (na veel gedoe) gisteren, dus kon runnen zonder aanpassingen. Code gebruikt substring om 'lists' te fixen; dat kost de meeste tijd waarschijnlijk 😊

Je 2e file triggert een conditie die niet origineel kon voorkomen (geen beslissing na compare), daar gooide ik eerst een exception maar return ik nu gewoon raw string length compare omdat ze functioneel gelijk zijn, maar niet in raw form; had ook return 0 (geen verschil) gedaan, maar dat maakt voor de uitkomst geen verschil, dus ik denk dat als laatste de raw lengte vergelijken ook goed is.

spoiler:

22673
20808
Code runtime: 00:00:02.9549417

226645370
37592808
Code runtime: 00:00:02.5404719

update:

Mijn sorted results die de part 2 waardes genereert; ik zie geen fout als ik met de hand kijk; maar zie dat jij duidelijk andere waardes hebt voor deel 2

[ Voor 9% gewijzigd door CMG op 14-12-2022 10:58 ]

[.oisyn]

@CMG Je part-2 antwoorden kloppen niet. Oh dat zei je al

spoiler:

van large-1 part-2 zijn gek genoeg de digits precies omgedraaid, maar dat lijkt me louter toeval?

Wat betreft:

Je 2e file triggert een conditie die niet origineel kon voorkomen (geen beslissing na compare), daar gooide ik eerst een exception maar return ik nu gewoon raw string length compare omdat ze functioneel gelijk zijn, maar niet in raw form; had ook return 0 (geen verschil) gedaan, maar dat maakt voor de uitkomst geen verschil, dus ik denk dat als laatste de raw lengte vergelijken ook goed is.

Het maakt voor part-1 weldegelijk een verschil. Gevraagd wordt om de indices op te tellen van de paren die in de juiste volgorde staan. Als ze equivalent zijn dan is de volgorde juist. Door iets anders te doen (bijvoorbeeld door string-lengte te vergelijken) kan het zijn dat je bepaalt dat ze in de verkeerde volgorde staan, waardoor het uiteindelijke antwoord niet juist is.

Voor part-2 zal het geen verschil maken.

.edit: zit net naar je sorted resultaten te kijken. Het valt me op dat je heel wat regels mist. Large-1 heeft 900 regels, oftewel 300 paren, dus ik verwacht 602 regels in je gesorteerde eindresultaat, maar jij hebt er maar 304. Large-2 heeft 90.000 regels, oftewel 30.000 paren, dus ik verwacht 60.002 regels in je gesorteerde eindresultaat, maar jij hebt er maar 13056.

[ Voor 88% gewijzigd door .oisyn op 14-12-2022 11:35 ]

[Janoz]

Voor de vingeroefening dan toch ook maar eens even de grote sets door mijn oplossing heen gegooid. Part 1 krijg ik uiteraard een stack overflow dus die negeer ik . Bij part 2 zie ik heel raar gedrag wat ik ook al bij de originele oplossing zag. Als ik alleen deel 1 doe is dat een stuk langzamer dan wanneer ik beiden tegelijk doe, terwijl ik in de tweede situatie meer doe. Zelfs als ik de declaratie van Package buiten de loop haal is deel 1 langzamer.

spoiler:

Part 1: 226645370
In 475ms
Part 2: 37225275
In 1688ms
Part 1: 226645370
Part 2: 801677840
In 347ms

[.oisyn]

@Janoz En draai het nu eens om, dus eerst both, daarna part1 en part2?

(Btw, frappant dat het woord "packet" bij jou "package" is geworden )

[Janoz]

Dan lijken ze meer op elkaar inderdaad. Zal wel wat JIT-shizzle zijn....

[Diderikdm]

Pfoe, vandaag in eerste instantie voor een brute-force aanpak gegaan. Werkte prima, maar runde in ~9s. Nu aangepast naar

spoiler:

Queue system welke voorgaande zand-hits (y - 1) bijhoudt en het eerste nog niet-zand-coord pakt om verder te gaan met berekenen

Nu beide parts in 290ms. Prima voor nu

Dag 14 - Python

[MatHack]

Dag 14 in C#

Part1 in 20,1578ms
Part2 in 308,2288ms

Dat is volledige simulatie van het zand (en 2x parsen, etc., want dat doe ik voor elk deel)

spoiler:

Aanpassing voor deel 2 was relatief simpel, puur een paar aanpassingen aan de grid afmetingen + een nieuwe rockformation of de onderste row.

[ Voor 6% gewijzigd door MatHack op 14-12-2022 12:22 ]

[CMG]

.oisyn schreef op woensdag 14 december 2022 @ 11:24:
@CMG Je part-2 antwoorden kloppen niet. Oh dat zei je al

spoiler:

van large-1 part-2 zijn gek genoeg de digits precies omgedraaid, maar dat lijkt me louter toeval?

Wat betreft:

[...]

Het maakt voor part-1 weldegelijk een verschil. Gevraagd wordt om de indices op te tellen van de paren die in de juiste volgorde staan. Als ze equivalent zijn dan is de volgorde juist. Door iets anders te doen (bijvoorbeeld door string-lengte te vergelijken) kan het zijn dat je bepaalt dat ze in de verkeerde volgorde staan, waardoor het uiteindelijke antwoord niet juist is.

Voor part-2 zal het geen verschil maken.

.edit: zit net naar je sorted resultaten te kijken. Het valt me op dat je heel wat regels mist. Large-1 heeft 900 regels, oftewel 300 paren, dus ik verwacht 602 regels in je gesorteerde eindresultaat, maar jij hebt er maar 304. Large-2 heeft 90.000 regels, oftewel 30.000 paren, dus ik verwacht 60.002 regels in je gesorteerde eindresultaat, maar jij hebt er maar 13056.

Ik gebruik .Union() om 2 extra regels toe te voegen; dat stript ook meteen de duplicates er uit 🤣Zoals gezegd; de originele input heeft dat soort dingen niet; elke input is anders.

En wat betreft geldigheid: als er geen a < b optreed, wordt het niet als geldig gezien, maar zonder antwoord als je de regels leest 😅 pas als er een verschil is, krijg je true/false, anders is het: 'check het volgende', dus het betreft hier je eigen interpretatie van de regels (net zoals ik er een heb gemaakt omdat het niet gedefinieerd is) 😅

[.oisyn]

CMG schreef op woensdag 14 december 2022 @ 12:22:
Zoals gezegd; de originele input heeft dat soort dingen niet; elke input is anders.

Maar dan ga je wel een brug te ver. De regels stellen misschien niet wat er moet gebeuren bij equivalente paren, maar die comparison stopt bij louter die paren. Wat jij met je sort vervolgens doet is elke regel met potentieel elke andere regel vergelijken, terwijl dat helemaal niet hoeft, aangezien je alleen maar geinteresserd bent in de plek van [[2]] en [[6]] (oftewel, hoeveel regels voor [[2]] staan, niet wat de onderlinge volgorde van die regels is).

(.edit: en ik heb het ook even gecheckt, in geen van @Soultaker's inputs zijn er paren waarbij de twee delen equivalent zijn. Je creëert dus vooral zelf een probleem waar die er niet is . Dat maakt de argumentatie hieronder dan ook meteen irrelevant voor de oplossing van de puzzel.)

En wat betreft geldigheid: als er geen a < b optreed, wordt het niet als geldig gezien, maar zonder antwoord als je de regels leest 😅 pas als er een verschil is, krijg je true/false, anders is het: 'check het volgende', dus het betreft hier je eigen interpretatie van de regels

Dat ditgedrukte verzin je zelf, dat staat er helemaal niet bij

Uiteindelijk is de vraag:

Determine which pairs of packets are already in the right order. What is the sum of the indices of those pairs?

Over het algemeen is het zo, dat als a niet voor b komt, en b niet voor a, dan zijn ze equivalent. Vandaar dat je ook alleen maar een < hoeft te definieren om ook dingen als == en != te krijgen. En als ze equivalent zijn, dan is er geen verkeerde volgorde. Dat is geen vreemde interpretatie van de regels .

[ Voor 7% gewijzigd door .oisyn op 14-12-2022 12:37 ]

[CMG]

.oisyn schreef op woensdag 14 december 2022 @ 12:31:
[...]

Maar dan ga je wel een brug te ver. De regels stellen misschien niet wat er moet gebeuren bij equivalente paren, maar die comparison stopt bij louter die paren. Wat jij met je sort vervolgens doet is elke regel met potentieel elke andere regel vergelijken, terwijl dat helemaal niet hoeft, aangezien je alleen maar geinteresserd bent in de plek van [[2]] en [[6]] (oftewel, hoeveel regels voor [[2]] staan, niet wat de onderlinge volgorde van die regels is).

(.edit: en ik heb het ook even gecheckt, in geen van @Soultaker's inputs zijn er paren waarbij de twee delen equivalent zijn. Je creëert dus vooral zelf een probleem waar die er niet is . Dat maakt de argumentatie hieronder dan ook meteen irrelevant voor de oplossing van de puzzel.)


[...]

Dat ditgedrukte verzin je zelf, dat staat er helemaal niet bij

Uiteindelijk is de vraag:

[...]

Over het algemeen is het zo, dat als a niet voor b komt, en b niet voor a, dan zijn ze equivalent. Vandaar dat je ook alleen maar een < hoeft te definieren om ook dingen als == en != te krijgen. En als ze equivalent zijn, dan is er geen verkeerde volgorde. Dat is geen vreemde interpretatie van de regels .

Paren maken komt pas daarna bij mij, maar moet idd gewoon Concat ipv union doen.

Wat ik doe is het deterministisch maken; als er een verschil aan te wijzen is; dat te doen; anders is a,b even geldig als b,a en kun je dan zeggen dat ze goed staan als de omgekeerde input zegt dat ze ook goed staan?

De vraag is, is !false als je klaar bent in dit geval true of unknown 😅 zeker omdat sort gewoon die 3 statussen ondersteund.

[torx]

Ik kon het niet laten om een visualisatie te maken

[.oisyn]

CMG schreef op woensdag 14 december 2022 @ 12:49:
Wat ik doe is het deterministisch maken; als er een verschil aan te wijzen is; dat te doen; anders is a,b even geldig als b,a en kun je dan zeggen dat ze goed staan als de omgekeerde input zegt dat ze ook goed staan?

Wat ik al in mijn edit zei, het is niet een case die voorkomt in Soultaker's input dus het is irrelevant

[CMG]

torx schreef op woensdag 14 december 2022 @ 12:51:
Ik kon het niet laten om een visualisatie te maken
[Afbeelding]

Grappig; eigenlijk, als ik het zo bekijk is het gewoon een raycast 😅 ik twijfel of ik dat niet meteen zo ga doen in een kleine rewrite 😅

[CMG]

.oisyn schreef op woensdag 14 december 2022 @ 12:57:
[...]


Wat ik al in mijn edit zei, het is niet een case die voorkomt in Soultaker's input dus het is irrelevant

Wel voor deel 2 als je alle losse regels op een hoop gooit

[.oisyn]

CMG schreef op woensdag 14 december 2022 @ 12:57:
[...]

Wel voor deel 2 als je alle losse regels op een hoop gooit

Het is niet relevant voor je antwoord . Als C na A en na B komt, dan maakt niet het uit wat de onderlinge volgorde van A en B is als je alleen maar de plek van C wilt weten.

[ Voor 25% gewijzigd door .oisyn op 14-12-2022 12:59 ]

[_mike_]

Rust

Op de naieve manier, maar snel genoeg lijkt me:

day-14: regolith-reservoir
day-14: parsing: 134.444µs
day-14: part1: 151.057µs
day-14: part2: 5.822701ms
day-14: finishing: 11.053µs
day-14: total: 6.120005ms

[CMG]

.oisyn schreef op woensdag 14 december 2022 @ 12:58:
[...]


Het is niet relevant voor je antwoord . Als C na A en na B komt, dan maakt niet het uit wat de onderlinge volgorde van A en B is als je alleen maar de plek van C wilt weten.

Ah zo, nu begrijp ik wat je bedoeld 😊

[CMG]

Code aangepast en nog eens gerund, nu krijg ik wel de zelfde waardes 😊

spoiler:

22673
80802
Code runtime: 00:00:04.1800599

226645370
801677840
Code runtime: 00:00:06.2076882

[gedonie]

Dag 14 was weer een leuke puzzel in Java.

spoiler:

Heb voor deel 2 wel een redelijke simpele oplossing gevonden door een driehoekberekening. Dan weet ik exact hoeveel geblokkeerde blokken ik links en rechts van het val punt (500) op de bodem (max Y van alle punten + 2) moet neerleggen om het zand te blokkeren bij de bodem.

[deboder]

En hier mijn Viz met 'blur' en 'bloom' shader

[P_Tingen]

gedonie schreef op woensdag 14 december 2022 @ 13:36:
Dag 14 was weer een leuke puzzel in Java.

spoiler:

Heb voor deel 2 wel een redelijke simpele oplossing gevonden door een driehoekberekening. Dan weet ik exact hoeveel geblokkeerde blokken ik links en rechts van het val punt (500) op de bodem (max Y van alle punten + 2) moet neerleggen om het zand te blokkeren bij de bodem.

spoiler:

Ik leg juist maar drie extra punten; zodra ik zie dat mijn zandkorrel de vloer gaat raken, leg ik er snel op de posities recht onder de zandkorrel en links en rechts daarvan een extra stukje vloer. En dan nog alleen als ze er al niet zijn uiteraard.

https://github.com/patric...ster/2022/Day-14/day-14.p
Regel 57-63. Wel Progress 4GL maar ik denk goed leesbaar voor niet-progressologen

[Janoz]

@gedonie @P_Tingen wat een gedoe met de vloer

spoiler:

ik stop gewoon wanneer het zand laag genoeg is

[corbosman]

14 met php

spoiler:

recursion

spoiler:

part1 en 2 kunnen tegelijk, als je op de juiste diepte bent record je zandkorrels voor deel 1

[ Voor 27% gewijzigd door corbosman op 14-12-2022 16:12 ]

[Soultaker]

.oisyn schreef op woensdag 14 december 2022 @ 01:58:
Part2 toegevoegd, de tijden worden niet significant anders (komt vooral omdat die dividers zo kort zijn dat je het antwoord al na een paar checks weet)

Ha, ik ben toch sneller op mijn “trage” CPU! (code)

$ ./solve < ../testdata/13.in 
6272
22288
Time: 24 us

$ ./solve < ../extradata/aoc_2022_day13_large-1.txt 
22673
80802
Time: 27568 us

$ ./solve < ../extradata/aoc_2022_day13_large-2.txt 
226645370
801677840
Time: 15507 us

Het idee is om

spoiler:

de strings al tijdens het parsen te vergelijken. Daardoor heb je slechts O(1) geheugen nodig (zelfs geen stack space, in mijn implementatie), en kun je het in praktisch sublineaire tijd oplossen, al heb ik strict genomen nog wel O(N) tijd nodig om de regeleindes te vinden in de invoer.

Ik vind het wel leuk om te zien hoeveel orden-van-grootte je dit soort problemen vaak nog kunt optimaliseren M'n huidige code is nog steeds verre van optimaal.

[corbosman]

.oisyn schreef op woensdag 14 december 2022 @ 02:06:
[...]


Wel gek, ik zie niet in hoe je hierme data die incompatible is met json kan genereren. Weet je waar de fout zit?
Misschien is de nesting gewoon te diep

nee de nesting mag vrijwel oneindig dus dat is het niet. Geen idee, het is ook te groot om even na te lopen met de hand.

[.oisyn]

corbosman schreef op woensdag 14 december 2022 @ 16:21:
[...]


nee de nesting mag vrijwel oneindig dus dat is het niet. Geen idee, het is ook te groot om even na te lopen met de hand.

Ja, het mág wel oneindig, maar wellicht dat je parser het gewoon niet trekt

[.oisyn]

Soultaker schreef op woensdag 14 december 2022 @ 16:17:
[...]


Ha, ik ben toch sneller op mijn “trage” CPU! (code)

$ ./solve < ../testdata/13.in 
6272
22288
Time: 24 us

$ ./solve < ../extradata/aoc_2022_day13_large-1.txt 
22673
80802
Time: 27531 us

$ ./solve < ../extradata/aoc_2022_day13_large-2.txt 
226645370
801677840
Time: 19513 us

Het idee is om

spoiler:

de strings al tijdens het parsen te vergelijken. Daardoor heb je slechts O(1) geheugen nodig (zelfs geen stack space, in mijn implementatie), en kun je het in praktisch sublineaire tijd oplossen, al heb ik strict genomen nog wel O(N) tijd nodig om de regeleindes te vinden in de invoer.

Dat doe ik allang

[corbosman]

.oisyn schreef op woensdag 14 december 2022 @ 16:22:
[...]

Ja, het mág wel oneindig, maar wellicht dat je parser het gewoon niet trekt

Lijkt me sterk, da's gewoon de default php json decoder. Als daar een bug in zat was dat denk ik wel bekend. En ZO enorm groot is het nou ook weer niet. De decoder kan tot 2147483647 nested depth. Het is ook echt een invalid json exception ipv een depth exception.

Cor

[.oisyn]

corbosman schreef op woensdag 14 december 2022 @ 16:37:
[...]


En ZO enorm groot is het nou ook weer niet. De decoder kan tot 2147483647 nested depth. Het is ook echt een invalid json exception ipv een depth exception.

Ah ok, dat is gewoon gedefinieerd. De exception geeft dus ook niet aan waar de fout zit? Wel raar.

[corbosman]

Ik heb even een online json validator gepakt en die zegt dit, maar geen idee of dat klopt want ik weet niet wat die precies doet. Een 2e zegt hetzelfde.