Advent of Code 2020

[dcm360]

bakkerjangert schreef op dinsdag 8 december 2020 @ 13:07:
In de opdracht staat duidelijk aangegeven dat je uit de loop moet ontsnappen door een enkel instructie te wijzigen. Als je een instructie wijzigt buiten je originele loop zal dat geen effect hebben (want die roep je nooit aan) en kun je dus direct overslaan. Wel mee eens dat de optimalisatie niet groot en zelfs 0 zou kunnen zijn.

De grap is dan wel weer dat als je alle instructies hebt uitgevoerd in de initiële run, het mogelijk is om met 1 iteratie door de instructies vast te stellen welke wijziging er voor zorgt dat het programma eindigt. Je hebt dan 2 gevallen:
- De laatste instructie in de lijst is een jmp, en moet een nop worden
- Een nop veranderen in een jmp springt uit het programma

Het meest efficiënte wat ik nu kan bedenken:
- Neem alle uitgevoerde instructies
- Check voor alle uitgevoerde instructies of wisselen leidt naar een onuitgevoerde instructie. Indien niet zo, negeer deze
- Voer de programma's met de resterende wissels uit. Dat zijn er hooguit ½n vanwege de check hiervoor.

[diabolofan]

dcm360 schreef op dinsdag 8 december 2020 @ 13:03:
[...]

Ja, maar je kan op deze manier dus de instructies overslaan die niet op het initiële pad zaten. Als je namelijk een instructie buiten het initiële pad aanpast, verandert het pad niet en zit je weer in dezelfde loop.

Ah precies, ik snap 'm

[MrHaas]

Oplossing zonder bruteforce:

spoiler:

Ik maak 2 lijsten van nodes: lijst die naar end kan connecten en lijst met alle nodes die benaderd kunnen worden vanuit begininstructie. Daarna kijk ik voor elke node in de 2e lijst of de targetindex van de swap in de 1e lijst zit, zo ja, dan zorgt swappen ervoor dat start met end verbonden kan worden.

[ydderf]

Van de 625 regels (instructies) zijn er bij mij in het initiele pad(van deel 1) 94 instructies die "nop" of "jmp" zijn. Dus door alleen die te proberen voor deel 2, kan je al wel behoorlijk wat besparen.

[P_Tingen]

Dit zou de tijd kunnen verkorten omdat je niet het beginstuk iedere keer opnieuw doet:

code:

lees instructie

als instructie = jmp of nop:
  bewaar de state zoals die op dat moment is. 
  wissel jmp <-> nop
  test de uitkomst
  als geen infinite-loop dan klaar!
  anders haal bewaarde state weer terug

verwerk instructie
goto begin

[indexample]

part 2: found exit!
last acc = 1403 after 135 tries

optimalisatie met alleen nop/jmp uit initiele run:

part 2: found exit!
last acc = 1403 after 17 tries

[ Voor 22% gewijzigd door indexample op 08-12-2020 14:55 ]

[CTVirus]

spoiler: dag 4.1 (98 chars)

p$<.read.split(/\n\n/).map{|l|l.split /\W/}.count{|l|x=(%w{byr iyr eyr hgt hcl ecl pid}-l).empty?}

spoiler: dag 4.2 (371 chars)

