Advent of Code 2020

[DataGhost]

Hydra schreef op maandag 14 december 2020 @ 20:20:
[...]


2^34 is een groot getal. Het is niet voor niets dat deze dag, itt tot de meeste anderen, niet naar het voorbeeld in deel 1 verwijst maar een nieuw voorbeeld geeft. Proberen dat voorbeeld voor deel 2 werkend te krijgen is een dood spoor.

Leef je verder uit hoor

Je zegt dat het ongeschikt is maar het waarom geef je verder geen goed antwoord op. 2^34 is inderdaad een groot getal en dat is precies de reden waarom

spoiler:

deze opgave je richting een dictionary-achtig type duwt voor het geheugen. Daarmee ben je echter niet direct bij simulatie uitgekomen. Juist vanwege de grootte van de getallen en de exponentiële uitleg in de voorbeelden zou je verwachten dat de testinvoer zodanig is dat je exponentieel genaaid wordt wat betreft je geheugen. Ik ging er daarom ook vanuit dat het voorbeeld niet was herhaald in deel twee, omdat het gigantische getal voor vrijwel iedereen direct duidelijk zou maken dat die input niet dmv simulatie op te lossen is.

Maar voor complexere oplossingen is het misschien nog te vroeg in de maand.

Los daarvan, waarom zou het voorbeeld van deel 1 ongeschikt voor deel 2 zijn? Waar blijkt dat uit? In dag 4 wordt voor deel 2 ook een andere input gegeven, is de input van deel 1 dan daarom ongeschikt (die invoer geeft in beide delen dezelfde uitkomst trouwens)? Of is er een ander criterium? Je kan het in ieder geval van tevoren niet weten en pas na het handmatig doorlezen van de puzzel-invoer

spoiler:

of het botweg simuleren ervan zou je kunnen beredeneren hoeveel geheugen er nodig zou zijn,

terwijl je de puzzel-invoer eigenlijk niet eens zou moeten lezen om daar je oplossing op aan te passen. Het kan wel, maar dan kan je het bijna net zo goed met de hand doen en het antwoord in je programma hardcoden. Moet je helemaal zelf weten verder.

[Soultaker]

edit:
Nevermind, m'n idee werkt niet

[ Voor 92% gewijzigd door Soultaker op 14-12-2020 20:57 ]

[Hydra]

DataGhost schreef op maandag 14 december 2020 @ 20:46:
Los daarvan, waarom zou het voorbeeld van deel 1 ongeschikt voor deel 2 zijn?

spoiler:

Ik snap echt niet wat er zo lastig aan te begrijpen is.

Je moet 2 tot de macht "aantal Xen in de mask" adressen berekenen in deel 2 toch? In het voorbeeld in deel 1 is het aantal heel groot. In je voorbeeld input in deel 2, en in je echte input niet. Dat maakt het voorbeeld in deel 1, wat niet voor niets niet genoemd wordt in deel 2, simpelweg ongeschikt.

Number okay in deel 2. Number too big in deal 1. Da's alles toch?

Het heeft niks met een dictionary te maken. Da's een memory probleem, niet een "de computer is te lang bezig" probleem.

Je kan het in ieder geval van tevoren niet weten

Als je ziet wat je moet doen wel. Het aantal permutaties dat berekend moet worden is duidelijk uit de voorbeelden in deel 2.

[ Voor 19% gewijzigd door Hydra op 14-12-2020 21:07 ]

[DataGhost]

Hydra schreef op maandag 14 december 2020 @ 21:04:
[...]

spoiler:

Ik snap echt niet wat er zo lastig aan te begrijpen is.

Je moet 2 tot de macht "aantal Xen in de mask" adressen berekenen in deel 2 toch? In het voorbeeld in deel 1 is het aantal heel groot. In je voorbeeld input in deel 2, en in je echte input niet. Dat maakt het voorbeeld in deel 1, wat niet voor niets niet genoemd wordt in deel 2, simpelweg ongeschikt.

Number okay in deel 2. Number too big in deal 1. Da's alles toch?

Ik snap ook niet wat er zo lastig aan te begrijpen is, kijk maar:

spoiler:

$ cat 14b.in.test
mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

$ time ./aoc.py 14 b
1735166787584
TEST OUTPUT DO NOT SUBMIT

real 0m0,151s
user 0m0,119s
sys 0m0,032s

Werkt dus gewoon prima, en snel. Niks too big, niks ongeschikt. Geeft op de testinvoer van deel 2 ook het correcte antwoord, alsmede op de volledige puzzel-invoer.

[veldsla]

Zo..de..knetters, dat was een lekker stukje bit shifting / twiddling. Performance niet denderend (5ms). Geen idee of er nog ruimte is, vind het wel even best zo (link)

[DataGhost]

Hydra schreef op maandag 14 december 2020 @ 21:04:
[...]

Als je ziet wat je moet doen wel. Het aantal permutaties dat berekend moet worden is duidelijk uit de voorbeelden in deel 2.

Je kan van tevoren niet weten dat

spoiler:

er geen soortgelijke case als voor deel 1 in de puzzel-invoer kan zitten zonder de puzzel-invoer te bekijken. Het aantal permutaties is duidelijk te zien ja, en dat is dus volkomen onpraktisch in een hele hoop gevallen. Helaas niet bij de daadwerkelijke puzzel-invoer.

[Hydra]

DataGhost schreef op maandag 14 december 2020 @ 21:09:
Ik snap ook niet wat er zo lastig aan te begrijpen is, kijk maar:

spoiler:

$ cat 14b.in.test
mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X


Werkt dus gewoon prima, en snel.

Hoe werkt je code dan?

spoiler:

Je moet toch die drie waardes 'setten' op 34^2 adressen? Dat doe je niet in een paar MS toch?

Ik probeer er achter te komen waar m'n denkfout zit hoor; probeer je niet af te fakkelen

[DataGhost]

Hydra schreef op maandag 14 december 2020 @ 21:21:
[...]


Hoe werkt je code dan?

spoiler:

Je moet toch die drie waardes 'setten' op 34^2 adressen? Dat doe je niet in een paar MS toch?

Ik probeer er achter te komen waar m'n denkfout zit hoor; probeer je niet af te fakkelen

Ongeveer zoals MrHaas in "Advent of Code 2020".

spoiler:

Mijn memory is, na het uitvoeren van het voorbeeld van deel 1, een dictionary met in totaal 2 entries. Vervolgens komt daar in lineaire tijd (aantal entries * aantal bits) het antwoord uit.

En voor een computer is 34 36² = 1296 adressen prima in een paar ms te doen, maar zoveel gebruik ik er dus niet eens. Dit is in ieder geval in een VM op een laptop uit 2011

[ Voor 12% gewijzigd door DataGhost op 14-12-2020 21:29 ]

[Hydra]

Maar dat werkt toch niet met de 'echte' input? Daar zitten meerdere masks in.

[Dricus]

Day 14 (Kotlin), maar dan functioneel

Ik kon het niet laten om toch nog een poging te wagen om een 100% functionele oplossing te maken, en dat is gelukt! En zonder te "cheaten" met een mutable collection .

En als bonus heb ik ook nog een gedeelde implementatie van het "draaien" van het programma, in de vorm van een higher order function waar het specifieke deel voor part 1 en part 2 aan meegegeven kan worden.

Met 51 millisecondes voor deel 2 vind ik de performance ook dikke prima!

