Advent of Code 2021

[Dricus]

Zo, na 4 iteraties ben ik nu aanbeland bij een versie van dag 4 die ik best goed leesbaar vind. Ook de performance van Clojure valt niet tegen voor mijn gevoel, maar ik heb ook niet echt iets om het mee te vergelijken.

Ik meet de performance van I/O, het parsen van de input en de algoritmes voor deel 1 en 2 los van elkaar, om een beetje inzicht te krijgen in hoe de tijd daartussen verdeeld is.

Puzzle 2021-04 [I/O: 2,426 ms | Parse: 3,327 ms | Part 1: 30,597 ms | Part 2: 47,594 ms]

Zijn er anderen die ook dit soort metingen doen?

[dcm360]

Optimaliseren is op zich wel leuk, maar met puzzels van deze grootte vaak niet zo nodig. Op de invoer van vandaag doet mijn oplossing 100ms over het parsen, 40ms over deel 1 en 26ms over deel 2 (iets met een JVM die er voor zorgt dat deel 2 vaak een voorsprongetje krijgt als ik iets van deel 1 hergebruik. Voer ik beide oplossingen nogmaals uit, kom ik uit op 5ms en 10ms). De input van DataGhost levert dan weer een ruime 4 minuten aan rekenwerk op, vooral omdat ik na het trekken van een getal alle kaarten een keer transpose om te kijken of een kolom vol (of in mijn geval: leeg) is.

Cranzai schreef op zaterdag 4 december 2021 @ 16:01:
[...]

De cluster zou het wel enigszins sneller maken door de snellere cores en meer/sneller geheugen neem ik aan?
Om nou direct met OpenACC te gaan werken o.i.d is me ook zo wat

Zou het cluster echt snellere cores en sneller geheugen hebben dan? Vergeleken met consumentenhardware zijn clusters meestal snel vanwege de hoeveelheid cores en geheugenbandbreedte, maar leveren in op kloksnelheid en latency. Voor speelgoedprobleemjes als dit zou ik de voorkeur hebben voor hoge kloksnelheid en lage latency,

[Cranzai]

DataGhost schreef op zaterdag 4 december 2021 @ 16:04:
[...]

Vaak gaat een groot deel al vanzelf als je de juiste datastructuren kiest, die voor het doel wat je beoogt en de operaties die je vaak doet een snelle looptijd hebben. Iets simpels als het verschil tussen een linked list en een normale list is al O(n) voor element access. Op dezelfde manier is

spoiler:

zoeken naar een getal in een array/list O(n) terwijl dat sneller kan met andere structuren

Dan hoef je qua leesbaarheid nog niet eens heel veel in te leveren. Je kan eens een blik werpen op mijn implementatie (dat zijn wel spoilers) en daarna op die van @Soultaker, die weliswaar iets lastiger te lezen is maar nog sneller omdat zijn aanpak nog iets beter/sneller is.

Goed punt, de structuren die jij gebruikt heb ik deels ook of in ieder geval geprobeerd. Lukte alleen niet altijd om het te implementeren door de vorm en de datatypes idd

Classes, zoals jouw oplossing, ben ik niet zo bedreven in. Subroutine achtige dingen zoals de oplossing van Soultaker wat meer, alleen had ik het nog niet zo vernuftig voor elkaar qua logica.

Maar bedankt voor de discussie vandaag, weer wat mooie inzichten gedaan

[ Voor 3% gewijzigd door Cranzai op 04-12-2021 17:10 ]

[DataGhost]

Cranzai schreef op zaterdag 4 december 2021 @ 17:08:
[...]


Goed punt, de structuren die jij gebruikt heb ik deels ook of in ieder geval geprobeerd. Lukte alleen niet altijd om het te implementeren door de vorm en de datatypes idd

Classes, zoals jouw oplossing, ben ik niet zo bedreven in. Subroutine achtige dingen zoals de oplossing van Soultaker wat meer, alleen had ik het nog niet zo vernuftig voor elkaar qua logica.

Oh het kan allebei hoor. Classes zijn alleen vaak een manier om bij elkaar horende logica en data bij elkaar te houden. In principe kan je alles omschrijven naar functies, in Python is het ook niet meer dan dat. Het is zelfs behoorlijk expliciet in Python te zien, aangezien het eerste argument van een class function (a.k.a. method) altijd "self" is. Dus object.functie() is dezelfde aanroep als klasse.functie(object), waarbij je object zou kunnen zien als gewoon een dictionary met wat data erin. Uiteindelijk is het niet heel spannend maar als je er nog nooit mee gewerkt hebt moet je dat beeld even correct in je hoofd zien te krijgen.
Zo zou je in de code van Soultaker het een en ander om kunnen schrijven zodat bijv. row_left[i][c] iets wordt als i.row_left[c] waarbij i dan een bingokaart-object is. De logica die nu in zijn hoofdcode staat kan dan verplaatsen naar binnen de bingokaart-klasse, waardoor je bijv. ook tegelijkertijd een ander soort bingokaarten zou kunnen gebruiken (dwars door elkaar zelfs) zonder dat je de hoofdcode aan hoeft te passen, mocht dat ooit een logische toepassing hebben. Bijvoorbeeld als je een andere speler een 6x6-bingokaart geeft met 11 vakjes al afgestreept.

[EfBe]

DataGhost schreef op zaterdag 4 december 2021 @ 12:32:
[...]

Ik heb wat testinvoer gemaakt voor deel twee, met

spoiler:

grotere bingokaarten, deze zijn 100x100. Deel 2 met deze kaarten duurt bij mij zo'n 4 seconden (Python, in een VM op een 11 jaar oude laptop) met als antwoord 3074334900. Ik ben benieuwd hoe snel dat bij jou gaat dan, als je daar zin in hebt

https://sigyn.dataghost.com/aoc/2021/aoc-2021-day3-part2.txt

Mijn code is binnen de seconde klaar, maar wel met een verkeerd antwoord (-1220632396). Had een int overflow. Nadat ik de nodige code naar long's had geconverteerd werkt het nu. .NET 6 release build, met file laden/parsen heeft mijn oplossing 318ms nodig Dat is sneller dan ik had verwacht

[DataGhost]

EfBe schreef op zaterdag 4 december 2021 @ 17:23:
[...]

Mijn code is binnen de seconde klaar, maar wel met een verkeerd antwoord (-1220632396). Had een int overflow. Nadat ik de nodige code naar long's had geconverteerd werkt het nu. .NET 6 release build, met file laden/parsen heeft mijn oplossing 318ms nodig Dat is sneller dan ik had verwacht

Alvast graag gedaan voor de onvermijdelijke keer dat je daar anders nog tegenaan ging lopen deze maand

[Janoz]

DataGhost schreef op zaterdag 4 december 2021 @ 12:32:
[...]

Ik heb wat testinvoer gemaakt voor deel twee, met

spoiler:

grotere bingokaarten, deze zijn 100x100. Deel 2 met deze kaarten duurt bij mij zo'n 4 seconden (Python, in een VM op een 11 jaar oude laptop) met als antwoord 3074334900. Ik ben benieuwd hoe snel dat bij jou gaat dan, als je daar zin in hebt

https://sigyn.dataghost.com/aoc/2021/aoc-2021-day3-part2.txt

Mijn implementatie doet deze in 182ms, en dan heeft hij A en B berekend

[Kazu]

DataGhost schreef op zaterdag 4 december 2021 @ 14:47:
[...]

