Advent of Code 2017

[P.O. Box]

Anoniem: 159174 schreef op maandag 11 december 2017 @ 12:07:
Typische opdracht om eerst na te denken en dan pas code te kloppen. Ik had gedacht dat de tweede opdracht een stuk lastiger zou zijn dan de eerste, maar dat is weer niet zo.

Inderdaad.... mijn probleem was vooral dat ik er niet echt lekker in kwam en daardoor het heel lang duurde voordat ik een logica zag.... eigenlijk stuurde vraag 2 mij pas naar de juiste logica en had ik vraag 1 in eerste instantie heel omslachtig opgelost... uiteindelijk n.a.v. vraag 2 mijn code voor vraag 1 ook ontzettend kunnen versimpelen

[Hydra]

@Lye Korter dan die van mij; nogal overengineered

[ThaStealth]

Dag 12, was eigenlijk wel een makkie tov de vorige 2 dagen

spoiler:

Gewoon recursive door een dictionary zoeken en alle gevonden elements aan een lijstje toevoegen, deel 2 is door alle nummers lopen en kijken of hij nog niet inde bestaande groeplijst zit, als dat niet het geval is is het een losse groep

[vliegnerd]

Eindelijk weer eens:

spoiler:

Breath first search! (python)

[Daedalus]

vliegnerd schreef op dinsdag 12 december 2017 @ 12:04:
Eindelijk weer eens:

spoiler:

Breath first search! (python)

spoiler:

Jammer alleen dat met een set niet is te bepalen of je nu breath-first of depth-first zoekt Bovendien, als je in jouw oplossing de set door een list vervangt is het een depth-first search, tenzij je de pop voor een popleft vervangt. Niet dat het uitmaakt, zowel DFS as BFS werken net zo goed voor dit probleem.

[Quadro!]

Dag 12 in Haskell, Voelt een beetje als cheaten met de juiste library

[vliegnerd]

Quadro! schreef op dinsdag 12 december 2017 @ 12:43:
Dag 12 in Haskell, Voelt een beetje als cheaten met de juiste library

Tof! Fijne library in Haskell!

In 2015 was het elke weer een andere functie van de python "itertools" library, waarmee de puzzel bijna een one-liner werd.

[Hydra]

Quadro! schreef op dinsdag 12 december 2017 @ 12:43:
Dag 12 in Haskell, Voelt een beetje als cheaten met de juiste library

In 2015 heb ik de oplossingen zowel in Java als in Scala gedaan. Er as een vraag waar je alle permutaties van de lijst nodig had. In Java dat dus zelf geimplementeerd, in Scala is dat gewoon een onderdeel van de list API. Scheelde 90% van de code ofzo

[ Voor 3% gewijzigd door Hydra op 12-12-2017 14:22 ]

[vliegnerd]

Daedalus schreef op dinsdag 12 december 2017 @ 12:23:
[...]

spoiler:

Jammer alleen dat met een set niet is te bepalen of je nu breath-first of depth-first zoekt Bovendien, als je in jouw oplossing de set door een list vervangt is het een depth-first search, tenzij je de pop voor een popleft vervangt. Niet dat het uitmaakt, zowel DFS as BFS werken net zo goed voor dit probleem.

Ik zal proberen te antwoorden zonder spoilers

Goed dat je het even aanstipt. Nu heb ik het verschil weer helder. Een list kan nuttig zijn in dit geval. En dan pop() of pop(0) (list.popleft() bestaat niet, dan heb je deque nodig) om te kiezen tussen de twee verschillende manieren van zoek volgorde.

Wel belangrijk als je bijvoorbeeld een echt maze gaat doorzoeken. Wie weet morgen.

[Lye]

vliegnerd schreef op dinsdag 12 december 2017 @ 17:09:
[...]


Ik zal proberen te antwoorden zonder spoilers

Goed dat je het even aanstipt. Nu heb ik het verschil weer helder. Een list kan nuttig zijn in dit geval. En dan pop() of pop(0) (list.popleft() bestaat niet, dan heb je deque nodig) om te kiezen tussen de twee verschillende manieren van zoek volgorde.

Wel belangrijk als je bijvoorbeeld een echt maze gaat doorzoeken. Wie weet morgen.

Het is makkelijk te onthouden als je bedenkt wat je nodig hebt voor de manieren van zoeken.

Als je depth-first zoekt ga je dus zo diep mogelijk, dit doe je op basis van de laatst gegenereerde waarde, dus LIFO => stack.
Als je breadth-first zoekt wil je juist eerst nodes bekijken die zo dicht mogelijk bij je oorspronkelijke node zitten, dus FIFO => queue.

[Bee.nl]

Dag 12 in PHP

Ongeveer 120 ms op een oude machine met PHP 7, dus ik ben niet ontevreden. De snelheidswinst zit hem vooral in het gebruik van array keys ipv values. Verder weer niet heel erg moeilijk.

[Camulos]

Waar @ThaStealth het mooi recursief heeft gedaan... doe ik het iteratief mbv een queue

Dag 12 in C#

Relatieve makkelijke opdracht, zolang je weet hoe je grafen efficient kan coden + doorzoeken.

spoiler:

Deze vraag gaat enkel om hoe groot een bepaalde Forest is, en daarna hoeveel Forests er zijn

[Daedalus]

vliegnerd schreef op dinsdag 12 december 2017 @ 17:09:
[...]


Ik zal proberen te antwoorden zonder spoilers

Goed dat je het even aanstipt. Nu heb ik het verschil weer helder. Een list kan nuttig zijn in dit geval. En dan pop() of pop(0) (list.popleft() bestaat niet, dan heb je deque nodig) om te kiezen tussen de twee verschillende manieren van zoek volgorde.

popleft is inderdaad van een deque. Had even te snel over using lists as queues heen gelezen. Belangrijk is wel om te beseffen dat een set per definitie ongeordend is, en er daarom weinig te LIFO'en of FIFO'en is

[Hydra]

Dag 13 in Kotlin

Kutopdracht

spoiler:

Deel 1 was makkelijk maar ik had een verkeerde aanpak (eigenlijk een simpele simulator) die ik helemaal niet nodig had. Voor part 2 was dat veel en veel te traag.

[Mawlana]

Gisteren moest ik weer hieraan denken... Mooie gelegenheid om eens te stoeien met Python (in plaats van R de afgelopen twee jaren). Inmiddels tot en met dag 6 afgerond.

[Lye]

Hydra schreef op woensdag 13 december 2017 @ 09:08:
Dag 13 in Kotlin

Kutopdracht

spoiler:

Deel 1 was makkelijk maar ik had een verkeerde aanpak (eigenlijk een simpele simulator) die ik helemaal niet nodig had. Voor part 2 was dat veel en veel te traag.

Kutopdracht kun je wel stellen ja..

spoiler:

Mijn eerste plan was ook om een simulator te schrijven. Echter had ik direct al het idee dat dit te traag zou zijn voor 2, dus ben op zoek gegaan naar een alternatieve oplossing. Vond deze opdracht veel lijken op dag 15 van vorig jaar, behalve dat ik niet zo snel kon bedenken hoe ik hier het Chinese remainder theorem voor kon gebruiken (al zou dat wel mogelijk moeten zijn)..

Uit eindelijk best tevreden met mijn oplossing, draait in minder dan 100ms

[Anoniem: 159174]

Gewoon bruteforcen: rond de 80ms.

spoiler:

En niet vergeten dat bij het tweede deel de eerste wall er wel enigzins toe doet

[Peelee]

Voor deel 2 de vraag absoluut niet goed gelezen stelde ik na een tijdje (en een aantal foute antwoorden) vast Voortaan goed lezen is dus de boodschap

spoiler:

ik liep door de firewall en stopte telkens 1 picoseconde als er niet verder gegaan kon worden als de volgende layer een scanner had, waarbij ik dan de totale doorlooptijd als antwoord gaf. Ipv in het begin te staan wachten om er vervolgens in 1 keer door te kunnen gaan..

[ThaStealth]

spoiler:

Eerst een simulator geschreven, die deed er na optimizen ~13 sec over. Je kunt namelijk de status voordat je de firewall in gaat "saven" en deze als je "af" bent weer terugzetten + 1 beweging extra doen om de simulator klaar te zetten voor de volgende poging en door ook een early exit te doen als je 1 node raakt (want je wil 0 hits hebben) ipv de hele riedel door te rekenen
Nadat ik het antwoord gegeven had nog even geoptimaliseerd en tot de conclusie gekomen dat je kan uitrekenen wat de positie van een node is aan de hand van de verstreken tijd (die formule uitdokteren was even een gepiel). Resultaat is een winst van ~500ms
Daarna nog wat verder geoptimaliseerd (gebruikte eerst een Dictionary om te bepalen wat de lengte was van elke layer, maar hier liep ik tegen performanceprobleem van de ContainsKey functie aan), deze eerst omgescheven naar een List<int> (~ 200ms) en vervolgens naar een array (<80ms)

Dag 13, C#

[Kraay89]

Kan iemand mij een tip geven over dag 10? Door de wall of text is me niet duidelijk wat ik nou moet hashen en wat ik moet gebruiken als 'list of lengths' voor die hash. Ik interpreteer het als beide de input string?

Dus de input string hashen met de inputstring geconverteerd tot lengths?
of begin ik net als bij deel 1 met een lijst van 0 tm 255?

[ Voor 9% gewijzigd door Kraay89 op 13-12-2017 14:53 ]

[Anoniem: 420461]

In deel 2 werk je met de ASCII codes van de input (waar je 17, 31, 73, 47, 23 achter plakt) en moet je van het resultaat steeds elke 16 met elkaar Xor-en om tot 16 getallen te komen die je dan weer omzet naar een hex string.

[ Voor 10% gewijzigd door Anoniem: 420461 op 13-12-2017 14:46 ]

[Kraay89]

Anoniem: 420461 schreef op woensdag 13 december 2017 @ 14:44:
In deel 2 werk je met de ASCII codes van de input (waar je 17, 31, 73, 47, 23 achter plakt) en moet je van het resultaat steeds elke 16 met elkaar Xor-en om tot 16 getallen te komen die je dan weer omzet naar een hex string.

Met alle respect: Daar heb ik geen fluit aan. Het is geen antwoord op mijn vraag maar een (zeer matige) herhaling van de opdracht.

[Anoniem: 420461]

Wat wil je dan - dat ik je er stap voor stap doorheen praat? Als je het niet zelf wilt uitvogelen kun je beter in de eerste post even naar de diverse gits kijken hoe anderen het aangepakt hebben.

[Kraay89]

Nee, ik vraag welke input en welk startpunt ik moet gebruiken. 1 hash ronde gebruikt de input(+ een paar waarden) als lengths. Maar waar voer ik die hash op uit? ook op diezelfde input?

Edit: Voor de duidelijkheid: ik ben nog helemaal niet bezig met die dense hash. dus XOR ben ik nog niet aan toe. Puur het startpunt begrijp ik niet.

[ Voor 29% gewijzigd door Kraay89 op 13-12-2017 14:59 ]

[Anoniem: 420461]

Je gebruikt de ASCII waardes plus suffix als input om de eerste ronde nu 64 keer te doorlopen, waarbij je current position en skip size niet reset bij elke ronde..

[Kraay89]

Ja maar... ugh. je snapt me niet.

spoiler:

voorbeeld.
'1,2,3' is de input. ASCII is dat [49, 44, 50, 44, 51]. Ga ik dit dan hashen met [49, 44, 50, 44, 51, 17, 31, 73, 47, 23] (hetzelfde + die extra waarden?)

dat kan toch niet?

[ Voor 4% gewijzigd door Kraay89 op 13-12-2017 15:10 ]

[ThaStealth]

Kraay89 schreef op woensdag 13 december 2017 @ 14:58:

spoiler:

Nee, ik vraag welke input en welk startpunt ik moet gebruiken. 1 hash ronde gebruikt de input(+ een paar waarden) als lengths. Maar waar voer ik die hash op uit? ook op diezelfde input?