p$<.read.split(/\n\n/).map{|l|l.split /[^:#\w]+/}.map{|l|l.map{|i|i.split ?:}.to_h}.count{|l|('1920'..'2002')===l['byr']&&('2010'..'2020')===l['iyr']&&('2020'..'2030')===l['eyr']&&(/^(\d+)cm$/===l['hgt']&&('150'..'193')===$1||/^(\d+)in$/===l['hgt']&&('59'..'76')===$1) &&!(l['hcl']!~/#[\da-f]{6}$/)&&%w{amb blu brn gry grn hzl oth}.any?(l['ecl'])&&!(l['pid']!~/^\d{9}$/)}

[Varienaja]

Op veler verzoek gesplitst per dag: Dag 8.

[Creepy]

Ik loop een dagje achter maar dag 7 is ook af. Zo nog eens met dag 8 aan de slag. Weer niet heel erg spannend. Ik was nog even bang dat mijn naive oplossing voor het aantal bags een geheugen probleem zou worden, maar dat was niet het geval.

[ThoNohT]

Dag 8 in F#

Kon het inmiddels niet meer laten om er toch een parsertje op los te laten. Het is nog niet nodig, maar soms toch ook wel leuk om te bouwen. Ik hoop dat ik daarmee mooi in de volgende opdrachten kan gaan uitbreiden.

[WernerL]

Dag 8 ook weer afgerond. Gewoon voor de meest straight forward oplossing gegaan. Dus bruteforce voor deel 2.

https://github.com/Werner...blob/main/src/08/index.ts

[Creepy]

Het eerste deel van part 8 was een eitje, maar deel 2 heb ik wat langer moeten debuggen totdat ik het juiste antwoord had. Zie hier

spoiler:

Niet bruteforce, maar een history stack bijhouden en een laatst gewijzigde index. BIj een loop net zolang instructies van de history poppen totdat je geen acc tegen komt, of net zo lang poppen totdat je bij de laatste gewijzigde instructie bent, die weer terug wijzigen en verder poppen tot de volgende jmp of nop.

[Varienaja]

Heel interessant @Creepy! Ik had eerlijk gezegd het gevoel dat brute-forcen de enige mogelijkheid was om onderdeel B vandaag op te lossen. Immers: je weet niet welke instructie je moet omkeren. Dus je moet gewoonweg allemaal na elkaar uitproberen.
Je kunt inderdaad de state gaan onthouden, zodat je het gemodificeerde programma niet steeds vanaf het begin moet gaan uitvoeren, maar aangezien dit programma sowieso wild heen en weer jumped is het maar de vraag hoeveel je effectief bespaart.

Anyway. Jij hebt net als ik Java gebruikt, dus ik kon lekker makkelijk vergelijken. Gek genoeg komt daar het volgende uit (4 runs getimed):

Varienaja Puzzle08: 0,069s 0,075s 0,078s 0,068s
Creepy Day8: 0,101s 0,125s 0,107s 0,104s

Hoe vaak ik de tests ook uitvoer, mijn brute-force is iets sneller. En dat terwijl jij enkel en alleen de puzzles oplost, en mijn code ook de voorbeeld-input nog even meeneemt. Wellicht dat jouw oplossing met nog grotere input op een gegeven moment gaat winnen, maar ik voel me met dit resultaat gesterkt in mijn beslissing geen onderzoek te doen naar iets efficiënters als brute-force.

[Creepy]

Is dat alleen mijn algoritme getest? Of de volledige code? Want als ik zo kijk denk ik dat jouw code een stukje efficienter de boel parsed in vergelijking met de Scanner's en Instructions die ik elke keer aanmaak. Ik ben wel benieuwd wat er gebeurd als je mijn algoritme in jouw code daadwerkelijk inbouwd. Maar goed, wat zijn we aan het optimaliseren, 101ms vs 68ms

En ik was er een beetje vanuit gegaan dat de input te groot zou zijn om maar elke keer dom te bruteforcen, maar dat blijkt dus van niet.

[ Voor 15% gewijzigd door Creepy op 08-12-2020 21:26 ]

[Osxy]

Ben in C# bij deel 2 voor semi brute force gegaan.

Haal lijst op van alle potentiele replacements, doe replacement, test die nieuwe input totdat ik het programma kan afdraaien.

Kom zelfs daarmee nog op 23ms. sorry, 56ms.

23ms is alleen als ik part a en b achter elkaar draai en er dus al wat just-in-time compiling heeft plaats gevonden

https://github.com/osxy/A...2020/AoC2020/Days/Day8.cs

[ Voor 34% gewijzigd door Osxy op 08-12-2020 21:40 ]

[Varienaja]

Ik heb jouw main methode en mijn testDay8 methode getimed om te vergelijken. Daarin worden zowel A als B uitgerekend. En het gaat inderdaad qua cpu-tijd inderdaad nergens over Maar ik houd van efficiënte code, dus ben jouw idee aan het uitpluizen. Het is een heel nette oplossing!

[Caelorum]

ThoNohT schreef op maandag 7 december 2020 @ 08:34:
Dag 7 in F#

Eigenlijk moet ik er nog staartrecursie van maken bij part 2. Maar, misschien later. Het is nu nog niet heel belangrijk, want ik krijg het antwoord gewoon snel zonder overflows.

Ik loop inmiddels een dag achter, maar wel leuk om te zien hoe verschillend de oplossing is. Het lukte me niet om het "mooi" te doen met regexen, dus maar fparsec gebruikt om een parser te schrijven en het resultaat in een onetime mutable dictionary te stoppen.

[Down]

Deze deed me denken aan een aantal puzzels uit voorgaande edities. Weer lekker los gegaan met C# (deel 1 en deel 2).

Dricus schreef op dinsdag 8 december 2020 @ 08:53:
Dag 8 (Kotlin)

Erg leuke opdracht weer! Tot nu toe zijn de opdrachten erg geschikt om wat mentale ochtengymnastiek mee te doen .

spoiler:

Dit was een hele leuke gelegenheid om de support voor tail recursion in Kotlin eens te gebruiken om zo een functional style oplossing te maken voor een probleem dat lijkt te schreeuwen om een imperatieve oplossing.

Mooi werk. Ik had juist het gevoel van "nou, laat ik deze maar eens imperatief doen dan" .

Woy schreef op dinsdag 8 december 2020 @ 08:22:
https://github.com/rverst...de2020/blob/main/Day08.cs

Ik heb het nu nog een beetje snel in elkaar gezet, want kan het wel te veel overengineeren, maar je weet toch niet exact wat er gaat komen.

Grappig hoe erg onze oplossingen op elkaar lijken . Ik heb nooit zin om extra classes te definiëren dus gebruik tuples, maar Records zijn misschien nog wel mooier. Leest wel fijner weg, maar ben er nog niet zo aan gewend.

[Caelorum]

ThoNohT schreef op dinsdag 8 december 2020 @ 18:06:
Dag 8 in F#

Kon het inmiddels niet meer laten om er toch een parsertje op los te laten. Het is nog niet nodig, maar soms toch ook wel leuk om te bouwen. Ik hoop dat ik daarmee mooi in de volgende opdrachten kan gaan uitbreiden.

Parsers maken het toch ook wel weer handig. Is er overigens een reden waarom je een eigen parser gebruikt ipv fparsec?

https://github.com/ajeckm.../blob/master/day8/day8.fs <-- wel een bruteforce methode, maar ach.. het werkt

[Varienaja]

Dag 9. Nog steeds niet heel moeilijk. Maar o, o, o, wat moet je overal secuur zijn! Het heeft me weer het nodige tijdverlies opgeleverd bij het debuggen. Maar nu heb ik 'm!

[ZieglerNichols]

Dag 9 in Matlab: https://pastebin.com/Yaq561Zx

Ik was even in de war met de uiteg bij deel 1, omdat het eerste number opeens 20 werd i.p.v. 1, maar de range van nummers waarin je moest zoeken bevatte dan wel weer 1. Ik heb dat maar genegeerd en gewoon altijd de vorige 25 nummers bewaard en dat werkte.

[ThoNohT]

Caelorum schreef op dinsdag 8 december 2020 @ 23:50:
Is er overigens een reden waarom je een eigen parser gebruikt ipv fparsec?

Ik vind het mooi om te (laten) zien hoe simpel het is om een eigen parser combinator library op te zetten (ok de performance is niet zo goed als fparsec, maar ik verwacht geen hele projecten te hoeven gaan parsen). En een van mijn regels was ook dat ik geen externe libraries wilde gebruiken. Voor wat ik in dag 8 heb gedaan is zelfs de library die ik nu erin heb gezet al overkill, maar ik heb ze allemaal al eerder gemaakt dus wilde een redelijk complete basis neerzetten waar ik mee verder kan gaan. Ik verwacht dat ik er wel meer van zal kunnen gebruiken in de komende dagen.

[dcm360]

Toch wel weer tegen een klassiek probleempje aan weten te lopen: sommige invoergetallen passen niet in een int. Het mooiste is nog wel dat ik daar pas achter kwam bij het oplossen van het 2e deel, toen ik alle getallen ging parsen in plaats van direct een sliding window over een iterator te plaatsen. Voor de rest was het vooral een kwestie van goed lezen, toch met wat slordigheidjes enkele pogingen gedaan over het matchen van het gegeven voorbeeld. Mijn oplossing voor dag 9

[Hydra]

Dag 9 in Kotlin

Leuke opdracht. In deel 2 ging ik even een beetje nat omdat ik de opdracht niet goed gelezen had. Nog maar even nadenken over hoe ik deel 2 op een functionele ipv iteratieve manier op kan lossen...

[Dricus]

Dag 9 (Kotlin)

Deel 2 was even puzzelen, voornamelijk om het in functional style op te lossen. Maar verder weer heel goed te doen. Het blijft gaaf om te zien hoe je met functional style veel meer gericht bent op het wat dan op het hoe.

[Mschamp]

Dag 9 in C#
Viel op zich nog mee. En door eerdere puzzels de valkuil al kunnen ontwijken
https://github.com/mscham.../blob/master/2020/Day9.cs

[Gilotto]

Zo, eindelijk weer tijd gevonden om verder te puzzelen.
Dag 2 is gelukt (F#)
https://github.com/Gilotto/AdventOfCode/blob/main/Day2.fs

Ik loop nog flink achter...

Dag 3 is ook klaar
https://github.com/Gilotto/AdventOfCode/blob/main/Day3.fs

[ Voor 20% gewijzigd door Gilotto op 09-12-2020 10:51 ]

[ThoNohT]

Dag 9 in F#
Tweede opdracht was wel grappig. Geen brute force als in alle combinaties proberen, maar recursief programmaatje dat gewoon nummers achter elkaar plakt zolang het kan, en backtrackt zodra hij over de limiet is gegaan.

[nescafe]

Hmm, bij mij is het antwoord goed ondanks dat ik geen rekening heb gehouden met de voorwaarde "the two numbers in the pair must be different". Jammer

Dag 9 in C# (LINQPad) met gebruik van MoreEnumerable pkg.

[armageddon_2k1]

Day 9 in Kotlin

Ben er erg tevreden mee. Heb een mooie tailrec functie gemaakt en part 2 mooi in een one-liner (voor leesbaarheid over meerdere regels, maar soit).
Heb wel een extension functie gemaakt op Collection<Long> om de min en max uit te rekenen.

Heb het mooi functioneel kunnen houden zelfs.

[ Voor 13% gewijzigd door armageddon_2k1 op 09-12-2020 09:00 ]

[Dricus]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 08:55:
Day 9 in Kotlin

Ben er erg tevreden mee. Heb een mooie tailrec functie gemaakt en part 2 mooi in een one-liner (voor leesbaarheid over meerdere regels, maar soit).
Heb wel een extension functie gemaakt op Collection<Long> om de min en max uit te rekenen.

Heb het mooi functioneel kunnen houden zelfs.

Cool, zo'n "functional brute force" . Jouw manier van oplossen speelde ook wel door mijn hoofd, maar de premature optimizer in mij wees dat idee snel van de hand .

[armageddon_2k1]

@Dricus Hij is bloedje snel (18ms en 22ms respectievelijk, inclusief 2x de input inladen), dus optimaliseren zal wel . Lekker sequences gebruiken en gaan met die banaan.

[ Voor 21% gewijzigd door armageddon_2k1 op 09-12-2020 09:17 ]

[ydderf]

Dag 9 in C# is hier ook gelukt. Met voor mij een persoonlijk succesje. Deel 1 geprogrammeerd en 1x op "run" gedrukt en hij gaf meteen het juiste antwoord. Deel 2 helaas ff een i++ vergeten....

[eamelink]

Dit was wel een leuke inderdaad

Bij dit soort dingen merk ik altijd wel dat als je het een tijdje niet gedaan hebt, je allerlei standaard functies bent vergeten. Typisch val ik dan op een handgemaakte recursieve functie terug.

[ydderf]

Van dat vergeten heb ik niet zo veel last. Maar dat komt meer doordat ik veel functies uberhaubt niet ken. Dus mijn oplossingen zijn ook altijd redelijk straight forward.

@armageddon_2k1 Hoe berekenen jullie die tijd? Bij mij start ik een stopwatch aan het begin van de code en stop ik hem net voor de "Console.WriteLine("Result is:....")". Ik werk dan in Visual Studio Code en start mijn appicatie in de terminal met "dotnet run". Voor dag 9 kom ik dan op 7msec uit voor deel 1 en 2 samen.
Is dat een methode waarmee ik de tijd kan vergelijken met de tijden die jullie noemen?
(niet dat ik me echt met de tijd bezig hou, een oplossing vinden is soms al uitdagend genoeg voor mij...)

[armageddon_2k1]

@ydderf Ik heb een test-suite die alle Quiz-vragen doorloopt. Per test in die suite geeft mijn IDE mooi aan hoeveel ms ie over die test deed. Zodoende. Heb er verder niet over nagedacht ofzo. Zal vast niet superaccuraat zijn, maar geeft de orde-grote aan. Als iets 25ms duurt vind ik het prima. Als iets 25s duurt niet.

[evanraalte]

https://github.com/evanra.../blob/master/day9/day9.py

Goed lezen is een kunst . Heb geprobeerd om het een beetje efficient te doen, maar het ging al vrij snel dus niet al te veel moeite ingestopt achteraf.

[Down]

Dag 9 in C# (deel 1 en deel 2).

Ook hier deel 1 functioneel opgelost en deel 2 imperatief. Misschien vanavond nog even kijken of ik tijd heb om deel 2 ook functioneel op te lossen.

Langzaam maar zeker gaat het niveau omhoog. Ik ben benieuwd wanneer de eerste puzzel komt waar ik een heel weekend aan ga verkloten.

[Dricus]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 09:16:
@Dricus Hij is bloedje snel (18ms en 22ms respectievelijk, inclusief 2x de input inladen), dus optimaliseren zal wel . Lekker sequences gebruiken en gaan met die banaan.

Ja, eensch. Mijn oplossing is eigenlijk net zo brute force en is ook snel zat, dus dikke prima zo.

[Creepy]

Varienaja schreef op dinsdag 8 december 2020 @ 21:36:
Ik heb jouw main methode en mijn testDay8 methode getimed om te vergelijken. Daarin worden zowel A als B uitgerekend. En het gaat inderdaad qua cpu-tijd inderdaad nergens over Maar ik houd van efficiënte code, dus ben jouw idee aan het uitpluizen. Het is een heel nette oplossing!

Ik gok dat de Stack vervangen met een Dequeue ook wel eens kan helpen....... een Stack is threadsafe ala Vector, een ArrayDequeue niet, dus dat zou ook alweer aardig moeten schelen.. affijn. Op naar dag 9.

[MueR]

Dag 9 in PHP. Vanochtend ook eindelijk toegekomen aan deel twee van dag 8, want het was veel te druk gisteren

[Hydra]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 08:55:
Day 9 in Kotlin

Ben er erg tevreden mee.

Terecht! Mooier dan die van mij IMHO.

[armageddon_2k1]

Hydra schreef op woensdag 9 december 2020 @ 11:23:
[...]


Terecht! Mooier dan die van mij IMHO.

"De dag die je wist dat zou komen"

[Hydra]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 11:29:
"De dag die je wist dat zou komen"

LOL

Ga part 2 ook nog refactoren hoor; kreeg ik alleen vanochtend niet meer voor elkaar

[Woy]

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

Ik heb weer voor de snelle eenvoudige oplossing gekozen, want had er eigenlijk geen tijd voor

[DataGhost]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 08:55:
Day 9 in Kotlin

Ben er erg tevreden mee. Heb een mooie tailrec functie gemaakt en part 2 mooi in een one-liner (voor leesbaarheid over meerdere regels, maar soit).
Heb wel een extension functie gemaakt op Collection<Long> om de min en max uit te rekenen.

Heb het mooi functioneel kunnen houden zelfs.

Mooi, maar ik krijg de kriebels van je hardcoded antwoord van part 1 in part 2 Kan je daar niet een call naar part1() in doen?

[eamelink]

Woy schreef op woensdag 9 december 2020 @ 12:16:
https://github.com/rverst...de2020/blob/main/Day09.cs

Ik heb weer voor de snelle eenvoudige oplossing gekozen, want had er eigenlijk geen tijd voor

Ik vind deel twee wel erg fraai; de startindex van de sum ophogen zodra je over de zoekwaarde heenkomt

[nescafe]

Woy schreef op woensdag 9 december 2020 @ 12:16:
https://github.com/rverst...de2020/blob/main/Day09.cs

Mooi opgelost (part 2)!

Om te voldoen aan "find a contiguous set of at least two numbers" zou je nog de voorwaarde || start == end kunnen toevoegen aan je while-conditie, zodat hij door blijft zoeken als de range te klein is.

[ Voor 10% gewijzigd door nescafe op 09-12-2020 12:57 ]

[armageddon_2k1]

DataGhost schreef op woensdag 9 december 2020 @ 12:37:
[...]

Mooi, maar ik krijg de kriebels van je hardcoded antwoord van part 1 in part 2 Kan je daar niet een call naar part1() in doen?

Huh?

[jelknab]

ik krijg met de testinput voor part 2: 25, 40, 62. Dit summed ook netjes naar 127, maar is dus blijkbaar niet de reeks die mijn programma zou moeten outputten, erg frustrerend.

Nog nooit zolang met een dag bezig geweest .

Zie al wat fout gaat, slecht gelezen .

[ Voor 8% gewijzigd door jelknab op 09-12-2020 13:15 ]

[Creepy]

Zo, en dag 9 ook weer af https://github.com/CodeEn...dventofcode2020/Day9.java

En idd, mooie oplossing Woy, uiteindelijk verschuift het window gewoon waardoor je dat kan doen. Had ik ook aan moeten denken

[DataGhost]

armageddon_2k1 schreef op woensdag 9 december 2020 @ 12:57:
[...]


Huh?

Heh? Gek. Ik zou toch zweren dat ik dat hardcoded zag staan.

[ydderf]

@jelknab Je moet een aansluitende range van getallen hebben. Dus niet een willekeurige combinatie

[ Voor 0% gewijzigd door ydderf op 09-12-2020 13:17 . Reden: typo ]

[DataGhost]

jelknab schreef op woensdag 9 december 2020 @ 13:10:
ik krijg met de testinput voor part 2: 25, 40, 62. Dit summed ook netjes naar 127, maar is dus blijkbaar niet de reeks die mijn programma zou moeten outputten, erg frustrerend.

Nog nooit zolang met een dag bezig geweest .

Zie al wat fout gaat, slecht gelezen .

Ik zou stap 2 nog eens lezen dan want je getallen zijn fout.
Edit: ah dat had je ondertussen zelf ook door

[ Voor 5% gewijzigd door DataGhost op 09-12-2020 13:16 ]

[heuveltje]

Dus zover hebben :
We met onze declaraties gesjoemeld om die goed te keuren ook al is dat niet het geval.
De beveiliging van een winkel omzeild
De Douane omzeild door het complete systeem te hacken.
Buiten alle systemen om een zetel in een vliegtuig gegenereerd.

En nu zijn we dat vliegtuig aan het hacken.

Ik begin een behoorlijke criminele vibe op te pikken voor deze vakantie !

[ Voor 12% gewijzigd door heuveltje op 09-12-2020 14:34 ]

[jelknab]

Mijn C# oplossing voor vandaag (@ydderf thanks, domme fout van mij).
https://github.com/jelkna...0Code%202020/Day9/Day9.cs

[Woy]

nescafe schreef op woensdag 9 december 2020 @ 12:54:
[...]
Om te voldoen aan "find a contiguous set of at least two numbers" zou je nog de voorwaarde || start == end kunnen toevoegen aan je while-conditie, zodat hij door blijft zoeken als de range te klein is.

Ah, je hebt gelijk, daar heb ik helemaal overheen gelezen, geluk dat er dan geen entry met exact die waarde was voordat ik de range had.

[dcm360]

Stiekem deed mijn oplossing ook al hetzelfde als die van Woy, maar dan iets minder efficiënt (want de hele tijd opnieuw de sum uitrekenen is nergens voor nodig). Aangezien ik het niet kon laten, heb ik toch maar een verbeterde versie gemaakt. Daarmee is het ook de eerste deelopdracht tot zover waarbij het berekenen van een antwoord op mijn laptop binnen 1ms lukt.

In zekere zin is mijn oplossing daarmee ook volledig functioneel (was het al eigenlijk), tenzij een while-loop vermommen als tail-recursive functie niet telt.

[MaNDaRK]

Waar ik dag 7 nog steeds niet af heb, toch maar even 9 gemaakt. Vond hem erg leuk.

En ik denk dat ik een mooie, leesbare oplossing heb in Python, part #1 en #2

[Gimmeabrake]

Ik had gisteren een bruiloft, dus zojuist dag 8 (#1, #2) en 9 (#1, #2) opgelost in PHP.

Woy schreef op woensdag 9 december 2020 @ 12:16:
https://github.com/rverst...de2020/blob/main/Day09.cs

Ik heb weer voor de snelle eenvoudige oplossing gekozen, want had er eigenlijk geen tijd voor

Damn, zo kort kan het ook. Mijn oplossing voor deel 2 is soort van hetzelfde, alleen dan véél omslachtiger

[armageddon_2k1]

ydderf schreef op woensdag 9 december 2020 @ 13:14:
@jelknab Je moet een aansluitende range van getallen hebben. Dus niet een willekeurige combinatie

Ja dat had ik dus ook.... en de willekeurige combinatie is wat moeilijker dan de aansluitende range, want dat is gewoon een window. Had hem zelfs mooi tail-recursive gemaakt. Nouja, gestashed voor te toekomst

[Caelorum]

ydderf schreef op woensdag 9 december 2020 @ 09:48:
[...]
@armageddon_2k1 Hoe berekenen jullie die tijd? Bij mij start ik een stopwatch aan het begin van de code en stop ik hem net voor de "Console.WriteLine("Result is:....")". Ik werk dan in Visual Studio Code en start mijn appicatie in de terminal met "dotnet run". Voor dag 9 kom ik dan op 7msec uit voor deel 1 en 2 samen.
Is dat een methode waarmee ik de tijd kan vergelijken met de tijden die jullie noemen?
(niet dat ik me echt met de tijd bezig hou, een oplossing vinden is soms al uitdagend genoeg voor mij...)

Als je het echt goed wilt doen pak je benchmarkdotnet

[veldsla]

Korte runtimes zijn best wel variabel, dus een looped benchmark is vast aan te bevelen. cpu governor op performance zetten en alle problemen achter elkaar runnen helpt ook.

Ik vind dag 9 een leuke. Performance valt ook niet tegen. Alle dagen tot nu toe net iets meer dan 2ms, waarvan 1.3ms parse en ruim 600µs solve:

code:

$ RUSTFLAGS="-C target-cpu=native" cargo run --release -- --all
    Finished release [optimized] target(s) in 0.02s
     Running `target/release/aoc2020 --all`
day parse      part1     part2     total      output     
1   24.343µs   2.859µs   1.899µs   29.101µs   539851     212481360
2   231.085µs  21.886µs  74.231µs  327.202µs  465        294
3   96.446µs   1.641µs   5.749µs   103.836µs  164        5007658656
4   402.399µs  56.271µs  50.583µs  509.253µs  200/265    116/265
5   55.847µs   960ns     22.584µs  79.391µs   901        661
6   109.532µs  8.96µs    17.143µs  135.635µs  6565       3137
7   288.766µs  135.337µs 4.164µs   428.267µs  332        10875
8   45.277µs   2.249µs   67.343µs  114.869µs  1134       1205
9   46.787µs   65.339µs  111.665µs 223.791µs  1930745883 268878261
all 1.300482ms           650.863µs 2.175169ms

[ Voor 3% gewijzigd door veldsla op 24-12-2020 11:59 ]

[Swedish Clown]

Aangezien niemand meedoet met Erlang, misschien wel leuk om te zien hoe Dag 9 in Erlang opgelost kan worden Vanavond eens zien of hier nog mee valt te code-golfen

Erlang:

-module(day9).

%%%_* Exports ==================================================================

-export([ part_1/0
        , part_2/0
        ]).

%%%_* API ======================================================================

-spec part_1() -> integer().
part_1() ->
  {L1, L2} = lists:split(25, input()),
  solve_part1(L2, L1).

-spec part_2() -> integer().
part_2() ->
  find_range(input(), 2, part_1()).

%%%_* Internal =================================================================
input() ->
  util:read_file("day9.txt", <<"\n">>, fun(B) -> binary_to_integer(B) end).

solve_part1([H | T], L) ->
  case is_weakness(H, lists:reverse([H | L])) of
    false -> H;
    true -> solve_part1(T, tl(L ++ [H]))
  end.

is_weakness(Int, L) ->
  [ true || X <- L, Y <- L, X + Y =:= Int ] =/= [].

find_range(L, N, Answer) ->
  case find_range_n(L, N, Answer) of
    false -> find_range(L, N + 1, Answer);
    {true, Result} -> lists:min(Result) + lists:max(Result)
  end.

find_range_n(L, N, _) when length(L) < N -> false;
find_range_n(L, N, Answer) ->
  {L1, _} = lists:split(N, L),
  case lists:sum(L1) of
    Answer -> {true, L1};
    Sum when Sum > Answer -> false;
    _ -> find_range_n(tl(L), N, Answer)
  end.

_{De syntax highlighter is niet ideaal}

[Caelorum]

Brakkie41 schreef op woensdag 9 december 2020 @ 16:17:
Aangezien niemand meedoet met Erlang, misschien wel leuk om te zien hoe Dag 9 in Erlang opgelost kan worden Vanavond eens zien of hier nog mee valt te code-golfen

[code=erlang,line,tabwidth]
[...]

Is de find_range_n een bruteforce implementatie? Kan het niet helemaal volgen met die syntax, maar herken delen uit hoe ik het opgelost: https://github.com/ajeckm.../blob/master/day9/day9.fs

[Dricus]

Voor de grap nog een tweede implementatie van dag 9 geschreven: https://github.com/Dricus...ode/year2020/Day09.kt#L33

spoiler:

Geïnspireerd op Wikipedia: Bogosort

Performance valt niks tegen: ±100ms

[ Voor 6% gewijzigd door Dricus op 09-12-2020 16:24 ]

[Swedish Clown]

Caelorum schreef op woensdag 9 december 2020 @ 16:23:
[...]

Is de find_range_n een bruteforce implementatie? Kan het niet helemaal volgen met die syntax, maar herken delen uit hoe ik het opgelost: https://github.com/ajeckm.../blob/master/day9/day9.fs

Yup brute force maar met enige zachtaardigheid Ik neem de eerste N elementen van me List en check of de sum matched met me antwoord dan wel of die te hoog ligt. Als ik erboven zit, break ik uit me loop en probeer ik het opnieuw met N + 1 vanuit find_range. Dus in eerste instantie, sum ik alles per twee elementen op, vervolgens per 3, per 4 etc. etc. totdat ik het antwoord heb

Het is in ieder geval de meest elegante manier die ik kon bedenken tijdens het drinen van me eerste koffie

[ Voor 7% gewijzigd door Swedish Clown op 09-12-2020 16:38 ]

[P_Tingen]

Woy schreef op woensdag 9 december 2020 @ 12:16:
https://github.com/rverst...de2020/blob/main/Day09.cs

Ik heb weer voor de snelle eenvoudige oplossing gekozen, want had er eigenlijk geen tijd voor

Wow, deel 2 is elegant!
Maar als ik dat probeer te jatten toe te passen dan loopt het mis met de testinvoer. Ik krijg dan in de stap vóórdat het goede antwoord zou moeten komen:

code:

15+25+47+40 = 147

Dat is te hoog, dus wordt de begin-index verhoogd, dus krijg ik:

code:

25+47+40 = 122

Die is weer te laag zodat de eind-index wordt verhoogd:

code:

25+47+40+62 = 184

En dan ben ik het goede window voorbij. Of zie ik het nu verkeerd?
Noot: ik los het niet op in c# maar in een 4GL (link)

[Caelorum]

Brakkie41 schreef op woensdag 9 december 2020 @ 16:33:
[...]
Yup brute force maar met enige zachtaardigheid [...] Het is in ieder geval de meest elegante manier die ik kon bedenken tijdens het drinen van me eerste koffie

ahja ik pak gewoon eerst alle sublijsten van 2 en check dat en daarna sublijsten van 3, enz. Niet echt elegant, maar inderdaad wel makkelijk implementeren en op mijn input duurt het ergens tussen de 10ms en de 6s afhankelijk van waar ik begin (grootste sublijsten, of kleinste)

[Woy]

P_Tingen schreef op woensdag 9 december 2020 @ 16:36:
[...]

Wow, deel 2 is elegant!
Maar als ik dat probeer te jatten toe te passen dan loopt het mis met de testinvoer. Ik krijg dan in de stap vóórdat het goede antwoord zou moeten komen:

code:

15+25+47+40 = 147

Dat is te hoog, dus wordt de begin-index verhoogd, dus krijg ik:

code:

25+47+40 = 122

Die is weer te laag zodat de eind-index wordt verhoogd:

code:

25+47+40+62 = 184

En dan ben ik het goede window voorbij. Of zie ik het nu verkeerd?
Noot: ik los het niet op in c# maar in een 4GL (link)

Welke taal gebruik je dat

code:

15+25+47+40 = 147

waar is? Bij de talen die ik gebruik is dat gewoon 127

[Woy]

0 : 0 => 35 => 35
0 : 1 => +20 => 55
0 : 2 => +15 => 70
0 : 3 => +25 => 95
0 : 4 => +47 => 142
1 : 4 => -35 => 107
1 : 5 => +40 => 147
2 : 5 => -20 => 127 range found

[DataGhost]

P_Tingen schreef op woensdag 9 december 2020 @ 16:36:
[...]

Wow, deel 2 is elegant!
Maar als ik dat probeer te jatten toe te passen dan loopt het mis met de testinvoer. Ik krijg dan in de stap vóórdat het goede antwoord zou moeten komen:

code:

15+25+47+40 = 147

Dat is te hoog, dus wordt de begin-index verhoogd, dus krijg ik:

code:

25+47+40 = 122

Die is weer te laag zodat de eind-index wordt verhoogd:

code:

25+47+40+62 = 184

En dan ben ik het goede window voorbij. Of zie ik het nu verkeerd?
Noot: ik los het niet op in c# maar in een 4GL (link)

Ik ken je taal niet, niet heel in-depth naar gekeken maar volgens mij klopt er iets niet met de volgorde van je assignments.

[ydderf]

@P_Tingen Ik denk dat je eerst je oude waarde er af moet halen (wanneer je som te hoog is) en daarna pas je index start moet verhogen. Je haalt nu de volgende waarde er af. Dus de eerste keer doe je min 20 ipv min 35.

p.s. dat je in 4GL twee instructies zo achter elkaar kan zetten leest voor mij de eerste keer niet heel makkelijk.

code:

ASSIGN iStart = iStart + 1 dSum = dSum - dVal[iStart].

[armageddon_2k1]

@Woy Deel 2 heb je erg elegant bedacht. Groeit en krimpt al naar gelang.

[Swedish Clown]

Even de code omgetoverd tot wat ik nu maar doop het @Woy-algoritme. Part 2 (welke dus inclusief een call naar part 1 is) draait in 6.3 ms (gemiddelde over 10.000 runs)

Erlang:

-module(day9).

%%%_* Exports ==================================================================

-export([ part_1/0
        , part_2/0
        , input/0
        ]).

%%%_* API ======================================================================

-spec part_1() -> integer().
part_1() ->
  {L1, L2} = lists:split(25, input()),
  solve_part1(L2, L1).

-spec part_2() -> integer().
part_2() ->
  Input = input(),
  IndexedMap = maps:from_list(lists:zip(lists:seq(1,length(Input)), Input)),
  find_range(IndexedMap, part_1(), {{1, 2}, maps:get(1, IndexedMap)}).

%%%_* Internal =================================================================
input() ->
  util:read_file("day9.txt", <<"\n">>, fun(B) -> binary_to_integer(B) end).

solve_part1([H | T], L) ->
  case is_weakness(H, lists:reverse([H | L])) of
    false -> H;
    true -> solve_part1(T, tl(L ++ [H]))
  end.

is_weakness(Int, L) ->
  [ true || X <- L, Y <- L, X + Y =:= Int ] =/= [].

find_range(Map, Answer, {{LIdx, HIdx}, Acc}) when Acc =:= Answer ->
  lists:sum(
    maps:fold(fun(K, V, [Min, Max]) when K >= LIdx andalso K =< HIdx - 1 ->
                  [lists:min([Min, V]), lists:max([Max, V])];
                 (_, _, A) ->
                  A
              end, [infinity, 0], Map));
find_range(Map, Answer, {{LIdx, HIdx}, Acc}) when Acc > Answer ->
  find_range(Map, Answer, {{LIdx + 1, HIdx}, Acc - maps:get(LIdx, Map)});
find_range(Map, Answer, {{LIdx, HIdx}, Acc}) ->
  find_range(Map, Answer, {{LIdx, HIdx + 1}, maps:get(HIdx, Map) + Acc}).

[Osxy]

Was best trots op mijn oplossingen.

Voorgaande jaren was het heel veel loopjes in loopjes met nog wat loopjes en dit jaar is de code al stuk efficienter.

100% efficient? Nee maar kom heel eind.
https://github.com/osxy/A...2020/AoC2020/Days/Day9.cs

[joppybt]

Woy schreef op woensdag 9 december 2020 @ 13:56:
[...]

Ah, je hebt gelijk, daar heb ik helemaal overheen gelezen, geluk dat er dan geen entry met exact die waarde was voordat ik de range had.

Er is natuurlijk altijd een entry met exact die waarde: het getal dat uit het eerste deel naar voren kwam.

Het zou fout kunnen gaan als de som-reeks *na* het getal komt dat je moet zoeken maar dat schijnt bij niemand te gebeuren.

[Varienaja]

Interessant te zien op https://adventofcode.com/2020/stats dat er iedere dag duizenden afvallers zijn, maar dag 7 en dag 8 zijn haast door evenveel mensen opgelost. Dag 8 vond ik toch ook weer niet triviaal simpel, dus zijn nu onderhand alleen nog die-hards over in de race?

[DataGhost]

Hmm, ik heb geprobeerd wat testdata te maken voor wie het interessant vindt iets met z'n looptijd op deel 2 te doen, of om gewoon het verschil tussen bruteforce en slim inzichtelijk te krijgen. Volgens mij is mijn data zo minimaal mogelijk en zo worst-case mogelijk, maar om alles in 64-bits integers te laten passen helaas maar anderhalf keer zo groot als de originele testdata. Gevolg daarvan is dat mijn bruteforce-oplossing daar alsnog binnen een halve seconde mee klaar is. Voor degenen die geen 64-bits limiet hebben heb ik ook een tweede bestand wat tien keer zo groot is als de testinvoer en daarmee 24 seconden duurt. Mijn slimme oplossing is zelfs met het grote bestand maar 26ms 8ms bezig, dus ongeveer een factor 10000 3000 verschil (hey, dat is toevallig joh even fout gekeken, en een van de simpele optimalisaties die al in m'n bruteforce zat drukt dit getal ook behoorlijk).

64-bits: https://sigyn.dataghost.com/aoc/2020/day9-1519.txt
Groter: https://sigyn.dataghost.com/aoc/2020/day9-10000.txt

Antwoorden volgens mijn code:

spoiler:

64-bits: 12257834190867346557
Groter: 2198510517307864597716296795632060495122744773898541767640392842304449109848429531781989708563719307705316882272284830331269

[ Voor 12% gewijzigd door DataGhost op 09-12-2020 21:13 ]

[Osxy]

DataGhost schreef op woensdag 9 december 2020 @ 20:54:
Hmm, ik heb geprobeerd wat testdata te maken voor wie het interessant vindt iets met z'n looptijd op deel 2 te doen, of om gewoon het verschil tussen bruteforce en slim inzichtelijk te krijgen. Volgens mij is mijn data zo minimaal mogelijk en zo worst-case mogelijk, maar om alles in 64-bits integers te laten passen helaas maar anderhalf keer zo groot als de originele testdata. Gevolg daarvan is dat mijn bruteforce-oplossing daar alsnog binnen een halve seconde mee klaar is. Voor degenen die geen 64-bits limiet hebben heb ik ook een tweede bestand wat tien keer zo groot is als de testinvoer en daarmee 24 seconden duurt. Mijn slimme oplossing is zelfs met het grote bestand maar 26ms 8ms bezig, dus ongeveer een factor 10000 3000 verschil (hey, dat is toevallig joh even fout gekeken, en een van de simpele optimalisaties die al in m'n bruteforce zat drukt dit getal ook behoorlijk).

64-bits: https://sigyn.dataghost.com/aoc/2020/day9-1519.txt
Groter: https://sigyn.dataghost.com/aoc/2020/day9-10000.txt

Antwoorden volgens mijn code:

spoiler:

64-bits: 12257834190867346557
Groter: 2198510517307864597716296795632060495122744773898541767640392842304449109848429531781989708563719307705316882272284830331269

Om het werkend te krijgen met de >64bit moet ik teveel moeite doen
Maar de 64bit lijst is bij mij sneller dan de orginele input haha. 30ms voor part 2 waar de orginele puzzel input 60ms is.

[Wesley]

M'n browser & Google Spreadsheets vonden de 1M cellen voor deel 1 en 500+k cellen voor deel 2 niet zo leuk, maar ben er wel gekomen zonder scripts. Nog even vastgezeten door domme fout deel 2 waar ik eerste en laatste getal nam ipv min, max.

[Osxy]

Wesley schreef op woensdag 9 december 2020 @ 21:24:
M'n browser & Google Spreadsheets vonden de 1M cellen voor deel 1 en 500+k rijen voor deel 2 niet zo leuk, maar ben er wel gekomen zonder scripts. Nog even vastgezeten door domme fout deel 2 waar ik eerste en laatste getal nam ipv min, max.

Jup die fout maakte ik ook eerst haha.

[ Voor 19% gewijzigd door Osxy op 09-12-2020 21:26 ]

[Soultaker]

Over dag 8 (Handheld Halting):

MrHaas schreef op dinsdag 8 december 2020 @ 13:42:
Oplossing zonder bruteforce:

Dit is een hele nette oplossing. Ik denk dat je 't ook als een kortste pad probleem kan zien, waarbij

spoiler:

het gewicht van een verbinding 0 of 1 is, afhankelijk van of je de instructie flipt of niet.

Bijvoorbeeld voor een programma vanaf instructie 100:

100: acc +123
101: nop +45
102: jmp +67

geeft een graaf met:

Verbinding van 100 naar 101 met gewicht 0.
Verbinding van 101 naar 102 met gewicht 0.
Verbinding van 101 naar 146 met gewicht 1.
Verbinding van 102 naar 169 met gewicht 0.
Verbinding van 102 naar 103 met gewicht 1.

Je kunt dan in O(N) tijd een kortste pad vinden. Het antwoord is dus som van de acc instructies die je tegenkomt op je pad.

Wat interessant is aan deze aanpak is dat 'ie ook werkt als er meerdere instructies geflipt moeten worden. Je vind hiermee altijd de oplossing die het minst aantal instructies flipt.

[P_Tingen]

ydderf schreef op woensdag 9 december 2020 @ 17:26:
@P_Tingen Ik denk dat je eerst je oude waarde er af moet halen (wanneer je som te hoog is) en daarna pas je index start moet verhogen. Je haalt nu de volgende waarde er af. Dus de eerste keer doe je min 20 ipv min 35.

p.s. dat je in 4GL twee instructies zo achter elkaar kan zetten leest voor mij de eerste keer niet heel makkelijk.

code:

ASSIGN iStart = iStart + 1 dSum = dSum - dVal[iStart].

Ah, denk ik ook inderdaad. De nuance zit - zie ik nu - in de plek van de ++

[DataGhost]

Osxy schreef op woensdag 9 december 2020 @ 21:17:
[...]


Om het werkend te krijgen met de >64bit moet ik teveel moeite doen
Maar de 64bit lijst is bij mij sneller dan de orginele input haha. 30ms voor part 2 waar de orginele puzzel input 60ms is.

Ha, ik zie denk ik al waarom. Je code ziet eruit als bruteforce maar je doet wat slimme dingen adhv de "vorm" van de input waardoor het dat in de praktijk niet is. Ik denk dat het daardoor altijd wel snel zal blijven. Ik heb geprobeerd de voor jou worst-case testdata te maken maar die zal nog steeds snel zijn dus heel nuttig is dat ook niet.

spoiler:

In mijn testdata is het laatste getal altijd de som van de drie voorgaande getallen, dat bekijkt jouw code bij de tweede iteratie al. Je eerste iteratie is overbodig trouwens, want je hebt al bewezen dat die nooit het juiste antwoord kan zijn.

[ Voor 16% gewijzigd door DataGhost op 09-12-2020 21:47 ]

[Osxy]

DataGhost schreef op woensdag 9 december 2020 @ 21:43:
[...]

Ha, ik zie denk ik al waarom. Je code ziet eruit als bruteforce maar je doet wat slimme dingen adhv de "vorm" van de input waardoor het dat in de praktijk niet is. Ik denk dat het daardoor altijd wel snel zal blijven. Ik heb geprobeerd de voor jou worst-case testdata te maken maar die zal nog steeds snel zijn dus heel nuttig is dat ook niet.

spoiler:

In mijn testdata is het laatste getal altijd de som van de drie voorgaande getallen, dat bekijkt jouw code bij de tweede iteratie al. Je eerste iteratie is overbodig trouwens, want je hebt al bewezen dat die nooit het juiste antwoord kan zijn.

Ja er zijn nog paar dingen te optimaliseren maar ben eigenlijk best heel trots op de code dit jaar Door de structuur van de input levert het reversen van de lijst bij zoeken naar deel 2 een factor 20 verschil in executie tijd op.

[ Voor 7% gewijzigd door Osxy op 09-12-2020 21:57 ]

[P_Tingen]

ydderf schreef op woensdag 9 december 2020 @ 17:26:
@P_Tingen Ik denk dat je eerst je oude waarde er af moet halen (wanneer je som te hoog is) en daarna pas je index start moet verhogen. Je haalt nu de volgende waarde er af. Dus de eerste keer doe je min 20 ipv min 35.

p.s. dat je in 4GL twee instructies zo achter elkaar kan zetten leest voor mij de eerste keer niet heel makkelijk.

code:

ASSIGN iStart = iStart + 1 dSum = dSum - dVal[iStart].

Dat was het inderdaad, domme fout, maar ik ben niet gewend aan ++ of -- instructies, laat staan dat ik let op of ze voor of achter de variabele staan.

https://github.com/patric...0/Day-09/day-09-extent2.p

Nu deel 2 in 2ms (in mijn eerste aanpak 662ms)

[ Voor 3% gewijzigd door P_Tingen op 09-12-2020 21:53 ]

[Dido]

Ben ik vandaag echt de tweede die zijn tweede ster krijgt hier?

Met name deel 1 was natuurlijk een enorm uitgebreide manier om iets heel simpels te omschrijven, maar deel twee betekende toch even graven in intussen ver weggezakte combinatoriek, vooral omdat de voorbeelden ook wel op een verkeerde manier een correct antwoord konden geven

[Varienaja]

Nou.. ik vind deel 1 nog niet zo gemakkelijk. Op beide voorbeelden heb ik nu eindelijk het goede antwoord. Maar op de echte input is mijn pc nog aan het rekenen. Dus qua performance doe ik iets *heel* fout.

[Dido]

Varienaja schreef op donderdag 10 december 2020 @ 06:52:
Nou.. ik vind deel 1 nog niet zo gemakkelijk. Op beide voorbeelden heb ik nu eindelijk het goede antwoord. Maar op de echte input is mijn pc nog aan het rekenen. Dus qua performance doe ik iets *heel* fout.

Dat weet ik wel zeker, dit is < milliseconden werk.

spoiler:

Het gaat uiteindelijk alleen maar om de verschillen tussen de nummertjes nadat je ze gesorteerd hebt

[Varienaja]

Dat heb ik ook ontdekt. Nu moet ik tellen. Dat kon ik bij kansrekening en statistiek al niet goed, laat staan nu..

[Dido]

Ik geef toe, deel twee heb ik eerst in Excel opgelost Dat telt wat inzichtelijker

[Daanoz]

Deel 2 vandaag was wel weer een mooie, zonder optimalisaties ging dat een hele tijd duren.

spoiler:

Uiteindelijk met memoization naar 3ms voor zowel deel 1 als 2

[Woy]

Deel 1 was inderdaad eenvoudig, maar ik had zonder koffie nog even niet in mijn hoofd hoe ik het wat eleganter kon doen, dus gewoon de simepele versie met loop gedaan.

Deel 2 had ik ook wel snel, maar ging zonder optimalisatie inderdaad wel even duren, ook hier kan het vast nog wel wat mooier, maar het werkt, en is wel gewoon helder wat er gedaan wordt.

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

[Dido]

Daanoz schreef op donderdag 10 december 2020 @ 07:52:
Deel 2 vandaag was wel weer een mooie, zonder optimalisaties ging dat een hele tijd duren.

spoiler:

Als je de jolt-stappen in een lijstje zet, en vervolgens kijkt hoe vaak de patronen 113, 1113 en 11113 voorkomen heb je weinig meer te optimaliseren? Loopje, loopje, machtsverheffen, en klaar is Klara?
Mijn naieve implementatie draait binnen 1 ms, dus ik ga niet optimaliseren

[armageddon_2k1]

Dag 10 was weer leuk.
Part 1 was heel simpel. Maakt het fijn dat Kotlin een uitgebreide stdlib heeft waardoor dingen als windows van reeksen een eitje zijn.

Part 2 even rustig doordenken en de getalletjes even opgeschreven. Was uiteindelijk ook makkelijk, maar mijn trein reed het station net binnen. Dus snel even keihard fietsen en op werk afmaken

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

Weer twee mooie oneliners in Kotlin.

[ Voor 10% gewijzigd door armageddon_2k1 op 10-12-2020 08:13 ]

[ElkeBxl]

Deel 2 was echt een lastige, tot ik eens alle getallen deftig begon op te schrijven.... Oplossing

spoiler:

Zeker toen ik eens alle combinaties begon te maken bij 3 opeenvolgende jolts van 1, 4 opeenvolgende jolts van 1, 5 opeenvolgende jolts van 1, ... Zat nog wel een leuke sequentie in die me na wat lezen op wikipedia tot tribonacci bracht

[dcm360]

Ach, hoe lang kan het duren om door meer dan een biljoen combinaties te lopen?

Uiteraard is dit een vraag die schreeuwt om dynamic programming: ieder 'probleem' is te definiëren als 1 tot 3 kleinere subproblemen, net zo lang tot je aan het einde bent. Dat dus netjes toegepast in mijn oplossing.

[eamelink]

Dit was een leuk puzzeltje! Bij deel twee even goed nadenken wat het probleem nou precies is. Daarna zijn zowel een bottom-up fold als een recursieve top-down oplossing triviaal, al moet je bij die laatste wel even memoizen (of herschrijven naar tailrec, maar dan wordt'ie weer minder triviaal)


Day 10, Deel 2, met fold (dit is de mooiste):

spoiler:

def arrangements(adapters: Set[Int]): Long =
(1 to adapters.max).foldLeft(List[Long](0,0,1))((acc, joltage) => acc.tail
(if (adapters contains joltage) acc.sum else 0)).last

Day 10, Deel 2, recursief met memoization:

spoiler:

def arrangementsRecursive(adapters: Set[Int]): Long = {

val map = mutable.Map[Int, Long](-2 -> 0, -1 -> 0, 0 -> 1)
def arrangements(joltage: Int): Long = map.getOrElseUpdate(joltage,
if(adapters contains joltage) {
arrangements(joltage - 1) + arrangements(joltage - 2) + arrangements(joltage - 3)
} else 0)

arrangements(adapters.max)
}

De gedachte is eigenlijk simpel:

spoiler:

Het aantal oplossingen n(j) voor joltage j is:
- 0 als er geen adapter is voor joltage j
- n(j -1) + n(j -2) + n(j-3) als wer wel een adapter is voor joltage j

Het is dus bijna een Fibonacci sequence, maar met een extra elementje en een ifje

[ Voor 74% gewijzigd door eamelink op 10-12-2020 09:08 ]

[ydderf]

Dag 10, Deel 1 ff snel in Excel geplakt.
Deel 2 moet ik nog ff over nadenken. Maar ben bang dat de factor tijd ff niet meewerkt.....