Advent of Code 2019

[schoene]

Ik had deel 2 ook eerst met de hand gedaan, maar uiteindelijk heb ik het toch geprogrammeerd, het is toch eenvoudiger dan ik eerst dacht.

spoiler:

Een brute force algoritme om 3 subsets van de uit te voeren bewegeningen te vinden waarmee je de volledige set kan opbouwen duurde hier (op een pc van 8 jaar oud) 5ms

[ Voor 40% gewijzigd door schoene op 17-12-2019 22:13 ]

[bakkerjangert]

Gisteren was wel pittig. Na veel gepuzzel ben ik er uit.

spoiler: title

Uiteindelijk heb ik de volgorde handmatig bepaald en de lengte laten bepalen met een A* search package in python. De deuren heb ik dan dus ook initeel allemaal als open staan aangezien ik handmatig de volgorde al correct bepaald had. Door dit voorwerk was Part 2 een appeltje eitje voor mij. Tip: Je moet alleen alle keys zoeken --> Niet alle deuren hoeven bezocht te worden.

[veldsla]

Dag 19 na wat 1-based 0-based misverstanden niet zo'n probleem. Nu nog 16 en 18 afmaken. Het kost toch wel wat meer tijd dan verwacht.

[CMG]

veldsla schreef op donderdag 19 december 2019 @ 10:51:
Dag 19 na wat 1-based 0-based misverstanden niet zo'n probleem. Nu nog 16 en 18 afmaken. Het kost toch wel wat meer tijd dan verwacht.

Ik vond het leuk dat ik vandaag in een paar minuten kon oplossen; gisteren ben ik 1,5-2 uur bezig geweest en ik weet hoe ik het moet gaan oplossen, maar ik heb gewoon de tijd niet momenteel om hem te doen, met als resultaat dat ik nu voor het eerst een dag niet opgelost heb :-/

Ik ga 'm nog wel doen, maar ik heb echt geen idee wanneer ik even een blok van 2 uur heb om het netjes te doen zoals ik wil.

[GeertenVink]

Ja, dag 18 had ik ook niet af voor mijn werk, en dan blijft ie toch gewoon liggen tot het weekend is. Beetje jammer.

[Soultaker]