Hm, gek. Ik kon ook niet direct vinden waarom jouw uitkomst niet klopte. Met wat simpele aanpassingen aan je magic numbers (in revisie g3929193) komt er bij mij nog een andere (wederom verkeerde) uitkomst uit, namelijk 3098648098 na 25 seconden. Dus dat is zo mogelijk nog vreemder

Het is wel duidelijk, I need to step up my game Mijn oplossing voor vandaag is redelijk sloppy en super inefficient, had gewoon even de tijd moeten nemen om eerder na te denken over een betere oplossing

[ShitHappens]

Good, day 4 herschreven om met de meermaals aangehaalde "grote" input om te kunnen gaan.

spoiler:

Was compleet de skip() en limit() van Stream vergeten

Ben jaloers op de programmeersels die voor part 1 in luttele (sub)second resultaat geven, dat gaat 'm niet worden hier

[TrailBlazer]

ben best wel trots op mijn Python baksel uiteindelijk. Voor het eerst met Numpy en matrixen gewerkt

spoiler:

achteraf had ik geen aparte matrix voor de hits hoeven te maken maar had ik gewoon de waardes van de gevonden posities op nul moeten zetten. Als er dan een kolom of rij 0 was geweest was dat ook voldoende geweest.

Als er iemand wat commentaar wil leveren graag

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[ShitHappens]

TrailBlazer schreef op zaterdag 4 december 2021 @ 20:55:

spoiler:

achteraf had ik geen aparte matrix voor de hits hoeven te maken maar had ik gewoon de waardes van de gevonden posities op nul moeten zetten. Als er dan een kolom of rij 0 was geweest was dat ook voldoende geweest.

spoiler:

Relatief gevaarlijke aanname, ik had in m'n te trekken nummers en in de kaarten daadwerkelijke nullen zitten. Dus misschien werkt je oplossing wel met jouw input, maar niet met alle?

Alhoewel... Net jouw code uitgevoerd met mijn input en loopt gewoon netjes. Dus om één of andere reden loopt 't toch goed

[ Voor 10% gewijzigd door ShitHappens op 04-12-2021 21:09 ]

[Cranzai]

ShitHappens schreef op zaterdag 4 december 2021 @ 20:58:
[...]

spoiler:

Relatief gevaarlijke aanname, ik had in m'n te trekken nummers en in de kaarten daadwerkelijke nullen zitten. Dus misschien werkt je oplossing wel met jouw input, maar niet met alle?

spoiler:

Inderdaad, zo'n set had ik ook.
Mooiste is denk ik gwn deleties toepassen en dan lege rijen/kolommen checken.

[TrailBlazer]

ShitHappens schreef op zaterdag 4 december 2021 @ 20:58:
[...]

spoiler:

Relatief gevaarlijke aanname, ik had in m'n te trekken nummers en in de kaarten daadwerkelijke nullen zitten. Dus misschien werkt je oplossing wel met jouw input, maar niet met alle?

spoiler:

ik zie inderdaad ook kaarten met 0 in mijn input zitten dan is mijn methode van een aparte matrix voor de hits zo slecht nog niet idd

[martyw]

Heb de hitstate in de bingokaart opgenomen, mijn versie draait in ~40ms op mijn core i5-11500@Ubuntu 21.10 (Python 3.9.7)
https://github.com/martyw/AOC2021/blob/main/day4.py

[ Voor 4% gewijzigd door martyw op 04-12-2021 21:26 ]

[DataGhost]

TrailBlazer schreef op zaterdag 4 december 2021 @ 20:55:
ben best wel trots op mijn Python baksel uiteindelijk. Voor het eerst met Numpy en matrixen gewerkt

Als er iemand wat commentaar wil leveren graag

Algemene tip, niet alleen voor jou maar ook voor anderen: probeer magic numbers en "magic/copypaste code" (bijv. wat je op regel 10 doet) te vermijden. Als het echt moet is het beter om constanten te gebruiken zodat je die op 1 plek in je code kan wijzigen, mocht deel 2 van een opdracht daar aanleiding toe geven. Dat is niet alleen makkelijker maar zorgt er ook voor dat je minder fouten kan maken bij het aanpassen. Liefst bepaal je dat soort dingen automatisch aan de hand van de input, waar dat logisch is. Er zullen vast opdrachten komen waarbij dit een issue gaat opleveren.

[Reptile209]

Pfff... onnodig lang bezig geweest met deel twee. Deel 1 had ik vrij snel in elkaar geprutst in PHP. Deel twee wilde maar niet lukken, ook niet op basis van het voorbeeld. Bleek dat ik een uur over een typo in een variabelenaam heb zitten turen, in de check op een kolom-bingo. Die deed helemaal niets want $card bestond wel, maar $cards niet, dus ik zat braaf een null-variabele te checken. PHP vond het allemaal best. En in deel 1 kwam ik daar blijkbaar mee weg, maar in deel twee dus niet...

Nu maar even

PHP:

ini_set('display_errors', 1);
error_reporting(E_ALL);

in mijn standaard template toegevoegd. Vorige jaren nooit last van gehad (en verder doe ik niet veel met PHP hier), dus zal wel een update zijn geweest die het standaard onderdrukt in de output...

[TrailBlazer]

DataGhost schreef op zaterdag 4 december 2021 @ 21:34:
[...]


Algemene tip, niet alleen voor jou maar ook voor anderen: probeer magic numbers en "magic/copypaste code" (bijv. wat je op regel 10 doet) te vermijden. Als het echt moet is het beter om constanten te gebruiken zodat je die op 1 plek in je code kan wijzigen, mocht deel 2 van een opdracht daar aanleiding toe geven. Dat is niet alleen makkelijker maar zorgt er ook voor dat je minder fouten kan maken bij het aanpassen. Liefst bepaal je dat soort dingen automatisch aan de hand van de input, waar dat logisch is. Er zullen vast opdrachten komen waarbij dit een issue gaat opleveren.

je bedoelt dat het beter zo kan dus in plaats van die afmeting van die matches matrix te hard coden het zo op te lossen.

Python:

class Bingo:

    def __init__(self,card_data):
        self.card = np.array(card_data)
        self.shape = self.card.shape
        #self.matches = np.array([[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]])
        #self.matches = np.array([[0 for i in range(0,self.shape[1])] for j in range(0,self.shape[0])])
        self.matches = np.full(self.shape,0)
        self.card_won = False

[ Voor 1% gewijzigd door TrailBlazer op 04-12-2021 22:23 . Reden: np.full is veel makkelijker ]

[keeperson]

TrailBlazer schreef op zaterdag 4 december 2021 @ 22:19:
[...]


je bedoelt dat het beter zo kan dus in plaats van die afmeting van die matches matrix te hard coden het zo op te lossen.

Python:

class Bingo:

    def __init__(self,card_data):
        self.card = np.array(card_data)
        self.shape = self.card.shape
        #self.matches = np.array([[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]])
        #self.matches = np.array([[0 for i in range(0,self.shape[1])] for j in range(0,self.shape[0])])
        self.matches = np.full(self.shape,0)
        self.card_won = False

Waar ik denk dat @DataGhost op doelt is dat je die bingokaart beter kan initialiseren met iets als BINGO_CARD_DEFAULT_STATE. Dan is het voor de lezer duidelijk wat er gaande is. Nu moet jouw opvolger in de toekomst gaan gokken wat je in godesnaam zou bedoelen. Beetje hetzelfde met het gebruik van het getal pi.

[martyw]

martyw schreef op zaterdag 4 december 2021 @ 21:16:
Heb de hitstate in de bingokaart opgenomen, mijn versie draait in ~40ms op mijn core i5-11500@Ubuntu 21.10 (Python 3.9.7)
https://github.com/martyw/AOC2021/blob/main/day4.py