[DRaakje]

ydderf schreef op maandag 14 december 2020 @ 20:17:
Dag 14, deel 1 gereed
Morgen maar eens naar deel twee kijken..

Nice! Ik had de bitwise operators ook gebruikt, maar op 1 of andere manier klikte het niet lekker in mijn hoofd en had ik nog een extra invert stap erin zitten. Dit is inderdaad veel netter. Kleine opmerking, waarom gebruik je voor je memory niet gewoon een dictionary?

Er zit een kleine bug in:

spoiler:

Je gebruikt nu 32bits addressen voor 36bits waarden

[joppybt]

Soultaker schreef op maandag 14 december 2020 @ 16:48:
Ik zie trouwens dat we 200 deelnemers op het Tweakers leaderbord hebben staan (waarvan er ruim 150 daadwerkelijk een probleem hebben opgelost)! Dat is best veel.

Volgens mij toont het leaderboard maximaal 200 deelnemers en zijn er wel meer.
De leaderboard van vorige jaren toont er ook exact 200, dat zou wel heel toevallig zijn.

Je kunt wel zien dat vorig jaar maar zo'n 50 mensen verder zijn gekomen dan de eerste 13 dagen, daar zijn we nu al wel overheen volgens mij.

[HectorMalot]

DataGhost schreef op maandag 14 december 2020 @ 21:26:
[...]

Ongeveer zoals MrHaas in "Advent of Code 2020".

spoiler:

Mijn memory is, na het uitvoeren van het voorbeeld van deel 1, een dictionary met in totaal 2 entries. Vervolgens komt daar in lineaire tijd (aantal entries * aantal bits) het antwoord uit.

En voor een computer is 34 36² = 1296 adressen prima in een paar ms te doen, maar zoveel gebruik ik er dus niet eens. Dit is in ieder geval in een VM op een laptop uit 2011

Het is niet 36² maar 2³⁶ in deel 2 toch? 68.7 miljard allocaties van 36 bits: 295 Gigabyte aan geheugen zonder compressie. Of doe je iets speciaals om ze op mask te alloceren en na afloop de dubbele allocaties eruit te halen?

[Mschamp]

joppybt schreef op maandag 14 december 2020 @ 22:03:
[...]

Volgens mij toont het leaderboard maximaal 200 deelnemers en zijn er wel meer.
De leaderboard van vorige jaren toont er ook exact 200, dat zou wel heel toevallig zijn.

Je kunt wel zien dat vorig jaar maar zo'n 50 mensen verder zijn gekomen dan de eerste 13 dagen, daar zijn we nu al wel overheen volgens mij.

Ik dacht ergens gelezen te hebben dat je maximum 200 mensen in zo een leaderboard kan hebben, zal daardoor exact 200 blijven.

Wel leuk om te lezen dat er zoveel verschillen in doelen zijn: ik ben al blij als ik het kan oplossen, anderen stellen zich nog extra doelen

[Swedish Clown]

"That private leaderboard is full. [OK]"

Moet zeggen dat het voor mij toch wel even tegenviel vandaag... Voorbeelden klopten al snel maar mijn input zit me dwars en de puinhoop die ik er in eerste instantie van had gemaakt maakte het debuggen niet gemakkelijker. Nu netjes opgeruimd en in 50 regels door in 1x door zowel deel 1 als deel 2 lopen.

[ Voor 103% gewijzigd door Swedish Clown op 15-12-2020 00:33 ]

[DataGhost]

Soultaker schreef op maandag 14 december 2020 @ 19:48:
[...]

Hoe voorkom je een exponentiële groei van het aantal bitmasks na splitsen?
[...]
enzovoorts. Je verdubbelt dus steeds het aantal bitmasks en dan kom je op 2^{N/2 + 2} - 1 bitmasks uit, wat nog steeds exponentiële groei is. Voor N = 36 is dat ongeveer een miljoen, wat toevallig net in het geheugen past.

Best een goeie richting worst-case ja. Ik weet niet of er nog ergere voorbeelden te verzinnen zijn. Ik heb jouw voorbeeld wat verder uitgebreid tot deze input en daarna ook eens met groepjes van 3 tot deze input. Onderaan beide bestanden staat de debug-output die na elke assignment de gebruikte hoeveelheid geheugen laat zien, en de hoeveelheid tijd. Qua geheugengebruik geeft dat een interessante grafiek De rechte lijnen (logaritmische schaal) laten een duidelijk exponentieel verband zien. Voor de puzzel-invoer is 'ie redelijk lineair.

Hydra schreef op maandag 14 december 2020 @ 21:44:
Maar dat werkt toch niet met de 'echte' input? Daar zitten meerdere masks in.

Jawel

spoiler:

Het uiteindelijke geheugengebruik is voor mijn puzzel slechts 1198 entries, wat neerkomt op 36 kiB, terwijl simulatie 2,5 MiB geheugen nodig heeft.

$ time ./aoc.py 14 b full
len(mem): 1198
getsizeof(mem): 36960
3440662844064

real 0m0,364s
user 0m0,332s
sys 0m0,032s

En dan voor simulatie:
$ ./aoc.py 14 b full
len(mem): 79171
getsizeof(mem): 2621536
3440662844064

HectorMalot schreef op maandag 14 december 2020 @ 22:05:
[...]


Het is niet 36² maar 2³⁶ in deel 2 toch? 68.7 miljard allocaties van 36 bits: 295 Gigabyte aan geheugen zonder compressie. Of doe je iets speciaals om ze op mask te alloceren en na afloop de dubbele allocaties eruit te halen?

Ik reageerde daarmee op de berekening van Hydra, ik weet niet precies waar die op gebaseerd was maar de absolute uitkomst vond ik niet heel heftig voor een computer. Ik heb inderdaad eerder gezegd dat

spoiler:

simulatie minimaal zo'n 256GB geheugen en heel veel tijd nodig zou hebben op die input, daarom dat ik naar een andere oplossing zocht en die heb gevonden .

[Rips10]

Leuke puzzel vandaag, maar toch altijd jammer als het tweede deel los staat van het eerste deel.
Alles opgelost met bitwise operations en bit-shifts
Day 14 C#

[joppybt]

DataGhost schreef op maandag 14 december 2020 @ 21:09:
[...]

Ik snap ook niet wat er zo lastig aan te begrijpen is, kijk maar:

spoiler:

$ cat 14b.in.test
mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

$ time ./aoc.py 14 b
1735166787584
TEST OUTPUT DO NOT SUBMIT

real 0m0,151s
user 0m0,119s
sys 0m0,032s

Werkt dus gewoon prima, en snel. Niks too big, niks ongeschikt. Geeft op de testinvoer van deel 2 ook het correcte antwoord, alsmede op de volledige puzzel-invoer.

code:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

Voor wie zich zoals ik afvraagt waarom 1735166787584 (dit is toch geen spoiler?) het correcte antwoord is als je deel 2 toepast op de testinvoer van deel 1: je kunt het handmatig uitrekenen.

spoiler:

De mem[7] (0111) zal alleen geheugenplaatsen zetten die door mem[8] (1000) niet geraakt worden (dat zou anders zijn als ze overlappende bitjes hadden of als er een 1 stond in de laatste karakters van de mask).
De tweede mem[8] instructie zal de eerste weer wissen.
Ofwel: effectief heb je alleen met de mem[7] instructie te maken.

