:strip_icc():strip_exif()/u/36083/crop5dca9e34ce091_cropped.jpeg?f=community)
Engineering is like Tetris. Succes disappears and errors accumulate.
/u/47683/Asterix%252060x60.png?f=community)
:strip_icc():strip_exif()/u/6143/rincewind.jpg?f=community)
“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”
Mooi, met die LINQ expressie in part 1!
spoiler:
Vanwaar die startwaarde voor timestamp bij part 2? Het lijkt optimalisatie te zijn, maar dan had je ook wel hoger kunnen gaan zitten, gegeven de informatie in de opdracht. En het is wel nano-optimalisatie, want ik begin gewoon bij 1 en mijn oplossing (die hetzelfde werkt als de jouwe) heeft in 110 microsecondes het antwoord 
.
.Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...
Voorbeeld in part 2 (17,x,13,19) had ik vrij snel opgelost. Maar ja, die oplossing werkte niet meer echt snel met meerdere buslijnen.:
Dag 13 deel 2 is voor mij de eerste puzzel waarbij ik denk... Uhh...
Omdat ik eerdere edities heb meegedaan, herken ik het getaltheorie dingetje wel. Maar vervolgens weet ik niet hoe ik het moet oplossen.
spoiler:Bus ID zijn priemgetallen, dus het zal wel Chinese Remainder Theorem zijn...
Ik ga eerst maar eens met 3 getallen op papier proberen... Er komt de laatste jaren altijd zo'n moment dat de puzzel meer tijd kost dan ik eraan kan besteden... En vandaag is waarschijnlijk die dag ;-)
(Mijn Python oplossingen: https://github.com/tomkooij/adventofcode)
EDIT: Eehmm.. tip: als je vastzit, lees de opdracht in plaats van bovenstaande. Ik had (niet voor het eerst) een heel andere opdracht in gedachten
Ik las op reddit een hint en vond daarna desbetreffende getaltheorie. Dan is het opeens simpel.
:strip_icc():strip_exif()/u/282184/65x65.jpg?f=community)
:strip_icc():strip_exif()/u/593726/crop5dcaa04cb6842_cropped.jpeg?f=community)
spoiler:
Was begonnen met in stappen van het grootste interval te werken, ging redelijk voor de testen, maar echte opgave duurde veel te lang.
Dan gevonden dat de huidige situatie zich maar voordoet bij veelvouden van het kleinste gemeen veelvoud van alle reeds geplande bussen. Zie nu dat jullie spreken dat het allemaal priemgetallen zijn, dan had ik dus eigenlijk gewoon kunne vermenigvuldigen
. Begon toch wat denkwerk in te kruipen.
Dan gevonden dat de huidige situatie zich maar voordoet bij veelvouden van het kleinste gemeen veelvoud van alle reeds geplande bussen. Zie nu dat jullie spreken dat het allemaal priemgetallen zijn, dan had ik dus eigenlijk gewoon kunne vermenigvuldigen
. Begon toch wat denkwerk in te kruipen.https://github.com/mscham...blob/master/2020/Day13.cs
Dat was omdat er in de tekst dit stond:
[...]
Mooi, met die LINQ expressie in part 1!
spoiler:Vanwaar die startwaarde voor timestamp bij part 2? Het lijkt optimalisatie te zijn, maar dan had je ook wel hoger kunnen gaan zitten, gegeven de informatie in de opdracht. En het is wel nano-optimalisatie, want ik begin gewoon bij 1 en mijn oplossing (die hetzelfde werkt als de jouwe) heeft in 110 microsecondes het antwoord
Maar ik zie dat ik nog een factor 1000 te laag begonnen ben
“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”
/u/22283/crop5e2c64c410533.png?f=community)
:strip_exif()/u/11775/SoulTaker.gif?f=community)
:strip_exif()/u/90636/nintendo.gif?f=community)
:strip_icc():strip_exif()/u/189778/crop58e3af7a85b51.jpeg?f=community)
:strip_icc():strip_exif()/u/140697/crop6180fb9103afa_cropped.jpg?f=community)
/u/12668/hydra.png?f=community)
Nou, ben weer wat beter dus maar aan de slag gegaan.
Fuck man, deel 2 van dag 10 ben ik echt uren mee bezig geweest! DP is echt m'n ding niet Op naar dag 11
Fuck man, deel 2 van dag 10 ben ik echt uren mee bezig geweest! DP is echt m'n ding niet
Op naar dag 11
https://niels.nu
/u/126369/Daos2.png?f=community)
Uit de lappenmand dus en weer inhalen:
Nou, ben weer wat beter dus maar aan de slag gegaan.
Fuck man, deel 2 van dag 10 ben ik echt uren mee bezig geweest! DP is echt m'n ding niet
DP heb je in feite niet nodig, je kan ook gewoon een fold doen over de waardes (oplopend) en in de accumulator een lookup bijhouden. Effectief natuurlijk DP maar dan waar de waardes al op volgorde liggen. Sortering is ook O(n) te doen omdat je weet wat het maximum kan zijn (3*n).
Engineering is like Tetris. Succes disappears and errors accumulate.
Mijn oplossing is niet zo consise als een aantal die ik hier heb gezien, maar het was voor mij wel overzichtelijk wat er gebeurde. Duurde best wel een tijd voor ik 'm had tho
https://github.com/evanraalte/aoc2020/tree/master/day13
[/spoiler]
https://github.com/evanraalte/aoc2020/tree/master/day13
[/spoiler]
“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”
:strip_exif()/u/3287/crop6274f828ec8f4.gif?f=community)
Heuveltjes CPU geschiedenis door de jaren heen : AMD 486dx4 100, Cyrix PR166+, Intel P233MMX, Intel Celeron 366Mhz, AMD K6-450, AMD duron 600, AMD Thunderbird 1200mhz, AMD Athlon 64 x2 5600, AMD Phenom X3 720, Intel i5 4460, AMD Ryzen 5 3600 5800x3d
:strip_icc():strip_exif()/u/91018/dgtw.jpg?f=community)
Dat gebeurt heel vaak expres. Een opgave met lelijke corner cases verzinnen en daar dan die corner cases bij weglaten, of alleen sommige corner cases weglaten. Soms wordt in de opgave wel eens uitgelegd waarom een van de corner cases misgaat, dat is soms een hint dat er meer is en soms een rottigheidje om je minder oplettend te maken. Ik kijk zelf het liefst helemaal niet naar de voorbeeld-input, ik implementeer de opgave zoals ik denk dat 'ie zou moeten en verzin tijdens het implementeren al corner cases. Meestal gaat het dan op de voorbeeldinput wel direct goed en op de opgave ook. Ik heb dit jaar nog geen fout antwoord ingestuurd in ieder geval
Vandaag was wel de eerste keer dat ik de daadwerkelijke puzzel-input had bekeken.
spoiler:
Ik zag dat alle buslijnen in de voorbeelden priem waren en gokte dat dat daar ook zo zou zijn, dat zou wat wiskunde schelen. Maar ik zag al gauw dat ik de verkeerde kant op aan het rekenen was (foutje) en in de aanpak die ik daarna verzon boeit het niet of ze priem zijn of niet.
Gebeurt bij alle software die je wilt ontwikkelen, de specificaties zijn altijd ruk en je zal toch echt zelf alle corner cases moeten verzinnen en testen.
Nja er staat letterlijk "vandaag" boven, en het is een spoiler. Daarom staat 'ie in een spoiler
. Ik denk niet dat je er enorm veel aan hebt trouwens.Een goeie richtlijn is om op geen enkele spoiler te klikken als er "X december" boven de post staat en X > hoe ver jij bent met oplossen.
[ Voor 24% gewijzigd door DataGhost op 13-12-2020 16:51 ]
/u/200133/artemis_square_e_60-60.png?f=community)
:strip_exif()/u/29138/caffeine.gif?f=community)
Ah, thanks. Vergeten te generaliseren. Het is gewoon de ID van de eerste bus van de voorbeeldcode. Ik heb de code ff aangepast.
Normaal doe ik nog een refactoringslag over de code maar daar had ik nu geen zin meer in
https://niels.nu
Zo, rustige zondag gehad dus
spoiler:
Cycle detection snap ik niet. Het is toch gewoon een reeks?
Engineering is like Tetris. Succes disappears and errors accumulate.
Begrijpelijk @Hydra. Soms bekijk ik mijn eigen code een halfuur later nog eens en gruw dan van wat er soms nog voor onhandige kronkels in zitten.
Siditamentis astuentis pactum.
Sorry hoor, je kunt ook even gewoon lezen
To be fair, er staat letterlijk “vandaag” boven z’n spoiler. Weet niet helemaal wat ie anders kan doen. Elke dag is er een puzzel en het is vrij normaal spoilers over de lopende dag te plaatsen.
Engineering is like Tetris. Succes disappears and errors accumulate.
Heb 't gerefactored. Stuk minder code:
Begrijpelijk @Hydra. Soms bekijk ik mijn eigen code een halfuur later nog eens en gruw dan van wat er soms nog voor onhandige kronkels in zitten.
Later nog 'es nadenken over of 't functioneel kan.
https://niels.nu
@Hydra Prima, ik ga me er verder niet al te druk over maken verder.
De puzzels worden moeilijker, gelukkig hoef ik nog maar twee dagen te werken en heb ik daarna lekker tijd de puzzels te doen.
Naast schuur opruimen, zolder schilderen, plintjes plaatsen, tuin nog wat opruimen, kelder opruimen, stellingkast bij schoonmoeder bouwen, lampen plaatsen... maar verder genoeg tijd
De puzzels worden moeilijker, gelukkig hoef ik nog maar twee dagen te werken en heb ik daarna lekker tijd de puzzels te doen.
Naast schuur opruimen, zolder schilderen, plintjes plaatsen, tuin nog wat opruimen, kelder opruimen, stellingkast bij schoonmoeder bouwen, lampen plaatsen... maar verder genoeg tijd
Engineering is like Tetris. Succes disappears and errors accumulate.
Paar regels is prima. bij langere posts liever link naar oplossing.
Ik heb de handdoek er maar inggegooid bij opdracht 2 van vandaag.
Hiervoor heb je volgens mij toch iets meer wiskundige achtergrond nodig, dan ik heb
Heuveltjes CPU geschiedenis door de jaren heen : AMD 486dx4 100, Cyrix PR166+, Intel P233MMX, Intel Celeron 366Mhz, AMD K6-450, AMD duron 600, AMD Thunderbird 1200mhz, AMD Athlon 64 x2 5600, AMD Phenom X3 720, Intel i5 4460, AMD Ryzen 5 3600 5800x3d
:strip_icc():strip_exif()/u/98225/crop5dc806a4a2281_cropped.jpeg?f=community)
Bedankt! Zonder hint had ik de computer waarschijnlijk 24u moeten laten draaien voordat ik een antwoord had gekregen
Met de hulp lukte het me dan eindelijk nadat ik een keer heel goed keek naar het eerste voorbeeld.
spoiler:
Een klein deel daarvan beter gezegd...
[ Voor 3% gewijzigd door Sharkware op 13-12-2020 22:17 ]
:strip_icc():strip_exif()/u/19784/crop5602e6447372a_cropped.jpeg?f=community)
Ik ben er ook een groot deel van de dag mee bezig geweest. De post van Woy heeft mij geholpen - even afstand nemen. Hint.:
Ik heb de handdoek er maar inggegooid bij opdracht 2 van vandaag.
Hiervoor heb je volgens mij toch iets meer wiskundige achtergrond nodig, dan ik heb
spoiler:
Probeer de opdracht op te delen in kleinere opdrachten.
Dag 13 in C# (LINQPad).
Nadeel van LINQ is dat het nogal lastig debugt. Ik was lange tijd met ParallelEnumerable bezig en kreeg arithmetic overflow errors. Blijkt dat deze 'maar' int.MaxValue elementen kan verwerken.
[ Voor 24% gewijzigd door nescafe op 13-12-2020 23:09 ]
* Barca zweert ook bij fixedsys... althans bij mIRC de rest is comic sans
Verwijderd
:
[...]
Paar regels is prima. bij langere posts liever link naar oplossing.
Ik heb de handdoek er maar inggegooid bij opdracht 2 van vandaag.
Hiervoor heb je volgens mij toch iets meer wiskundige achtergrond nodig, dan ik heb
spoiler:
ik heb het getal zelf nog niet, maar de berekening is in principe niet heel moeiljk
Hint: zoek voor iedere buslijn eens los het veelvoud waarop de bus op het juiste moment vertrekt:
Hiervoor geldt dat het verschil van de rest van de deling gelijk is aan het wegrijmoment - de busperiode.
In principe (het zijn allemaal priemgetallen) hoef je alleen maar te zoeken in de rij 1..nxm, waar n 19 en m een van de andere busnummers is.
Je moet verder opletten als het verschil in aanrijtijd groter wordt als een geheel maal de cyclustijd van de eerste bus (19). Dan moet je je zoekveld vergroten met 19*m, en het geheel aantal 19 van de tussenoplossing aftrekken.
ZO krijg je 8 'gemene delers' die je met elkaar moet vermenigvuldigen:
114 209 15580 228 304 532 8284 456
Nu nog ff een onlinecalculator vinden die arbitrair grote getallen aankan...
Hint: zoek voor iedere buslijn eens los het veelvoud waarop de bus op het juiste moment vertrekt:
Hiervoor geldt dat het verschil van de rest van de deling gelijk is aan het wegrijmoment - de busperiode.
In principe (het zijn allemaal priemgetallen) hoef je alleen maar te zoeken in de rij 1..nxm, waar n 19 en m een van de andere busnummers is.
Je moet verder opletten als het verschil in aanrijtijd groter wordt als een geheel maal de cyclustijd van de eerste bus (19). Dan moet je je zoekveld vergroten met 19*m, en het geheel aantal 19 van de tussenoplossing aftrekken.
ZO krijg je 8 'gemene delers' die je met elkaar moet vermenigvuldigen:
114 209 15580 228 304 532 8284 456
Nu nog ff een onlinecalculator vinden die arbitrair grote getallen aankan...
Ik was begonnen met een slimme manier van bruteforcen.
pak 1 x de hoogste bus, probeer die te vergelijken met de hoogste bus daaronder. Als dat lukt dan de volgende kijken of die klopt. Mocht dat lniet lukken probeer dan 2 keer de hoogste bus etc.
Ging nog wel in de test, maar werd onmogelijk in de 2e ronde
Grappig. an de hand van die opmerking (buslijnen 2,3,5 -> goede tijd =
ben ik gaan puzzelen.En toen ik die ging uitschrijven op een stuk papier, werd het me wel een stuk duidelijker.
spoiler:
Ik had totaal niet ingezien dat de periode tussen wanneer bus1&bus2 aan de eisen voldoen, gelijk bleef, en dat dat vrij simpel te berekenen is.
pak 2,3,5 als voorbeeld
de 1e keer dat *2 1 kleiner is dan *3 is bij 1x3 (2-3)
de 2e keer dat *2 1 kleiner is dan *3 is bij 3x3 (8-9)
de 3e keer dat *2 1 kleiner is dan *3 is bij 5x3 (14-15)
En je ziet een patroon ontstaan, het herhaalt zich in dit geval elke keer met 2
nu ga je 3 en 5 zoeken, waarbij je alleen nog maar in stappen van +2*3 te checken
de 1e keer dat *3 ook 1 kleiner is dan *5 is bij 2x5 (8,9,10)
de 2e keer dat *3 ook 1 kleiner is dan *5 is bij 8x5 (38,39,40
de 3e keer dat *3 ook 1 kleiner is dan *5 is bij 14x5 (68,69,70)
Het herhaald zich om de 6 stappen, nu kun je de volgende zoeken
En vanaf nu hoef je alleen nog maar in stappen van +(6x5) te checken.
ik had al een routine geschreven, die prima die stappen kon bereken door een for loopje.
Zijn nog geen 70 cycles nodig om de 1e 2 waarden te vinden.
pak 2,3,5 als voorbeeld
de 1e keer dat *2 1 kleiner is dan *3 is bij 1x3 (2-3)
de 2e keer dat *2 1 kleiner is dan *3 is bij 3x3 (8-9)
de 3e keer dat *2 1 kleiner is dan *3 is bij 5x3 (14-15)
En je ziet een patroon ontstaan, het herhaalt zich in dit geval elke keer met 2
nu ga je 3 en 5 zoeken, waarbij je alleen nog maar in stappen van +2*3 te checken
de 1e keer dat *3 ook 1 kleiner is dan *5 is bij 2x5 (8,9,10)
de 2e keer dat *3 ook 1 kleiner is dan *5 is bij 8x5 (38,39,40
de 3e keer dat *3 ook 1 kleiner is dan *5 is bij 14x5 (68,69,70)
Het herhaald zich om de 6 stappen, nu kun je de volgende zoeken
En vanaf nu hoef je alleen nog maar in stappen van +(6x5) te checken.
ik had al een routine geschreven, die prima die stappen kon bereken door een for loopje.
Zijn nog geen 70 cycles nodig om de 1e 2 waarden te vinden.
Kan je uitleg niet helemaal volgen, maar geloof wel dat we op dezeflde weg zitten
[ Voor 19% gewijzigd door heuveltje op 14-12-2020 01:16 ]
Heuveltjes CPU geschiedenis door de jaren heen : AMD 486dx4 100, Cyrix PR166+, Intel P233MMX, Intel Celeron 366Mhz, AMD K6-450, AMD duron 600, AMD Thunderbird 1200mhz, AMD Athlon 64 x2 5600, AMD Phenom X3 720, Intel i5 4460, AMD Ryzen 5 3600 5800x3d
:strip_icc():strip_exif()/u/51489/heforshe_logo_detail.jpg?f=community){kind=logo}
Congrats
Ik heb het dus meer traditioneel aangepakt (ijverig gaan tikken terwijl je voorzichtig aan je eerste koffie nipt) en vandaag bij stap 1 ben ik in zo ongeveer elke valkuil gestapt die maar kon
Deel twee ging wel in 1 keer goed, na een vierde koffie en 5 minuten pauze
Grappig om te zien dat het dit jaar beter vol te houden lijkt. Bijna 2 keer zo veel mensen die goud hebben op dag 13 versus 33% meer op dag 1. Er blijven dus relatief meer mensen doorgaan.
[ Voor 13% gewijzigd door Dido op 14-12-2020 07:48 ]
Done! Deze ging lekker
https://github.com/evanra...lob/master/day14/day14.py
Uurtje bezig geweest, niet veel fouten gemaakt. Toch bijna 10 keer (snelste had een oplossing in 6 min!) zo traag als de snelste vandaag
https://github.com/evanra...lob/master/day14/day14.py
Uurtje bezig geweest, niet veel fouten gemaakt. Toch bijna 10 keer (snelste had een oplossing in 6 min!) zo traag als de snelste vandaag
[ Voor 8% gewijzigd door evanraalte op 14-12-2020 11:38 ]
:strip_icc():strip_exif()/u/585680/olliolli-buttonjpg-df0ded_60w.jpg?f=community)
Ik ben ook echt bijna de hele middag bezig geweest om p2 voor elkaar te krijgen. Ik had een vergelijkbare oplossing bedacht als @heuveltje, maar het debuggen viel niet mee met de summiere testcases.
Zo een eenvoudige puzzel als vandaag voelt dan wel even heel erg fijn
Zo een eenvoudige puzzel als vandaag voelt dan wel even heel erg fijn
Day 14
Dit was wel een leuke. Wel veel werk!
Edit: FF snel de loops in part 1 en part 2 omgebouwd naar een fold-left. Da's nu typisch iets wat je in 'productie' relatief weinig gebruikt (ook vanwege de "wat is deze?" reacties van sommige collega's) dus ik vind het wel cool om daar nu een beetje mee te oefenen
Dit was wel een leuke. Wel veel werk!
spoiler:
Wat je voor deel 1 en 2 nodig hebt verschilt enorm, afgezien van het parsen van de input kun je niet zo veel hergebruiken.
Verder ben ik gewoon 'dom' integers naar binary strings aan het omzetten geweest en vice versa. If it works, it ain't stupid. Ga misschien nog wel ff kijken of ik 't korter op kan schrijven. "Feelin' cute, might refactor later"
Verder ben ik gewoon 'dom' integers naar binary strings aan het omzetten geweest en vice versa. If it works, it ain't stupid. Ga misschien nog wel ff kijken of ik 't korter op kan schrijven. "Feelin' cute, might refactor later"
Edit: FF snel de loops in part 1 en part 2 omgebouwd naar een fold-left. Da's nu typisch iets wat je in 'productie' relatief weinig gebruikt (ook vanwege de "wat is deze?" reacties van sommige collega's) dus ik vind het wel cool om daar nu een beetje mee te oefenen
[ Voor 19% gewijzigd door Hydra op 14-12-2020 10:19 ]
https://niels.nu
/u/73449/Mithrandir.JPG?f=community)
Ik vind mijn oplossing voor deel 2 dag 13 ook wel mooi
Na de hint gelezen te hebben dat het allemaal priem getallen zijn ben is gaan nadenken over hoe het op te lossen.
Na de hint gelezen te hebben dat het allemaal priem getallen zijn ben is gaan nadenken over hoe het op te lossen.
spoiler:
Het eerste getal wat deelbaar is door aantal priem getallen is altijd alle getallen maal elkaar. Maar dit zochten we niet precies.
t % priem 1 = 0
t + x % priem 2 = 0
enz...
Volgens mij doet die voorwaarde zich ieder stapgrootte priem 1 * priem 2 zich een keer voor.
Vervolgens ga je opzoek naar een punt waar je aan t + x % priem_n = 0 en verminigvuldig je weer je stap groote met priem_n
enz.. tot je tot het einde bent
t % priem 1 = 0
t + x % priem 2 = 0
enz...
Volgens mij doet die voorwaarde zich ieder stapgrootte priem 1 * priem 2 zich een keer voor.
Vervolgens ga je opzoek naar een punt waar je aan t + x % priem_n = 0 en verminigvuldig je weer je stap groote met priem_n
enz.. tot je tot het einde bent
At dawn on the fifth day look to the east
Vandaag was meer een oefening voor begrijpend lezen dan programmeren voor mij.
Deel 1, fout. Oh, niet goed gelezen dat de mask kon veranderen.
Ik pakte gewoon de eerste regel als mask en ging daar de rest mee inlezen (als er mem in voorkwam, dus ook geen error.)
Deel 2, fout. Oh, als de mask 0 is overschrijft hij niet.
Uiteindelijk wel de juiste antwoorden gekregen.
Deel 1, fout. Oh, niet goed gelezen dat de mask kon veranderen.
Ik pakte gewoon de eerste regel als mask en ging daar de rest mee inlezen (als er mem in voorkwam, dus ook geen error.)Deel 2, fout. Oh, als de mask 0 is overschrijft hij niet.
Uiteindelijk wel de juiste antwoorden gekregen.
[ Voor 16% gewijzigd door coop op 06-12-2021 13:48 ]
Als het langzaam is gebruikt je niet genoeg bitmasks. Mijn oplossing (ook in Python) runt in 100 ms ofzo.:
Uurtje bezig geweest, niet veel fouten gemaakt. Toch bijna 10 keer zo traag als de snelste vandaag
Je ziet bij deze opdracht ook gelijk wie de old-school programmeurs zijn.
Haha, ik wilde niet dubbelzinnig zijn. Ik bedoel dat het mij 60 minuten kostte om de code te schrijven, tov de kennelijk 6 minuten die het iemand anders kostte:
[...]
Als het langzaam is gebruikt je niet genoeg bitmasks. Mijn oplossing (ook in Python) runt in 100 ms ofzo.
Je ziet bij deze opdracht ook gelijk wie de old-school programmeurs zijn.
. Bit masking is nou niet bepaald old-school, ik gebruik het nog steeds dagelijks
Vandaag was inderdaad ook weer goed te doen. Ik moest even denken welke vorm ik de floating bits permutaties zou doen, en het dilemma hoe ik de bits zou addresseren ( De index van de mask string, of normal bit-nrs )
https://github.com/rverst.../blob/main/Y2020/Day14.cs
)https://github.com/rverst.../blob/main/Y2020/Day14.cs
“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”
Deel 1 met bitmasks kunnen oplossen, ooit iets over geleerd en ik heb het vrijwel nooit meer nodig (denk ik). Dus leuk om tegen te komen!
Deel 2 kwam ik op dezelfde manier niet uit:
java: https://github.com/Moofnor/AoC2020/tree/main/day14
Deel 2 kwam ik op dezelfde manier niet uit:
spoiler:
Kan dat met bitshift? Ik zat vast en heb uiteindelijk maar gewoon over de bits geloopt met recursion bij 'X'. Daardoor mijn langzaamste script tot nu toe. Dus als dat anders kan hoor ik graag tips
java: https://github.com/Moofnor/AoC2020/tree/main/day14
- I can accurately say I was born on Earth, but it's not very precise. I can precisely say I was born at latitude 37.229N, longitude 115.811W, but that is not at all accurate - Matt Parker
Challenge accepted! Bij het fatsoeneren van de code heb ik gepoogd zoveel mogelijk her te gebruiken. Day 14.
Ik geloof niet dat het er lees- en /of begrijpbaarder door geworden is.
Siditamentis astuentis pactum.
Dank voor de uitgebreide uitleg!
Zeer helder, nu onthouden voor de volgende keer.
- I can accurately say I was born on Earth, but it's not very precise. I can precisely say I was born at latitude 37.229N, longitude 115.811W, but that is not at all accurate - Matt Parker
Hm, ik was begonnen aan een "moeilijke" oplossing voor deel 2. Ging prima op de testinput in de opdracht maar vervolgens was het antwoord op de volledige invoer fout. Dus extra testcases maken om te kijken waar mijn denkfout precies zat,
spoiler:
en een simulator gemaakt die het gewoon simuleerde (zoals schijnbaar elke oplossing die hier is langsgekomen), zodat ik kon zien in hoeverre mijn antwoord fout was. Voor de gein heb ik deze ook even op de volledige input gedraaid en tot mijn verbazing kwam daar bijna instant het correcte antwoord uit wat ik niet verwacht had als je kijkt naar de testinput voor deel 1, ik ging ervan uit dat de volledige input daar genoeg op zou lijken om simuleren lekker te kunnen vergeten.
Nou, fijn, opdracht klaar, antwoord ingeleverd, maar het antwoord wat mijn "moeilijke" methode gaf ligt maar 0,3% van het uiteindelijke antwoord vandaan, dus dat is wel frustrerend, het *voelt* alsof ik in de goede richting zit. Ik heb er nog behoorlijk over nagedacht maar ik denk dat ik een fout in mijn idee heb en dat het best wel eens zou kunnen zijn dat de veranderingen die ik moet maken alsnog voor een worst-case looptijd zorgen die niet beter is dan simulatie, maar hopelijk wel met een beter geheugengebruik.
Nou dus de vraag om te zien of het überhaupt kan: wie heeft een algoritme wat deel 2 correct oplost, en bovendien zonder aanpassingen de testinput van deel 1 kan oplossen binnen een seconde en met minder dan zeg, iets royaals als 16GB geheugengebruik?
wat ik niet verwacht had als je kijkt naar de testinput voor deel 1, ik ging ervan uit dat de volledige input daar genoeg op zou lijken om simuleren lekker te kunnen vergeten.Nou, fijn, opdracht klaar, antwoord ingeleverd, maar het antwoord wat mijn "moeilijke" methode gaf ligt maar 0,3% van het uiteindelijke antwoord vandaan, dus dat is wel frustrerend, het *voelt* alsof ik in de goede richting zit. Ik heb er nog behoorlijk over nagedacht maar ik denk dat ik een fout in mijn idee heb en dat het best wel eens zou kunnen zijn dat de veranderingen die ik moet maken alsnog voor een worst-case looptijd zorgen die niet beter is dan simulatie, maar hopelijk wel met een beter geheugengebruik.
Nou dus de vraag om te zien of het überhaupt kan: wie heeft een algoritme wat deel 2 correct oplost, en bovendien zonder aanpassingen de testinput van deel 1 kan oplossen binnen een seconde en met minder dan zeg, iets royaals als 16GB geheugengebruik?
Hint 1::
Hm, ik was begonnen aan een "moeilijke" oplossing voor deel 2. Ging prima op de testinput in de opdracht maar vervolgens was het antwoord op de volledige invoer fout. Dus extra testcases maken om te kijken waar mijn denkfout precies zat,
spoiler:en een simulator gemaakt die het gewoon simuleerde (zoals schijnbaar elke oplossing die hier is langsgekomen), zodat ik kon zien in hoeverre mijn antwoord fout was. Voor de gein heb ik deze ook even op de volledige input gedraaid en tot mijn verbazing kwam daar bijna instant het correcte antwoord uit
Nou, fijn, opdracht klaar, antwoord ingeleverd, maar het antwoord wat mijn "moeilijke" methode gaf ligt maar 0,3% van het uiteindelijke antwoord vandaan, dus dat is wel frustrerend, het *voelt* alsof ik in de goede richting zit. Ik heb er nog behoorlijk over nagedacht maar ik denk dat ik een fout in mijn idee heb en dat het best wel eens zou kunnen zijn dat de veranderingen die ik moet maken alsnog voor een worst-case looptijd zorgen die niet beter is dan simulatie, maar hopelijk wel met een beter geheugengebruik.
Nou dus de vraag om te zien of het überhaupt kan: wie heeft een algoritme wat deel 2 correct oplost, en bovendien zonder aanpassingen de testinput van deel 1 kan oplossen binnen een seconde en met minder dan zeg, iets royaals als 16GB geheugengebruik?
spoiler:
Je bent alleen geinteresseerd in de elementen die je aanpast in memory. Dus de secties in je geheugen die "0" zijn hoef je niet op te slaan.
Hint 2:
spoiler:
Kijk of je taal iets als een dictionary support (het heet dictionary in Python althans)
Nja ik ben niet helemaal van gisteren
Dat gebruik ik ook al gewoon. Maar kijk eens naar de voorbeeldinput bij deel 1:code:
1
2
3
4
| mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X mem[8] = 11 mem[7] = 101 mem[8] = 0 |
spoiler:
Ik wens je heel veel succes met een dictionary, map, of wat dan ook. Mijn simulatie gebruikt ook gewoon een dict maar dit "kleine" voorbeeldje past daar niet in
spoiler:
Bij een mask met allemaal X (bijna het voorbeeld dus) heb je 236 = 68 miljard adressen. Met 32 bits inhoud per geheugencel (maximale waarde zo'n 4 miljard) kost dat minimaal 256GB. En in alle simulatie-voorbeelden hier ben je elke toewijzing dus die 68 miljard adressen opnieuw aan het genereren.
spoiler:
Een dict zal in dit geval alleen maar slechter zijn dan een statische array, of hoogstens even goed.
:
[...]
Nja ik ben niet helemaal van gisteren
code:
spoiler:Ik wens je heel veel succes met een dictionary, map, of wat dan ook. Mijn simulatie gebruikt ook gewoon een dict maar dit "kleine" voorbeeldje past daar niet in
spoiler:Bij een mask met allemaal X (bijna het voorbeeld dus) heb je 236 = 68 miljard adressen. Met 32 bits inhoud per geheugencel (maximale waarde zo'n 4 miljard) kost dat minimaal 256GB. En in alle simulatie-voorbeelden hier ben je elke toewijzing dus die 68 miljard adressen opnieuw aan het genereren.
spoiler:Een dict zal in dit geval alleen maar slechter zijn dan een statische array, of hoogstens even goed.
spoiler:
Maar het voorbeeld bij deel 2 gebruikt ruim minder dan dat. En jouw input file ook naar alle waarschijnlijkheid. Dus gewoon deel 2 niet testen met de test-invoer van deel 1 dus.
[ Voor 4% gewijzigd door dcm360 op 14-12-2020 16:05 ]
Zo, hij was niet moeilijk, maar mijn hersens wilden geen elegante oplossing doen. Heb net als @Hydra ook gewoon binary strings zitten opbouwen....
Daarnaast wel regex aangeleerd om eens te gebruiken, toch wel fijn
https://github.com/rj-cod...rjcoding/aoc2020/Day14.kt
Hij is wel wat traag (~1,5s), dus later eens refactoren om die addresses wat slimmer te genereren......
Daarnaast wel regex aangeleerd om eens te gebruiken, toch wel fijn
https://github.com/rj-cod...rjcoding/aoc2020/Day14.kt
Hij is wel wat traag (~1,5s), dus later eens refactoren om die addresses wat slimmer te genereren......
Engineering is like Tetris. Succes disappears and errors accumulate.
spoiler:
Mag een deel van de uitdaging nog wel zijn om iets met een algoritmisch leuke looptijd te krijgen? Ik heb het probleem allang opgelost en het antwoord allang ingestuurd maar ik ben gewoon op zoek naar een algoritme wat alle invoer in een acceptabele tijd op kan lossen. Sterker nog, ik verwacht eigenlijk dat dit probleem in de komende dagen nog een vervolg krijgt waarin dit weer belangrijk wordt, tenzij er geen goed algoritme voor bestaat.
Volgens mij is het antwoord op de testinvoer 1735166787584 en dat zou ik er graag binnen afzienbare tijd uit krijgen met een algoritme wat voor deel 2 gebruikt is.
Ik heb het probleem allang opgelost en het antwoord allang ingestuurd maar ik ben gewoon op zoek naar een algoritme wat alle invoer in een acceptabele tijd op kan lossen. Sterker nog, ik verwacht eigenlijk dat dit probleem in de komende dagen nog een vervolg krijgt waarin dit weer belangrijk wordt, tenzij er geen goed algoritme voor bestaat.Volgens mij is het antwoord op de testinvoer 1735166787584 en dat zou ik er graag binnen afzienbare tijd uit krijgen met een algoritme wat voor deel 2 gebruikt is.
Edit: ondertussen heb ik iemand gevonden die het voor elkaar heeft gekregen op bijna dezelfde manier die ik in gedachten had, en met het correcte antwoord voor de invoer van deel 1. Hij vertelde me binnen een paar seconden het antwoord in m'n spoiler, dus het kan. Dus ik ga verder puzzelen
Edit2: ondertussen gelukt trouwens.
[ Voor 14% gewijzigd door DataGhost op 14-12-2020 18:50 ]
Dag 14 in F#
Lekker niks bitmasken. Ik zou toch al lineair door de string heen moeten lopen om de mask op te bouwen, dan is nog een paar keer erdoorheen om te vergelijken niet zo'n probleem. Het draait nog altijd in 300ms Optimizen kan altijd nog wel als het belangrijker wordt in een latere opdracht.
Lekker niks bitmasken. Ik zou toch al lineair door de string heen moeten lopen om de mask op te bouwen, dan is nog een paar keer erdoorheen om te vergelijken niet zo'n probleem. Het draait nog altijd in 300ms
Optimizen kan altijd nog wel als het belangrijker wordt in een latere opdracht.
Logica klopte van geen kant. Laat maar.:
[...]
spoiler:Mag een deel van de uitdaging nog wel zijn om iets met een algoritmisch leuke looptijd te krijgen?
Volgens mij is het antwoord op de testinvoer 1735166787584 en dat zou ik er graag binnen afzienbare tijd uit krijgen met een algoritme wat voor deel 2 gebruikt is.
Edit: ondertussen heb ik iemand gevonden die het voor elkaar heeft gekregen op bijna dezelfde manier die ik in gedachten had, en met het correcte antwoord voor de invoer van deel 1. Hij vertelde me binnen een paar seconden het antwoord in m'n spoiler, dus het kan. Dus ik ga verder puzzelen
[ Voor 34% gewijzigd door coop op 14-12-2020 18:37 ]
Je schreef dat er niks exponentieels aan is vandaag. Dat is feitelijk onjuist. Het is inderdaad zo dat dat, gezien de input, geen factor (
) van belang is.
Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...
:strip_icc():strip_exif()/u/1007893/crop5f84470ecb79a.jpeg?f=community)
Dag 14, deel 1 gereed
Morgen maar eens naar deel twee kijken..
spoiler:
Opgelost door bitwise operators te gebruiker. De eerste keer de X-en in mask vervangen door 1-en. De tweede keer met een mask waarbij de X-en door 0-en vervangen zijn.
/f/image/zqBv5WPP8q1B3XvruH36IoKn.png?f=fotoalbum_medium)
:fill(white):strip_exif()/f/image/zqBv5WPP8q1B3XvruH36IoKn.png?f=user_large)
Morgen maar eens naar deel twee kijken..
Soms gaat het niet zoals het moet, maar moet het maar zoals het gaat
Oh, zeker. Mijn bijdrage was een goed bedoelde poging om te laten zien dat je tekst door @DataGhost waarschijnlijk iets te letterlijk geïnterpreteerd was:
[...]
Je begrijpt wel wat ik bedoel denk ik
. Ik moet me ook niet overal mee bemoeien 
.
Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...
Moet niet, maar mag wel hoor:
Oh, zeker. Mijn bijdrage was een goed bedoelde poging om te laten zien dat je tekst door @DataGhost waarschijnlijk iets te letterlijk geïnterpreteerd was
https://niels.nu
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
[ Voor 14% gewijzigd door Hydra op 14-12-2020 20:21 ]
https://niels.nu
spoiler:
Ummmm, ik moet eerlijk bekennen dat looptijden uitrekenen niet m'n sterkste kant is, of dat ik er in ieder geval niet veel tijd aan heb besteed. Anyway, de manier waarop het bij mij werkt hou ik alleen maar niet-overlappende bitmasks bij, zoals je zelf ook al doet. Als je een nieuw bitmask toevoegt heeft die alleen overlap als alle 1 en 0 gelijk zijn op plekken waar geen X staat. Dus de verschillen zijn dan ook puur in de Xjes. Als er overlap is wordt een bepaald bitmask vervangen door maximaal n specifiekere bitmasks waarbij n het aantal Xjes is in het bitmask dat al bestond. Per nieuw toegevoegd bitmask kan je er dus maximaal b nieuwe bitmasks voor in de plaats krijgen. Uiteindelijk kan je met genoeg assignments a het hele geheugen vullen (lees: hetzelfde worst-case geheugengebruik krijgen als simulatie) maar dat gebeurt dan pas bij 2b assignments.
Hm, het doorgestreepte stuk klopt niet helemaal, er kunnen maximaal b nieuwe voor in de plaats komen maar dan wel voor elke die al in het geheugen stond en niet onafhankelijk daarvan. Ik denk dat je tegenvoorbeeld en berekening valide is. Ik weet niet of er een betere mogelijkheid is. Bij weinig assignments en simulatie-onvriendelijke masks blijft deze oplossing wel beter, maar het kan vast nog beter
Hm, het doorgestreepte stuk klopt niet helemaal, er kunnen maximaal b nieuwe voor in de plaats komen maar dan wel voor elke die al in het geheugen stond en niet onafhankelijk daarvan. Ik denk dat je tegenvoorbeeld en berekening valide is. Ik weet niet of er een betere mogelijkheid is. Bij weinig assignments en simulatie-onvriendelijke masks blijft deze oplossing wel beter, maar het kan vast nog beter