Nog wat gerefactored, zit nu op 29 ms

[YoToP]

@martyw jouw code doet er bij mij 36 ms(3800XT@Manjaro) over. (part 1+ part 2)
Ik blijf haken op ~46ms(alleen part 2).. matig dus. en de 100x100 van DataGhost duurt 36 minuten.. oeps
Mooi voor vandaag, morgen weer een dag !

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/4/p2.py

[martyw]

YoToP schreef op zaterdag 4 december 2021 @ 23:18:
@martyw jouw code doet er bij mij 36 ms(3800XT@Manjaro) over. (part 1+ part 2)
Ik blijf haken op ~46ms(alleen part 2).. matig dus. en de 100x100 van DataGhost duurt 36 minuten.. oeps
Mooi voor vandaag, morgen weer een dag !

spoiler:

https://github.com/YoToP/AoC-2021/blob/main/4/p2.py

Python is single threaded, en mijn i5 is daarin rapper dan jouw Ryzen: https://www.cpubenchmark....Intel-i5-11500/3797vs4238, maar als we nog wat puzzels gaan krijgen waar je ze over de cores kan verdelen win je!
Ook is het wel raadzaam wat te leren over list comprehensions, laat de taal voor je werken in plaats van dat je het zelf doet!

[ Voor 14% gewijzigd door martyw op 04-12-2021 23:37 ]

[vandeGerrit]

Varienaja schreef op zaterdag 4 december 2021 @ 15:28:
[...]
Mijn oplossing doet 400ms over jouw 100x100 invoer.
[...]
Bij mijn weten simuleer ik het hele spel en dat duurt echt niet lang.
[...]

Idem hier, ik zit op 299ms, en simuleer het hele spel.

spoiler:

Je hoeft niet continue alle score kaarten langs om op bingo te controleren. Is er geen getal gewijzigd, is er ook in die ronde geen bingo. Daarnaast hoef je ook niet alle kolommen en rijen te controleren, enkel degene met een gemarkeerd getal.

[Janoz]

Meeste winst blijf je halen door je algoritme goed te kiezen. Je hoeft niet het hele spel te simuleren. Het is niet voor niks dat de getrokken getallen voor de borden komen. Bij het inlezen weet ik al in welke beurt het bord bingo gaat krijgen. Het uiteindelijke antwoord is dan gewoon de kleinste en de grootste bijhouden tijdens het inlezen. Het speel algoritme heeft een complexiteit van orde MxN waarbij er M getrokken getallen zijn en N borden. Mijn algoritme is orde N.

https://github.com/Janoz-.../com/janoz/aoc/y2021/day4

Binnen 200ms los ik de 100x100 dataset van @DataGhost op.

[DataGhost]

keeperson schreef op zaterdag 4 december 2021 @ 22:26:
[...]


Waar ik denk dat @DataGhost op doelt is dat je die bingokaart beter kan initialiseren met iets als BINGO_CARD_DEFAULT_STATE. Dan is het voor de lezer duidelijk wat er gaande is. Nu moet jouw opvolger in de toekomst gaan gokken wat je in godesnaam zou bedoelen. Beetje hetzelfde met het gebruik van het getal pi.

Dat bedoelde ik juist niet voor die regel of in ieder geval niet helemaal op die manier. De afmeting van de kaart kan je bijv. een constante van maken zodat je bij het initialiseren van het bord een bord met daadwerkelijk die grootte kan maken. Als je bijv. in je source gaat zoeken naar "5" om te vervangen met "6" ofzo, zie je natuurlijk iets als "[0,0,0,0,0]" gauw over het hoofd wat later in je programma allemaal gekke "ongerelateerde" problemen kan geven. Als je ergens "AFMETING=5" hebt en dan bijv. "[0 for i in range(AFMETING)]" gebruikt, gaat die ook vanzelf mee goed.

[DataGhost]

TrailBlazer schreef op zaterdag 4 december 2021 @ 22:19:
[...]


je bedoelt dat het beter zo kan dus in plaats van die afmeting van die matches matrix te hard coden het zo op te lossen.
[..]

Ik heb numpy nooit gebruikt maar als die vanzelf een vierkante matrix met de juiste afmetingen maakt adhv de lijst getallen die je erin stopt, dan ja, dat is precies wat ik bedoel.

[Rogier V]

Opgelost!
https://github.com/rogier...er/AOC2021/Day04/Day04.fs

Heb relatief lang aan deel 1 gezeten om kennis te krijgen van Array2d in F#. Ook het parsen naar een matrix ging niet van een leien dak. Deel 2 had ik binnen een minuut opgelost door

spoiler:

List.MinBy met een List.MaxBy te vervangen

.

[Varienaja]

Wat weer een gepriegel :-D

spoiler:

Goh, kunnen lijnen ook van hoge coordinaten naar lage gedefinieerd zijn?

En ik dacht dat ik voor onderdeel B alleen maar de if x1==x2 || y1==y2 moest weghalen, maar mijn code was toch nog lang niet voorbereid op diagonalen.

Alstublieft: https://github.com/varien...tofcode2021/Puzzle05.java

[Woy]

Deze was voor mij erg makkelijk. Er zou nog wel iets geoptimaliseerd kunnen worden, maar dat is totaal niet nodig, en ben wel tevreden over de code. Deel 2 was een eitje

https://github.com/rverst.../blob/main/Y2021/Day05.cs

[Dricus]

Dag 5 in Clojure

Deze was onverwachts makkeljk.

spoiler:

Ik was al bezig om code te schrijven om het diagram zoals in de omschrijving getoond op te gaan bouwen. Daarvoor had ik een lijst nodig met alle punten die gedekt worden door elke lijn. Toen ik die eenmaal had, bedacht ik dat ik ook gewoon kan kijken hoe vaak elk punt in die lijst voorkomt .

Deel 2 was super makkelijk, omdat ik in deel 1 al rekening gehouden had met diagonale lijnen van 45 graden. Voor deel 1 had ik al alle diagonale lijnen uit de input gefilterd. Voor deel 2 was de enige wijziging dat ik dat filteren niet meer hoefde te doen.

[Caelorum]

Rogier V schreef op zondag 5 december 2021 @ 01:02:
Opgelost!
https://github.com/rogier...er/AOC2021/Day04/Day04.fs

Heb relatief lang aan deel 1 gezeten om kennis te krijgen van Array2d in F#. Ook het parsen naar een matrix ging niet van een leien dak. Deel 2 had ik binnen een minuut opgelost door

spoiler:

List.MinBy met een List.MaxBy te vervangen

.

Een mooiere oplossing dan die van mij :-)
Ik ga deze vandaag of morgen nog even aanpassen, want er zitten net iets teveel while-loopjes en mutable in. (en een seq met seq.head opddeze manier gebuiken is gewoon ranzig). Eens kijken of ik een early return kan fabriceren met takewhile. https://github.com/ajeckm...ob/master/Puzzles/day4.fs.

[armageddon_2k1]

Dag 5 in Kotlin

Was weer goed te doen. Ik hou er altijd van om het mooi te maken met wat helpers die ik nog had van vorige edities (zoals Alignment en ranges tussen twee points). Dan is het meteen een eitje en wordt de code lekker clean.

[Hydra]

En dag 5 in Kotlin

Heel veel code-reuse hier. Most alleen wel een angle functie fixen want die was stuk Uiteindelijk wel in m'n nopjes met hoe simpel de code eigenlijk is.

[ZieglerNichols]

Dag 5 in MATLAB.