Edit: Voor de duidelijkheid: ik ben nog helemaal niet bezig met die dense hash. dus XOR ben ik nog niet aan toe. Puur het startpunt begrijp ik niet.

Anoniem: 420461 schreef op woensdag 13 december 2017 @ 15:01:

spoiler:

Je gebruikt de ASCII waardes plus suffix als input om de eerste ronde nu 64 keer te doorlopen, waarbij je current position en skip size niet reset bij elke ronde..

Heren, even de [ spoiler] tag gebruiken.

spoiler:

Bij opdracht 1 interpreteer je de lijst als integers, dus als er 14,20,41 staat interpreteer je dus ook 14 en 20 en 21. Bij opdracht 2 moet je de waardes converteren naar chars dus:
14,20,41 word dan:
49 en 52 en 44 => 14,
50 en 48 en 44 => 20,
52 en 49 en 44 => 41,

Daarna moet je nog die waardes toevoegen. Je lijst van lengtes word ~3x zo lang

Oja, je "basis" waar je de bewerkingen op uitvoert is een lijstje met x nummers die je gaat husselen. Dat "lijstje" van 0..5 in het voorbeeld word dan dmv de start positie tot start pos + lengte iedere keer gedraaid.
Je hebt slechts 1 input, en dat is je lijst met lengtes.

Hopelijk is het nu duidelijker.

[ Voor 24% gewijzigd door ThaStealth op 13-12-2017 15:14 ]

[Kraay89]

ThaStealth schreef op woensdag 13 december 2017 @ 15:08:
[...]

Heren, even de [ spoiler] tag gebruiken.

spoiler:

Bij opdracht 1 interpreteer je de lijst als integers, dus als er 14,20,41 staat interpreteer je dus ook 14 en 20 en 21. Bij opdracht 2 moet je de waardes converteren naar chars dus:
14,20,41 word dan:
49 en 52 en 44 => 14,
50 en 48 en 44 => 20,
52 en 49 en 44 => 41,

Daarna moet je nog die waardes toevoegen. Je lijst van lengtes word ~3x zo lang

Hopelijk is het nu duidelijker.

Sorry, volgens mij vielen de spoilers wel mee. Mijn laatste voorbeeld dan maar even ingekapseld.

spoiler:

Ik snap die conversie wel. Ik snap niet wat je vervolgens moet hashen.

[EagleTitan]

Kraay89 schreef op woensdag 13 december 2017 @ 15:14:
[...]


Sorry, volgens mij vielen de spoilers wel mee. Mijn laatste voorbeeld dan maar even ingekapseld.

spoiler:

Ik snap die conversie wel. Ik snap niet wat je vervolgens moet hashen.

spoiler:

Het resultaat van de lijst van 0 tot 255

[ThaStealth]

Kraay89 schreef op woensdag 13 december 2017 @ 15:14:
[...]


Sorry, volgens mij vielen de spoilers wel mee. Mijn laatste voorbeeld dan maar even ingekapseld.

spoiler:

Ik snap die conversie wel. Ik snap niet wat je vervolgens moet hashen.

spoiler:

Hetzelfde als bij opdracht 1.
Bij het voorbeeld opdracht 1 heb je een lijstje van 0..5 die je dmv de lengtes die je als int lijst krijgt shuffled.
Deze lijst word naar 256 veranderd bij de echte opdracht. Dit geld nog steeds voor opdracht 2.
Je hebt dus een lijst van 256 getallen (0..255) die je moet shuffelen aan de hand van de lengtes die je als char lijst krijgt nu

[Kraay89]

EagleTitan schreef op woensdag 13 december 2017 @ 15:16:
[...]

spoiler:

Het resultaat van de lijst van 0 tot 255

ThaStealth schreef op woensdag 13 december 2017 @ 15:17:
[...]

spoiler:

Hetzelfde als bij opdracht 1.
Bij het voorbeeld opdracht 1 heb je een lijstje van 0..5 die je dmv de lengtes die je als int lijst krijgt shuffled.
Deze lijst word naar 256 veranderd bij de echte opdracht. Dit geld nog steeds voor opdracht 2.
Je hebt dus een lijst van 256 getallen (0..255) die je moet shuffelen aan de hand van de lengtes die je als char lijst krijgt nu

Toch wel dus. Bedankt.

[vliegnerd]

[quote]Lye schreef op woensdag 13 december 2017 @ 10:10:
[...]

spoiler:

Mijn eerste plan was ook om een simulator te schrijven. Echter had ik direct al het idee dat dit te traag zou zijn voor 2, dus ben op zoek gegaan naar een alternatieve oplossing. Vond deze opdracht veel lijken op dag 15 van vorig jaar, behalve dat ik niet zo snel kon bedenken hoe ik hier het Chinese remainder theorem voor kon gebruiken (al zou dat wel mogelijk moeten zijn)..

[quote]

Het is inderdaad overduidelijk op te lossen met

spoiler:

Chinese remainder theorem

Alleen moet ik nog steeds uitvogelen hoe dat werkt

[Anoniem: 1004565]

https://github.com/DutchG...er/Rust/day13/src/main.rs

Beide delen ook nog cuncurrent gedaan!

[Camulos]

Dag 13 was leuk! Deel 1 + Deel2 binnen 350ms

Toch eens gekeken hoe ik linq kon gebruiken om van de string-input direct een dictionary te maken.
Verder veel te lang bezig geweest om de movement van de scanners te ontdekken

spoiler:

Had eerst net als anderen een simulator geschreven om het heen-en-weer-gaande beweging te simuleren, wat natuurlijk erg traag is.. en dan kom je er achter dat het met kan met:
PositieVanScanner = picosecond % (2 * firewall[picosecond] - 2)

En met achter komen is het vooral kijken/leren/inspireren uit de reddit solution thread

C# oplossing dag 13

[farlane]

Loop natuurlijk al weer veel te ver achter door tijdgebrek maar heb zojuist dag 9 gedaan met C#, op Linux met VSCode/NET core. Blij verrast moet ik zeggen, verbazend.