Er staan 34 X-en in het masker. Dan volgt 2^34 * 101 = 1735166787584

[Soultaker]

Mschamp schreef op maandag 14 december 2020 @ 22:07:
Ik dacht ergens gelezen te hebben dat je maximum 200 mensen in zo een leaderboard kan hebben, zal daardoor exact 200 blijven.

Ah, dat verklaart het. Wel jammer dan dat er nu plekken bezet worden door mensen met 0 punten. Waarschijnlijk hebben die zich in de voorgaande jaren ingeschreven.

[Reptile209]

Soultaker schreef op maandag 14 december 2020 @ 22:45:
[...]

Ah, dat verklaart het. Wel jammer dan dat er nu plekken bezet worden door mensen met 0 punten. Waarschijnlijk hebben die zich in de voorgaande jaren ingeschreven.

Misschien kan @Daanoz een kleine schoonmaak houden in de leaderboard? Iedereen die nog geen enkele ster gehaald heeft er uit? Dan kunnen ze altijd opnieuw joinen als ze nu nog een inhaalslag gaan maken.

[Daanoz]

Reptile209 schreef op dinsdag 15 december 2020 @ 01:07:
[...]

Misschien kan @Daanoz een kleine schoonmaak houden in de leaderboard? Iedereen die nog geen enkele ster gehaald heeft er uit? Dan kunnen ze altijd opnieuw joinen als ze nu nog een inhaalslag gaan maken.

Ga ik morgen even doen

[Verwijderd]

Hmm, tot nu toe allesvrij aardig met matlab kunnen doen, ook binnen (hooguit) een paar 100ms, deze echter kostte me minuten.

grootste issue was niet zozeer het genereren van de 128,256 of 512 subadressen (met stringmanipulatie) maar het terugzoeken in een list of het adres al eerder was voorgekomen.
Ik ben dus lineair door de instructies gegaan en heb voor ieder gegenereerd adres gekeken of het reeds eerder voorgekomen was.
De opdrachten tot nu toe kennende kn je op 3 vingers natellen dat dat het geval zou zijn.

Is er iemand die deel 2 dag 14 heeft kunenn oplossen door vooraf te bepalen dat er slechts 87025 unieke adressen zijn?

Hmm,als je na een run weet hoeveel adressen er zijn en dat gebruikt voor initialisatie is het ongeveer een factor 20 sneller, maar nog steeds seconden. Moet beter kunnen.

[ Voor 11% gewijzigd door Verwijderd op 15-12-2020 01:30 ]

[Varienaja]

Jeetje onderdeel B is vandaag wel érg triviaal hoor. Gelukkig ben ik daardoor binnen een half uur klaar. En dat komt goed uit, want vandaag moet ik de kinderen klaarmaken voor school.

spoiler:

Ik zit me hier met mijn dochter te verbazen over de vele mensen in de ranglijst die vandaag alleen nog een zilveren ster hebben. Proberen zij eerst alle voorbeelden? Ik heb de extra voorbeelden pas achteraf geprobeerd, en vastgesteld dat die megalangzaam tot een oplossing komen. Maar met de echte input was onderdeel B vlug klaar.

[ Voor 48% gewijzigd door Varienaja op 15-12-2020 07:07 ]

[Dido]

Varienaja schreef op dinsdag 15 december 2020 @ 06:30:
Jeetje onderdeel B is vandaag wel érg triviaal hoor. Gelukkig ben ik daardoor binnen een half uur klaar. En dat komt goed uit, want vandaag moet ik de kinderen klaarmaken voor school.

spoiler:

Ik zit me hier met mijn dochter te verbazen over de vele mensen in de ranglijst die vandaag alleen nog een zilveren ster hebben. Proberen zij eerst alle voorbeelden? Ik heb de extra voorbeelden pas achteraf geprobeerd, en vastgesteld dat die megalangzaam tot een oplossing komen. Maar met de echte input was onderdeel B vlug klaar.

Aks je deel 1 meteen optimaliseert dan is 2 triviaal. Doe je 1 gewoon naief, dan kom je er achter dat deel twee wel heel erg lang gaat duren, en dan moet je dus alsnog gaan optimaliseren

spoiler:

Naieve oplossing voor deel 1 is gewoon letteerlijk de tekst volgen, dus een lijst nummers bijhouden en elke keer door die lijst lopen om te kijken wanneer een nummer voor het laatst gezegd was.
Dat werkt uitstekend voor 2020 nummers, maar voor 300 miljoen wordt dat een ander verhaal...

[Dricus]

Dag 15 (Kotlin)

Eerst maar eens even een quick & dirty, slecht geoptimaliseerde versie, want ik heb weinig tijd vanochtend. Voor nu vind ik 6 secondes voor deel 2 prima . Later vandaag ga ik nog wel eens kijken of ik een wat snellere variant kan maken.

[ElkeBxl]

Varienaja schreef op dinsdag 15 december 2020 @ 06:30:

spoiler:

Ik zit me hier met mijn dochter te verbazen over de vele mensen in de ranglijst die vandaag alleen nog een zilveren ster hebben. Proberen zij eerst alle voorbeelden? Ik heb de extra voorbeelden pas achteraf geprobeerd, en vastgesteld dat die megalangzaam tot een oplossing komen. Maar met de echte input was onderdeel B vlug klaar.

Niet iedereen start om 6u en ik heb zelf deel moeten herschrijven voor deel 2 omdat ik al snel op een "Maximum call stack size exceeded" botste. Maar gelukkig kon ik de logica bijna volledig overnemen en dan ben ik gewoon maar gaan douchen terwijl die toch nog ff bezig was met rekenen.

[Varienaja]

Uiteraard start niet iedereen om 6 uur. Ik wou alleen maar zeggen dat ik antwoord B direct na antwoord A had. En ik dacht dat dat bij iedereen zo moest zijn

spoiler:

Alleen even de for ophogen.

En ja: 20 sekonden wachten ofzo.

Ik heb ook geluk gehad, want met de extra voorbeelden vond ik nog fouten die blijkbaar een correct antwoord op onderdeel B niet in de weg stonden. Sterker nog: ik heb nog steeds de extra voorbeelden niet nagerekend. Duurt me te lang. Nu moet ik aan het werk. vanmiddag kom ik er pas aan toe mijn code op te ruimen, af te maken en op github te committen.

[Woy]

spoiler:

Inderdaad deel2 was erg triviaal, ik heb alleen even deel 1 in een methode met argument gerefactored, en aangeroepen in deel 2. Ik had wel het geluk dat ik gekozen had om het niet functioneel op te lossen, want dan had ik mogelijk wel gewoon een volledige lijst opgebouwd.

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

[ydderf]

DRaakje schreef op maandag 14 december 2020 @ 21:55:
[...]

Kleine opmerking, waarom gebruik je voor je memory niet gewoon een dictionary?

Er zit een kleine bug in:

spoiler:

Je gebruikt nu 32bits addressen voor 36bits waarden

Goede vraag. Ik denk voornamelijk om dat ik nu 14 dagen C# programmeer ervaring heb (plus nog een aantal dagen in 2018) en een beetje de weg weet te vinden met de list. Maar als ik ff google op de dictionary dan had dat misschien ook wel mooier gepast. Thanks voor de tip, daar ga ik zeker nog ff na kijken!

spoiler:

Ik weet niet of die ook voor mij bedoeld was, maar volgens Visual Studio Code, is het datatype long een "64-bit signed integer". En wanneer ik kijk naar mijn input, dan zitten daar ook waardes in boven de 32 bit en de puzzel oplossing wordt geaccepteerd.

[Woy]

@ydderf een long is inderdaad een Int64 ( Het is zelfs een alias voor dat type )

[armageddon_2k1]

Heb Day 14 nog even een factor 10 sneller gemaakt.
Leermomentje in Kotlin: Immutable maps zijn een factor 10 langzamer dan mutable maps.....

Helaas is de immutable collection library van Kotlin nog niet zo mooi als die van Scala.

[dcm360]

Deel 1 inderdaad naïef opgelost, en vervolgens voor deel 2 een 'verbeterde' versie geschreven. Waarbij de oplossing voor deel 2 wel dubbel zo lang doet over het oplossen van deel 1, dus de complexiteit loont pas op het moment dat er veel stappen doorgerekend moeten worden.

In Scala lijken immutable maps dan weer sneller te zijn dan mutable maps, althans, als ik de immutable map in mijn oplossing vervang door een mutable map duurt het uitvoeren langer (hoe veel langer weet ik dan weer niet, daar had ik niet het geduld voor).

[ThoNohT]

Dag 15 in F#.

Deel 2 kostte wel anderhalve minuut, en hij bouwt een map van ~800MB op lijkt het. Dus er kan waarschijnlijk ergens nog wel iets efficienter gok ik

[Creepy]

Zo, gisteren eindelijk weer eens wat tijd kunnen pakken voor dag 10. Part 1 was een eitje maar voor part 2 klikte, dat duurde wel ff.... hopelijk vandaag ff wat tijd pakken voor dag 11 tot 15.

[coop]

Vandaag was wel makkelijk.

spoiler:

Bij deel 1 een lijst van alle genoemde nummers bijgehouden. Dat ging aardig snel. Dat kan natuurlijk niet op voor deel 2, dus toen maar omgebouwd naar een dict met de laatste 2 keren dat een getal (de key) genoemd was. Deel 1 loopt in 800μs, deel 2 in 22 seconde.

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

[Hydra]

Day 15, voorlopige versie.

Brute-force-ish aanpak, doet er te lang over op deel 2 (24 seconden).

spoiler:

Heb het donkerbruine vermoeden dat er een cycle in de sequence zit die zich vrij rap gaat herhalen. Later maar even een keertje induiken.

[eamelink]

Dat was inderdaad een makkie, en m'n deel 1 oplossing voldeed ook (net) voor deel 2. Gewoon recht toe recht aan met een unfold.

[GladstoneW]

Hydra schreef op dinsdag 15 december 2020 @ 10:04:
Day 15, voorlopige versie.

Brute-force-ish aanpak, doet er te lang over op deel 2 (24 seconden).

spoiler:

Heb het donkerbruine vermoeden dat er een cycle in de sequence zit die zich vrij rap gaat herhalen. Later maar even een keertje induiken.

spoiler:

Ik had ook dat vermoeden, maar er nog geen kunnen vinden. Volgens reddit gaat het om een Van Eck Sequence en blijkbaar is daar nog nooit door een wiskundige een cyclus in ontdekt. Dus brute force is helaas the only way to go. Overigens runt mijn code met wat optimalisaties in ongeveer 1 seconde (C#).

[Hydra]

@GladstoneW Ah, check, thanks. Heb ff een simpele change gemaakt en zit nu op 10 sec. Zal 'es ff in jouw code duiken om te zien wat jij gedaan hebt.

[Daanoz]

@Soultaker @Reptile209

Even opgeruimd, zouden weer 42 plekjes moeten zijn!

[GladstoneW]

Hydra schreef op dinsdag 15 december 2020 @ 10:14:
@GladstoneW Ah, check, thanks. Heb ff een simpele change gemaakt en zit nu op 10 sec. Zal 'es ff in jouw code duiken om te zien wat jij gedaan hebt.

Dat moet je die wel hebben

spoiler:

Alhier mijn code. Regel 15-50 is mijn originele langzame code, regel 53-70 de snellere.

[ThoNohT]

Het lijkt erop dat de imperatieve aanpak met mutable maps/dicts hier een stuk sneller is dan mijn functionele waarbij ik mijn immutable map de hele tijd update.

[Hydra]

GladstoneW schreef op dinsdag 15 december 2020 @ 10:21:
Dat moet je die wel hebben

spoiler:

Alhier mijn code. Regel 15-50 is mijn originele langzame code, regel 53-70 de snellere.

Cool, thanks. Ik ga he verder niet aanpassen; dan ben ik letterlijk 1 op 1 iemand anders z'n oplossing aan het overnemen. Wel mooi te zien dat gewoon een array gebruiken hier enorm veel efficienter is.

[Swedish Clown]

Vanavond even mee puzzelen maar ben benieuwd welke data structure in Erlang het snelste zal zijn dus zal wat benchmarks draaien met de verschillende oplossingen

Thanks @Daanoz nu heb ik ook een plekje op het Tweakers board

[ Voor 17% gewijzigd door Swedish Clown op 15-12-2020 10:36 ]

[dcm360]

GladstoneW schreef op dinsdag 15 december 2020 @ 10:21:
[...]

Dat moet je die wel hebben

spoiler:

Alhier mijn code. Regel 15-50 is mijn originele langzame code, regel 53-70 de snellere.

spoiler:

Maar gaat dit ook goed als ik in het begin een getal noem dat groter is dan het aantal turns?

[ydderf]

Dag 14 deel 2 ook afgerond. Totaal part 1 + part 2 in 13 sec.

spoiler:

Voor deel 2 heb ik het adres (=basis adres) uitgerekend waarbij alle X-en in de mask als nul beschouwd worden.
Vervolgens per mask voor elke X de decimale waarde bepaald en opgeslagen. Bijv. x10x geeft {8, 1}.
Hierna weet je dat je bij dit voorbeeld 2^2 adressen moet schrijven.
Basis adres + 0, basis adres + 1, basis adres + 8, basis adres + 1 + 8.

[Woy]

ydderf schreef op dinsdag 15 december 2020 @ 10:51:
Dag 14 deel 2 ook afgerond. Totaal part 1 + part 2 in 13 sec.

spoiler:

Voor deel 2 heb ik het adres (=basis adres) uitgerekend waarbij alle X-en in de mask als nul beschouwd worden.
Vervolgens per mask voor elke X de decimale waarde bepaald en opgeslagen. Bijv. x10x geeft {8, 1}.
Hierna weet je dat je bij dit voorbeeld 2^2 adressen moet schrijven.
Basis adres + 0, basis adres + 1, basis adres + 8, basis adres + 1 + 8.

Buiten het feit dat een dictionary zoals gezegd een eenvoudigere/snellere oplossing is, nog even twee opmerkingen over deze code:

C#:

if (memory.Where(m => m.adres == memAdres).Count() > 0)
{
    //Remove double record
    memory.RemoveAll(m => m.adres == memAdres);
}

De Count() > 0 is er inefficient, want hij moet de volledige list door om een count te berekenen. Een Any() is daar een stuk efficienter, aangezien die stopt bij de eerste match.

Tevens kun je die check weglaten en gewoon direct RemoveAll doen, aangezien die niet faalt als hij er 0 vind.

[GladstoneW]

dcm360 schreef op dinsdag 15 december 2020 @ 10:39:
[...]

spoiler:

Maar gaat dit ook goed als ik in het begin een getal noem dat groter is dan het aantal turns?

spoiler:

Nee, inderdaad niet. Deze optimalisatie werkt niet op alle inputs, maar wel op de puzzelinput.

[Soultaker]

Hydra schreef op dinsdag 15 december 2020 @ 10:04:
Day 15, voorlopige versie.

Brute-force-ish aanpak, doet er te lang over op deel 2 (24 seconden).

Een tip die het waarschijnlijk iets sneller maakt (maar hooguit een constante factor):

spoiler:

Je hoeft geen List<Int> op te slaan; een enkele Int volstaat. Immers is alleen de positie waarop een getal voor het laatst genoemd werd is van belang.

Wel moet je oppassen dat je de Map pas updatet nádat je de vorige voorkomen gecheckt hebt.

Oplossing in Python (bruteforce, zoals iedereen).

edit:
Ik kan het iets sneller maken door een list i.p.v. een dict te gebruiken; ongeveer 1 seconde in Python met PyPy.

[ Voor 11% gewijzigd door Soultaker op 15-12-2020 11:42 ]

[heuveltje]

Vanochted 20 min mee bezig geweest, maar kreegg nog niet het antwoord wat ik verwacht
En nog niet naar andermans antwoorden wil kijken :
the 2020th number spoken will be 436.

ze Bedoelen toch het nummer wat in ronde 2020 word uitgrsproken ?
Niet het 2020e unieke nummer wat uitgesproken word

[Hydra]

Soultaker schreef op dinsdag 15 december 2020 @ 11:23:
Een tip die het waarschijnlijk iets sneller maakt (maar hooguit een constante factor):

spoiler:

Je hoeft geen List<Int> op te slaan; een enkele Int volstaat. Immers is alleen de positie waarop een getal voor het laatst genoemd werd is van belang.

Wel moet je oppassen dat je de Map pas updatet nádat je de vorige voorkomen gecheckt hebt.

Dat was een oudere versie; dit is 'em nu.

spoiler:

Ik had eerder al in plaats van alle occurences alleen de laatste 2 onthouden in een array. Toen ging ik al van 25 naar 10 seconden. Nu nog een laatste aanpassing gemaakt dat 'ie de laatste 2 posities in 1 grote array opslaat, nu zit ik op 4.5 sec (dit is een oude laptop by the way).

Ik kan die array inderdaad halveren maarja, dan kan ik net zo goed iemand anders z'n code overnemen want dan is er niks 'eigens' meer aan

Daarbij moet ik nu 'es ff echt aan 't werk. Ze betalen me niet om eindeloos AoC submissions te optimaliseren

[ Voor 5% gewijzigd door Hydra op 15-12-2020 11:51 ]

[dcm360]

heuveltje schreef op dinsdag 15 december 2020 @ 11:49:
Vanochted 20 min mee bezig geweest, maar kreegg nog niet het antwoord wat ik verwacht
En nog niet naar andermans antwoorden wil kijken :
the 2020th number spoken will be 436.

ze Bedoelen toch het nummer wat in ronde 2020 word uitgrsproken ?
Niet het 2020e unieke nummer wat uitgesproken word

Niet echt in welke ronde, maar in welke beurt. Er wordt gevraagd naar het n-de getal, niet naar het laatste getal nadat iedereen n keer aan de beurt geweest is.

[ThoNohT]

heuveltje schreef op dinsdag 15 december 2020 @ 11:49:
ze Bedoelen toch het nummer wat in ronde 2020 word uitgrsproken ?
Niet het 2020e unieke nummer wat uitgesproken word

Dat bedoelen ze inderdaad. Heb je die kleine testjes ook nog gedaan, of het voorbeeld wat een voor een is uitgeschreven? Daar kun je mooi je rondes met de nummers checken.

[heuveltje]

ThoNohT schreef op dinsdag 15 december 2020 @ 11:51:
[...]

Dat bedoelen ze inderdaad. Heb je die kleine testjes ook nog gedaan, of het voorbeeld wat een voor een is uitgeschreven? Daar kun je mooi je rondes met de nummers checken.

Moet ik nog doen, maar ik moest werken.
Had nog geen tijd te debuggen waarom ik op een ander antwoord uitkwam

Dus nu zit ik al de halve dag in mijn hoofd te debuggen, wat de productivteit ook niet ten goede komt

Uberhaubt is die AOC niet goed voor mij, al meerdere keren half uur te laat, omdat ik toch nog iets werkend wou hebben voor ik vertrok

* heuveltje zwemt gelukkig nog in de tvt uren

[ Voor 16% gewijzigd door heuveltje op 15-12-2020 12:11 ]

[Varienaja]

GladstoneW schreef op dinsdag 15 december 2020 @ 10:21:

spoiler:

Alhier mijn code. Regel 15-50 is mijn originele langzame code, regel 53-70 de snellere.

Heel cool, die snelle methode . Ik ga vanavond kijken of ik mijn oplossing daarheen kan transformeren zonder teveel af te kijken.

Mijn oplossing voor Dag 15.

heuveltje schreef op dinsdag 15 december 2020 @ 12:10:
Uberhaubt is die AOC niet goed voor mij, al meerdere keren half uur te laat, omdat ik toch nog iets werkend wou hebben voor ik vertrok

Ik denk dat je baas in z'n handjes mag knijpen met iemand die in z'n vrije tijd programmeren oefent. Al onze oefening zal zich in de toekomst op het werk vast en zeker eens bewijzen.

[ Voor 28% gewijzigd door Varienaja op 15-12-2020 12:25 ]

[Hydra]

Varienaja schreef op dinsdag 15 december 2020 @ 12:23:
Ik denk dat je baas in z'n handjes mag knijpen met iemand die in z'n vrije tijd programmeren oefent. Al onze oefening zal zich in de toekomst op het werk vast en zeker eens bewijzen.

'Vrije tijd'

[Woy]

Het grootste probleem waar ik tot nog toe overigens tegenaan gelopen ben is dat Jetbrains blijkbaar nog niet echt goed support heeft voor de nieuwe C# 5 features. Zowel Rider als Resharper crashen continue bij mijn oplossing van dag 14

[ThoNohT]

C# 5 is niet echt meer nieuw?

[Woy]

ThoNohT schreef op dinsdag 15 december 2020 @ 12:51:
C# 5 is niet echt meer nieuw?

Ok, je hebt gelijk .net 5.0 en C# 9

[Hydra]

Gave uitleg trouwens over deze sequence: YouTube: Don't Know (the Van Eck Sequence) - Numberphile

Vind het wel cool dat ik na 5 jaar AoC nog steeds zo vaak nieuwe dingen leer

[Soultaker]

heuveltje schreef op dinsdag 15 december 2020 @ 11:49:
ze Bedoelen toch het nummer wat in ronde 2020 word uitgrsproken ?

Dat bedoelen ze inderdaad (het 2020e nummer in de reeks), maar let op dat er vanaf 1 geteld wordt, dus afhankelijk van hoe je het geïmplementeerd hebt moet je misschien een ronde eerder of later stoppen.

[Swedish Clown]

Heb even voor de lol wat benchmarks gedraait voor de verschillende data structures om de waardes in op te slaan en kom op interessante resultaten uit. Persistent term heb ik achterwege gelaten aangezien het redelijk kostbaar is om een write uit te voeren naar persistent_term dus dat heeft bij voorbaat weinig zin schat ik zo in.

Vanavond maar eens verder mee puzzelen en zien of ik het allemaal wat sneller kan laten lopen Mijn vermoeden is dat de lists:keystore/4 erg duur is aangezien deze als enige puur Erlang land door de list heen wandelt tot de key is gevonden om hem vervolgens te vervangen. De rest is allemaal als BIF/NIF geïmplementeerd en dus in C-land leeft.

Note: Dit is m'n eerste versie en ik heb 0 tijd besteed aan optimalisering van de code.

Part1

Storage Type	Time (us)
process dictionary	529
map	1275
ETS	1410
list	5136

De relevante code voor diegene die interesse heeft in hoe de verschillende data structures benaderd worden.

Erlang:

new_store(list, _) -> [];
new_store(map, _) -> #{};
new_store(process_dictionary, _) -> ignore;
new_store(ets, Name) -> ets:new(Name, [set]).

store(Num, Turns, Store, list) ->
  lists:keystore(Num, 1, Store, {Num, Turns});
store(Num, Turns, Store, map) ->
  maps:put(Num, Turns, Store);
store(Num, Turns, Store, ets) ->
  true = ets:insert(Store, {Num, Turns}),
  Store;
store(Num, Turns, _Store, process_dictionary) ->
  put(Num, Turns).

lookup(Num, Store, list) ->
  case lists:keyfind(Num, 1, Store) of
    false -> [];
    {_Key, Value} -> Value
  end;
lookup(Num, Store, map) ->
  maps:get(Num, Store, []);
lookup(Num, Store, ets) ->
  case ets:lookup(Store, Num) of
    [] -> [];
    [{_Key, Value}] -> Value
  end;
lookup(Num, _Store, process_dictionary) ->
  case get(Num) of
    undefined -> [];
    Value -> Value
  end.

destroy(_Store, list) -> ok;
destroy(_Store, map) -> ok;
destroy(_Store, process_dictionary) -> erase();
destroy(Store, ets) -> ets:delete(Store).

[ Voor 3% gewijzigd door Swedish Clown op 15-12-2020 17:24 ]

[ydderf]

Day 15 ook afgerond. Met behulp van een dictionary kom ik zo'n 4 seconde uit voor part 1 en 2 gezamenlijk.

@Woy en @DRaakje bedankt dat jullie de tijd hebben genomen om feedback te geven op mijn oplossing van dag 14. Wordt gewaardeerd!

[Woy]

ydderf schreef op dinsdag 15 december 2020 @ 16:56:
Day 15 ook afgerond. Met behulp van een dictionary kom ik zo'n 4 seconde uit voor part 1 en 2 gezamenlijk.

@Woy en @DRaakje bedankt dat jullie de tijd hebben genomen om feedback te geven op mijn oplossing van dag 14. Wordt gewaardeerd!

Nog 1tje dan

C#:

if ((i & 1) > 0) { offset += values[0]; } //0001
if ((i & 2) > 0) { offset += values[1]; } //0010
if ((i & 4) > 0) { offset += values[2]; } //0011
if ((i & 8) > 0) { offset += values[3]; }
if ((i & 16) > 0) { offset += values[4]; }
if ((i & 32) > 0) { offset += values[5]; }
if ((i & 64) > 0) { offset += values[6]; }
if ((i & 128) > 0) { offset += values[7]; }
if ((i & 256) > 0) { offset += values[8]; }
if ((i & 512) > 0) { offset += values[9]; }

if ((i & 1024) > 0) { offset += values[10]; }
if ((i & 2048) > 0) { offset += values[11]; }
if ((i & 4096) > 0) { offset += values[12]; }
if ((i & 8192) > 0) { offset += values[13]; }
if ((i & 16384) > 0) { offset += values[14]; }
if ((i & 32768) > 0) { offset += values[15]; }
if ((i & 65536) > 0) { offset += values[16]; }
if ((i & 131072) > 0) { offset += values[17]; }
if ((i & 262144) > 0) { offset += values[18]; }
if ((i & 524288) > 0) { offset += values[19]; }

Kun je makkelijker schrijven als

C#:

for(int bit = 0; bit < 20; bit++)
{
    if ((i & (1 << bit)) > 0) { offset += values[bit]; } //0001
}

En je comment bij 4 //0011 is niet correct, dat is natuurlijk 0100

[Dricus]

Zo, nog even mijn ultraslome oplossing van vanmorgen aan het refactoren geweest. Hij is nu zoveel mogelijk functional, maar voor de performance moest ik wel een concessie doen door mutable state te bewaren.

De performance van deel 2 is van 5 a 6 seconden naar zo'n 530 millisecondes gegaan.

spoiler:

En een array van Ints gebruiken om de state in bij te houden is enorm veel sneller dan een Map!

Dag 15 (Kotlin)

[Varienaja]

Wauw @Dricus 30 miljoen keer recursief dezelfde methode in. Dat krijg ik in Java niet voor elkaar

[Dricus]

Varienaja schreef op dinsdag 15 december 2020 @ 20:11:
Wauw @Dricus 30 miljoen keer recursief dezelfde methode in. Dat krijg ik in Java niet voor elkaar

Tail recursion FTW!

[eamelink]

Varienaja schreef op dinsdag 15 december 2020 @ 20:11:
Wauw @Dricus 30 miljoen keer recursief dezelfde methode in. Dat krijg ik in Java niet voor elkaar

Nee, hij gaat er geen 30 miljoen keer in, hij doen een while loop 30 miljoen keer, dat is juist het hele idee van de tail call optimization .

Probeer het eens met https://kag0.github.io/tail/ en laat me weten hoe het bevalt

[ydderf]

Woy schreef op dinsdag 15 december 2020 @ 17:02:
[...]

Nog 1tje dan

C#:

if ((i & 1) > 0) { offset += values[0]; } //0001
if ((i & 2) > 0) { offset += values[1]; } //0010
if ((i & 4) > 0) { offset += values[2]; } //0011
if ((i & 8) > 0) { offset += values[3]; }
if ((i & 16) > 0) { offset += values[4]; }
if ((i & 32) > 0) { offset += values[5]; }
if ((i & 64) > 0) { offset += values[6]; }
if ((i & 128) > 0) { offset += values[7]; }
if ((i & 256) > 0) { offset += values[8]; }
if ((i & 512) > 0) { offset += values[9]; }

if ((i & 1024) > 0) { offset += values[10]; }
if ((i & 2048) > 0) { offset += values[11]; }
if ((i & 4096) > 0) { offset += values[12]; }
if ((i & 8192) > 0) { offset += values[13]; }
if ((i & 16384) > 0) { offset += values[14]; }
if ((i & 32768) > 0) { offset += values[15]; }
if ((i & 65536) > 0) { offset += values[16]; }
if ((i & 131072) > 0) { offset += values[17]; }
if ((i & 262144) > 0) { offset += values[18]; }
if ((i & 524288) > 0) { offset += values[19]; }

Kun je makkelijker schrijven als

C#:

for(int bit = 0; bit < 20; bit++)
{
    if ((i & (1 << bit)) > 0) { offset += values[bit]; } //0001
}

En je comment bij 4 //0011 is niet correct, dat is natuurlijk 0100

Ik was het aan het typen en dacht ook al: “Dit is te vaak hetzelfde en er zit een logica in, dat moet simpeler kunnen”. Maar ik kwam ff niet op een andere oplossing. Maar zo te zien aan mijn commentaar was de meeste scherpte er al af.....

[MrHaas]

Nog ff flashback naar dag 14: toch nog even de oplossing geimplementeerd zoals ik hier beschreef: https://github.com/arjand...ob/main/day14/src/main.rs

Code is echt superranzig maar had geen zin meer om het op te ruimen. Qua snelheid is ie ongeveer even snel als de simulatie methode op de input maar deze runt iig op het example van deel 1 zonder out of memory te gaan .

[Swedish Clown]

Hier mijn oplosssing voor Dag 15 inclusief een partij boiler plate om de verschillende data structures te abstraheren en te kunnen testen voor hun performance. Dit is wat ik juist zo mooi vind aan AoC om verbaasd te zijn over hoe snel of hoe traag sommige data structures zijn voor bepaalde taken

Dag 15 (Erlang)

code:

27> day15:benchmark(part_1, [ets, map, list, process_dictionary, counters]).
Time for ets -> 652 us
Time for map -> 491 us
Time for list -> 2126 us
Time for process_dictionary -> 224 us
Time for counters -> 288 us
Time for dict -> 1793 us

28> day15:benchmark(part_2, [ets, map, process_dictionary, counters, list]).
Time for ets -> 17131967 us
Time for map -> 44155990 us
Time for process_dictionary -> 6420875 us
Time for counters -> 6834171 us

process_dictionary is de snelste

De tijd voor plain lists heb ik maar opgegeven voor part 2, mocht die ooit gedurende de nacht finishen, dan edit ik me post wel

[heuveltje]

Pfft. onderhand dag 15 ook af.
Veel te lang liggen zoeken naar een bug die uiteindelijk in de invoer leek te zitten

Wel grappig om te zien hoeveel impact debug optie heeft op de snelheid trouwens
Python runnen met debug optie in VS code, 22.5 sec.
Python runnen zonder debug optie in VS code : 15.7 sec

Voor de rest waag ik me even nog niet te veel aan optimaliseren

[DRaakje]

Pffff. zeg dat wel. Wat heb ik lopen klooien, uiteindelijk wel een oplossing waarbij deel 2 in 3 seconden klaar is. Ik kreeg gewoon niet helder wat er nou precies gebeurde. Achteraf toch beter moeten uitwerken ipv gewoon gaan code kloppen.

[heuveltje]

Kon het niet laten en ook dag 8 nog ingehaald

* heuveltje gaat nu snel naar bed

[ Voor 31% gewijzigd door heuveltje op 16-12-2020 01:18 ]

[ZieglerNichols]

Dag 16 Matlab: https://pastebin.com/wbsfq8Jb

Was een leuke mix van code en 'handmatig' wat delen oplossen. Soms is het sneller om iets zelf uit te werken dan om de code ervoor te schrijven

Update 8:10: Nu het handmatige deel ook maar in code gedaan: https://pastebin.com/py0rDiqR

[ Voor 19% gewijzigd door ZieglerNichols op 16-12-2020 08:11 ]

[Varienaja]

Jeemig de peemig. Wat zat ik mezelf in de knoop te denken vanmorgen. Uiteindelijk met een schone lei opnieuw begonnen, en floep: binnen een kwartier een oplossing voor onderdeel B.

[Dricus]

Dag 16 (Kotlin)

Eigenlijk niet al te moeilijk, maar ik kreeg het alsnog moeilijk met deel 2 door mijn eigen suffigheid. Combinatie van niet goed lezen

spoiler:

Je moet natuurlijk wel even alle ongeldige tickets negeren bij het reverse engineeren van de velden uit de nearby tickets!

en

spoiler:

Wanneer leer ik nou eens dat je een Long moet gebruiken als er vermenigvuldigd moet worden!

De oplossing is nu nog imperative. Later vandaag ga ik nog wel even kijken of ik hem functional kan maken.

[Hydra]

Dag 16

Eitje. Alles in 1 keer goed. Meeste tijd ging eigenlijk in 't parsen zitten.

[Emiel L]

Leuke opdracht vandaag. Mijn oplossing in Swift hier.

Met een runtime van 0.0005949759483337403 seconden was het ook niet lang wachten op een antwoord 😃.

[Woy]

Mmm, deel 1 had ik snel, en ook deel 2 heb ik snel een oplossing, maar niet het juiste antwoord. Helaas vandaag niet zoveel tijd, dus vanavond even verder kijken of ik de opdracht niet goed lees, of toch ergens een stomme fout gemaakt heb.

[Gilotto]

Ik ben pas bij dag 4 en vind het al best pittig. Zal wel aan de ervaring liggen

Wel mooi om eens een parser te schrijven.

Dag 5 is dan weer simpel

[ Voor 20% gewijzigd door Gilotto op 16-12-2020 16:49 . Reden: dag 5 ]

[Hydra]

Grappig. De uitvinder van de sequence van gister is een Nederlander en ik heb 'em ff op LinkedIn toegevoegd. Hij wist helemaal niet dat deze in AoC gebruikt werd Hoe cool is het dat je zo'n sequence submit en dat zoveel mensen erover leren!

[Hydra]

Gilotto schreef op woensdag 16 december 2020 @ 10:46:
Ik ben pas bij dag 4 en vind het al best pittig. Zal wel aan de ervaring liggen

Niet alleen werkervaring hoor, ook ervaring met dit soort code contests. Heel veel van deze opdrachten lijken op opdrachten van de afgelopen 5 jaar. Ik was in 2015 ook veel langer bezig

[eamelink]

Woy schreef op woensdag 16 december 2020 @ 10:39:
Mmm, deel 1 had ik snel, en ook deel 2 heb ik snel een oplossing, maar niet het juiste antwoord. Helaas vandaag niet zoveel tijd, dus vanavond even verder kijken of ik de opdracht niet goed lees, of toch ergens een stomme fout gemaakt heb.

Ik had hem ook fout, want ik had als laatste stap de cijfers opgeteld in plaats van vermenigvuldigd. Hopelijk jij ook

[armageddon_2k1]

Day 16 was easy-peasy!

En Kotlin blijft heerlijk. IntRanges for the win.

https://github.com/rj-cod...rjcoding/aoc2020/Day16.kt

Zaten een paar subtiliteiten in waar je op moest letten.

spoiler:

- Voor de error rate berekening kunnen er per ticket meerdere foute tussen zitten.
- Moet even goed nadenken over de eliminatie van valid fields in Part 2. Als er nog maar 1 field mogelijk is bij een positie is ie niet meer mogelijk bij andere posities. Maar dan moet je hem wel recursief weghalen.

Mooie bijkomstigheid van dit jaar AoC, ik haat Regex niet meer :-) Ik vind het zelfs erg handig!