Altijd weer een gedoe met 1-based indexing

[Woy]

Hydra schreef op zondag 5 december 2021 @ 09:18:
En dag 5 in Kotlin

Heel veel code-reuse hier. Most alleen wel een angle functie fixen want die was stuk Uiteindelijk wel in m'n nopjes met hoe simpel de code eigenlijk is.

Jouw util functie voor regex parsing is wel elegant, dat moet ik ook maar eens toevoegen, maakt het parsen een stuk duidelijker.

[DataGhost]

Hm, voor een opdracht in het weekend had ik 'm iets complexer verwacht, maar goed In ieder geval weer eens een generator gebruikt, die maak ik niet heel vaak.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[coop]

Lekker wakker worden zo op de zondagochtend.
Dag 5 in Python

Deel 1 had ik zo, maar deel 2 was even puzzelen. Uiteindelijk toch wel blij met mijn code.

spoiler:

Door het voorbeeld in deel 2 werd ik op het verkeerde been gezet. Had 1x een fout antwoord nodig voordat ik bedacht dat een diagonaal niet perse met dezelfde indices is. [0,0]->[8,8], maar ook [6,4]->[2,0].

[Remcoder]

En ook klaar, ik vind dat het nog een best elegante oplossing is geworden.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Ik was het meeste tijd kwijt bij deel 2 om uit te werken welke richting de diagonaal op loopt, van linksboven naar rechtsonder, of van linksonder naar rechtsboven. Daarna miste ik nog een math.abs, en had ik nog een off by one error in het tekenen van de diagonaal.

[Mschamp]

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Vandaag viel goed mee. Met de Math.Sign functie in C# was de richting bepalen heel eenvoudig. Functie geeft 0, 1 of -1

[ Voor 38% gewijzigd door Mschamp op 05-12-2021 09:54 ]

[DataGhost]

coop schreef op zondag 5 december 2021 @ 09:48:
Lekker wakker worden zo op de zondagochtend.
Dag 5 in Python

Deel 1 had ik zo, maar deel 2 was even puzzelen. Uiteindelijk toch wel blij met mijn code.

spoiler:

Door het voorbeeld in deel 2 werd ik op het verkeerde been gezet. Had 1x een fout antwoord nodig voordat ik bedacht dat een diagonaal niet perse met dezelfde indices is. [0,0]->[8,8], maar ook [6,4]->[2,0].

Sorry, ik maak graag code van anderen kapot. Daarom vandaag ook weer een heel simpele "upping the ante":

https://sigyn.dataghost.com/aoc/2021/aoc-2021-day5.txt

edit:
Oeps, er zat een typo in, dus als je deze binnen een minuut had binnengehaald even opnieuw downloaden

Antwoorden:

spoiler:

Deel 1: 5
Deel 2: 13

[ Voor 6% gewijzigd door DataGhost op 05-12-2021 10:03 ]

[Woy]

Woy schreef op zondag 5 december 2021 @ 09:31:
[...]

Jouw util functie voor regex parsing is wel elegant, dat moet ik ook maar eens toevoegen, maakt het parsen een stuk duidelijker.

Dit heb ik nu toegevoegd, helaas is het in C# niet zo elegant te doen als in Kotlin, dus heb ik tot 6 groups geimplementeerd met wat code duplication, voor een Utility function wel te overzien.

[Woy]

DataGhost schreef op zondag 5 december 2021 @ 10:01:
[...]

Sorry, ik maak graag code van anderen kapot. Daarom vandaag ook weer een heel simpele "upping the ante":

https://sigyn.dataghost.com/aoc/2021/aoc-2021-day5.txt

edit:
Oeps, er zat een typo in, dus als je deze binnen een minuut had binnengehaald even opnieuw downloaden

Antwoorden:

spoiler:

Deel 1: 5
Deel 2: 13

spoiler:

Zet er dan minstens ook een negatief getal in
Ik moest even mijn datatype aanpassen van int->long, maar verder geen issue. Dat is meestal wel het eerste wat ik bij een opdracht doe, checken welke range de input ( en verwachte output ) ligt om het juiste datatype te kiezen.

[DataGhost]

Woy schreef op zondag 5 december 2021 @ 10:14:
[...]

spoiler:

Zet er dan minstens ook een negatief getal in
Ik moest even mijn datatype aanpassen van int->long, maar verder geen issue. Dat is meestal wel het eerste wat ik bij een opdracht doe, checken welke range de input ( en verwachte output ) ligt om het juiste datatype te kiezen.

Ja dat vond ik een beetje overkill Maar, speciaal voor jou dan, omdat het te makkelijk was
https://sigyn.dataghost.com/aoc/2021/aoc-2021-day5-woy.txt
Antwoorden:

spoiler:

Deel 1: 5
Deel 2: 15

[MrHaas]

Als je echt the ante wil uppen, voeg dan lijnen toe met lengte van > 10**9 zodat je ook heel andere oplossing moet bouwen

[Hydra]

Woy schreef op zondag 5 december 2021 @ 09:31:
Jouw util functie voor regex parsing is wel elegant, dat moet ik ook maar eens toevoegen, maakt het parsen een stuk duidelijker.

Ja, die is ook al best oud. Was er wel klaar me om honderd verschillende splits te hebben in het "lees de input" stukje, en dan is dit toch wel een stuk duidelijker

[Hydra]

Woy schreef op zondag 5 december 2021 @ 10:10:
helaas is het in C# niet zo elegant te doen als in Kotlin

Join the dark side Komrad!

[ Voor 8% gewijzigd door Hydra op 05-12-2021 10:59 ]

[Diderikdm]

Python dag 5

Had eigenlijk verwacht dat we met de onderzeeër door een pad met minste weerstand moesten sturen naar een andere plek, maar die puzzels zullen later wel komen

[ Voor 37% gewijzigd door Diderikdm op 05-12-2021 11:48 ]

[EfBe]

En done https://github.com/FransB.../src/AoC2021.Code/Day5.cs

Geen array gebruikt, maar kan slimmer mbt direction

[gedonie]

Zo dag 5 ook achter de rug in Java.

[Hydra]

gedonie schreef op zondag 5 december 2021 @ 11:48:
Zo dag 5 ook achter de rug in Java.

Grappig dat je voor elke dag een aparte module maakt Wat is de reden daarvoor?

[DataGhost]

MrHaas schreef op zondag 5 december 2021 @ 10:53:
Als je echt the ante wil uppen, voeg dan lijnen toe met lengte van > 10**9 zodat je ook heel andere oplossing moet bouwen

Okee. Ik heb het zelf nog niet gebouwd dus ik heb de uitkomsten met de hand berekend, hopelijk kloppen ze

https://sigyn.dataghost.c...oc-2021-day5-realshit.txt
Antwoorden (denk ik):

spoiler:

Deel 1: 156
Deel 2: 456789012345678901234568052

[gedonie]

Hydra schreef op zondag 5 december 2021 @ 11:58:
[...]


Grappig dat je voor elke dag een aparte module maakt Wat is de reden daarvoor?

Dat ik de opdracht ook nog in andere talen uit wil proberen en zo alles een beetje per dag bij elkaar staat. Buiten dat niet echt een reden.

[MrHaas]

DataGhost schreef op zondag 5 december 2021 @ 12:23:
[...]

Okee. Ik heb het zelf nog niet gebouwd dus ik heb de uitkomsten met de hand berekend, hopelijk kloppen ze

spoiler:

Deze werkt idd niet op de standaard O(m*n) oplossing waar n het aantal lijnen is en m de maximale lengte.
Er is een O(n^2) oplossing mogelijk als je er vanuit gaat dat er geen collineaire lijnen zijn waarbij je van elke 2 lijnen de intersectie bepaalt (in closed-form). Helaas zitten er al collineaire in de sample input dus daar kan je niet vanuit gaan. Je zou iets kunnen verzinnen om die collineaire segmenten apart te behandelen denk ik?

Misschien als ik straks nog tijd heb

[DataGhost]

MrHaas schreef op zondag 5 december 2021 @ 12:36:
[...]

spoiler:

Deze werkt idd niet op de standaard O(m*n) oplossing waar n het aantal lijnen is en m de maximale lengte.
Er is een O(n^2) oplossing mogelijk als je er vanuit gaat dat er geen collineaire lijnen zijn waarbij je van elke 2 lijnen de intersectie bepaalt (in closed-form). Helaas zitten er al collineaire in de sample input dus daar kan je niet vanuit gaan. Je zou iets kunnen verzinnen om die collineaire segmenten apart te behandelen denk ik?

Misschien als ik straks nog tijd heb

Ik heb al een idee en al werkend voor deel 1, maar inderdaad niet sneller dan O(n^2).

[zwippie]

Woy schreef op zondag 5 december 2021 @ 10:10:
[...]

... helaas is het in C# niet zo elegant te doen als in Kotlin ...

Deze opdracht was weer erg fijn om te doen in een functionele taal (ik vrees de latere opdrachten).

Vast subjectief, maar ik vind dit eindresultaat ook best elegant.

spoiler:

Ik gebruik een map met als key een {x, y} coördinaat en als value het aantal lijnstukken dat dit punt kruist. Het bepalen van de coördinaten op een lijnstuk is niet zo ingewikkeld als je ranges kunt gebruiken.

[Creepy]

Zo, eindelijk dag 4 kunnen doen. Ik las hier en daar dat er wat problemen waren met deel 2, maar met mijn oplossing had ik daar geen last van en was effectief meer van hetzelfde.
https://github.com/CodeEn...eer/aoc/aoc2021/Day4.java

Vanmiddag nog dag 5 doen.

[Diderikdm]

MrHaas schreef op zondag 5 december 2021 @ 12:36:
[...]

spoiler:

Deze werkt idd niet op de standaard O(m*n) oplossing waar n het aantal lijnen is en m de maximale lengte.
Er is een O(n^2) oplossing mogelijk als je er vanuit gaat dat er geen collineaire lijnen zijn waarbij je van elke 2 lijnen de intersectie bepaalt (in closed-form). Helaas zitten er al collineaire in de sample input dus daar kan je niet vanuit gaan. Je zou iets kunnen verzinnen om die collineaire segmenten apart te behandelen denk ik?

Misschien als ik straks nog tijd heb

spoiler:

Dit heb ik niet gebruikt in mijn oplossing, maar je zou idd per lijn kunnen checken of de vector gelijk is aan een andere lijn, en de waarde van x (of y) op het nulpunt van de y (of x)-as gelijk is aan elkaar. Vervolgens een check of de hooste/laagste waarde van de een groter/kleiner is dan de kleinste/grootste waarde van de ander voor beide lijnen en vervolgens een min-max berekening van de start-eind coordinaten van beide lijnen (als ze overlap hebben), als je hier voor de andere lijnen de intersectie-coordinaten (als die er zijn) aan toevoegt, hoef je inderdaad vermoedelijk niet de gehele range te computen en werkt dit voor grote getallen voor (x,y) naar waarschijnlijkheid ongeveer even snel als voor kleinere getallen.

[DataGhost]

Diderikdm schreef op zondag 5 december 2021 @ 13:42:
[...]

spoiler:

Dit heb ik niet gebruikt in mijn oplossing, maar je zou idd per lijn kunnen checken of de vector gelijk is aan een andere lijn, en de waarde van x (of y) op het nulpunt van de y (of x)-as gelijk is aan elkaar. Vervolgens een check of de hooste/laagste waarde van de een groter/kleiner is dan de kleinste/grootste waarde van de ander voor beide lijnen en vervolgens een min-max berekening van de start-eind coordinaten van beide lijnen (als ze overlap hebben), als je hier voor de andere lijnen de intersectie-coordinaten (als die er zijn) aan toevoegt, hoef je inderdaad vermoedelijk niet de gehele range te computen en werkt dit voor grote getallen voor (x,y) naar waarschijnlijkheid ongeveer even snel als voor kleinere getallen.

Je vergeet een case die de boel heel erg lelijk maakt en ook al in de testset op AoC zelf voorkomt.

[Diderikdm]

DataGhost schreef op zondag 5 december 2021 @ 13:50:
[...]

Je vergeet een case die de boel heel erg lelijk maakt en ook al in de testset op AoC zelf voorkomt.

Welke case bedoel je hierin? Ik zie m zo snel niet

[DataGhost]

Diderikdm schreef op zondag 5 december 2021 @ 13:56:
[...]


Welke case bedoel je hierin? Ik zie m zo snel niet

spoiler:

Die waar er een drietje staat

[Diderikdm]

DataGhost schreef op zondag 5 december 2021 @ 13:58:
[...]

spoiler:

Die waar er een drietje staat

spoiler:

Ah True.. Al zou je dat wel kunnen afvangen door het gebruik van een set

[DataGhost]

Diderikdm schreef op zondag 5 december 2021 @ 14:02:
[...]

spoiler:

Ah True.. Al zou je dat wel kunnen afvangen door het gebruik van een set

spoiler:

Probeer dat maar eens op de laatste testinvoer die ik gemaakt heb, ik denk dat je geheugen te klein is

[Diderikdm]

DataGhost schreef op zondag 5 december 2021 @ 14:04:
[...]

spoiler:

Probeer dat maar eens op de laatste testinvoer die ik gemaakt heb, ik denk dat je geheugen te klein is

Ik zal het later vandaag/morgen proberen, heb nu geen tijd meer om het te schrijven. Is wel een leuke testcase

[iThinkSo]

Vanochtend (onbedoeld) 6:01 wakker, dus toch maar ff de laptop gepakt en gekeken of ik nog wat punten kon pakken; maar dat viel vies tegen. Wel een leuke opdracht vandaag wat makkelijker dan vorige dagen in mijn beleving

[YoToP]

Dat was een leuke puzzel.
Mijn code deed er eerst 60+ seconden over om een antwoord uit te spugen. Daar mijn sterretjes voor vandaag mee verdiend.

spoiler:

Daarna de Defaultdict geïmplementeerd, dit had ik gezien bij Diderikdm thanks!

Tijd is nu 56 ms.
Eerste input van DataGhost in 1 keer overleefd.
de Sh!t input is nog bezig, zal die er ooit komen? zal het vanavond wel zien.
github dag5 p2

[DevWouter]

DataGhost schreef op zaterdag 4 december 2021 @ 14:39:
[...]

Als het gaat om grote O-notatie van looptijden maakt de omgeving bijna niks meer uit Ik heb een andere oplossing uit dit topic getest op mijn nieuwe input en dat duurde ruim 33 minuten Die van Kazu heb ik moeten aanpassen en die gaf na 25 seconden het verkeerde antwoord, dus dat ligt of aan mij of niet. Met de "verkeerde aanpak" ben je in ieder geval een orde van grootte (of twee) langer bezig en dan gaat geen snelle CPU je helpen. Ook staat in about van AoC dat alle oplossingen maximaal 15 seconden nodig hebben op 10 jaar oude hardware. Bij in ieder geval de wedstrijden waaraan ik heb meegedaan (BAPC en NWERC) was algoritmische complexiteit van zeer groot belang en moest je oplossing eigenlijk binnen een paar seconden eruit komen rollen anders werd 'ie niet goedgerekend.