[Anoniem: 1004565]

veldsla schreef op dinsdag 12 december 2017 @ 10:28:
[...]


Helpt zeker! zit nu op zo'n 3.5ms.

Day 12 vond ik weer tijd voor een eenvoudig perl scriptje!

heb dag 10 nog ff aangepast... https://github.com/DutchG...er/Rust/day10/src/main.rs

Nu is 'ie nog véél sneller!!!

[EagleTitan]

Veel te lang lopen kloten met deel 1.

spoiler:

Je moet dus ook de extra lengths toevoegen zoals bij deel 2 van dag 10

Nu eens kijken hoe we deel 2 gaan oplossen.

[vliegnerd]

EagleTitan schreef op donderdag 14 december 2017 @ 09:23:
Veel te lang lopen kloten met deel 1.

spoiler:

Je moet dus ook de extra lengths toevoegen zoals bij deel 2 van dag 10

Ja, precies, daarom:

spoiler:

Deze commit zodat ik:

from day10 import knot_hash
kan doen

[ Voor 7% gewijzigd door vliegnerd op 14-12-2017 10:05 ]

[Lye]

Nou, voor het eerst in mijn leven coroutines gebruikt om de knot hashes te berekenen. Scheelt toch de helft van de tijd.

spoiler:

Bij deel 2 een paar hele domme fouten gemaakt. Java's BitSets hebben als leftmost bit natuurlijk de hoogste index en je moet in- en exclusive ranges niet door elkaar halen..

Ik was voor de verandering eens op tijd wakker. Als ik bovenstaande fouten niet gemaakt had was het algoritme wat had moeten werken genoeg geweest voor een top 100 plek, echter heb ik bovenstaande fouten waarschijnlijk gemaakt omdat ik vroeg wakker was

Kotlin oplossing

Overigens Tip voor dag 14 (en 10):

spoiler:

Je hoeft de binary representation van de hexadecimale string natuurlijk niet te bepalen als je knot hash functie geen hexadecimale string maar een byte array teruggeeft. Dit scheelt 2 conversies per hash, wat op zich toch prettig is

.

[ Voor 17% gewijzigd door Lye op 14-12-2017 09:51 ]

[Hydra]

Mijn Kotlin oplossing voor dag 14

In deel 1 een domme fout gemaakt en veel te lang bezig geweest.

spoiler:

Als er een fout in je to-binary methode zit die je niet kunt zien in de eerste input, dan duurt het wel ff voordat je doorhebt waar de fout zit. En een simpele 'to binary' functie is natuurlijk triviaal en je verwacht niet dat daar de fout in zit.

Deel 2 was relatief simpel; die squares had ik al. Dan nog een flood-fill bouwen.

[ThaStealth]

Dag 14 in C#
Uurtje bezig geweest (veel langer dan ik gewild had).

spoiler:

Vond het jammer dat je Dag 10 moest gebruiken, als je dit niet had was je meteen kansloos hier. Uiteindelijk lang vast gezeten op het probleem dat je bij probleem 2 van dag 10 die extra tekens moest meegeven, dit had ik niet door waardoor ik de hele tijd de verkeerde hashes kreeg... En er was natuurlijk geen voorbeeldje gegeven van "Voorbeeld input geeft "d1acce...." als eerste hash.

[Hydra]

Ik liep zelf ook een beetje stuk op het gebrek aan voorbeelden. Ik dacht namelijk eerst dat m'n hash verkeerd was (hoewel ik die hergebruik van Dag 10).

[Anoniem: 1004565]

Deel 1 dag 14:
https://github.com/DutchG...er/Rust/day14/src/main.rs

[vliegnerd]

Dag 14 in python

Vandaag een combinatie van dag 10 van 2017 en dag 13 van 2016 Wel een leuke opdracht

spoiler:

Ik had in mijn knot_hash functie van dag 10 last van het gebrek aan leading zero's. In deel A nog geen probleem, maar voor deel B wel... Het doolhof klopt dan gewoon niet.

Mijn oplossing voor deel B is de maze solver van dag 13 van 2016. Dat was geen probleem, maar er zat nog best wat werk in het debuggen van de leading zero's in dag10 (in de hexstring) en daarna leading zero's in de binary string...

[Daanoz]

veldsla schreef op zondag 10 december 2017 @ 11:34:
Mooie hash functie hoor zo'n knot hash . Vorig jaar zaten we flink in de md5, dus we hebben kans deze nog eens nodig te hebben!

Iets met voortschrijdend inzicht? Na deze post nog even getwijfeld om alvast het voorbereidende werk te doen... Vanochtend natuurlijk spijt, koste toch wel weer even een minuutje of 10 om het netjes te exposen en tegelijkertijd dag 10 in leven te houden...

[rnark]

Na een paar dagen weinig tijd vandaag weer begonnen met dag 15, nu nog 'even' de overige dagen inhalen.

[EagleTitan]

Dag 15 was wel weer heel simpel

[Hydra]

Inderdaad. Erg makkelijk.

rnark schreef op vrijdag 15 december 2017 @ 06:32:
Na een paar dagen weinig tijd vandaag weer begonnen met dag 15, nu nog 'even' de overige dagen inhalen.

In ieder geval Dag 10 doen voor je Dag 14 doet

[ Voor 46% gewijzigd door Hydra op 15-12-2017 08:09 ]

[ThaStealth]

Dag 15 in C#

Was een makkie tov de vorige dagen, fijn om met een makkelijke de vrijdag te beginnen .

[veldsla]

Daanoz schreef op donderdag 14 december 2017 @ 21:04:
Iets met voortschrijdend inzicht? Na deze post nog even getwijfeld om alvast het voorbereidende werk te doen... Vanochtend natuurlijk spijt, koste toch wel weer even een minuutje of 10 om het netjes te exposen en tegelijkertijd dag 10 in leven te houden...

Altijd leuk om gelijk te krijgen ik moest pub voor de functie zetten en het was klaar . Dag 15 met rust iterators. eitje.