Ik heb medelijden met de deelnemers die zonder informatica-opleiding (of op z'n minst gedegen kennis van lineare algebra) deel twee van dag 22 op proberen te lossen.

De code zelf is uiteindelijk best eenvoudig (Python code voor deel 2, voor de nieuwsgierigen), maar voor je daar bent aangekomen moet je wel een aantal vertaalslagen gemaakt hebben.

Python heeft trouwens wel een aantal dingen die goed van pas kwamen:

• Python's pow() functie accepteert een derde argument.
• In Python heeft de uitkomst van de modulus-operator hetzelfde teken als de deler (e.g., -1 % 10 == 9). In de meeste andere programmeertalen heeft de uitkomst juist het teken van het deeltal (e.g., -1 % 10 = -1).

[Daanoz]

Geen fijne dag tot nu toe voor mij... Eerste oplossing voor deel 2 ging 3.8 jaar duren, dus dat werd hem niet, nu met een meer wiskundige aanvalshoek loop ik tegen het integer limiet van JS aan . Daar is dan wel weer het alternatief BigInt voor, maar die kan dan weer niet zomaar machtsverheffen .

[Soultaker]

Daanoz schreef op zondag 22 december 2019 @ 13:05:
Daar is dan wel weer het alternatief BigInt voor, maar die kan dan weer niet zomaar machtsverheffen .

Hint:

spoiler:

Wikipedia: Exponentiation by squaring

Talen zonder bigints zijn hier inderdaad wel in het nadeel. Niet omdat de getallen belachelijk groot worden (je kunt alle operaties modulo N doen), maar omdat de tussenresultaten (het resultaat van een vermenigvuldiging, bijvoorbeeld) niet in een 64-bit integer passen, en je dus ofwel 128-bit integers (die bijna geen enkele taal ondersteunt) of bigints nodig hebt.

[Reynouts]

Soultaker schreef op zondag 22 december 2019 @ 12:37:
Ik heb medelijden met de deelnemers die zonder informatica-opleiding (of op z'n minst gedegen kennis van lineare algebra) deel twee van dag 22 op proberen te lossen.

Om deel 2 van vandaag te tackelen heb je meer aan een wiskunde opleiding dan informatie opleiding. Heeft weinig met programmeren te maken imo.

Petje af als/dat je dit zo uit de mouw schudt. Voor mij was dit helaas een stap te ver om zonder enkele hints op te kunnen lossen.

Morgen maar weer de Intcomputer van stal halen

[Ethikka]

Zelfs met hints snap ik er de ballen van.

Informatica opleiding (en de bijbehorende discrete wiskunde) is meer als 20 jaar terug en verschillende hints leunen dusdanig op harde wiskunde dat ik er niks mee kan. Eerste puzzel in 4 jaar tijd die ik gevoelsmatig gewoon niet kan. Wellicht ga ik hem eens proberen, maar voor nu gooi ik de handdoek in de ring.

[GeertenVink]

Gisteren heb ik er acht en een half uur over gedaan, vandaag voor de derde keer ooit global points, en voor het eerst allebei de parts. #68/46.. dit was triviaal met mijn implementatie van de IntCode VMs. Best wel blij mee.

[GeertenVink]

Soultaker schreef op zondag 22 december 2019 @ 13:16:
Talen zonder bigints zijn hier inderdaad wel in het nadeel. Niet omdat de getallen belachelijk groot worden (je kunt alle operaties modulo N doen), maar omdat de tussenresultaten (het resultaat van een vermenigvuldiging, bijvoorbeeld) niet in een 64-bit integer passen, en je dus ofwel 128-bit integers (die bijna geen enkele taal ondersteunt) of bigints nodig hebt.

Niet per se, je kan (a * b) % m in een n-bits ruimte doen zolang m in (n-1) bits past.

Zoiets:
https://www.geeksforgeeks...egers-under-large-modulo/

[Daanoz]

Ik ben uiteindelijk overstag gegaan, en heb een library gezocht die mathematische berekening kon doen met de BigInt. Ook dat ging niet direct eenvoudig, de eerste die ik probeerde liep ook tegen een limiet bij iets van 1e10000000.

spoiler:

De sleutel zit hem inderdaad in het direct kunnen doen van de modulo bij een berekening.

[Soultaker]

GeertenVink schreef op maandag 23 december 2019 @ 09:55:
Niet per se, je kan (a * b) % m in een n-bits ruimte doen zolang m in (n-1) bits past.

Ach ja, klopt inderdaad. Dat maakt het wel weer iets lastiger omdat je de 128-bits vermenigvuldiging zelf in tweeën moet splitsen. Hetzelfde zou ook in Javascript kunnen, aangezien de modulus ongeveer 48 bits nodig had, en IEEE double-precision floats die Javascript gebruikt een mantissa van 52 bits hebben.

[CMG]

Soultaker schreef op zondag 22 december 2019 @ 12:37:
...
Python heeft trouwens wel een aantal dingen die goed van pas kwamen:

• Python's pow() functie accepteert een derde argument.

Voor C# is er BigInteger.ModPow

[CMG]

GeertenVink schreef op maandag 23 december 2019 @ 06:26:
Gisteren heb ik er acht en een half uur over gedaan, vandaag voor de derde keer ooit global points, en voor het eerst allebei de parts. #68/46.. dit was triviaal met mijn implementatie van de IntCode VMs. Best wel blij mee.

Congrats, dat lijkt me echt een goed gevoel geven Ik ga zelf niet zo ver dat ik er om 6:00 uit voor achter de PC ga zitten, maar dat moet een goed gevoel geven als je de top100 haalt

[Reynouts]

Leuke laatste puzzel om het af te sluiten. In het begin vond ik het intcode verhaal niet zoveel, maar ze hebben er echt coole puzzels mee kunnen maken. Veel van de andere dagen iets met pathfinding, waar bfs vaak prima werkte. Ook weer een paar zeer pittige wiskunde dagen erbij.

Ik heb er dit jaar gemiddeld langer over gedaan dan vorig jaar. Had het idee dat er vorig jaar net wat meer simpele puzzles inzaten die niet voortborduurde op iets wat je al moest hebben.

Heb er wel weer van genoten!

[Soultaker]

Reynouts schreef op woensdag 25 december 2019 @ 15:36:
In het begin vond ik het intcode verhaal niet zoveel, maar ze hebben er echt coole puzzels mee kunnen maken.

Ik vond de intcode-machine vooral een slimme manier om opgaven te kunnen maken waarin je meer moet doen dan alleen één antwoord berekenen. Meestal was de intcode-machine een soort obfuscated testomgeving, die client-side in plaats van server-side draait.

Dat heeft veel voordelen: je kunt interactieve opgaven maken (zoals de Breakout clone en de doolhof) en problemen waarbij je meer feedback krijgt dan alleen goed of fout (zoals de Springbot opgave) en zelfs deelnemers oplossingen laten brute-forcen zonder dat het de server belast. Deelnemers kunnen bovendien in elke taal en omgeving werken die ze maar willen, wat verschilt van wedstrijden waarin deelnemers hun code insturen en die op de server geëvalueerd wordt.

In vorige jaren waren er ook een aantal simulatie-opgaven, waarbij je vooral goed moest lezen en dan precies de beschreven logica moest implementeren, wat niet echt interessant was. Die opgaven lijken dit jaar te zijn vervangen door opgaven waarbij de logica simpelweg in de vorm van een intcode-programma werd aangeleverd. Dat leidde tot leukere programmeerproblemen.

Alleen al door de afwezigheid van simulatie-opgaven vond ik dit jaar leuker dan de vorige jaren.

[Daanoz]

Nog wat mooie grafiekjes van het leaderboard: (Credits to Adé Mochtar & Jeroen Heijmans)

[Reynouts]

@Daanoz tijd voor een nieuw draadje? 😁

[Daanoz]

Reynouts schreef op zondag 29 november 2020 @ 19:31:
@Daanoz tijd voor een nieuw draadje? 😁

Goeie, gaan we doen!

edit, here we go: Advent of Code 2020

[ Voor 28% gewijzigd door Daanoz op 29-11-2020 20:38 ]