Oh boy... Ik had ooit een oplossing geschreven die perfect werkte, maar toen we die in productie hadden gezet had die niet de verwachte performance. De hoeveelheid RAM was niet voldoende waar door het OS geheugen ging pagen. En dat realiseerde ik me pas toen we de interne cache op grote 0 zetten. Zonder paging deed het systeem het binnen 45 seconden ipv 900 seconden. Zelfs bij het testen van kleinere oplossing (zonder paging) was het systeem sneller. Les toen was: RAM (en paging) vermijden als je het met de CPU-cache ook kan zelfs al kost het meer CPU cycles.

En recentelijk had ik een algorithme geschreven waarbij ik er van uit ging dat er meerdere cores aanwezig waren. Dat had die wel op acceptatie, maar niet op productie. Dus daarbij laat ik de cache resultaten opslaan in de database. Toen ging de response tijd van 30 seconden terug naar 0.1 seconde.

Wat ik probeer te zeggen is dat de omgeving wel degelijk een grote invloed heeft op wat je schrijft.

Gezien de huidige datasets zeer klein zijn is naiefe oplossing in mijn ogen vaak ook de meest pragmatisch.

Als ik jouw code zo zie (nofi, qua code prima maar qua tijdscomplexiteit ziet het er niet heel snel uit) wil ik je daarom uitdagen om het binnen 15 seconden te laten lopen op welke hardware dan ook Misschien dat je daar wel meer zin van krijgt om het "netjes te maken"

No offense taken. Het netjes maken en optimaliseren doe ik wanneer nodig is. Mijn grootste ergernis is telkens de parser. Daar jeuken mijn handen elke keer.

Edit: hoewel snelle code meestal niet heel netjes/duidelijk is voor een lezer. Maar het kan wel.

Absoluut, maar zoals een beroemde schrijfer ooit zei: Sorry voor deze lange brief, ik had weinig tijd.

[ShitHappens]

Lekker dit.... Part 1 goede oplossing gevonden, maar loop klem op Part 2.

spoiler:

Kom ik er nu net achter, dat volgens het voorbeeld van part 1 het grid er zo uit zou moeten zien:

code:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

spoiler:

Echter ziet dan mijn grid eruit als:

code:

.........2
....1....2
.11.1....2
....2....1
....1....1
....1....1
....1.....
11112.....
....1.....
....1.....

spoiler:

Wat dus alsnog een correct antwoord geeft voor Part 1, maar met de diagnoalen van Part 2 er dusdanig iets fout gaat dat het antwoord niet klopt

[DevWouter]

ShitHappens schreef op zondag 5 december 2021 @ 14:59:
Lekker dit.... Part 1 goede oplossing gevonden, maar loop klem op Part 2.

spoiler:

Kom ik er nu net achter, dat volgens het voorbeeld van part 1 het grid er zo uit zou moeten zien:

code:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

spoiler:

Echter ziet dan mijn grid eruit als:

code:

.........2
....1....2
.11.1....2
....2....1
....1....1
....1....1
....1.....
11112.....
....1.....
....1.....

spoiler:

Wat dus alsnog een correct antwoord geeft voor Part 1, maar met de diagnoalen van Part 2 er dusdanig iets fout gaat dat het antwoord niet klopt

Je grid is 90 graden gedraaid en dat komt omdat je eerst over X loopt en dan over Y loopt. Draai die twee for-loops om en je hebt het goeie resultaat.

[ShitHappens]

Yes na nauwkeuriger vergelijken kwam ik ook tot die ontdekking Is nu opgelost

[armageddon_2k1]

DataGhost schreef op zondag 5 december 2021 @ 12:38:
[...]

Ik heb al een idee en al werkend voor deel 1, maar inderdaad niet sneller dan O(n^2).

Ja, mijnes gaat kapot op jouw upping-the-ante input. Maarja, dat was ook te verwachten

[NickThissen]

Ik doe voor het eerst mee, gekozen voor Julia omdat ik die taal graag wil leren. Bij de eerste paar opdrachten was ik voornamelijk bezig met basis Julia dingen (90% van de tijd in de input lezen, 10% in de oplossing schrijven) maar op dag 5 ging het al een stuk sneller.

Is het normaal dat de input voor part 1 en 2 altijd hetzelfde blijft? Ik had eigenlijk verwacht dat part 2 met een veel moeilijkere input zou komen precies om de simpele "doe maar gewoon bruteforce loop" oplossingen vast te laten lopen. Misschien komt dit later nog? Ik probeer nu in part 1 altijd al iets te doen wat redelijk efficient is maar het blijkt tot nu toe nooit nodig.

[DataGhost]

DevWouter schreef op zondag 5 december 2021 @ 14:58:
[...]


Oh boy... Ik had ooit een oplossing geschreven die perfect werkte, maar toen we die in productie hadden gezet had die niet de verwachte performance. De hoeveelheid RAM was niet voldoende waar door het OS geheugen ging pagen. En dat realiseerde ik me pas toen we de interne cache op grote 0 zetten. Zonder paging deed het systeem het binnen 45 seconden ipv 900 seconden. Zelfs bij het testen van kleinere oplossing (zonder paging) was het systeem sneller. Les toen was: RAM (en paging) vermijden als je het met de CPU-cache ook kan zelfs al kost het meer CPU cycles.

En recentelijk had ik een algorithme geschreven waarbij ik er van uit ging dat er meerdere cores aanwezig waren. Dat had die wel op acceptatie, maar niet op productie. Dus daarbij laat ik de cache resultaten opslaan in de database. Toen ging de response tijd van 30 seconden terug naar 0.1 seconde.

Wat ik probeer te zeggen is dat de omgeving wel degelijk een grote invloed heeft op wat je schrijft.

Gezien de huidige datasets zeer klein zijn is naiefe oplossing in mijn ogen vaak ook de meest pragmatisch.

Caching telt niet. In ieder geval niet bij het redeneren over algoritmische looptijden dmv grote-O notatie. Wat was je oplossing geweest als het uitrekenen van de response bij lege cache 2 jaar had geduurd? Gewoon 2 jaar laten rammelen en het resultaat cachen zodat het er daarna binnen 0.1 seconden eruit komt rollen? Dat verandert verder helemaal niks aan de grote-O performance van het algoritme zelf, en bij een andere input kan je weer opnieuw gaan rekenen. Daarom maakt de omgeving voor het redeneren daarmee helemaal niet uit. Het is geen exacte tijdsduur die ermee wordt aangegeven, maar een verwachting voor hoe de looptijd verhoudingsgewijs toeneemt bij toenemde grootte van input. Maar als je toch graag met absolute tijden werkt, kan je grofweg zeggen dat een O(n²)-algoritme wat 1ms per stap nodig heeft een input van 5x5 in 625ms verwerken, voor een input van 100x100 al 27 uur nodig heeft en 1000x1000 kost 31 jaar. Een O(n)-algoritme is voor 5x5 in 25ms klaar, voor 100x100 in 10 seconden en voor 1000x1000 in iets meer dan een kwartiertje. Cache gaat je hier op geen enkele manier mee helpen. Ook cores niet. O(n²) op 1 core "is O(n²/4)" wat gewoon weer neerkomt op O(n²) want de functie groeit alsnog verhoudingsgewijs even hard. "Dezelfde looptijd" dus.

[ Voor 4% gewijzigd door DataGhost op 05-12-2021 15:37 ]