spoiler:

Hoewel ik het natuurlijk eerst fout deed en 40M iteraties voor b uitvoerde...

[Reptile209]

Dag 15 was inderdaad niet erg ingewikkeld.

spoiler:

Is er nog een handigere manier om (waarde * factor) % maxint te berekenen, al dan niet in combinatie met dat je alleen de laatste 16 bits nodig hebt? Heb het nu gewoon brute-force gedaan in PHP, maar ik heb het gevoel dat je dit wiskundig kunt optimaliseren.

En nog een vraag: kan je nog ergens terugzien welke score's je per dagdeel hebt gekregen binnen de Tweakers Leaderboard?

[Radiant]

veldsla schreef op vrijdag 15 december 2017 @ 09:36:
[...]

spoiler:

Hoewel ik het natuurlijk eerst fout deed en 40M iteraties voor b uitvoerde...

spoiler:

Ik had er even 50M laten berekenen

[Anoniem: 159174]

[quote]Reptile209 schreef op vrijdag 15 december 2017 @ 09:41:
Dag 15 was inderdaad niet erg ingewikkeld.

spoiler:

Is er nog een handigere manier om (waarde * factor) % maxint te berekenen, al dan niet in combinatie met dat je alleen de laatste 16 bits nodig hebt? Heb het nu gewoon brute-force gedaan in PHP, maar ik heb het gevoel dat je dit wiskundig kunt optimaliseren.

Gevoelsmatig denk ik van niet. 2^31-1 en 2^16-1 zijn relatief priem, en dan gaat het denk ik niet goed met de resten... maar ja, dat is slechts een gevoel.

[Anoniem: 1004565]

Voor Rust is er een library wat het concurrent uitrekenen van dingen erg makkelijk maakt..., bij deel 2 kan je namelijk elke het volgende nummer van Generator1 en Generator2 tegelijkertijd uitrekenen.

Tevens start berekent dit ook part1 en part2 tegelijkertijd!
https://github.com/DutchG...er/Rust/day15/src/main.rs

runned in 29 seconden!

Edit: strings waren langzaam...xor was veul sneller

[ Voor 7% gewijzigd door Anoniem: 1004565 op 15-12-2017 15:53 ]

[veldsla]

Ehm 29s? Misschien nog even kijken waar die tijd in zit dan (is dat wel een release build?). Het kan op 1 core in ~0.5s.
Oh wacht:

spoiler:

Je vergelijkt de bits mbv de string representatie. dat zal wel wat schelen!

Dat ziet er al een stuk beter uit.

spoiler:

Leuk dat je mijn XOR modulo oplossing hebt gebruikt. De mask AND is in theorie vast sneller. In de praktijk optimaliseert de compiler het verschil weg.

Nu heb je eigenlijk alleen nog last van de overhead van de parallelle calls naar de iterator next. Haal die eens weg en je zult zien dat het nog rapper loopt!

[ Voor 75% gewijzigd door veldsla op 15-12-2017 13:48 ]

[Soultaker]

Mja, dag 15 is zo'n fuck-deelnemers-die-een-dynamische-taal-gebruiken opgave. 40 miljoen iteraties is niet veel in C, maar wel in Python.

Mijn eenvoudige oplossing in Python duurt 40 seconden.

Mijn oplossing geoptimaliseerd met Numpy heeft er nog 2 seconden voor nodig, en is een stuk minder leesbaar.

Trouwens, mis ik iets, of heeft numpy geen implementatie van machtsverheffen-modulo-n (zoals de standaardfunctie pow() wel ondersteunt?) Daar zit nu de bottleneck, maar ik weet niet hoe ik dat in numpy moet implementeren. edit: handmatig wat geoptimaliseerd; daar bleek niet veel tijdswinst mee te behalen.

[ Voor 6% gewijzigd door Soultaker op 15-12-2017 12:54 ]

[Anoniem: 1004565]

veldsla schreef op vrijdag 15 december 2017 @ 12:29:
Ehm 29s? Misschien nog even kijken waar die tijd in zit dan (is dat wel een release build?). Het kan op 1 core in ~0.5s.
Oh wacht:

spoiler:

Je vergelijkt de bits mbv de string representatie. dat zal wel wat schelen!

Dat ziet er al een stuk beter uit.

spoiler:

Leuk dat je mijn XOR modulo oplossing hebt gebruikt. De mask AND is in theorie vast sneller. In de praktijk optimaliseert de compiler het verschil weg.

Nu heb je eigenlijk alleen nog last van de overhead van de parallelle calls naar de iterator next. Haal die eens weg en je zult zien dat het nog rapper loopt!

YUP hahahaha, dacht eerst dat het omzetten van getal naar binair als String wel een goede approach zou zijn....die xor is wel slim!!!

[DRaakje]

Vandaag was inderdaad er makkelijk. Voor de C# mensen onder ons.

code:

0b1111_1111_1111_1111 == 0xFFFF

is een erg fijne manier van werken met binary dingen

verder gisteren nog een video gemaakt van mijn oplossing

[herbalmart77]

https://ibb.co/kQEozm

Gatenkaas

[ Voor 47% gewijzigd door herbalmart77 op 15-12-2017 16:05 ]

[Daedalus]

Soultaker schreef op vrijdag 15 december 2017 @ 12:34:
Mja, dag 15 is zo'n fuck-deelnemers-die-een-dynamische-taal-gebruiken opgave. 40 miljoen iteraties is niet veel in C, maar wel in Python.

Mijn eenvoudige oplossing in Python duurt 40 seconden.

Mijn oplossing geoptimaliseerd met Numpy heeft er nog 2 seconden voor nodig, en is een stuk minder leesbaar.

Trouwens, mis ik iets, of heeft numpy geen implementatie van machtsverheffen-modulo-n (zoals de standaardfunctie pow() wel ondersteunt?) Daar zit nu de bottleneck, maar ik weet niet hoe ik dat in numpy moet implementeren. edit: handmatig wat geoptimaliseerd; daar bleek niet veel tijdswinst mee te behalen.

