Advent of Code 2020

[RangedNeedles]

joppybt schreef op donderdag 17 december 2020 @ 22:00:
Pfft, JavaScript is geen fijne taal om dit te doen. Veel te veel tijd gestoken in het dynamisch uitbreiden van de array's
Zelf houd ik me niet bezig met de performance maar heeft iemand het nog zo geoptimaliseerd:

spoiler:

Omdat je 2D begint zal de volgende dimensie symmetrisch zijn: bij deel 1 zal het vlak van z=-1 altijd gelijk zijn aan het vlak met z=+1. Zodoende hoef je maar de helft (+1) uit te rekenen.
In deel twee kan het waarschijnlijk nog meer schelen.

JS breidt z'n arrays toch automatisch uit? Ik vind het net heel handig hiervoor! Stel je voor dat je dit in Java wil doen, dan vliegen de IndexOutOfBoundsExceptions je waarschijnlijk om de oren

Maar ik heb in mijn oplossing JS daartoe niet eens de kans gegeven. Een truc was om de initial state gewoon te "padden". Dus je maakt je begin cube eigenlijk te groot, centreert de initial state en laat het zooitje dan z'n ding doen.

[Hydra]

Zo. Code flink opgeschoond!

spoiler:

Shunting Yard implementatie gefixt zodat 'ie haakjes aankan, en ook even een eigen Stack (wrapper voor mutable list) gemaakt ter vervangingen van java.util.Stack die beter aansluit op Kotlin collections.

[armageddon_2k1]

...weg...

[ Voor 94% gewijzigd door armageddon_2k1 op 18-12-2020 13:38 ]

[Soultaker]

Dijkstra is echt de held met z'n simpele maar krachtige algoritmen.

[ThoNohT]

spoiler:

Shunting yard ken(de) ik niet.

Dus een mooie LL0 parser die de precedence niet goed kan doen. Maar dan fix ik dat toch gewoon in mijn expression boom

[ Voor 3% gewijzigd door ThoNohT op 18-12-2020 14:46 ]

[Moofnor]

Zo, dat was een lange zit. Deel 1 ging best soepel, maar bij twee wel lang vast gezeten. Vanavond maar even bij lezen want

spoiler:

Nog nooit gehoord van shunting yard

Daarom een houtje touwtje oplossing geworden met veel loops en recursion...

spoiler:

Deel 1 optellen en vermenigvuldigen tot (, dan haakjes tellen en de substring in recursion oplossen, enzovoort.

Deel 2 werkte dat natuurlijk niet, dus opgelost in 2.5 loops, eerst loop die haakjes oplost zoals in deel 1 en alles in een list zet. Dan een loop die door blijft gaan tot er 1: geen '+' meer in de list zit, en 2: list nog 1 lang is.
Genoeg kans om te refactoren iig

java: https://github.com/Moofnor/AoC2020/tree/main/day18

[Hydra]

ThoNohT schreef op vrijdag 18 december 2020 @ 13:35:
SPOILER ken(de) ik niet.

Ik vind dit best wel een spoiler eigenlijk

Ik kende 'em vooral al omdat we ergens in 't voorgaande jaar 'em ook heb moeten toepassen. Zat overigens eerste te overwegen met Antlr een grammar + parser te maken. Ga ik misschien alsnog doen; erg leuk.

[ThoNohT]

Hydra schreef op vrijdag 18 december 2020 @ 14:26:
[...]
Ik kende 'em vooral al omdat we ergens in 't voorgaande jaar 'em ook heb moeten toepassen. Zat overigens eerste te overwegen met Antlr een grammar + parser te maken. Ga ik misschien alsnog doen; erg leuk.

Excuus, aangepast. Doe jij het ook nog even in je quote?
Ik zit nog te denken om

spoiler:

shunting yard

dan maar eens te implementeren. Dat lijkt van wikipedia redelijk goed te doen. Benieuwd of ik dan dezelfde resultaten krijg.

[Verwijderd]

spoiler:

Voor deel 1 een parser die de stukken tussen haakjes uitrekent en weer tussen de originele input plakt tot er geen haakjes meer zijn.
Kon dat vervolgens hergebruiken voor deel 2, waar ik exact dat deed voor de 'a + b' strings en die daarna in de parser voor deel 1 gooi.

perfromance is in matlab natuurlijk om te huilen met strings:

deel 1: 239 ms
deel 2: 411 ms

[coop]

Veel te lang bezig geweest met dag 18.
Uiteindelijke een oplossing die 35-36ms over ieder deel doet, best tevreden mee, maar duurde wel lang voordat ik de oplossing had.

spoiler:

Eerst de groepen tussen haken moeten identificeren, dat duurde het langste. Uiteindelijk maak ik een lijst met groepen aan en verwijs naar een andere groep met 'group_n', deze vervang ik dan later als ik ga rekenen. Toen de logica voor het rekenen. Deel 2 was erg simpel ipv kijken naar * en +, eerst naar + en daarna naar *. Ik liep nog tegen een probleem op dat ik replace(x[*+]y, eval(x[*+]y) deed, waardoor mijn som niet klopte wegens overtreding van rekenvolgorde.

[ Voor 5% gewijzigd door coop op 22-08-2023 00:44 ]

[Verwijderd]

Hydra schreef op vrijdag 18 december 2020 @ 12:45:
Zo. Code flink opgeschoond!

spoiler:

Shunting Yard implementatie gefixt zodat 'ie haakjes aankan, en ook even een eigen Stack (wrapper voor mutable list) gemaakt ter vervangingen van java.util.Stack die beter aansluit op Kotlin collections.

Had ik die gekend, had ik deze

spoiler:

https://nl.mathworks.com/...change/68458-evalequation

kunnen gebruiken...

[ThoNohT]

Verwijderd schreef op vrijdag 18 december 2020 @ 16:11:
Had ik die gekend, had ik deze

spoiler:

https://nl.mathworks.com/...change/68458-evalequation

kunnen gebruiken...

Die gaat je operator precedence niet goed doen lijkt me, of is die daar ook instelbaar?

[bakkerjangert]

coop schreef op vrijdag 18 december 2020 @ 15:33:
Veel te lang bezig geweest met dag 18. https://github.com/tluijf...020/blob/main/Day%2018.py
Uiteindelijke een oplossing die 35-36ms over ieder deel doet, best tevreden mee, maar duurde wel lang voordat ik de oplossing had.

spoiler:

Eerst de groepen tussen haken moeten identificeren, dat duurde het langste. Uiteindelijk maak ik een lijst met groepen aan en verwijs naar een andere groep met 'group_n', deze vervang ik dan later als ik ga rekenen. Toen de logica voor het rekenen. Deel 2 was erg simpel ipv kijken naar * en +, eerst naar + en daarna naar *. Ik liep nog tegen een probleem op dat ik replace(x[*+]y, eval(x[*+]y) deed, waardoor mijn som niet klopte wegens overtreding van rekenvolgorde.

Daar was ik ook mee aan het worstelen, maar na wat googlen vond ik deze:

spoiler:

re.findall('\([^()]*\)', string)
link

[Verwijderd]

ThoNohT schreef op vrijdag 18 december 2020 @ 16:20:
[...]

Die gaat je operator precedence niet goed doen lijkt me, of is die daar ook instelbaar?

Ja, dat is een tabel in de betreffende functie, dus dat was appeltje eitje geweest....

Heb mijn implementatie hier staan nu

[ Voor 19% gewijzigd door Verwijderd op 18-12-2020 18:24 . Reden: toevoegen link naar code ]

[coop]

bakkerjangert schreef op vrijdag 18 december 2020 @ 16:23:
[...]


Daar was ik ook mee aan het worstelen, maar na wat googlen vond ik deze:

spoiler:

re.findall('\([^()]*\)', string)
link

Oh dat is veel simpeler. Had mij veel tijd bespaard. Thanks!

[Hydra]

Verwijderd schreef op vrijdag 18 december 2020 @ 16:11:
Had ik die gekend, had ik deze

spoiler:

https://nl.mathworks.com/...change/68458-evalequation

kunnen gebruiken...

Ik kende 'em ook vooral omdat 'ie eerder voorbij is gekomen. Zo vaak implementeer ik dit soort zaken niet That said; ik heb met opzet niet een bestaande implementatie 'gestolen'. Ik hou voor mezelf aan dat ik geen externe libraries of andermans code gebruik. Ik kijk hoogstens als ik vast zit hoe iemand anders 't gedaan heeft.

[veldsla]

Zo alles opgelost met alleen de parser/combinator (nom). Kostte me wel veel tijd, maar uiteindelijk was het best simpel. Misschien nog een beetje opruimen..

[Soultaker]

Overigens is het SY algoritme niet de enige of die meest simpele oplossing voor dag 18. Voor deel 2 kun je ook een LL(1) grammatica opstellen:

spoiler:

P = S | S '*' P
S = E | E '+' S
E = [0-9]+ | '(' P ')'

die kun je volgens eenvoudig parsen met een recursive descent parser.
Voorbeeldcode in Python: shunting yard vs recursive descent (alleen deel 2).

Het voordeel van recursive descent is vooral dat het vrij makkelijk is om een ad-hoc algoritme te implementeren.

[Mschamp]

Mijn oplossing voor vandaag C# https://github.com/mscham...blob/master/2020/Day18.cs
Had ook nog nooit van dat algoritme gehoord, dus op een andere manier gedaan. Volgens de ingebouwde stopwatch in .net ook nog behoorlijk snel <100ms voor beide samen

[ Voor 20% gewijzigd door Mschamp op 18-12-2020 18:46 ]

[Soultaker]

Ongerelateerde vraag: is er iemand die in Haskell werkt?

Voor dag 15 (met de van Eck serie) had ik deze oplossing bedacht. Dat werkt prima voor deel 1, maar bij deel 2 gebruikt 'ie bijna 9 GiB geheugen (en ongeveer 2 minuten tijd). Enig idee hoe ik dit kan verbeteren?

[wmkuipers]

Ik heb vandaag echt heel erg veel mooie oplossingen gezien, zeker voor deel 2. Ik heb deel 2 een beetje gehackt, door

spoiler:

alle opening/closing brackets te vervangen door dubbele brackets, aan het begin en het eind een opening/closing bracket toevoegen, en * te vervangen door )*(. Met die paar string manipulaties kon je equation gewoon in de oplossing van deel 1.

1 + 2 * 3 + 4 * 5 + 6
wordt dan
(1 + 2 )*( 3 + 4 )*( 5 + 6)

en kan door dezelfde parser

[Hydra]

@Soultaker spoilers

[Dricus]

Dag 18 (Kotlin)

Nou, dit was dus een uitgelezen kans om eindelijk eens voor het eerst in ~30 jaar programmeren een parser te implementeren vanaf scratch. Ik heb me niet heel erg verdiept in parsers, maar volgens mij is het een recursive descent parser.

Niet mijn kortste code, maar dat was niet het doel, alhoewel de losse tokenizer achteraf niet echt nodig was geweest. Maar het was wel leuk om te doen!

Ik ben er wel tevreden mee dat ik de verschillen tussen dag 1 en 2 met minimale overhead heb weten te implementeren.

[Reynouts]

spoiler:

Na deel 1 op te lossen met een eigen "parser", voor deel 2 toch een andere route ingeslagen en lui geweest door in Python eval te gebruiken en mijn eigen intwrapper klasse te maken waarbij ik de dunder methods override.

Voor part 1 moet de precedence gelijkwaardig zijn, dus kun je bijvoorbeeld __sub__ gebruiken voor multiply en voor part 2 kan je __add__ als multiply implementeren en __mul__ als add (ik doe het nog iets anders, zodat ik 1 klasse kan gebruiken). Dan een simpele regex find/replace voor de operators en eval doet de rest.

code

[ Voor 38% gewijzigd door Reynouts op 18-12-2020 20:47 ]

[Varienaja]

Code gefatsoeneerd.

Ik heb een piepkleine grammatica geïmplementeerd:

spoiler:

Expr = Term operator Expr
Term = 0-9 | (Expr)

Dat had ik vanmorgen ook al, alleen toen zaten er toen nog onnodige kronkels en redundanties in. Voor onderdeel B t.o.v. A is er maar een piepkleine wijziging nodig.

[ Voor 8% gewijzigd door Varienaja op 18-12-2020 21:47 ]

[Varienaja]

Lachen hoor Dag 19. Voorbeeld correct.

spoiler:

Mijn 4k beeldscherm niet breed genoeg voor een huge-ass regex. En ik in een ondebugbare situatie.

En deze gast doet hetzelfde en heeft geen problemen?

[ Voor 33% gewijzigd door Varienaja op 19-12-2020 07:18 ]

[armageddon_2k1]

Dag 19 Part 1 af, maar part 2 werken mijn hersenen even niet meer goed genoeg voor.
Even laten rusten, ik weet zo niet hoe ik dit op moet lossen.

[Hydra]

Dag 19 in Kotlin

Om 7u opgestaan. Uiteindelijk veel te lang mee bezig geweest t.o.v. hoe simpel het eigenlijk is. In de ochtend onder druk (ik moet om 10u weg) werken is echt mijn ding niet. Uiteindelijk via een hint op Reddit toch weer de juiste weg ingeslagen (die ik eerder losgelaten had omdat ik dacht dat het niet ging werken).

[Dido]

Echt voor het allereerst in mijn leven dat ik zat te staren naar een string en dacht

spoiler:

hey, dat lijkt wel een regex, dat gaat het leven simpeler maken!

Sowieso tot op heden bijna geen ervaring met die ondingen,m dus dat was alsnog wel even puzzelen.

Bij deel twee wist ik in eerste instantie ook niet hoe ik verder moest, maar uiteindelijk bleek het eigenlijk vrij simpel.

spoiler:

De rules die je vervangt vervangen door iets slimmers helpt natuurlijk... alleen jammer dat ik vervolgens het voorbeeld goed had, maar de echte input natuurlijk niet, daar was mijn antwoord te hoog. Nu heb ik het verschil tussen * en + geleerd

Dat leaderboard blijft verwarrend, trouwens. Vandaag 1083 punten gescoord

[ Voor 5% gewijzigd door Dido op 19-12-2020 09:27 ]

[Hydra]

Dido schreef op zaterdag 19 december 2020 @ 09:15:
Echt voor het allereerst in mijn leven dat ik zat te staren naar een string en dacht

spoiler:

hey, dat lijkt wel een regex, dat gaat het leven simpeler maken!

Ho. Ly. Fuck. Hoe ben ik niet op dat idee gekomen.

Brb, hele shit omschrijven.

Edit: Ah, zo simpel is het niet.

spoiler:

Domweg een regex bouwen voor deel 1 werkt gewoon en is heel simpel. Alleen met deel 2 wordt de regex recursief gemaakt, en dan werkt het dus niet zo snel meer. Nouja, geen tijd meer om dat met die andere aanpak te fixen dus ik hou het hier maar ff bij.

[ Voor 30% gewijzigd door Hydra op 19-12-2020 09:36 ]

[Reynouts]

spoiler:

Met 1 regex oplossen is lastig voor p2, maar een regex die je find en replaced werkt eenvoudig.

Als je kijkt moet je in regel 8 een "+" achter de 42 plakken. En regel 11 moet van de vorm 42{n}31{n} zijn, waarbij n gelijk moet zijn. Dan kan je in een loopje de n replacen voor een getal en die steeds ophogen totdat er niets meer te vinden is of een max bereikt.

[Daanoz]

Reynouts schreef op zaterdag 19 december 2020 @ 10:08:

spoiler:

Met 1 regex oplossen is lastig voor p2, maar een regex die je find en replaced werkt eenvoudig.

Als je kijkt moet je in regel 8 een "+" achter de 42 plakken. En regel 11 moet van de vorm 42{n}31{n} zijn, waarbij n gelijk moet zijn. Dan kan je in een loopje de n replacen voor een getal en die steeds ophogen totdat er niets meer te vinden is of een max bereikt.

spoiler:

Hetzelfde inderdaad gedaan, het schijnt dat sommige regex engines 'n' gelijk kunnen houden, helaas niet in de mijne dus ik kan het niet uitproberen. Volgens mij heet het balanced constructs: http://www.regular-expressions.info/balancing.html, en het zou in .NET moeten zitten.

[Woy]

Bij deze was part2 erg eenvoudig, want mijn oplossing voor part1 kon daar al prima mee omgaan:

https://github.com/rverst.../blob/main/Y2020/Day19.cs

Het was dus puur een kwestie van de rules vervangen

[ Voor 15% gewijzigd door Woy op 21-12-2020 16:14 ]

[Woy]

Varienaja schreef op zaterdag 19 december 2020 @ 06:54:
Lachen hoor Dag 19. Voorbeeld correct.

spoiler:

Mijn 4k beeldscherm niet breed genoeg voor een huge-ass regex. En ik in een ondebugbare situatie.

En deze gast doet hetzelfde en heeft geen problemen?

Ik moet zeggen dat ik het een creatieve oplossing vind, maar niet erg elegant

[eamelink]

Vreselijk dit

spoiler:

Deel 1 was natuurlijk een regular expression, dus die even vertalen naar een regex zodat Java hem snapt, en gaan.

Bij deel twee, het vervangen van rule #8 is het nog steeds een regular expression, dus dat was geen probleem.

Na het vervangen van deel 11 is het geen regular expression meer. Gelukkig zijn er veel Regex engines die net wat meer kunnen dan regular languages, alleen die van Java is een beetje mank. Dus geforkt naar PHP, die wel recursieve regexes ondersteunt

Alleen het gaf niet het goede antwoord . Geen idee waarom. M'n test-voorbeeldjes werkten, er matchte ook meer, maar niet genoeg om een of andere reden.

Toen was ik het zat en heb ik dezelfde tactiek als @Reynouts gebruikt. Hij was zo bloedsnel, dat het aantal regexen ver-honderd-voudigen geen probleem moest zijn, en dat zou moeten werken als ik de lengte van de input zo inschatte . Uiteindelijk bleek '4' zelfs genoeg te zijn

[ThoNohT]

Dag 19 in F#, alleen deel 1 werkt tot nu toe. Deel 2 geeft wel meer oplossingen, maar niet genoeg. Ik ga later nog kijken of ik kan vinden waarom dat is.

spoiler:

Geen regex voor mij. Ik zag eigenlijk meteen een context-vrije grammatica voor me. Dus die heb ik geparsed naar regels. En dan een functie om een regel in een parser om te zetten, et voila.

Voor de vorige opdracht had ik mijn parser combinators al lazy gemaakt, dus recursieve definities is ook geen probleem, (zolang als een recursieve definitie maar niet direct begint met een recursieve call, want dan gaat de parser loopen bij het uitvoeren, maar dat is hier geen probleem).

Voor deel 2 heb ik mijn eigen recursieve regels geprobeerd, en die parset hij allemaal goed, dus ik weet nog niet wat er fout aan is op het moment.

Edit: Ik heb gevonden wat mijn parser verkeerd doet. Maar nog niet waarom

[ Voor 4% gewijzigd door ThoNohT op 19-12-2020 14:21 ]

[Soultaker]

Dag 19:

spoiler:

Ik had vandaag goed gegokt door voor deel 1 al een recursieve parser te schrijven (code), wat ook voor deel 2 werkt. Ik had verwacht dat ik memoization had moeten toepassen (op het paar: huidige regel, positie in de string) maar dat bleek helemaal niet nodig.

De recursive aanpak werkt omdat geen regel de lege string kan matchen (anders zou je in een oneindige lus terecht kunnen komen).

[patrick.k]

Dag 19:

spoiler:

Veel te lang over gedaan. Eerst regex aanpak geprobeerd in Rust, maar de Rust regex crate kon het niet aan (out of memory bij het compileren van de regex op de echte input).

Vervolgens voor de recursieve aanpak gegaan en daarmee deel 1 inmiddels opgelost, maar ik heb het idee dat ik nog steeds wat mis. Eager de | operator matchen op 1 of 2 matches zorgde voor het verkeerde resultaat. Altijd maar 1 kant pakken zorgt wel voor het goede resultaat op de hele input. Dat terwijl de beschrijving dikgedrukt zegt dat 'at least one' moet matchen.

Nu deel 2 maar eens beginnen.

[armageddon_2k1]

Blergh... Part 2 werkt wel op de voorbeeld input, maar niet op mijn eigen.

[Mschamp]

Ben er ook geraakt: C#
Waarschijnlijk niet echt properste manier, maar blij dat ik er geraakt ben. Wel niet zeker of het in alle gevallen werkt, voor mijn input ging het.

[armageddon_2k1]

Dag 19 in Kotlin

Uiteindelijk gelukt.... blegh. Wel lelijk geworden. Zo lelijk dat de syntax highlighting van Github het opgeeft....
De makkelijkste manier, of meest logische die ik voor ogen had, zoals @Hydra heeft zoals ik nu kan zien, lukte me gewoon niet voor elkaar te krijgen in mijn hoofd.

spoiler:

Uiteindelijk de replacement rules bekeken en toen was het duidelijk dat dat gewoon regexes waren. Toen eigenlijk gewoon regex gegenereerd aan de hand van de rules. Enige irritante was dat die tweede replacement rule wel benodigd dat beide sequences even vaak voorkomen. Dat duurde even. @Reynouts heeft het dus precies zo gedaan.

EDIT: O my god... de oplossingen zijn zo veel simpeler als ik van anderen bekijk

[ Voor 9% gewijzigd door armageddon_2k1 op 19-12-2020 16:13 ]

[Dricus]

Dag 19 (Kotlin)

Goeiedag, wat een worsteling was dit.

spoiler:

Deel 1 door een regex te bakken was zo gebeurd inderdaad. Maar voor deel 2 moest ik toch weer recursive descent gaan doen. En toen kreeg ik bij die "either or" regels het probleem dat de matching te greedy was in combinatie met die tail recursive regel 8.

Mijn oplossing was uiteindelijk om de greedy matching in tact te laten, en bij een tail recursive rule "brute force" combinaties te proberen en de beste eruit pikken.

[ppx17]

Day 19 in php

spoiler:

Dit leek teveel op regex'en om niet die kant op te gaan. Voor part 2 genereer ik gewoon 10 verschillende regex'en, met een fixed (fortyTwo){x}(thirtyOne){x} en tel k de matches op.

In eerste instantie had k tot 100 dezelfde groepen geprobeerd, maar dat was helemaal niet nodig, mijn input had maar 5 lagen recursie, dus heb de code tot 10 laten zoeken.

[Varienaja]

spoiler:

Ik had de fout dat ik bij het overschrijven van regels niet precies genoeg was. Dan was bijvoorbeeld regel 22 ook betroffen als ik regel 2 aan het overschrijven was. Dus regel 22 werd behandeld als 2x regel 2 na elkaar. Pff.. voordat dat begint op te vallen...

Het vervangen van regel 8 door "(42)+" en regel 11 door "(42){n}(31){n}" vind ik heel goed bedacht. Alleen kent java de laatste mogelijkheid niet, met die "balanced constructs". Dus ik heb mijn versie zo gelaten dat hij de 'oneindige' loop een maximaal aantal keren doorloopt. Niet netjes, maar goed genoeg om een kloppend antwoord mee te vinden.

Dus Dag 19.

[Dricus]

Hydra schreef op zaterdag 19 december 2020 @ 09:14:
Dag 19 in Kotlin

Om 7u opgestaan. Uiteindelijk veel te lang mee bezig geweest t.o.v. hoe simpel het eigenlijk is. In de ochtend onder druk (ik moet om 10u weg) werken is echt mijn ding niet. Uiteindelijk via een hint op Reddit toch weer de juiste weg ingeslagen (die ik eerder losgelaten had omdat ik dacht dat het niet ging werken).

Da's echt een verbluffend simpele oplossing! Kun je eens uitleggen hoe en waarom het nu precies werkt? Ik vind dat lastig uit de code te halen...

[Hydra]

Dricus schreef op zaterdag 19 december 2020 @ 17:06:
Da's echt een verbluffend simpele oplossing! Kun je eens uitleggen hoe en waarom het nu precies werkt? Ik vind dat lastig uit de code te halen...

spoiler:

Hij gaat recursief door de regels heen, gebruikmakende van de regelnummers als referenties. Als hij een 'match' heeft op een karakter, gaat hij recursief dieper met een substring van de regel. Dus als hij 'a' vindt in abc, gaat 'ie dieper met 'bc'.

De code waarmee ik de solution gesubmit heeft was een stuk smeriger / omslachtiger trouwens, daar zijn een paar refactoring slagen overheen gegaan.

[joppybt]

Ik heb deel twee uiteindelijk brute force opgelost

spoiler:

8: 42 | 42 8 kun je interpreteren als: één of meer keer 42 ('x' keer)
11: 42 31 | 42 11 31 kun je interpreteren als één of meer keer 42 ('y' keer) gevolgd door even vaak 31

Omdat 8 en 11 bij mij (en iedereen?) alleen bij stap 0 voorkomen probeer ik gewoon alle combinaties van x en y als uitgewerkte stap 0

Ik probeer dus voor stap 0 (maximaal input string lengte)
42 . 42 31
42 . 42 42 31 31
42 . 42 42 42 31 31 31
42 . 42 42 42 31 42 31 31 31
enzovoorts en dan
42 42 . 42 31
42 42 . 42 42 31 31
42 42 . 42 42 42 31 31 31
42 42 . 42 42 42 31 42 31 31 31
enzovoorts

Het is lelijk maar mijn check-routine uit deel 1 is verder gewoon ongewijzigd.

[armageddon_2k1]

@Hydra dat was dus precies wat ik wilde doen maar m’n hoofd werkte niet mee. Gelukkig raak ik dan helemaal niet gefrustreerd en kan ik het prima loslaten de rest van de dag.....

[Dricus]

Hydra schreef op zaterdag 19 december 2020 @ 17:40:

spoiler:

Hij gaat recursief door de regels heen, gebruikmakende van de regelnummers als referenties. Als hij een 'match' heeft op een karakter, gaat hij recursief dieper met een substring van de regel. Dus als hij 'a' vindt in abc, gaat 'ie dieper met 'bc'.

De code waarmee ik de solution gesubmit heeft was een stuk smeriger / omslachtiger trouwens, daar zijn een paar refactoring slagen overheen gegaan.

spoiler:

Het ging me er vooral om dat ik niet helemaal snapte hoe je voorkomt dat je te greedy gaat matchen. Dat was mijn grootste probleem.

Ik heb jouw oplossing maar eens in mijn eigen code toegepast, en met een println aan het begin van de isMatch wordt mooi inzichtelijk hoe het matchen verloopt. Het heeft veel weg van een foldRight, volgens mij.

Mijn oplossing komt in feite neer op een foldLeft, vandaar ook de greedy matching.

[armageddon_2k1]

Ik dacht dat het ontspannend was zo tijdens mijn vakantie dit te doen, maar ik vreet me op als het me niet lukt an nadien ben ik allemaal dingen aan het bookmarken als huiswerk ok ooit eens te leren (parsers bijvoorbeeld)

[Varienaja]

Hydra schreef op zaterdag 19 december 2020 @ 17:40:

spoiler:

Hij gaat recursief door de regels heen, gebruikmakende van de regelnummers als referenties. Als hij een 'match' heeft op een karakter, gaat hij recursief dieper met een substring van de regel. Dus als hij 'a' vindt in abc, gaat 'ie dieper met 'bc'.

Keizercode @Hydra! Ik heb het even nagebouwd. Jammer genoeg is het wat trager. Maar geen gekunstel "oneindig" loopende regexen!

[Hydra]

Oh wow. Deze opdracht heb ik in m'n 2e jaar informatica moeten doen, maar toen met driehoeken. Toen dagen over gedaan

[Mawlana]

Ze worden steeds lastiger... De opdrachten kosten me de laatste paar dagen uren in plaats van een (half)uurtje.

[ZieglerNichols]

Dag 20 in Matlab: https://pastebin.com/Tjtb9Q6T

Lekker puzzelen was dat

[Woy]

Part 1 heb ik vrij vlot opgelost, maar ik was al bang dan mijn solution voor part1 niet voldoende zou zijn voor Part 2

spoiler:

Ik zoek alleen de hoeken op, daarmee is het natuurlijk wel mogelijk om alsnog de image te vinden, maar nog wel wat extra werk. Overigens zou mijn part1 solution ook niet werken als er per toeval toch een match zou zijn met een outer edge van een corner.

Nu eerst even wat andere dingen doen, dan kijk ik vanmiddag verder naar Part 2

Hier vast Par1 ( nog niet gefatsoeneerd ):
https://github.com/rverst.../blob/main/Y2020/Day20.cs

[ Voor 12% gewijzigd door Woy op 21-12-2020 16:14 ]

[Dido]

Wat een leuke opdracht vandaag
Mazzel gehad dat ik deel 1 kennelijk zo had opgezet dat ik erop voort kon borduren voor deel 2.

spoiler:

Wel redelijk wat papier verspild bij het debuggen van mijn turnen en flippen

Alleen jammer dat deel 1 er 2,5 seconde over doet terwijl deel 2 vervolgens in 14ms klaar is.
Daar moet nog wel iets te optimaliseren zijn. Daar gaat m'n zondag

[ Voor 27% gewijzigd door Dido op 20-12-2020 09:24 ]

[Hydra]

Fuck. Geen tijd meer. Natuurlijk hele implementatie gebouwd die niet werkt en geen idee waarom. Guh.

Ik vind het nadeel van dit soort opdrachten dat je gewoon vrij veel 'shit' moet implementeren en pas als je veel code hebt kan kijken of het werkt. Als het dan niet werkt is het, gewoon door de complexiteit van wat je al hebt, lastig te vinden waar de oorzaak zit. Op een zondag om 9:30 je eigen code debuggen werkt ook voor geen meter

[Woy]

Dido schreef op zondag 20 december 2020 @ 09:21:
Alleen jammer dat deel 1 er 2,5 seconde over doet terwijl deel 2 vervolgens in 14ms klaar is.
Daar moet nog wel iets te optimaliseren zijn. Daar gaat m'n zondag

Deel 1 is bij mij wel een flink stuk sneller, 330 us, waarvan meer dan de helft al is voor IO en parsing van de input

[Hydra]

Oh duh. Je kan ze niet alleen roteren maar ook flippen... Nouja, vanmiddag verder.

Lezen is niet m'n forte om 8 uur in de ochtend...

Edit: Flip geimplementeerd en werkt nog steeds niet... Guh

[ Voor 19% gewijzigd door Hydra op 20-12-2020 10:06 ]

[Woy]

@Hydra je kunt op 2assen flippen

[Mschamp]

Woy schreef op zondag 20 december 2020 @ 10:37:
@Hydra je kunt op 2assen flippen

Is dat wel zo? Komt dat dan niet overeen met 2 rotaties van 90°?

[Hydra]

Woy schreef op zondag 20 december 2020 @ 10:37:
@Hydra je kunt op 2assen flippen

I know, maar de fout zit kennelijk ergens anders.

[Woy]

Mschamp schreef op zondag 20 december 2020 @ 10:57:
[...]


Is dat wel zo? Komt dat dan niet overeen met 2 rotaties van 90°?

Ja je hebt gelijk volgens mij. Voor mijn oplossing voor part 1 haalt dat echter niet uit.

[armageddon_2k1]

Hmm, mijn voorbeeld input werkt goed.
Maar mijn echte oplossing doet er heel lang over..... ik heb nog geen antwoord in ieder geval.

[eamelink]

Pfoe, das wel even werken zeg, die zeemonsters.

Voor deel 1 had ik de puzzel nog niet opgelost, maar dat is ook niet nodig om de vraag te kunnen beantwoorden. Maar dan moet je bij deel 2 wel extra veel werk verzetten.

spoiler:

Voor deel 1 heb ik gewoon gekeken hoeveel zijkanten van elk stukje matchen aan een ander stukje. Dan vind je er vier met 2 zijkanten; dat zijn dus de hoeken en daarmee heb je het antwoord van deel 1.

Bij deel twee, gefold over alle vakken, met als state de vakken + tile die geweest zijn en de overgebleven tiles. Zoekstrategie om een passende tile te vinden:
- Kijken of het een hoek, zijkant of midden-tile is, en dan filteren op aantal matchende zijkanten
- Kandidaat-tiles in alle mogelijke rotaties en flips nemen, en dan filteren op dat de buitenkanten goed zitten
- Filteren op wat er past naast de stukjes die er al liggen

Zeemonster is kwestie van alle transposities pakken en kijken of het past op het plaatje. Gelukkig geen overlap

[ Voor 3% gewijzigd door eamelink op 20-12-2020 12:05 ]

[Varienaja]

Wat een avontuur vandaag. Begonnen met een algemene puzzle-oplosser. Maar dat duurt veel te lang voor het vinden van een oplossing.

Dan met de slimme methode van @Woy de oplossing voor A gevonden.

spoiler:

Nu weet ik tenminste één positie 100% zeker. Dus dat hoek-stukje gelegd, en mijn langzame puzzle-solver de boel laten afmaken. Dat werkt: er komt een mooie 120x120 kaart uitgerold.

Daarin vind ik echter geen enkel monster, en dat is blijkbaar fout..

[eamelink]

Monsters!!!

[Dricus]

Dag 20 (Kotlin)

Deze vond ik super leuk! Uitdagend, maar wel goed te doen, en leuk om te implementeren. De performance is niet mega goed, maar met ongeveer 400ms voor deel 1 en 2 ben ik dik tevreden.

Ik heb nog geen refactoring gedaan, dus de code kan wellicht wat cleaner.

spoiler:

Ik had voor deel 1 al gezorgd dat ik het hele grid van tiles goed geordend had, dus daar kon ik voor deel 2 mooi mee vooruit.

Voor het opbouwen van het grid van tiles maak ik eerst een te groot leeg grid (4 * sqrt(aantal tiles)). In het midden plaats ik dan de eerste tile. Dan ga ik iteratief alle overgebleven tiles plaatsen:

Voor elke iteratie:
- Bepaal lege neighbors van laatst-gevulde tiles
- Zoek voor elk van die neighbors een permutation van een tile die past en plaats die

Als laatste schoon ik het grid op door lege posities weg te filteren.

De functie om permutaties te maken van tiles, kon ik voor deel 2 weer hergebruiken om permutaties van het complete image te maken.

Op elk van die permutaties ga ik vervolgens zoeken naar zeemonsters, en de eerste die er meer dan 0 heeft gebruik ik. Tenslotte is het een kwestie van de zeemonsters wissen en '#' tiles tellen.

[Hydra]

Ik heb weer tijd Ik heb zojuist de hele bende weggemikt en ga opnieuw beginnen

[Mschamp]

spoiler:

Ik had bij deel 1 ook de afbeelding niet teruggemaakt, maar gewoon geteld. Daardoor voor deel 2 volledig moeten herbeginnen.
https://github.com/mscham...blob/master/2020/Day20.cs

[ Voor 19% gewijzigd door Mschamp op 20-12-2020 12:52 ]

[Varienaja]

Jullie zulen je wel rotgelachen hebben.

spoiler:

Ik had het over een 120x120 kaart, waarop ik geen zeemonsters vinden kon. Die kaart moet dus 96x96 zijn.. de puzzleranden moeten eraf.

"Wer lesen kann ist klar im Vorteil."

Nu nog even fatsoeneren, dan kan ik de link geven.

[Hydra]

Frustrerend. Ik komt er niet uit.

Ik 'zoek' gewoon recursief door alle tiles met alle orientaties maar ik zie iets over 't hoofd en staar me er al uren blind op. Iemand een hint?

[Hydra]

eamelink schreef op zondag 20 december 2020 @ 12:20:
Monsters!!!

Spoilers!

[dcm360]

Zo, dat duurde inderdaad even. Dingen roteren is blijkbaar nogal ingewikkeld, zowel voor deel 1 als deel 2 heb ik flink moeten debuggen om dat werkend te krijgen. Mede daardoor is mijn code een flinke brei geworden.

[ZieglerNichols]

Hydra schreef op zondag 20 december 2020 @ 14:17:
Frustrerend. Ik komt er niet uit.

Ik 'zoek' gewoon recursief door alle tiles met alle orientaties maar ik zie iets over 't hoofd en staar me er al uren blind op. Iemand een hint?

Niet zozeer een hint, maar dit is de procedure die ik volg:

spoiler:

-Eerst zoek ik voor elk puzzelstuk welke andere stukken er op enige wijze aan vast passen
-Dan 'align' ik alle stukjes, d.w.z. dat ik ze allemaal zo neerleg dat ik ze zonder roteren of flippen aan elkaar kan leggen.
-Verwijder puzzelstukjesrand
-Maak de puzzel, door alle stukken op de juiste plek te leggen
-Zoek de monsters
-Antwoord = aantal # in oorspronkelijke map - N * aantal # in monster, met N het aantal gevonden monsters

[armageddon_2k1]

Woep woep!
Dag 20 in Kotlin

Best tevreden, maar was erg veel werk! Was erg blij dat ik gewoon het probleem in goeie hulpclasses op had gedeeld en alle afzonderlijke delen goed had getest. In Part 2 kwam dat goed van pas en stelde uiteindelijk weinig voor.

Wel veel code-kloppen zeg. Allemachtig. Maar mijn Complex class was weer handig (rotation-wise). En een lading off-by-1 errors die ik met tests eruit haalde.

[Hydra]

Fuck yeah! Part 1 done

[Hydra]

ZieglerNichols schreef op zondag 20 december 2020 @ 14:31:
Niet zozeer een hint, maar dit is de procedure die ik volg:

Niet gelezen maar ben een flink stuk verder! Had nieuwe code met een nieuwe aanpak. Nu nieuwe code met de oude aanpak (denkfout in de nieuwe) en het werkt wel. Man wat een opluchting! En door naar deel 2.

[Soultaker]

Ik zit ook vast op deel 2 van dag 20. Het voorbeeld werkt perfect, maar mijn antwoord voor deel 2 zou te hoog zijn (wat suggereert dat ik niet alle zeemonsters gevonden heb).

Inmiddels uitgevonden dat afhankelijk met welk van de vier hoekstukjes ik begin ik twee verschillende oplossingen kan krijgen (de ene correct, de andere niet).

ZieglerNichols schreef op zondag 20 december 2020 @ 14:31:

spoiler:

Antwoord = aantal # in oorspronkelijke map - N * aantal # in monster, met N het aantal gevonden monsters

spoiler:

Het risico met die aanpak is dat je overlappende monsters dubbel telt. Maar in mijn invoer lijkt dat niet voor te komen (maar ik heb deel 2 nog niet correct opgelost, dus wie weet).

[ Voor 17% gewijzigd door Soultaker op 20-12-2020 15:07 ]

[Varienaja]

Mijn beloofde code: Dag 20. Man man 600 regels. Als het de komende paar dagen zo verder gaat kom ik niet verder! Vandaag kon ik tijd besteden, maar de komende week moet ik elke dag naar 't werk...

[ZieglerNichols]

Soultaker schreef op zondag 20 december 2020 @ 14:50:
Ik zit ook vast op deel 2 van dag 20. Het voorbeeld werkt perfect, maar mijn antwoord voor deel 2 zou te hoog zijn (wat suggereert dat ik niet alle zeemonsters gevonden heb).

Kan iemand misschien z'n oplossing over mijn input runnen en me (in een DM) vertellen wat het correcte antwoord is? De invoer en m'n tussenresultaten staan hier: https://gist.github.com/m...1ca8ebedd6056987fbaf2e1df


[...]

spoiler:

Het risico met die aanpak is dat je overlappende monsters dubbel telt. Maar in mijn invoer lijkt dat niet voor te komen (maar ik heb deel 2 nog niet correct opgelost, dus wie weet).

spoiler:

Inderdaad, dat risico is er, maar voor mijn invoer kwam dat gelukkig niet voor. Ik hield er wel rekening mee bij het invoeren dat als het antwoord incorrect was, er waarschijnlijk overlap was.

[armageddon_2k1]

Hydra schreef op zondag 20 december 2020 @ 14:47:
Fuck yeah! Part 1 done

Wat was het euvel nou?

[Woy]

Zo, ik ga ook even voor part 2 zitten

[Hydra]

armageddon_2k1 schreef op zondag 20 december 2020 @ 15:05:
Wat was het euvel nou?

Ergens een fout in de code. Had zowel mijn aanpak als de code (rotatie e.d.) veranderd. Code was de 2e keer goed, aanpak niet. Oude aanpak weer gebruikt en toen ging het wel goed.

Nu met deel 2 bezig.

spoiler:

Klopt het dat je in deel 2 ook met andere rotaties nog steeds monsters vindt? Ik vind met een 'verkeerde' rotatie van de input 1 monster.

[ZieglerNichols]

Hydra schreef op zondag 20 december 2020 @ 15:33:
[...]


Ergens een fout in de code. Had zowel mijn aanpak als de code (rotatie e.d.) veranderd. Code was de 2e keer goed, aanpak niet. Oude aanpak weer gebruikt en toen ging het wel goed.

Nu met deel 2 bezig.

spoiler:

Klopt het dat je in deel 2 ook met andere rotaties nog steeds monsters vindt? Ik vind met een 'verkeerde' rotatie van de input 1 monster.

spoiler:

Ik vind maar in 1 specifieke orientatie monsters, maar ik weet niet of dat voor elke invoer zo is

[Mschamp]

Hydra schreef op zondag 20 december 2020 @ 15:33:
[...]


Ergens een fout in de code. Had zowel mijn aanpak als de code (rotatie e.d.) veranderd. Code was de 2e keer goed, aanpak niet. Oude aanpak weer gebruikt en toen ging het wel goed.

Nu met deel 2 bezig.

spoiler:

Klopt het dat je in deel 2 ook met andere rotaties nog steeds monsters vindt? Ik vind met een 'verkeerde' rotatie van de input 1 monster.

spoiler:

ik krijg maar in 1 orientatie monsters, maar test alle mogelijk orientaties op monsters en neem die som.

[ Voor 5% gewijzigd door Mschamp op 20-12-2020 15:37 ]

[DataGhost]

Hydra schreef op zondag 20 december 2020 @ 15:33:
[...]


Ergens een fout in de code. Had zowel mijn aanpak als de code (rotatie e.d.) veranderd. Code was de 2e keer goed, aanpak niet. Oude aanpak weer gebruikt en toen ging het wel goed.

Nu met deel 2 bezig.

spoiler:

Klopt het dat je in deel 2 ook met andere rotaties nog steeds monsters vindt? Ik vind met een 'verkeerde' rotatie van de input 1 monster.

Lijkt me onwaarschijnlijk. Gebeurt bij mij ook niet, net als bij bovenstaanden. Kan je jouw input anders ergens pasten?

[Hydra]

Mschamp schreef op zondag 20 december 2020 @ 15:36:

spoiler:

ik krijg maar in 1 orientatie monsters, maar test alle mogelijk orientaties op monsters en neem die som.

Klopt. Wederom een fuckup

[Soultaker]

Ah, eindelijk m'n fout gevonden. Ik had een functie geschreven voor het roteren van 10x10 tiles (gerepresenteerd als een lijst van strings):

Python:

def Rotate(grid):
    return [''.join(grid[c][9 - r] for c in range(10) for r in range(10)]

Later moet je ook het volledige grid van 96x96 cellen roteren, dus had ik die functie aangepast zodat 'ie werkt met arrays-van-strings van willekeurige grootte:

Python:

def Rotate(grid):
    return [''.join(grid[c][9 - r] for c in range(len(grid))) for r in range(len(grid[0]))]

Wat is het probleem? De 9 had natuurlijk ook vervangen moeten worden door len(grid)!

Het effect is dat 9 - r negatief wordt. In een normale programmeertaal zou je dan een IndexOutOfBoundsException oi.d. krijgen. Maar nee, niet in Python. Python begint doodleuk aan de andere kant van de lijst te lezen. De uitvoer ziet er dan correct uit maar klopt van geen kant. D'oh!

Ik heb dat altijd al een misfeature gevonden en dat bewijst zich nu maar weer eens.

[Hydra]

En deel 2 done. Fuck me, volgens mij nog nooit zo blij geweest met een programmeeropdracht...

Ter lering ende vermaeck: 200+ regels bagger

[ Voor 49% gewijzigd door Hydra op 20-12-2020 15:54 ]

[Dricus]

Hydra schreef op zondag 20 december 2020 @ 15:53:
En deel 2 done. Fuck me, volgens mij nog nooit zo blij geweest met een programmeeropdracht...

Gratz! Ik had precies hetzelfde. Even zo'n fuck yeah momentje .

[DataGhost]

Soultaker schreef op zondag 20 december 2020 @ 15:47:
Ik heb dat altijd al een misfeature gevonden en dat bewijst zich nu maar weer eens.

Rechter edge:

code:

"".join([line[-1] for line in self.image])

Heerlijke feature

En ik heb het niet getest, maar volgens mij doet dit wat je wilt, zonder dat je ooit een negatieve index kan krijgen:

code:

return [''.join(grid[c][r] for c in range(len(grid))) for r in reversed(range(len(grid[0])))]

[Hydra]

Dricus schreef op zondag 20 december 2020 @ 15:54:
Gratz! Ik had precies hetzelfde. Even zo'n fuck yeah momentje .

Ik vond deel 2 t.o.v. 1 veel meer straightforward trouwens. Ik moet nog wel even de code flink gaan opschonen.

[Dricus]

Hydra schreef op zondag 20 december 2020 @ 15:55:
Ik vond deel 2 t.o.v. 1 veel meer straightforward trouwens. Ik moet nog wel even de code flink gaan opschonen.

Dat vond ik ook. Maar dat kwam wel doordat ik geen shortcut had genomen voor deel 1. Ik heb het idee dat je dat ook in het globale leaderboard van vandaag ziet. De nummer 1 van vandaag was niet heel snel met deel 1, maar was vervolgens wel de eerste met 2 sterren.

[DataGhost]

Dricus schreef op zondag 20 december 2020 @ 15:59:
[...]

Dat vond ik ook. Maar dat kwam wel doordat ik geen shortcut had genomen voor deel 1. Ik heb het idee dat je dat ook in het globale leaderboard van vandaag ziet. De nummer 1 van vandaag was niet heel snel met deel 1, maar was vervolgens wel de eerste met 2 sterren.

Bij het lezen van deel 1 wist ik al dat deel 2 sowieso geen shortcuts toestond, dus ik was al begonnen met nette datastructuren en het ook volledig oplossen in pseudocode met een redelijke looptijd. Door mijn aanpak zag ik al snel dat er voor deel 1 een shortcut was, dus dat was heel snel klaar. Daardoor had ik nog wel veel werk voor deel 2 en vond ik deel 2 moeilijker dan deel 1, maar ik hoefde in ieder geval niet helemaal opnieuw te beginnen. Deel 2 is bij mij nog steeds een uitbreiding op deel 1.

[Woy]

Ik heb nu mijn image goed gereconstrueerd volgens mij. Eerst even eten maken, en daarna op zoek naar watermonsters. Ik ga voor deze opdracht nog wel een beetje werk hebben om het netjes te maken, want het is niet de meest onderhoudbare code, maar ik moet nog maar even kijken of ik daar zin in ga hebben

[Hydra]

Zo, de code even ingekort naar 135 regels. Veruit het meeste van alle AoC opdrachten dit jaar.

[Hydra]

Dricus schreef op zondag 20 december 2020 @ 15:59:
Dat vond ik ook. Maar dat kwam wel doordat ik geen shortcut had genomen voor deel 1. Ik heb het idee dat je dat ook in het globale leaderboard van vandaag ziet. De nummer 1 van vandaag was niet heel snel met deel 1, maar was vervolgens wel de eerste met 2 sterren.

Ja idd. 12 minuten. Vet lang! Bizar hoe snel sommigen zijn. Zit je dan de halve dag aan een opdracht te werken

[Dricus]

Hydra schreef op zondag 20 december 2020 @ 16:29:
Ja idd. 12 minuten. Vet lang! Bizar hoe snel sommigen zijn. Zit je dan de halve dag aan een opdracht te werken

"Niet heel snel, vergeleken met de anderen" had ik moeten schrijven . Nog steeds bizar snel inderdaad.

[Daanoz]

Poeh, dat was een heftige vandaag x). Minstens een uur kwijt geraakt door een bug in de rotatie van een tile, bij de rotatie werden ook 2 van de 4 zijdes geflipt... Er kwamen zeer bijzondere figuren uit