[Dricus]

Hydra schreef op woensdag 16 december 2020 @ 10:47:
Grappig. De uitvinder van de sequence van gister is een Nederlander en ik heb 'em ff op LinkedIn toegevoegd. Hij wist helemaal niet dat deze in AoC gebruikt werd Hoe cool is het dat je zo'n sequence submit en dat zoveel mensen erover leren!

Om welke sequence gaat het dan precies? Ik was er al van overtuigd dat de opdracht van gisteren waarschijnlijk op een bestaande sequence gebaseerd was, maar ik heb hem tot nu toe niet kunnen vinden.

[heuveltje]

armageddon_2k1 schreef op woensdag 16 december 2020 @ 10:54:
Day 16 was easy-peasy!

En Kotlin blijft heerlijk. IntRanges for the win.

https://github.com/rj-cod...rjcoding/aoc2020/Day16.kt

Zaten een paar subtiliteiten in waar je op moest letten.

spoiler:

- Voor de error rate berekening kunnen er per ticket meerdere foute tussen zitten.
- Moet even goed nadenken over de eliminatie van valid fields in Part 2. Als er nog maar 1 field mogelijk is bij een positie is ie niet meer mogelijk bij andere posities. Maar dan moet je hem wel recursief weghalen.

Mooie bijkomstigheid van dit jaar AoC, ik haat Regex niet meer :-) Ik vind het zelfs erg handig!