PyPy helpt veel in dit soort situaties. Executietijd ging van 38 + 21 seconden naar 1.1 + 1.5 seconden hier. Het vreemde is wel dat als ik jouw eenvoudige oplossing in PyPy draai het 6.6 seconden duurt. Als je de list comprehension vervangt door een loop (zoals hier) scheelt het een seconde, maar dan nog duurt het twee keer zolang, terwijl onze code nagenoeg identiek is.

[veldsla]

One Biiilion....En iets met een pink. Dat is zelfs te veel voor een gecompileerde taal (als de inner loop ook 10k iteraties is....zo beter? )

[ Voor 24% gewijzigd door veldsla op 16-12-2017 11:11 ]

[Soultaker]

veldsla schreef op zaterdag 16 december 2017 @ 10:59:
One Biiilion....En iets met een pink. Dat is zelfs te veel voor een gecompileerde taal

Ehh, een gecompileerd taal kan prima een miljard instructies per seconde uitvoeren. Maar er is inderdaad een betere aanpak te bedenken.

(Ik baal dat ik dit weekend zonder laptop op reis ben dus kan ik helaas niet coden...)

[Bee.nl]

Toch een relatief makkelijke opdracht voor een weekenddag. Mijn oplossing (php).

spoiler:

Er zit een cyclus in de dans. Dus het is een kwestie van de cyclus bepalen en dan de programmavolgorde opzoeken die hoort bij 1E9 % cyclus.

[Anoniem: 420461]

Bee.nl schreef op zaterdag 16 december 2017 @ 11:30:
Toch een relatief makkelijke opdracht voor een weekenddag.

Ligt er een beetje aan hoe duf je bent van de avond ervoor...

spoiler:

Ik heb dus echt veel te lang binnen de 10K moves naar dubbele gezocht, in plaats van in het resultaat ervan...

[Anoniem: 1004565]

https://github.com/DutchG...er/Rust/day16/src/main.rs

Niet heel moeilijk....

[EagleTitan]

Dag 16: dat duurde inderdaad wel even om te berekenen. Het uitdenken was sneller klaar zullen we maar zeggen

spoiler:

Maar met hint van @Bee.nl is het inderdaad zo klaar

edit:
Nu met extra optimalisaties (eenmalig parsen van instructies naar implementatie in Go interfaces), antwoord rond de 50ms

[ Voor 19% gewijzigd door EagleTitan op 16-12-2017 16:24 . Reden: optimaliseren kan je leren ]

[DRaakje]

ik had die hint niet nodig, maar bedacht hem nadat ik een half uur bezig was geweest om het dans algoritme te optimaliseren.

[ Voor 20% gewijzigd door DRaakje op 16-12-2017 15:26 ]

[Anoniem: 159174]

Toen ik de eerste opdracht las, wilde ik eigenlijk stoppen. Zo saai... Maar ff weggelegd voor de middag. Maar het tweede deel maakte het weer goed. Leuk om even na te denken hoe dit oplosbaar kon zijn.

[Reptile209]

Reptile209 schreef op vrijdag 15 december 2017 @ 09:41:
[...]
En nog een vraag: kan je nog ergens terugzien welke score's je per dagdeel hebt gekregen binnen de Tweakers Leaderboard?