[Creepy]

En dag 5 ook klaar.
https://github.com/CodeEn...eer/aoc/aoc2021/Day5.java
Ook hier was part 2 redelijk meer van hetzelfde

spoiler:

Straightforward een kaart in het geheugen bijhouden van ints en tellen. Genoeg geheugen voor de zut aangezien de coördinaten niet boven de 1024 uitkwamen

[ Voor 7% gewijzigd door Creepy op 05-12-2021 15:39 ]

[Hydra]

NickThissen schreef op zondag 5 december 2021 @ 15:15:
Is het normaal dat de input voor part 1 en 2 altijd hetzelfde blijft?

Ja, de input is voor beide delen altijd hetzelfde.

[DataGhost]

NickThissen schreef op zondag 5 december 2021 @ 15:15:
Ik doe voor het eerst mee, gekozen voor Julia omdat ik die taal graag wil leren. Bij de eerste paar opdrachten was ik voornamelijk bezig met basis Julia dingen (90% van de tijd in de input lezen, 10% in de oplossing schrijven) maar op dag 5 ging het al een stuk sneller.

Is het normaal dat de input voor part 1 en 2 altijd hetzelfde blijft? Ik had eigenlijk verwacht dat part 2 met een veel moeilijkere input zou komen precies om de simpele "doe maar gewoon bruteforce loop" oplossingen vast te laten lopen. Misschien komt dit later nog? Ik probeer nu in part 1 altijd al iets te doen wat redelijk efficient is maar het blijkt tot nu toe nooit nodig.

Het is nog maar de eerste week. Komende week zal het al wat moeilijker worden en vanaf ongeveer de 10e verwacht ik wel echt opdrachten die algoritmisch pittiger en pittiger worden. Delen 1 en 2 staan dan meestal haaks op elkaar qua oplossingsrichting, terwijl de input hetzelfde blijft. Dat is ook gedaan om het wat laagdrempeliger te houden voor mensen die dit nog nooit gedaan hebben, zo kan je langzaam aan complexere dingen maken en uitzoeken in plaats van dat je in het diepe gegooid wordt met geen flauw idee waar te beginnen.

Ik heb wel wat input gemaakt voor vandaag als je daar zin in hebt, waarbij bruteforcen inderdaad niet gaat lukken.
DataGhost in "Advent of Code 2021"
DataGhost in "Advent of Code 2021"
DataGhost in "Advent of Code 2021"

[ Voor 3% gewijzigd door DataGhost op 05-12-2021 15:46 ]

[Remcoder]

Mijn vriendin begint zich wel alweer te ergeren aan advent of code

Ik zit nu elke ochtend met de laptop op schoot de puzzel op te lossen

Ik ben wel benieuwd hoe lang ik dat vol kan houden, zodra het langer dan 30 minuten gaat kosten moet ik waarschijnlijk later op de dag ruimte gaan reserveren ervoor.

[DataGhost]

Ik zou haar leren programmeren.

[Creepy]

Janoz schreef op zaterdag 4 december 2021 @ 13:48:

spoiler:

Ik heb helemaal niks gemarkt. Zodra ik de trekkingen inlees maak ik ook een lookup tabel zodat ik van elk nummer weet in welke beurt hij getrokken wordt. Tijdens het inlezen schrijf ik vervolgens de posities in een tabel. Door dan het maximum van een rij of kolom te nemen weet ik in welke beurt deze vol is. Neem ik vervolgens het minimum van alle rijen en kolommen dan weet ik in welke beurt dat bord gewonnen heeft.

Score berekening is vervolgens heel simpel. Weer over dat tabelletje heen en overal waar de score hoger is dan de beurt telt hij wel mee.

Zo kan ik elk bord behandelen en kan ik alle borden negeren die niet de eerste of laatste zijn.

Dat is wel een hele elegante oplossing idd.

[MueR]

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Dagje 5 ook af.

[armageddon_2k1]

Remcoder schreef op zondag 5 december 2021 @ 15:52:
Mijn vriendin begint zich wel alweer te ergeren aan advent of code

Ik zit nu elke ochtend met de laptop op schoot de puzzel op te lossen

Ik ben wel benieuwd hoe lang ik dat vol kan houden, zodra het langer dan 30 minuten gaat kosten moet ik waarschijnlijk later op de dag ruimte gaan reserveren ervoor.

Wat ga je dan in de ochtend doen samen en waarom ergert je vriendin zich eraan? Anders investeer je ‘s ochtends eerst even wat tijd (meer dan 5 minuten niet nodig denk ik) in dingen samen doen met haar en als je het goed aanpakt heb je daarna wat tijd voor jezelf.

[Kazu]

Dag 5 was een leuke, en makkelijk te implementeren.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

spoiler:

Mijn oplossing voor de direction in deel 1 ging voor de diagonalen in 2 natuurlijk niet op, dus daar iets meer checks om de direction te bepalen. Maar ik zie hier soortgelijke oplossingen voorbij komen.

[DevWouter]

DataGhost schreef op zondag 5 december 2021 @ 15:16:
[...]

Caching telt niet. In ieder geval niet bij het redeneren over algoritmische looptijden dmv grote-O notatie. Wat was je oplossing geweest als het uitrekenen van de response bij lege cache 2 jaar had geduurd? Gewoon 2 jaar laten rammelen en het resultaat cachen zodat het er daarna binnen 0.1 seconden eruit komt rollen? Dat verandert verder helemaal niks aan de grote-O performance van het algoritme zelf, en bij een andere input kan je weer opnieuw gaan rekenen. Daarom maakt de omgeving voor het redeneren daarmee helemaal niet uit. Het is geen exacte tijdsduur die ermee wordt aangegeven, maar een verwachting voor hoe de looptijd verhoudingsgewijs toeneemt bij toenemde grootte van input. Maar als je toch graag met absolute tijden werkt, kan je grofweg zeggen dat een O(n²)-algoritme wat 1ms per stap nodig heeft een input van 5x5 in 625ms verwerken, voor een input van 100x100 al 27 uur nodig heeft en 1000x1000 kost 31 jaar. Een O(n)-algoritme is voor 5x5 in 25ms klaar, voor 100x100 in 10 seconden en voor 1000x1000 in iets meer dan een kwartiertje. Cache gaat je hier op geen enkele manier mee helpen. Ook cores niet. O(n²) op 1 core "is O(n²/4)" wat gewoon weer neerkomt op O(n²) want de functie groeit alsnog verhoudingsgewijs even hard. "Dezelfde looptijd" dus.

Oké, je mist volgens mij mijn punt: Qua theorie heb je gelijk, maar in de praktijk werkt het niet altijd zo mooi.

In beide voorbeelden was er een praktisch limiet (IO-bound en CPU-bound) waardoor bij een N boven X er sprake was van een andere big-O (in de praktijk). Dus moest ik in beide gevallen een andere algoritme schrijven die minder efficiënt was bij een kleine N maar efficiënter bij een grote N. Oh en de eerste was een NP probleem en consumeerde zijn eigen output als input.

In andere woorden de Big-O voor memory was dusdanig ongunstig dat ik er goed aan deed om de Big-O voor computational complexity in te leveren zodat ik in de praktijk een betere performance heb.

[Soultaker]

Ik had voor dag 5 eerst een oplossing gemaakt die

spoiler:

alle punten langsgaat, en voor elk punt telt hoeveel lijnen dat punt snijden

(code), maar dat is zowel langzamer als een stuk ingewikkelder dan de hier populaire variant van

spoiler:

per lijn alle punten te genereren, en dan simpelweg dubbelen te tellen