Zat vanmorgen nog vast op het debuggen van de procedure om zo veel mogelijk ranges te reduceren in deel 1. Wel 1 van die ironische dingen. Minimaal een half uur bezig geweest, voor iets wat ik in 2 min met de hand had kunnen doen , en wat me hoogstens een halve seconde processing time gaat besparen. :x

Time management is blijkbaar niet mijn ding

[Mschamp]

Dricus schreef op woensdag 16 december 2020 @ 10:58:
[...]

Om welke sequence gaat het dan precies? Ik was er al van overtuigd dat de opdracht van gisteren waarschijnlijk op een bestaande sequence gebaseerd was, maar ik heb hem tot nu toe niet kunnen vinden.

de Van Eck sequence:
https://oeis.org/A181391

[GladstoneW]

Mschamp schreef op woensdag 16 december 2020 @ 11:01:
[...]


de Van Eck sequence:
https://oeis.org/A181391

Ter toevoeging (ook al eerder gepost): Youtube: Don't Know (the Van Eck Sequence) - Numberphile

spoiler:

Filmpje bevat ook het bewijs dat de sequence niet cyclisch kan zijn, dus alleen brute force op te lossen (tenzij je input al cyclisch zou zijn, maar dat is natuurlijk niet zo).

[ Voor 5% gewijzigd door GladstoneW op 16-12-2020 11:05 ]