Toch wat gevonden: via de link naar de API bij de private leaderboard kan je een pak met JSON data (https://adventofcode.com/.../private/view/189709.json) ophalen met alle timestamps. Volgens mij zou je daarmee de scorelijst opnieuw kunnen berekenen, dus ook je eigen punten per onderdeel. #boelwerk.

[Lye]

Ik vond vandaag vervelend. Doordat er geen voorbeeld output bij 2 beschikbaar was werd het erg lastig om mijn algoritme te kunnen debuggen.

[Anoniem: 420461]

Reptile209 schreef op zaterdag 16 december 2017 @ 20:45:
#boelwerk.

Even snel dan...

[ThaStealth]

Whoehoe, eerste tweaker die dag 17 afheeft,
Vandaag was redelijk simpel tov gisteren, wat wel vervelend is dat er zowel gister als vandaag geen voorbeeld was bij probleem 2, gister heb ik er lang op gezeten om te achterhalen waar mijn bug zat (wat eenvoudig zou zijn met een fatsoenlijk voorbeeld).

spoiler:

Ik heb wat tijd verknalt vandaag met het verkeerd lezen van opdracht 2, ze vragen niet de currPos+1 waarde maar de waarde van plek 1...

[Reptile209]

Anoniem: 420461 schreef op zondag 17 december 2017 @ 03:24:
[...]

Even snel dan...

Nice

[Hydra]

Dag 16

spoiler:

Deel een was simpel en ik had 't net voordat ik weg moest af. Deel 2 daarentegen was te brute-forcen maar de runtime was immens. Maarja, je moet toch weg en toen ik een paar uur later terug was, had 'ie wel gewoon een correct antwoord

Vandaag dus maar even weer mee verder gegaan (na deel 17) en kwam er redelijk snel achter dat de patronen redelijk korte cycles hebben.

Dag 17

spoiler:

Weer een leuke oplossing bedacht die natuurlijk in deel 2 waardeloos was. Duurde wel ff voordat ik een methode had gevonden om deel 2 te berekenen zonder al die operaties ook daadwerkelijk op collections te doen.

[Lye]

Nou had ik voor deel 2 van vandaag een mooie functionele oplossing bedacht, deze werkte maar wat was die verschrikkelijk traag zeg.. Het duurde om en nabij de 850ms om de oplossing te genereren.

Een meer imperatieve oplossing die praktisch hetzelfde doet is meer 3x zo snel met 300ms.. Dan maar op deze manier

[Anoniem: 1004565]

Vond deel 2 niet leuk...
Dit is een poging tot bruteforce

http://prntscr.com/hooect

https://github.com/DutchG...er/Rust/day17/src/main.rs

EDIT

na wat gepieker toch maar besloten gebruik te maken van een LinkedList. GGRR Rust std-lib, er is dus geen .insert(positie, element) functie voor de linkedlist uit de std-lib....
gelukkig beston er al een crate die dit wel kon!
Een runtime van ~1640 seconden, maarja...

https://github.com/DutchG...er/Rust/day17/src/main.rs

Het kan volgens mij hier en daar nog iets verbeterd worden...

[ Voor 58% gewijzigd door Anoniem: 1004565 op 18-12-2017 00:05 ]

[Hydra]

Kotlin Dag 18

Son-of-a-bitch. Kleine spoiler voor de mensen die vast zitten:

spoiler:

32 bits ints zijn niet groot genoeg voor de registers.

Toen ik dat eenmaal doorhad, had ik meteen het antwoord. En deel 2 was, afgezien van dat de aanpak compleet anders was, best simpel.

[rnark]

Erg leuke opdracht vandaag! Deel twee kostte me meer tijd dan ik verwacht had, kon de vinger niet leggen op een fout. Uiteindelijk de eerste paar instructies met de hand gedaan, toen was de fout snel boven tafel

[Peelee]

Son-of-a-bitch. Kleine spoiler voor de mensen die vast zitten:

spoiler:

32 bits ints zijn niet groot genoeg voor de registers.

Same here..

spoiler:

Ik dacht eerst dat ik een instructie verkeerd interpreteerde doordat ik plots negatieve waarden kreeg, tot ik ook in de gaten had dat het door een overflow kwam

[Soultaker]

Hoe efficiënt is jullie oplossing voor deel 2 van dag 17 (Spinlock)?

Met K=303 (mijn invoer) en N=50,000,000 is de voor de hand liggende O(NK) oplossing nog best traag. Ik kan wel een manier bedenken om het in O(N log K) te doen, maar eigenlijk is het de factor N die kleiner moet worden, en daar heb ik geen goed idee voor.

Anoniem: 1004565 schreef op zondag 17 december 2017 @ 16:38:
na wat gepieker toch maar besloten gebruik te maken van een LinkedList. GGRR Rust std-lib, er is dus geen .insert(positie, element) functie voor de linkedlist uit de std-lib....
gelukkig beston er al een crate die dit wel kon!
Een runtime van ~1640 seconden, maarja...

Je hebt helemaal geen expliciete linked list nodig, je kunt gewoon indices van 0 t/m N als identifiers gebruiken, en je hoeft alleen maar de successor van elke node op te slaan. Daarvoor is een array van integers genoeg, zoals in m'n Python oplossing:
https://github.com/maksve...b/master/2017/17B-slow.py

edit: dit is sowieso geen handige aanpak. Zie P.O. Box' reactie hieronder.

[ Voor 4% gewijzigd door Soultaker op 18-12-2017 13:43 ]

[P.O. Box]

Soultaker schreef op maandag 18 december 2017 @ 13:12:
Hoe efficiënt is jullie oplossing voor deel 2 van dag 17 (Spinlock)?

Met K=303 (mijn invoer) en N=50,000,000 is de voor de hand liggende O(NK) oplossing nog best traag. Ik kan wel een manier bedenken om het in O(N log K) te doen, maar eigenlijk is het de factor N die kleiner moet worden, en daar heb ik geen goed idee voor.


[...]

Je hebt helemaal geen expliciete linked list nodig, je kunt gewoon indices van 0 t/m N als identifiers gebruiken, en je hoeft alleen maar de successor van elke node op te slaan. Daarvoor is een array van integers genoeg, zoals in m'n Python oplossing:
https://github.com/maksve...e/blob/master/2017/17B.py

spoiler:

Je hoeft de de list sowieso niet vast te leggen, omdat je altijd het 2e element nodig hebt. Alle overige elementen vastleggen is daarmee overbodig zolang de wegschrijf-positie niet gelijk is aan 1. In php ging daardoor mijn loopje van heul lang (heb hem niet afgewacht) naar enkele seconden voor 50.000.000....

[Soultaker]

P.O. Box schreef op maandag 18 december 2017 @ 13:31:
(spoiler voor 17B)

Ahh, dat had ik nog helemaal niet bedacht (terwijl dat veel meer lijkt op m'n aanpak van dag 17A). Slim! Dat maakt de implementatie sowieso O(N) en inderdaad redelijk snel (nog steeds meerdere seconden in Python, maar PyPy helpt).

[Anoniem: 159174]

Deel 1 ging prima, deel twee gaat even op de plank. Het moet wel leuk en combineerbaar met andere zaken blijven. Mis nu met C wel de taalconstructies als objecten, queues etc... Tja, eigen keus he..

[kenneth]

Zoals verwacht erg weinig tijd gehad na dag 8. Nu de lessen van de eerste week mentaal verwerkt zijn kijk ik opeens opvallend anders naar de problemen. Ik denk sneller in termen van folds, state machines en adt's. Zo was dag 9 eenvoudig toen het kwartje eenmaal viel en het kwartje valt steeds sneller. Ik was eerst bezig met een redelijk imperatieve oplossing maar het voelde al snel te omslachtig. Ik vind deze oplossing best elegant en aangezien ik op reddit dezelfde aanpak veel voorbij zag komen zal dat oordeel wel kloppen

Goed, halverwege dag 10 en de komende anderhalve week vakantie. Ik heb jullie hopelijk voor maandag bijgehaald

[veldsla]

Jammer dat de dag 18 opdracht niet in het weekend viel. Nu geen tijd om de code van vorig jaar op te ruimen. Wel een geinige variatie dit jaar.

[EagleTitan]

De halve dag besteed aan deel 2 omdat

spoiler:

de condition check voor de jump keek of niet 0 in plaats van groter dan 0

En dat maakte voor deel 1 geen verschil in de uitkomst, dus je merkt het ook niet

[ Voor 18% gewijzigd door EagleTitan op 18-12-2017 15:45 ]

[Hydra]

kenneth schreef op maandag 18 december 2017 @ 14:45:
Zoals verwacht erg weinig tijd gehad na dag 8. Nu de lessen van de eerste week mentaal verwerkt zijn kijk ik opeens opvallend anders naar de problemen. Ik denk sneller in termen van folds, state machines en adt's.

Precies! En dat vind ik ook zo cool van dit soort challenges. Zit toch al een tijdje in 't vak en het traint lekker de hersenspiertjes. Komt nog eens bij dat ik redelijk handig met Kotlin begin te worden en dat gaat in de nabije toekomst ook handig zijn.

Nadeel is alleen dat ik voor m'n werk nog Java type en ik continue puntcomma's vergeet en zo veel meer code moet schrijven

[wmkuipers]

Verwarrende deel 2 vandaag, heeft me veel tijd gekost.

[Quadro!]

Ik vond deel 2 wel tof vandaag! Ik heb alleen geen flauw idee hoe je fatsoenlijk concurrent dingen in Haskell doet, dus maar even snel iets in Go in elkaar geklust. Als ik meer tijd heb probeer ik hem nog wel in Haskell op te lossen.

[Soultaker]

Quadro! schreef op maandag 18 december 2017 @ 19:59:
Ik vond deel 2 wel tof vandaag! Ik heb alleen geen flauw idee hoe je fatsoenlijk concurrent dingen in Haskell doet, dus maar even snel iets in Go in elkaar geklust.

Je hoeft geen multithreading te gebruiken.

spoiler:

Je kunt gewoon twee machines maken en om-en-om een stap uitvoeren. Als een machine een rcv instructie probeert uit te voeren terwijl er geen uitvoer van de ander machine beschikbaar is, laat je 'm een stap overslaan.

(Python voorbeeld.) Dat moet in Haskell ook gewoon kunnen; sterker nog, dat is niet veel ingewikkelder dan de aanpak van deel 1.

[P.O. Box]

kan iemand die deel 2 van dag 18 heeft opgelost mijn zijn input en zijn antwoord PM'en? Ik krijg namelijk een oplossing, maar de site zegt dat mijn oplossing niet goed is, however, hij is wel goed voor iemand anders zijn opgave. Ik zal vast een fout gemaakt hebben, maar wil dat even uitsluiten door iemand anders zijn input te testen en te kijken of ik dan het juist antwoord (wat jij dus dan al hebt getoetst) wél krijg....

nevermind... ik zat program-0 te tellen grrrr....

[ Voor 6% gewijzigd door P.O. Box op 18-12-2017 22:36 ]

[Bee.nl]

Heel lang zitten staren op dag 18 deel 2. De code had ik vrij snel en alles leek te kloppen, maar toch kwam er steeds niet het juiste antwoord uit. Was ik gewoon vergeten om het eerste argument bij de jump te checken. Het kon immers zowel een registerwaarde als een vast getal zijn

Mijn php-oplossing voor vandaag. It ain't pretty, maar na zo lang staren was ik er wel even klaar mee.

[vliegnerd]

Bee.nl schreef op maandag 18 december 2017 @ 22:52:
Heel lang zitten staren op dag 18 deel 2. De code had ik vrij snel en alles leek te kloppen, maar toch kwam er steeds niet het juiste antwoord uit. Was ik gewoon vergeten om het eerste argument bij de jump te checken.

Precies dat... 2 uur frustratie ofzo.

[EagleTitan]

Zo, dat was day 19. Redelijk simpel

[Hydra]

Dag 19

Toch best ff mee bezig geweest.

spoiler:

M'n eerste richting was een DF search maar dat werkte niet lekker doordat je moet gaan springen en je dus sommige cells meerdere keren 'bezoekt'. Toen maar een 'domme' iteratieve approach gebruikt.

Wel veel code kunnen hergebruiken weer

[Soultaker]

Hydra schreef op dinsdag 19 december 2017 @ 09:49:
Dag 19

Toch best ff mee bezig geweest.

Ik denk dat je het probleem ingewikkelder hebt geïnterpreteerd dan nodig was.

spoiler:

Er zijn geen splitsingen in de invoer. Dus is het onderscheid tussen DFS en BFS ook betekenisloos, en hoef je ook geen visited set bij te houden.

Wel veel code kunnen hergebruiken weer

Meh, code hergebruiken is overrated Ik vond m'n oplossing simpel genoeg: https://github.com/maksve...de/blob/master/2017/19.py

[Hydra]

Soultaker schreef op dinsdag 19 december 2017 @ 10:59:
Ik denk dat je het probleem ingewikkelder hebt geïnterpreteerd dan nodig was.

spoiler:

Er zijn geen splitsingen in de invoer. Dus is het onderscheid tussen DFS en BFS ook betekenisloos, en hoef je ook geen visited set bij te houden.

Klopt, maar toen ik 't werkend had, was ik er aardig klaar mee

spoiler:

Die 'visited' is ook alleen om uit te vogelen op turns welke kant ik op moet, hiermee schakel ik de 'vorige' uit. Komt ook omdat ik bestaande code gebruik die voor mij uitvogelt wat de buren van een bepaald 'punt' zijn. Voor een turn is dat of de volgende of de vorige stap. Ik had ook prima alleen de vorige bij kunnen houden.

[Klaasvaak]

Vanmorgen tijdens het ontbijt aan deel 1 begonnen, maar met m'n slaperige kop een "if if " geschreven in plaats van een "if else if". Toen ik na het werk weer verder keek, was het probleem gelukkig zo gevonden. Deel twee was vandaag wel heel erg simpel.

[Anoniem: 1004565]

https://github.com/DutchG...er/Rust/day19/src/main.rs

Leuk! Mijn brein kraakte alleen wel een beetje.... Mijn loop bleef namelijk doorlopen eerst, waardoor ik veel meer letters kreeg dan eigenlijk moest... :3

[Hydra]

Dag 20 In Kotlin

Niet helemaal happy mee.

spoiler:

Hoewel ik de juiste antwoorden direct kreeg gaat dit niet werken voor alle inputs omdat ik niet detecteer of particles elkaar nog kunnen raken. Ik itereer gewoon 'dom' 500 keer en ga er dan maar vanuit dat het wel gelukt is.

Nouja. It compiles; let's ship it!