(code).

[iThinkSo]

Inderdaad zelf ook

spoiler:

alle punten gegenereerd en geteld, dit kan voor de mensen die Python gebruiken erg mooi met een collections.Counter:

Counter(pt for tips in parse(file) for pt in points(*tips, diagonals))

[TrailBlazer]

Ik vond vandaag makkelijker dan gisteren eigenlijk. Diagonalen gingen even mis in 1e instantie toen de logica on de punten te berekenen aangepast en toen werkte het redelijk snel.

spoiler:

Vandaag weer met numpy arrays gewerkt. Vooral handig dat je dan eenvoudig de coordinaten van allen punten die aan een bepaalde conditie voldoen kan genereren.

[Cranzai]

Het is weer gelukt, vandaag per saldo minder lang bezig geweest dan gisteren maar heb alles een beetje tussen de bedrijven door moeten doen.

https://github.com/Cranza.../2021/day5/python/day5.py

spoiler:

Ansich vandaag meer vertrouwen in de @DataGhost programma-killer input dan gisteren.
Heel bewust met een dictionary gewerkt zodat ik geen loze data elementen heb zoals in een pre-defined array bijvoorbeeld.

[ Voor 35% gewijzigd door Cranzai op 05-12-2021 19:24 ]

[rescla]

De lelijkste oplossing van de dag gaat denk ik naar mij: https://github.com/Rescla...blob/main/2021/day5.ipynb

spoiler:

Na wat geoogle kwam ik op shapely als interessante library om misschien te geruiken. Dat heeft support om intersects tussen lijnen te berekenen, dus dat had potentie.

Het eerste probleem waar ik tegenaan liep is dat het ook een lijn teruggeeft als je 2 lijnen hebt die deels over elkaar heen liggen. Dus daar moest ik alsnog los punten van gaan berekenen. Logisch vanuit het perspectief van de library, maar irritant voor deze puzzel.

Daarnaast was de output voor deel 2 niet correct met de intersect. Wel met de testdata, maar niet met de volledige set. Dus dat heb ik maar weer uitgecomment, en dan gaat het wel goed.

Effectief wordt die library dus niet meer gebruikt en is het nu gewoon dom lijntjes interpoleren en in een dict zetten. Afijn, de output klopt in ieder geval

[Verwijderd]

-

[ Voor 99% gewijzigd door Verwijderd op 05-09-2023 11:16 ]

[ElkeBxl]

armageddon_2k1 schreef op zondag 5 december 2021 @ 16:07:
Anders investeer je ‘s ochtends eerst even wat tijd (meer dan 5 minuten niet nodig denk ik) in dingen samen doen met haar

offtopic:
Oei, niet meer dan 5 minuten

Hier een inhaalslag moeten doen nadat ik vrijdag niet de tijd had gevonden om ermee bezig te zijn. Zodus dag 3, dag 4 en dag 5 in Rust.

Het is echt terug wennen voor mij om met een taal bezig te zijn waar woorden zoals "heap", "stack", aantal bits voor een getal, unsigned en dergelijke meer weer relevant worden, in mijn dagdagelijkse job als frontender met TypeScript/JavaScript moet ik daar nooit meer bij nadenken Maar het is leuk om nog eens uitgedaagd te worden!

[martyw]

Ik zie in alle commentaren dat ik me toch wat meer op de collections moet gaan inlezen, hopelijk lukt dat snel!
Vooralsnog kom ik op https://github.com/martyw/AOC2021/blob/main/day5.py (deel 1 doet er 62 ms over, deel 2 kost 172 ms op m'n i5-11500). Omdat ik wel gestructureerd bezig was/veel boilerplate heb was vandaag deel 2 snel gepiept.

[ Voor 17% gewijzigd door martyw op 05-12-2021 22:17 ]

[dcm360]

Ah, vandaag toch wel weer 2 'klassieke' problemen, en ik was alsog bij deel 1 eigenwijs genoeg om een oplossing te bouwen die niet werkte voor deel 2

spoiler:

Alle vissen los bijhouden loopt ruim te snel uit de klauwen, en aangezien je eigenlijk toch geen interesse hebt in individuele vissen kan je prima alleen de hoeveelheid vissen per dag opslaan. En voor deel 2 worden dat er uiteraard meer dan er in een Int past, maarja, ik was eigenwijs en mocht alsnog even de Int's vervangen door Long's.

[Varienaja]

Mooi optimaliseringsprobleem van een categorie die ik nog niet echt kende van AoC.

Mijn oplossing is dezelfde als die van @dcm360.

https://github.com/varien...tofcode2021/Puzzle06.java

[MrHaas]

spoiler:

Ik heb het opgelost met dynamic programming, omdat ik somehow niet op de meer obvious oplossing kwam :):

https://github.com/arjand...ain/python/06/solution.py

[ZieglerNichols]

Dag 6 in MATLAB

spoiler:

Ik hou alleen het aantal van elke 'soort' bij

[Dricus]

Dag 6 in Clojure

Leuk inkomertje voor de maandagochtend .

spoiler:

Net als de vorige schrijvers houd ik de aantallen per dag van de cyclus bij. Voordeel van Clojure is hier dat ik geen rekening heb hoeven houden met int/long, want dat doet Clojure al voor me. Als ik het in Kotlin had gedaan, had ik 99% zeker weer een search/replace int -> long moeten doen .

[Janoz]

dcm360 schreef op maandag 6 december 2021 @ 06:40:
Ah, vandaag toch wel weer 2 'klassieke' problemen, en ik was alsog bij deel 1 eigenwijs genoeg om een oplossing te bouwen die niet werkte voor deel 2

spoiler:

Alle vissen los bijhouden loopt ruim te snel uit de klauwen, en aangezien je eigenlijk toch geen interesse hebt in individuele vissen kan je prima alleen de hoeveelheid vissen per dag opslaan. En voor deel 2 worden dat er uiteraard meer dan er in een Int past, maarja, ik was eigenwijs en mocht alsnog even de Int's vervangen door Long's.

spoiler:

Ik had dezelfde histogram aanpak gekozen, maar je kon er wel vanuit gaan dat je grote input zou gaan krijgen. Dat in een array van 8 elementen proppen zou gegarandeerd wel ergens een overflow genereren.

Mijn oplossing in java:

spoiler:

[code=java]
Arrays.stream(input.split(",")).mapToInt(Integer::parseInt).forEach(i -> histogram[i]++);
for (int i=0; i<80; i++) {
long laboring = histogram[0];
System.arraycopy(histogram, 1, histogram, 0, 8);
histogram[6] += laboring;
histogram[8] = laboring;
}
return Arrays.stream(histogram).sum();
[/code]

[Woy]

Ja ik heb dezelfde aanpak als bovenstaande mensen, was al wel meteen duidelijk dat de naive oplossing problemen zou gaan geven

https://github.com/rverst.../blob/main/Y2021/Day06.cs

[Hydra]

LOL. Deel 1: "Euh, dit is te makkelijk"...

Yup

[Janoz]

Hydra schreef op maandag 6 december 2021 @ 07:54:
LOL. Deel 1: "Euh, dit is te makkelijk"...

Yup

En dan deel 2....

[armageddon_2k1]

Okee dan, ik laat deel 2 even rusten voor vanmiddag denk ik ;-)
Ik weet wel hoe ik het moet doen, maar ik ben niet scherp genoeg op het moment.

[coop]

Dag 6 in Python

spoiler:

Het lijkt wel een virus die visjes.

[ Voor 5% gewijzigd door coop op 06-12-2021 13:45 ]