[evanraalte]

Vandaag was veel werk, wel happy met m'n oplossing

https://github.com/evanra...lob/master/day16/day16.py

[Woy]

eamelink schreef op woensdag 16 december 2020 @ 10:54:
[...]


Ik had hem ook fout, want ik had als laatste stap de cijfers opgeteld in plaats van vermenigvuldigd. Hopelijk jij ook

Nee dat had ik wel goed. Het was een simpele overflow bij de vermenigvuldiging, een L toevoegen bij de seed voor aggregate loste het op.

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

Niet echt de meest efficiente oplossing overigens, maar ik vind het wel prima zo

spoiler:

Het is natuurlijk veel sneller om gewoon op te slaan wat de opties zijn, en die weg te strepen totdat er nog maar 1 is, in plaats van elke keer alle resterende opties weer opnieuw te berekenen.

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

[FrankMennink]

eamelink schreef op woensdag 16 december 2020 @ 10:54:
[...]


Ik had hem ook fout, want ik had als laatste stap de cijfers opgeteld in plaats van vermenigvuldigd. Hopelijk jij ook

Ik dank u hartelijk, maakte precies dezelfde fout en zat al een halfuur blind te staren waarom het niet klopte

[Hydra]

AoC is wel vaak een kwestie van goed lezen. Dat was vorig jaar nog een stuk erger met die IntCode opdrachten.

[ThoNohT]

Dag 16 in F#. Lekker veel parsers kunnen schrijven hier. Dit vind ik wel een mooi voorbeeld van hoe krachtig zo'n simpele parsers al zijn op zo'n ingewikkelde input.

Woy schreef op woensdag 16 december 2020 @ 11:54:

spoiler:

Het is natuurlijk veel sneller om gewoon op te slaan wat de opties zijn, en die weg te strepen totdat er nog maar 1 is, in plaats van elke keer alle resterende opties weer opnieuw te berekenen.

spoiler:

Ik had geobserveerd dat als je ze sorteert op aantal mogelijke opties, er steeds eentje minder was. Dus ik begon met de eerste, die maar een optie had, en bouwde zo een set op met gevallen die al geweest waren, en streepte deze weg uit het volgende element in de lijst. Hier kwam heel netjes een lijstje met 1 mogelijkheid per index uit.

[eamelink]

Ja ik was ook bezorgd dat ik het niet zou redden met wegstrepen, en dat je zou moeten kiezen en backtracken, maar dat was gelukkig niet nodig

[heuveltje]

GladstoneW schreef op woensdag 16 december 2020 @ 11:04:
[...]


Ter toevoeging (ook al eerder gepost): Youtube: Don't Know (the Van Eck Sequence) - Numberphile

spoiler:

Filmpje bevat ook het bewijs dat de sequence niet cyclisch kan zijn, dus alleen brute force op te lossen (tenzij je input al cyclisch zou zijn, maar dat is natuurlijk niet zo).

Ah interessant, had afgelopen keer nog een tijdje lopen puzzelen met de output.
Het leek mij dat er een herhalend patroon in moest zitten, maar ik kon het niet ontdekken

[Swedish Clown]

Geen idee of dit al eerder gedeeld is in in dit topic? Ik kon het niet vinden in ieder geval

Advent of Code: Behind the Scenes (Programming Puzzles)

[YouTube: Advent of Code: Behind the Scenes (Programming Puzzles)]

[CMG]

Helemaal vergeten om hier te vermelden Vorig jaar Advent of Code ontdekt (en meegedaan met private leaderboard, maar ik sta niet op tijd op om de challenge zo snel mogelijk te doen ), dit jaar besloten om elke dag de challenges te live-streamen en videos met annotaties naar YouTube te uploaden.

Tot nu toe een hoop lol gehad dit jaar. Problemen tot nu toe: dag 7 deel 2, dag 10 deel 2 en dag 15 (was van alles aan de hand, kreeg links en rechts berichtjes en om 10:00 zou een afspraak op de stoep staan), aangezien ik niet onbeperkt de tijd heb (run mijn eigen software bedrijf), heb ik dus al een paar keer moeten stoppen zonder een volledige oplossing, maar tot nu toe nog elke dag daarna begonnen met wat nog niet gedaan was en afgemaakt; benieuwd hoe de rest van de challenge gaat.

Favorieten tot nu toe?

Dag 8: mini-assembly
Dag 11; game of life
Dag 12; bootje
Dag 16: tickets

[Woy]

Ik zie dat ik overigens mijn record verbroken heb. Tot nog toe was 2015 het jaar dat ik het het langst vol gehouden had t/m dag 14

[Swedish Clown]

Same here, ben bij lange na nog nooit zo ver gekomen als dit jaar. Moet wel zeggen dat dit jaar ook veel leuker is dan vorig jaar met op zichzelf staande puzzels in plaats van een compleet software pakket in elkaar schroeven... (IntCode anyone...). Dat doe ik op me werk wel of wanneer ik bijdraag aan Open Source projecten

[ Voor 13% gewijzigd door Swedish Clown op 16-12-2020 16:39 ]