Advent of Code 2016

[vliegnerd]

Dag 10 (zaterdag, bots) ziet er uit als herhaling van de circuits? van vorig jaar. Nog geen gehad om daadwerkelijk op te lossen, maar lijkt goed te doen.

Maar dag 11 (elevator, rtg) ziet er indrukwekkend uit. Daar zie ik de oplossing nog niet... LEUK.

[Camulos]

- peter - schreef op zaterdag 10 december 2016 @ 23:08:
Phew, zat wat te hikken tegen dag 9, maar uiteindelijk bleek t allemaal goed te doen met recursie. Was gelijk al begonnen met lengte tellen ipv strings genereren, en dat was idd de juiste richting.

Ben ook aan het bijwerken.. en voor 9B ook recursie gebruikt.. het probleem leent zich hier uitermate goed voor Toch blijft het handig om 1 of 2 voorbeelden uit te werken, zodat je de base-case goed krijgt.

Edit 1: Als je met Dag 11 bezig gaat..

spoiler:

check dan vooral even Wikipedia: Missionaries and cannibals problem .. daarop is het probleem gebaseerd

Edit 2: heb uiteindelijk Day 11 met de hand gedaan.. kreeg code niet aan de praat

[ Voor 18% gewijzigd door Camulos op 11-12-2016 20:16 ]

[P_Tingen]

Damn, eindelijk deel 2 van dag 10 opgelost. De fuck is dat Progress (waar ik in werk) niet 0-based is, maar 1-based. Dat maakt sommige opgaven wat tricky voor mij. Ik had in mijn programma de '0' als indicatie dat iets niet gebruikt werd. Dat gaat natuurlijk mis als een van je bots zijn lading in output bin 0 moet droppen

Ik had een 'netwerk' van bots gemaakt dat steeds een cyclus doorgerekend werd. Toen ik 100.000 cycli had doorgerekend, had ik wel door dat er iets mis was.

Jammer, want deel 1 ging zo soepel; 1x programmeren en bij de eerste run zowel geen compiler errors en ook nog het goede antwoord.

Op naar dag 11....

[Daos]

Camulos schreef op zondag 11 december 2016 @ 14:02:
Edit 2: heb uiteindelijk Day 11 met de hand gedaan.. kreeg code niet aan de praat

Dan een hint:

spoiler:

Wel eens van de Breadth-first search (BFS) gehoord?

Lukt het nog niet dan:

spoiler:

BFS werkt met een boom en dat is een graaf zonder cycles. Op een of andere manier moet je zorgen dat de (denkbeeldige) structuur waarover je loopt een boom is.

En als het daarna nog niet lukt om het redelijk snel (< minuut) te doen:

spoiler:

Een moment-opname tussendoor kan ook niet exact hetzelfde zijn als een andere moment-opname tussendoor, maar wel 'gelijkvormig/equivalent' (weet niet hoe ik het moet noemen). Voor de rest van het algoritme maakt het dan niet uit vanuit welke je verder gaat. Bij beiden heb je nog evenveel stappen nodig.

[Bee.nl]

Het antwoord van deel 2 is eigenlijk heel erg flauw:

spoiler:

Antwoord van deel 1 plus 24. Iemand op Reddit heeft uitgezocht dat het een vast aantal moves kost om een compleet paar vanaf verdieping X naar verdieping 4 te krijgen.

Dus ik ga deel 2 niet meer bruteforcen. Deel 1 was gelukt in ~15sec. Na een middagje aan het algoritme te hebben gesleuteld vind ik het ook wel mooi geweest.

-edit-
Code opgeschoond en op GitHub gegooid.

[ Voor 13% gewijzigd door Bee.nl op 11-12-2016 21:51 ]

[Camulos]

Daos schreef op zondag 11 december 2016 @ 20:48:
[...]
Dan een hint:

spoiler:

Wel eens van de Breadth-first search (BFS) gehoord?

Thnx Had ook al wat in die richting geprogrammeerd.. maar wilde niet de optimale oplossing geven.. na 30 minuten klooien ben ik terug naar de tekentafel het whiteboard gegaan.. en bleek met het handje niet heel ingewikkeld te zijn ^^

@Daos: heb jij ook nog ergens code staan? (zag je niet in het overzicht van de startpost; just curious )

[ Voor 30% gewijzigd door Camulos op 11-12-2016 21:37 ]

[veldsla]

Lekker aan de bit operaties gegeaan, maakt wel een schone oplossing, maar de DFS recursieve solver doet daar geen eer aan. 11a gaat in een seconde of 2 ( als ik de diepte wat beperk). B werkt, maar duurt wel wat te lang, dus daar wil ik nog wel wat aan knutselen. (done, 5s)

[ Voor 12% gewijzigd door veldsla op 12-12-2016 14:56 ]

[vliegnerd]

Ik ben gisteravond flink bezig geweest met pen, papier en wikipedia om dag 11 op te lossen. Tot mijn grote verbazing werkte mijn "pen en papier" oplossing. D.w.z. de uitkomst werd geaccepteerd.

Vandaag (gelukkig) weer een eenvoudig probleem (en weer een herhaling van vorig jaar), zodat ik bij kan blijven binnen beperkte tijd. Ik ga proberen tijd vrij te maken voor een "echte" BFS oplossing van dag 11.

[veldsla]

Juist probleem 23 van vorig jaar. Computer afgestoft en opgeruimd. Code is weer wat netter. Wel flink wat iteraties nodig voor het kleine progje. 954395 voor a en 27683406 voor b. (toch maar 0.14s)

[ Voor 4% gewijzigd door veldsla op 12-12-2016 10:44 ]

[vliegnerd]

veldsla schreef op maandag 12 december 2016 @ 10:02:
Juist probleem 23 van vorig jaar. Computer afgestoft en opgeruimd. Code is weer wat netter. Wel flink wat iteraties nodig voor het kleine progje. 954395 voor a en 27683406 voor b. (toch maar 0.14s)

Jep, maar mijn oplossing in python doet >>minuut over deel B.

Elke regel wordt dan ook telkens opnieuw in geparsed e.d., maar het voldoet. Als ik tijd "over" heb steek ik die tijd wel in dag 11.

[Radiant]

Dag 11 is gelukt, mijn PHP-oplossing doet er 4,7s over; niet ontevreden

spoiler:

De hint hier over BFS en te stoppen met een branch als je de state al hebt gehad hebben wel geholpen. Verder kan je optimaliseren door ervan uit te gaan dat je maar 1 device mee naar beneden neemt en 2 naar boven.

[Daos]

Bee.nl schreef op zondag 11 december 2016 @ 21:35:
Het antwoord van deel 2 is eigenlijk heel erg flauw:

Hoe weet je dat de verschillende elementen elkaar niet beïnvloeden? Je kan bijvoorbeeld 2 microcontrollers tegelijk in de lift vervoeren.

Camulos schreef op zondag 11 december 2016 @ 21:36:
Thnx Had ook al wat in die richting geprogrammeerd.. maar wilde niet de optimale oplossing geven

Dan doe je iets fout, want

spoiler:

als je met een BFS bij de eindsituatie komt, dan is dat gegarandeerd in het minst mogelijk aantal stappen. Daarom is in deze puzzel een BFS handiger dan een DFS.

@Daos: heb jij ook nog ergens code staan? (zag je niet in het overzicht van de startpost; just curious )

Mijn dag 11

spoiler:

Mijn BFS is niet helemaal volgens het boekje. Ik doe level voor level ipv dat ik door de individuele nodes loop en een queue bijhoud.

[Bee.nl]

Daos schreef op maandag 12 december 2016 @ 17:06:
Hoe weet je dat de verschillende elementen elkaar niet beïnvloeden? Je kan bijvoorbeeld 2 microcontrollers tegelijk in de lift vervoeren.

Nou ja, ik heb het zelf niet uitgezocht maar het lijkt wel te kloppen met de antwoorden die ik heb gezien. Een koppel in de lift zorgt nooit voor conflicten met andere apparaten op een willekeurige verdieping, terwijl twee chips of twee generatoren dat wel kunnen doen. De exacte theorie erachter moet ik je helaas schuldig blijven. Ben zelf ook wel benieuwd hoe het zit.

[P_Tingen]

Ha! nr 12 was niet zo'n zware kluif. Wel voor mijn programma, want Progress is ronduit slecht in dit soort bulkwerk, maar toch de goede oplossingen gevonden. Tweede deel stond wel een kwartier te stampen.....

Nou die van gisteren nog

[ Voor 7% gewijzigd door P_Tingen op 12-12-2016 22:00 ]

[Bee.nl]

In de instructies van dag 12 zit wel een patroon, waardoor de instructieset sneller te verwerken is ([1] [2]). Ik heb zelf ook slechts de naïeve oplossing gedaan wegens gebrek aan tijd. De beide oplossingen rollen er binnen 10 sec uit.

[vliegnerd]

Bee.nl schreef op maandag 12 december 2016 @ 22:31:
In de instructies van dag 12 zit wel een patroon, waardoor de instructieset sneller te verwerken is (\[1] \[2]).

OMG, die LLVM optimalisaties uit link [2] (link naar betrefende reactie) !

Dag 13 is leuk, zeker als je met dag 11 bezig bent

[Lye]

Gisteren maar eens even een aantal dagen ingehaald, liep 3 dagen achter. Moet nu alleen dag 11 nog, maar dat komt wel zodra ik meer tijd heb. Dag 12 heb ik ook naief gedaan, al heb ik het gevoel dat de JVM stiekem heel veel optimaliseert, bij mij zijn beide delen binnen een seconde klaar, met een vergelijkbare implementatie als Bee.nl. Kan mij niet voorstellen dat PHP zoveel trager is.

Zometeen maar eens naar dag 13 kijken, ziet er interessant uit!

[ Voor 8% gewijzigd door Lye op 13-12-2016 12:54 ]

[Daedalus]

Dag 12 was een makkie, maar dag 11 kost me nog wel wat werk. Wist al wel dat een BFS de juiste aanpak is, maar na 8GB RAM en maar 10 stappen was het misschien tijd om te gaan snoeien in de zoekboom Heb nu wel deel 1 opgelost, maar voor deel 2 heb ik nog wat meer optimalisaties nodig.

Heb net dag 13 bekeken, en denk dat met de code van dag 11 je deze dag kunt oplossen.

[Radiant]

spoiler:

(Grove) visualisatie van vandaag

Wederom met BFS opgelost

[Bee.nl]

Dag 11 kan zelfs in 10ms

Dag 13 ziet er leuk uit. Straks maar eens aan beginnen.

-edit
Dag 13 is vrij simpel. Qua aanpak lijkt het sterk op dag 11, maar de search space is dermate klein dat optimalisaties niet nodig zijn en een naïeve aanpak volstaat.

[ Voor 38% gewijzigd door Bee.nl op 13-12-2016 21:23 ]

[Daedalus]

Dag 11 deel 2 eindelijk opgelost. Na veel lezen van mogelijke optimalisaties, en het omgooien van m'n code uiteindelijk de oplossing gevonden in minder dan 6 seconden

[edit]
Met de code van dag 11 is dag 13 een eitje

[ Voor 14% gewijzigd door Daedalus op 14-12-2016 02:07 ]

[Verwijderd]

In de top 100 van vandaag en gisteren staat een bekend persoon: Peter Norvig van google. Toch grappig om te zien dat hij zijn best doet om daar in te komen .

[MerijnB]

Zou iemand die dag 14 af heeft mij even willen helpen?

Het gaat over deel 1

Voorbeeld input + resultaten kloppen, maar bij echte input gaat er iets fout. Ik zie denk ik iets doms over het hoofd.

Mijn input is zpqevtbw

Output van mijn app: http://pastebin.com/QW7rNy0W
1e kolom is hoeveelste hash, 2e kolom welk karakter gevonden is, 3e kolom is de daadwerkelijke hash.

[ Voor 15% gewijzigd door MerijnB op 14-12-2016 13:58 ]

[Verwijderd]

MerijnB schreef op woensdag 14 december 2016 @ 13:57:
Zou iemand die dag 14 af heeft mij even willen helpen?

Het gaat over deel 1

Voorbeeld input + resultaten kloppen, maar bij echte input gaat er iets fout. Ik zie denk ik iets doms over het hoofd.

Mijn input is zpqevtbw

Output van mijn app: http://pastebin.com/QW7rNy0W
1e kolom is hoeveelste hash, 2e kolom welk karakter gevonden is, 3e kolom is de daadwerkelijke hash.

Dit is de output die mijn algoritme geeft (je mist index 4288).

code:

key  1 at index 3483 hash 777e17a9b1124c968a5999a69639bcd6
key  2 at index 3536 hash 1f02777d1cdd07e681ff3bacbddaa1f3
key  3 at index 3672 hash 1a3f80c66ed56777e30c57942f84494c
key  4 at index 3683 hash 60e4b5fac5bbf7775c7feaa00bf7efb6
key  5 at index 3747 hash 699d621039735d3a22ae4c006af3777d
key  6 at index 3772 hash cf75c21a33aa864647275fcadf777052
key  7 at index 3868 hash ddf93903b65b02e4e777b1a96f372d92
key  8 at index 4288 hash d2e6d2dcf0659a879a73ddaaa0a59e12
key  9 at index 4299 hash 60a34677c5617c72013fdde413277707
key 10 at index 4307 hash 229d3744e1d777caeb9066ee6d39e091

[MerijnB]

renebe heeft me al op weg geholpen, maar ik ben er nog steeds niet uit.

Ik ben wel benieuwd naar wat jullie hiermee doen. Ik kom op een gegeven moment deze hash tegen:
26e9f920003a424e89c4ab6aaaaa759f

Dit is zowel een key met 3 x '0', als een met 5 x 'a'

Welke van deze twee ('000' of 'aaaaa'), of beide, moet ik uitvoeren?

[vliegnerd]

MerijnB schreef op woensdag 14 december 2016 @ 16:42:
Ik ben wel benieuwd naar wat jullie hiermee doen. Ik kom op een gegeven moment deze hash tegen:
26e9f920003a424e89c4ab6aaaaa759f

Welke van deze twee ('000' of 'aaaaa'), of beide, moet ik uitvoeren?

Je moet in de volgende 1000 hashes alleen naar '00000' zoeken. Dat was (met een andere input) ook precies mijn probleem vandaag. Heeft mij een hoop hoofdpijn bezorgd

[MerijnB]

vliegnerd schreef op woensdag 14 december 2016 @ 16:48:
[...]


Je moet in de volgende 1000 hashes alleen naar '00000' zoeken. Dat was (met een andere input) ook precies mijn probleem vandaag. Heeft mij een hoop hoofdpijn bezorgd

Dus jij zegt dat ik niet deze hash mag gebruiken voor de 1000 voorgaande hashes die 'aaa' bevatten?

[Radiant]

Je mag vanaf die hash naar 00000 gaan zoeken, maar die hash telt ook mee mocht je zoeken naar 'aaaaa'. Zo werkt in ieder geval mijn implementatie en die gaf een goede output.

In eerste instantie probeerde ik tegelijkertijd naar sequences van 3 en 5 te zoeken, maar dat gaf problemen, dus dat kan je beter niet doen. Als je wil besparen op de tijd die het hashen kost zijn daar betere methodes voor.

[ Voor 3% gewijzigd door Radiant op 14-12-2016 17:04 ]

[vliegnerd]

MerijnB schreef op woensdag 14 december 2016 @ 16:49:
Dus jij zegt dat ik niet deze hash mag gebruiken voor de 1000 voorgaande hashes die 'aaa' bevatten?

Oh, sorry, nee dat bedoelde ik niet: Die 'aaaaa' mag je gewoon gebruiken als je zoekt naar een 5-tal. Maar als je 3-tallen zoekt, dan mag je van deze hash alleen '000' gebruiken, niet 'aaa'. Dat laatste deed ik eerst soms per ongeluk wel en dat kostte mij wat hoofdpijn.

(Ik moet ook gewoon regex-es leren...)

[MerijnB]

Radiant schreef op woensdag 14 december 2016 @ 17:04:
Je mag vanaf die hash naar 00000 gaan zoeken, maar die hash telt ook mee mocht je zoeken naar 'aaaaa'. Zo werkt in ieder geval mijn implementatie en die gaf een goede output.

In eerste instantie probeerde ik tegelijkertijd naar sequences van 3 en 5 te zoeken, maar dat gaf problemen, dus dat kan je beter niet doen. Als je wil besparen op de tijd die het hashen kost zijn daar betere methodes voor.

Hmm, dat deed ik al, wil iemand nog even naar mijn resultaat kijken? Wat blijkbaar niet goed is?

Input: zpqevtbw

Output: http://pastebin.com/ijdBrjiY

[Radiant]

08: 4288 (d2e6d2dcf0659a879a73ddaaa0a59e12) - 5209 (26e9f920003a424e89c4ab6aaaaa759f)

Deze ontbreekt in ieder geval in jouw resultaat. Lijkt erop dat je die skipt omdat de daar '000' ziet.

[ Voor 16% gewijzigd door Radiant op 14-12-2016 17:17 ]

[MerijnB]

Radiant schreef op woensdag 14 december 2016 @ 17:17:
08: 4288 (d2e6d2dcf0659a879a73ddaaa0a59e12) - 5209 (26e9f920003a424e89c4ab6aaaaa759f)

Deze ontbreekt in ieder geval in jouw resultaat. Lijkt erop dat je die skipt omdat de daar '000' ziet.

Uit mijn pastebin (onderaan) :

found key #1 (3483 -> 4399)
found key #2 (3536 -> 4399)
found key #3 (3672 -> 4399)
found key #4 (3683 -> 4399)
found key #5 (3747 -> 4399)
found key #6 (3772 -> 4399)
found key #7 (3868 -> 4399)
found key #8 (4288 -> 5209)

Gevonden!

< ipv <= zorgde ervoor dat ik dat ene paar wat precies 1000 hashes uit elkaar stond niet had.

[ Voor 9% gewijzigd door MerijnB op 14-12-2016 19:24 ]

[Verwijderd]

MerijnB schreef op woensdag 14 december 2016 @ 17:11:
[...]


Hmm, dat deed ik al, wil iemand nog even naar mijn resultaat kijken? Wat blijkbaar niet goed is?

Input: zpqevtbw

Output: http://pastebin.com/ijdBrjiY

Je mist nog

code:

key 39 at index 7558 hash 752255b794121deb53dbd7e5eee76244

[Bee.nl]

Mijn code werkte wel met de voorbeelden, maar niet met de input. Het duurde even voordat ik door had wat het was. Vrij triviale fout, maar je ziet het snel over het hoofd.

spoiler:

Je moet de 64 laagste(!) keys vinden en niet de 64 keys die je als eerst hebt kunnen matchen. Dus het kan zijn dat je na 64 gevonden keys nog verder moet zoeken, omdat er nog een triplet van een lagere iteratie is die nog gematcht kan worden binnen 1000 iteraties.

[ Voor 7% gewijzigd door Bee.nl op 14-12-2016 20:43 ]

[- peter -]

Dag 14 was wel weer leuk, niet al te moeilijk.

spoiler:

Zie dat niet iedereen het deed bij deel 2, dus misschien was t niet nodig geweest, maar ik heb de md5s die je met o.a. de 1..1000 loop maakt wel gecached, zodat je deze niet dubbelop ging berekenen. Was nu klaar in 2m20s, ipv 10m+

[ Voor 4% gewijzigd door - peter - op 14-12-2016 22:32 ]

[Soultaker]

Vandaag (dag 15) eindelijk weer een probleem waarbij een slimmere oplossing dan brute-force mogelijk was. Deel 2 had nog wel wat moeilijker gemogen.

[Radiant]

Soultaker schreef op donderdag 15 december 2016 @ 10:29:
Vandaag (dag 15) eindelijk weer een probleem waarbij een slimmere oplossing dan brute-force mogelijk was. Deel 2 had nog wel wat moeilijker gemogen.

https://www.reddit.com/r/...t_3_our_discs_got_larger/

Mijn code doet die tweede in 1139 iteraties, 11.48 ms.

[ Voor 9% gewijzigd door Radiant op 15-12-2016 11:29 ]

[P_Tingen]

Die gast heeft grappige dingen ingebouwd. Ik loop nog wat achter en ben even bezig met 13-b (office maze). In mijn code zat nog een foutje waardoor ik een te klein gedeelte van de maze doorzocht. Mijn antwoord was 135 en ik kreeg deze melding terug:

[Camulos]

Was met dag 14 bezig.. en achtte de kans niet zo groot dat er 2 verschillende 'quintets' (5 gelijke karakters achter elkaar) zouden voorkomen.

Korte test onder de 10.000.000 later, met mijn salt

code:

Found 2 quintets in the digest 7EBC28B434040502706188888B77777D , at index: 9430768

(zie 8 en 7).. had ik niet verwacht ^^

[Soultaker]

Camulos schreef op donderdag 15 december 2016 @ 23:35:
Was met dag 14 bezig.. en achtte de kans niet zo groot dat er 2 verschillende 'quintets' (5 gelijke karakters achter elkaar) zouden voorkomen.

De kans dat een quintet deel uitmaakt van een langere string is ongeveer 1 op 8 (iets minder omdat de quintet ook aan het begin/eind van de string kan voorkomen), dus heel vreemd is dat niet

Ik had er trouwens ook niet bij stilgestaan, totdat bleek dat ik keys dubbeltelde

edit:
Dag 16 is ook wel leuk. Je kúnt 'm brute-forcen, maar er is ook een efficiënte oplossing mogelijk: O(K² log N) waar K het aantal karakters uitvoer is, en N de lengte van de "gegenereerde" string, die je dan natuurlijk niet expliciet genereert. (mijn Python code loopt in <10 ms).

Het blijft wel jammer dat het "moeilijke" probleem steeds ook wel te brute-forcen is, waardoor het (als je voor de maximale score gaat) niet uitkan om een slimme oplossing te implementeren. Ik was daar nu een uur mee kwijt terwijl de trage code er maar 10 seconden over doet.

[ Voor 40% gewijzigd door Soultaker op 16-12-2016 22:46 ]

[Verwijderd]

Soultaker schreef op vrijdag 16 december 2016 @ 20:33:
[...]
Dag 16 is ook wel leuk. Je kúnt 'm brute-forcen, maar er is ook een efficiënte oplossing mogelijk: O(K² log N) waar K het aantal karakters uitvoer is, en N de lengte van de "gegenereerde" string, die je dan natuurlijk niet expliciet genereert. (mijn Python code loopt in <10 ms).

Het is zelfs in O(M + K log N) mogelijk waarbij M de grootte van de input is. Mijn methode berekent ook de prefix som van de bits, maar doet dat door de bijdrage van de input (en zijn inverse) en die van de verbindende 0 apart te berekenen.
Een ander voordeel van deze aanpak is dat je wellicht ook zou kunnen proberen om gegeven een output een bijbehorende input te vinden, want je kunt er denk ik een stelsel vergelijkingen in binaire variabelen uit krijgen. Maar daar heb ik nog niet goed over nagedacht, dus wellicht ben ik iets te optimistisch.

[vliegnerd]

Ha! Het is weer weekend, en er is (dus?) weer een deel B waarbij het brute forcen niet zomaar gaat zonder optimalisaties...

(hoewel het aantrekkelijk is om een C++ oplossing in elkaar te hacken en alsnog naief te brute forcen...)

[Radiant]

De maker is wel fan van pathfinding en md5 in ieder geval

[veldsla]

vliegnerd schreef op zaterdag 17 december 2016 @ 11:25:
Ha! Het is weer weekend, en er is (dus?) weer een deel B waarbij het brute forcen niet zomaar gaat zonder optimalisaties...

(hoewel het aantrekkelijk is om een C++ oplossing in elkaar te hacken en alsnog naief te brute forcen...)

Niet? Oh dan zal ik wel in die naïeve categorie vallen (0.1s op een 5 jaar oude MB air)

[Bee.nl]

vliegnerd schreef op zaterdag 17 december 2016 @ 11:25:
Ha! Het is weer weekend, en er is (dus?) weer een deel B waarbij het brute forcen niet zomaar gaat zonder optimalisaties...

(hoewel het aantrekkelijk is om een C++ oplossing in elkaar te hacken en alsnog naief te brute forcen...)

Oh de rekentijd van 17B viel hier eigenlijk wel mee? Mijn php-script is klaar in <0.1s. Ik heb naast de triviale condities geen optimalisaties toegepast.

Mocht je dag 16 (dragon curve) bedoelen: die kan zelfs opgelost worden in O(1).

[ Voor 14% gewijzigd door Bee.nl op 17-12-2016 13:06 ]

[vliegnerd]

Bee.nl schreef op zaterdag 17 december 2016 @ 12:57:
[...]

Oh de rekentijd van 17B viel hier eigenlijk wel mee?

Ja, eens... Ik had de code van dag 13 hergebruikt en vergeten het maze op 4x4 te limiteren. Ik kreeg dus HEEL veel oplossingen.. :-) Daarna geen enkel probleem.

[Radiant]

vliegnerd schreef op zaterdag 17 december 2016 @ 13:20:
[...]


Ja, eens... Ik had de code van dag 13 hergebruikt en vergeten het maze op 4x4 te limiteren. Ik kreeg dus HEEL veel oplossingen.. :-) Daarna geen enkel probleem.

Mijn code ging eindeloos negatief in het doolhof bij opgave 2, en ik maar denken dat er nog ergens een optimalisatie mist

[- peter -]

Men, 2 uur aan t werk om mijn code voor dag 11 werkend te krijgen, blijkt de echte input totaal onhaalbaar qua normaal doorrekenen....

spoiler:

En behalve herhalende zetten eruit te halen zie ik niet echt veel mogelijkheden zelf om nog meer te optimaliseren... Beetje teleurstellend.

[Soultaker]

Voor vandaag kon ik niets beters bedenken dan brute force, maar met numpy gaat dat vrij snel (~2,5 seconde) en de code ziet er niet slecht uit. Een puur-Python oplossing is aanzienlijk trager.

Heeft iemand nog een slimmere truc bedacht voor dit probleem, waardoor je het expliciet berekenen van alle rijen kunt vermijden?

- peter - schreef op zondag 18 december 2016 @ 02:56:
Men, 2 uur aan t werk om mijn code voor dag 11 werkend te krijgen, blijkt de echte input totaal onhaalbaar qua normaal doorrekenen....

Zit je vast bij het eerste of het tweede deel? Mijn oplossing is ook vrij traag, maar ik heb nog wel wat trucs bedacht om meer dubbele toestanden te elimineren, en dat scheelt aanzienlijk.

[Daos]

Er zijn een hoop optimalisaties voorbij gekomen waar ik mijn twijfels bij heb zoals per element oplossen of altijd 2 omhoog en 1 naar beneden.

Enige wat ik nog kon bedenken waarvan ik 100% zeker ben dat het juist is, is het volgende. Neem bijvoorbeeld

F4 .  .  .  .  .  
F3 .  .  .  LG .  
F2 E  HG HM .  .  
F1 .  .  .  .  LM 

dan

spoiler:

bestaat er nog een toestand die niet exact hetzelfde is, maar wel evenveel zetten nog nodig heeft om bij het eind te komen. Mijn programma ziet die twee toestanden als hetzelfde.

[JackBol]

Soultaker schreef op zondag 18 december 2016 @ 12:25:
Voor vandaag kon ik niets beters bedenken dan brute force, maar met numpy gaat dat vrij snel (~2,5 seconde) en de code ziet er niet slecht uit. Een puur-Python oplossing is aanzienlijk trager.

Heeft iemand nog een slimmere truc bedacht voor dit probleem, waardoor je het expliciet berekenen van alle rijen kunt vermijden?


[...]

Zit je vast bij het eerste of het tweede deel? Mijn oplossing is ook vrij traag, maar ik heb nog wel wat trucs bedacht om meer dubbele toestanden te elimineren, en dat scheelt aanzienlijk.

Het aantal veilige tegels per rij convergeert een beetje naar 49.6, maar dat is geen basis om het te berekenen ipv. te brute forcen. De puzzle is gebaseerd op rule 90, maar omdat de edges restricted zijn, kan je het volgens mij niet doorrekenen.

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

Wel ongeveer 10x trager, denk ik zo.

[ Voor 30% gewijzigd door JackBol op 18-12-2016 14:18 ]

[Radiant]

spoiler:

Je kan de trap-check versimpelen naar if (L != R) { trap }, maar veel verder kom ik ook niet.

0m31.762s in PHP

[ Voor 8% gewijzigd door Radiant op 18-12-2016 14:28 ]

[Daedalus]

Soultaker schreef op zondag 18 december 2016 @ 12:25:
Voor vandaag kon ik niets beters bedenken dan brute force, maar met numpy gaat dat vrij snel (~2,5 seconde) en de code ziet er niet slecht uit. Een puur-Python oplossing is aanzienlijk trager.

Heeft iemand nog een slimmere truc bedacht voor dit probleem, waardoor je het expliciet berekenen van alle rijen kunt vermijden?

Ik brute-force 'm in puur-Python in ~1.5 seconden. Kon niet zo snel een betere oplossing verzinnen.

edit:

Na wat optimalisaties in ~0.6 seconden, nog steeds brute-force.

[ Voor 9% gewijzigd door Daedalus op 18-12-2016 15:51 ]

[- peter -]

[b]Soultaker schreef op zondag 18 december 2016 @ 12:25:
[...]

Zit je vast bij het eerste of het tweede deel? Mijn oplossing is ook vrij traag, maar ik heb nog wel wat trucs bedacht om meer dubbele toestanden te elimineren, en dat scheelt aanzienlijk.

Dag 11 is eindelijk gelukt. Deel 2 in 6m25s, deel 1 in 21s. Wel met wat tips van Reddit.

spoiler:

Vooral de duplicates en lookalikes verwijderen helpt erg. Al ging ik nog wel de mist in met deel 2, waarbij ik dacht dat je moest uitgaan van de eindsituatie van deel 1 . Al snap ik nog niet helemaal waarom mijn code op rond 7000 unieke routes komt op het eind. Daar zit denk ik nog wat ruimte in, maar goed, ik heb t nu wel gehad

[ Voor 7% gewijzigd door - peter - op 18-12-2016 16:50 ]

[Soultaker]

Daedalus schreef op zondag 18 december 2016 @ 15:03:
[...]
Ik brute-force 'm in puur-Python in ~1.5 seconden. Kon niet zo snel een betere oplossing verzinnen.

Oh duh, je kunt natuurlijk de bits van een integer gebruiken als efficiënte array-van-bools. Daar had ik eerder aan moeten denken.

Ik heb daarmee mijn niet-numpy oplossing ook aardig snel weten te krijgen. Grappig om te zien dat de code bijna exact hetzelfde is als waar jij op uitkwam (nee, ik heb het niet gekopieerd, eerlijk waar).

[Bolukan]

Day 18 deel 1 leek bij mij van 3 jaar terug .... (wie dezelfde seed kreeg als ik, snapt hem)

[ Voor 3% gewijzigd door Bolukan op 18-12-2016 23:20 ]

[vliegnerd]

Zojuist nummer 239 van dag 19! Tijdens het ontbijt lukte deel A gemakkelijk, maar deel B... oei. Een naive implementatie in python runde @ 100 elfs verwijderen per seconde op de lange lijst. Dat ging "een tijdje" duren

Gelukkig lukte het in de trein om nog een wat slimmere implementatie te verzinnen die het binnen 5 seconden doet in python.

spoiler:

deque() in plaats van list(). deque heeft een constante time pop() i.t.t. list()

Ik zag dat SimonPrins 13 staat vandaag in het global leaderbord! Gefeliciteerd, knappe prestatie.

[ Voor 16% gewijzigd door vliegnerd op 19-12-2016 09:00 ]

[Bolukan]

Day 19 kon ik het eerste deel met pen en papier op het perron oplossen (alleen voor dec2bin en bin2dec even internet geraadpleegd), maar voor tweede deel ben ik benieuwd of het ook zonder brute-force kan. Mss iets met 3-talig stelsel.

Edit: Ja, ook 2e deel kan zonder brute-force. Ditmaal - gestimuleerd door Soultaker (zie hieronder) - geen internet gebruikt, maar een eigen dec2ter en ter2dec gebruikt in combinatie met potlood en blaadje.

[ Voor 30% gewijzigd door Bolukan op 19-12-2016 15:35 ]

[Soultaker]

Bolukan schreef op maandag 19 december 2016 @ 09:26:
alleen voor dec2bin en bin2dec even internet geraadpleegd

Pff, nepprogrammeur

[Bee.nl]

Dag 19 kan in ieder geval opgelost worden met een simpele formule.

spoiler:

Deel 1 heeft een terugkerend patroon met machten van 2: [1,1,3,1,3,5,7,1,3,5,7,9,11,13,15].
Deel 2 is feitelijk hetzelfde als 1, maar dan met machten van 3.

[ Voor 4% gewijzigd door Bee.nl op 19-12-2016 16:28 ]

[Soultaker]

Bee.nl schreef op maandag 19 december 2016 @ 16:20:

spoiler:

Deel 2 is feitelijk hetzelfde als 1, maar dan met machten van 3.

Slim! Hoe ben je daar achter gekomen?

[Bee.nl]

Soultaker schreef op maandag 19 december 2016 @ 22:34:
[...]

Slim! Hoe ben je daar achter gekomen?

Eerst een naïeve implementatie gebouwd en naar pakweg de eerste 50 antwoorden gekeken. Daar bleek een patroon in te zitten. Het patroon van deel 2 vinden is iets lastiger dan deel 1.

[vliegnerd]

Bee.nl schreef op maandag 19 december 2016 @ 22:41:
[...]

Eerst een naïeve implementatie gebouwd en naar pakweg de eerste 50 antwoorden gekeken. Daar bleek een patroon in te zitten. Het patroon van deel 2 vinden is iets lastiger dan deel 1.

Ik heb zelf een brute force oplossing gebruikt, omdat ik het patroon helemaal niet zag, maar via reddit kwam ik wel op een mooie uitleg van numberphile (josephus' problem). Een filmpje van een maand oud, dus voor een aantal deelnemers nog vers in het geheugen:

YouTube: The Josephus Problem - Numberphile

Via dit filmpje snapte ik tenminste het eerste deel met de machten van 2 / binair. Nu nog zelf deel 2 verzinnen.

[Bolukan]

vliegnerd schreef op dinsdag 20 december 2016 @ 13:04:
[...]Nu nog zelf deel 2 verzinnen.

*kuch* 3-talig stelsel *kuch*

[veldsla]

Had ik toch even geen zin om de reverse hash methode te doen. Brute forcing werkt toch ook prima

[JackBol]

vliegnerd schreef op dinsdag 20 december 2016 @ 13:04:
[...]




Ik heb zelf een brute force oplossing gebruikt, omdat ik het patroon helemaal niet zag, maar via reddit kwam ik wel op een mooie uitleg van numberphile (josephus' problem). Een filmpje van een maand oud, dus voor een aantal deelnemers nog vers in het geheugen:

YouTube: The Josephus Problem - Numberphile

Via dit filmpje snapte ik tenminste het eerste deel met de machten van 2 / binair. Nu nog zelf deel 2 verzinnen.

Ik had oplossing 1 ook gebruteforced (circulaire list gemaakt met alle elves en vervolgens while len(elves) != 1: pop de volgende elf). Via reddit inderdaad op de numberphile video terecht gekomen en vervolgens oplossing 1 herschreven naar een mathematische oplossing in base 2. Vervolgens zelf deel 2 gecheft in base 3.

[vliegnerd]

JackBol schreef op woensdag 21 december 2016 @ 10:41:
[...]


Ik had oplossing 1 ook gebruteforced (circulaire list gemaakt met alle elves en vervolgens while len(elves) != 1: pop de volgende elf). Via reddit inderdaad op de numberphile video terecht gekomen en vervolgens oplossing 1 herschreven naar een mathematische oplossing in base 2. Vervolgens zelf deel 2 gecheft in base 3.

Ja, op die manier is mij het uiteindelijk ook gelukt. Zou zelf niet op base 2 zijn gekomen, en al helemaal niet op base 3, maar na de hints hierboven, is het op de manier van het filmje van numberphile niet moeilijk.

Vandaag (dag 21) trouwens wel een "unscrambler" gemaakt... Terwijl brute force natuurlijk veel eenvoudiger is.

[Bee.nl]

Was ik net blij dat ik 21A netjes had opgelost, kwam ik bij deel 2.... Toen bekroop me een 'oh no you didn't ' gevoel bij het lezen van de unscrambler. Misschien maar de brute force doen.

-edit-
Gewoon gebruteforced binnen 2.5sec met een gejatte permutatiefunctie van SO. Ik vind het wel prima zo

[ Voor 33% gewijzigd door Bee.nl op 21-12-2016 13:52 ]

[Soultaker]

Het unscramblen is niet zo moeilijk -- gewoon de instructies in omgekeerde volgorde omgekeerd uitvoeren. Sommige instructies zijn hun eigen inverse ("swap position x with position y"), andere zijn vrij eenvoudig om te keren ("shift left", wordt "shift right").

De enige die wat extra moeite vergt is "rotate based on position of letter x", en nu wordt het meteen ook duidelijk waarom die zo raar gedefinieerd is

[JackBol]

Bee.nl schreef op woensdag 21 december 2016 @ 13:35:
Was ik net blij dat ik 21A netjes had opgelost, kwam ik bij deel 2.... Toen bekroop me een 'oh no you didn't ' gevoel bij het lezen van de unscrambler. Misschien maar de brute force doen.

-edit-
Gewoon gebruteforced binnen 2.5sec met een gejatte permutatiefunctie van SO. Ik vind het wel prima zo

Ik heb em ook gebruteforced. Het zijn slechts 40k permutaties. Daar ga ik geen uur voor coden
Python's itertools wederom for the win!!

edit: Er zijn een hoop puzzles bij die een goede programmeur 20 jaar geleden een hoop hoofdbrekens zouden bezorgen. We zitten hier allemaal op onze Core i7s te developen. We hoeven niet snel voor execution te optimizen.

[ Voor 14% gewijzigd door JackBol op 21-12-2016 16:01 ]

[Radiant]

Ja, hij had deel 2 wel flink kunnen opschalen naar een string van 100 karakters bijvoorbeeld, dat maakt het net wat leuker. Er waren nog een aantal puzzels waarbij bruteforce makkelijk tegen te gaan is door gewoon een flink complexe input te maken.
Kan niet ivm input natuurlijk

Daarom vond ik dag 9 wel leuk; daar moest je wel over nadenken want je had simpelweg niet de resources om het hele ding te decompressen

[ Voor 6% gewijzigd door Radiant op 21-12-2016 16:43 ]

[- peter -]

Ja, ik zat ook even te denken van... neee. bij dag 21 part 2. Maar het viel idd erg mee. Alleen de rotate by letter idd was even nadenken.

[JackBol]

Radiant schreef op woensdag 21 december 2016 @ 16:42:
Ja, hij had deel 2 wel flink kunnen opschalen naar een string van 100 karakters bijvoorbeeld, dat maakt het net wat leuker. Er waren nog een aantal puzzels waarbij bruteforce makkelijk tegen te gaan is door gewoon een flink complexe input te maken.
Kan niet ivm input natuurlijk

len(input) == len(output).
Echter had hij er wel een verhaal omheen kunnen lullen dat Bunnies graag 80-karakterige paswoorden hebben die prima met hun bunny-breinen zijn te onthouden

Ik vond day 17 star 2 ook leuk (zoek de langste legale route naar de vault). Hiervoor moest je namelijk de hele search space door. Ik had eerder namelijk hard zitten knutselen op een DFS solution voor star 1 toen ik realiseerde dat BFS sneller was. Echter kwam mijn DFS bij ster 2 goed van pas

[Soultaker]

Radiant schreef op woensdag 21 december 2016 @ 16:42:
Ja, hij had deel 2 wel flink kunnen opschalen naar een string van 100 karakters bijvoorbeeld, dat maakt het net wat leuker. Er waren nog een aantal puzzels waarbij bruteforce makkelijk tegen te gaan is door gewoon een flink complexe input te maken.
Kan niet ivm input natuurlijk

Beide inputs hadden best veel groter kunnen zijn; dat maakt voor deel 1 niet uit, maar voor deel 2 is een verdubbeling van de invoerlengte van 8 naar 16 karakters al voldoende om brute-forcen onpraktisch te maken. 8! = 40.320. 16! = 20.922.789.888.000.

Verder had ik zelf een oneven inputlengte gekozen. Dan had de rotate based on position of letter b regel simpelweg kunnen zijn "shift rechts met de index van b", in plaats van de huidige regel van "shift rechts met de index van b + 1 + nog 1 als index >= 4". Die formulering is niet echt elegant, maar hij was nodig om de uitvoer omkeerbaar te maken. Met een invoer van oneven lengte was dat niet nodig geweest.

[ Voor 7% gewijzigd door Soultaker op 21-12-2016 21:02 . Reden: typo ]

[JackBol]

Soultaker schreef op woensdag 21 december 2016 @ 18:29:
[...]

Beide inputs hadden best veel groter kunnen zijn; dat maakt voor deel 1 niet uit, maar voor deel 2 is een verdubbeling van de invoerlengte van 8 naar 16 karakters al voldoende om brute-forcen onpraktisch te maken. 8! = 40.320. 16! = 20.922.789.888.000.

Verder had ik zelf een oneven inputlengte gekozen. Dan had de rotate based on position of letter b regel simpelweg kunnen zijn "shift rechts met de index van b", in plaats van de huidige regel van "shift rechts met de index van b + 1 + nog 1 als index > 14". Die formulering is niet echt elegant, maar hij was nodig om de uitvoer omkeerbaar te maken. Met een invoer van oneven lengte was dat niet nodig geweest.

Mijn OCD-alarm ging ook af bij deze rotate

[Bolukan]

Voor de 2e keer global leaderboard punten gescoord, en wel met deel 2 van de opgave van day 22. Voor deel 1 was ik te laat uit bed gekomen en waren de punten al vergeven. Deel 2 heb ik zonder pen en papier uit het hoofd berekend. Ik denk dat ik daarmee de mensen die een bfs, etc aan het proberen waren heb ingehaald. Hihi

PS: Waar leeft die vent Eric eigenlijk. 06:00 is gewoon een belabberd tijdstip voor Europeanen.

[ Voor 13% gewijzigd door Bolukan op 22-12-2016 08:23 ]

[Bee.nl]

Dag 22 deel 2 kan in O(1) uitgerekend worden:

spoiler:

x_leeg+y_leeg+x_max+(x_max-1)*5

[ Voor 23% gewijzigd door Bee.nl op 22-12-2016 11:48 ]

[vliegnerd]

Bee.nl schreef op donderdag 22 december 2016 @ 11:39:
Dag 22 deel 2 kan in O(1) uitgerekend worden:

Voor mijn input werkt die formule niet. (Of ik doe iets fout...)

[Bee.nl]

vliegnerd schreef op donderdag 22 december 2016 @ 12:07:
[...]


Voor mijn input werkt die formule niet. (Of ik doe iets fout...)

Ik kom uit op:

spoiler:

7 + 17 + 36 + (36-1)*5 = 235

Schijnt te werken voor een aantal mensen op Reddit. Wie weet is die formule toch niet 100% waterdicht.

Uiteindelijk werkt het hetzelfde als dit spelletje: tile puzzle

[ Voor 11% gewijzigd door Bee.nl op 22-12-2016 12:18 ]

[JackBol]

Bolukan schreef op donderdag 22 december 2016 @ 08:13:
PS: Waar leeft die vent Eric eigenlijk. 06:00 is gewoon een belabberd tijdstip voor Europeanen.

New York.
De puzzles komen om 0:00 EST vrij.

[veldsla]

De formule is afhankelijk van de dimensies van het grid. En die verschillen blijkbaar per puzzel.

[Soultaker]

Ik vond dit weer een beetje een flutprobleem, waarbij je het antwoord makkelijker met de hand kunt vinden dan door iets te coden. Niet echt een programmeerprobleem, maar als puzzel ook niet echt interessant.

Bovendien bleek bij de vorige stap dat het wel mogelijk was om meer dan één lege cel te maken, maar dat heb je dan bij deel twee weer nergens voor nodig.

Bee.nl schreef op donderdag 22 december 2016 @ 11:39:
Dag 22 deel 2 kan in O(1) uitgerekend worden:

spoiler:

x_leeg+y_leeg+x_max+(x_max-1)*5

Dat werkt alleen als je de barrières compleet negeert. Mijn invoer ziet er zo uit, bijvoorbeeld: http://pastebin.com/raw/18E2Fqb1

Om de lege cel naar boven te slepen moet je om de barrière heen. Het aantal stappen is afhankelijk van de lengte van de barrière, niet alleen van de afmetingen van het grid.

[ Voor 8% gewijzigd door Soultaker op 22-12-2016 12:59 ]

[veldsla]

Zo! mijn barrière liet maar 1 vakje open. Stond nog even vreemd te kijken omdat ik dacht dat mijn node daar langs moest...

[Bolukan]

Soultaker schreef op donderdag 22 december 2016 @ 12:58:
Ik vond dit weer een beetje een flutprobleem, waarbij je het antwoord makkelijker met de hand kunt vinden dan door iets te coden. Niet echt een programmeerprobleem, maar als puzzel ook niet echt interessant.

Daarom was ik verbaasd dat nadat ik als 263e het eerste deel-'probleem' had opgelost, als 40e het tweede deel-'probleem' klaar had. Er moeten toch teveel vroege vogels zijn geweest die hiervoor aan het programmeren zijn geslagen.

Nou hopen dat in de laatste opgaven, nog iets leuks zit.

[ Voor 5% gewijzigd door Bolukan op 22-12-2016 13:13 ]

[veldsla]

En het nog steed niet opgelost hebben, want de stats zijn een beetje treurig.

[Bolukan]

He, nog een geheime puzzel gevonden op http://adventofcode.com/2016/sponsors:
Fvzcry gbpu? Xbz arkg-yriry glcra va Hgerpug bc baf areqxjnegvre!

spoiler:

Simpel toch? Kom next-level typen in Utrecht op ons nerdkwartier!

[Bee.nl]

Wel mee eens dat het jammer is dat dit met de hand kan, terwijl het juist programmeerwerk zou moeten zijn.

Soultaker schreef op donderdag 22 december 2016 @ 12:58:
Dat werkt alleen als je de barrières compleet negeert. Mijn invoer ziet er zo uit, bijvoorbeeld: http://pastebin.com/raw/18E2Fqb1

Om de lege cel naar boven te slepen moet je om de barrière heen. Het aantal stappen is afhankelijk van de lengte van de barrière, niet alleen van de afmetingen van het grid.

Toch geeft mijn input dezelfde soort map als jouw map.

spoiler:

1. Ga eerst naar links om de muur heen: x_e
2. Ga naar de oorsprong: y_e
3. Ga vervolgens helemaal naar rechts, naar punt G: x_max
4. Wandel om G heen, zodanig dat per 5 stappen G één plaats naar links opschuift: (x_max-1)*5
Tezamen geeft dat dus x_e + y_e + x_max + (x_max-1)*5

Misschien zie ik ergens iets over het hoofd?

-edit-
Volgens mij ligt het aan de lengte van de muur. Die van mij loopt op de linkse node na helemaal door, terwijl die van jou halverwege al stopt. Dus dan hoef je minder ver naar links te bewegen. Maar met een correctie op de x-coördinaat van de lege node in de formule werkt het ook voor inputs met een kortere muur.

[ Voor 24% gewijzigd door Bee.nl op 22-12-2016 16:28 ]

[vliegnerd]

Bee.nl schreef op donderdag 22 december 2016 @ 12:14:
[...]

spoiler:

7 + 17 + 36 + (36-1)*5 = 235

Schijnt te werken voor een aantal mensen op Reddit. Wie weet is die formule toch niet 100% waterdicht.

Nee, helaas dat is niet de oplossing:

spoiler:

227 (met de hand...)

Maar als ik naar de formule kijkt, samen met jouw opmerking hierboven, dan klopt dat inderdaad: Het ligt aan de lengte van de muur.

[ Voor 15% gewijzigd door vliegnerd op 22-12-2016 16:26 ]

[Bee.nl]

vliegnerd schreef op donderdag 22 december 2016 @ 16:25:
[...]


Nee, helaas dat is niet de oplossing:

spoiler:

227 (met de hand...)

Maar als ik naar de formule kijkt, samen met jouw opmerking hierboven, dan klopt dat inderdaad: Het ligt aan de lengte van de muur.

Jup. Ik zat net even je grid te bekijken en je muur begint op x=5. Dus dat betekent dat je 2x 4 stappen van mijn foute antwoord moet halen en dan kom je inderdaad uit op de oplossing die je gaf.

spoiler: de correcte formule

x_e + y_e + x_max + (x_max-1)*5 - (min(x_wall) - 1)*2

[veldsla]

Woah...damn. Ik zou vast iets met die dag 23 tip moeten doen, maar mijn baksel harkt die 3501374000 iteraties er gewoon in 19s doorheen :-) dat is 184 miljoen per seconde!

[Radiant]

Ik vind dit wel een fantastische oplossing

[Bee.nl]

veldsla schreef op vrijdag 23 december 2016 @ 11:06:
Woah...damn. Ik zou vast iets met die dag 23 tip moeten doen, maar mijn baksel harkt die 3501374000 iteraties er gewoon in 19s doorheen :-) dat is 184 miljoen per seconde!

Met php duurt dat nogal erg lang, dus uiteindelijk maar gewoon de vermenigvuldiging ingebouwd.

spoiler:

Deze instructieset: cpy b c, inc a, dec c, jnz c -2, dec d, jnz d -5
Is feitelijk hetzelfde als a = a + b * d, c = 0, en d = 0.

Radiant schreef op vrijdag 23 december 2016 @ 11:27:
Ik vind dit wel een fantastische oplossing

Ja die gast maakt altijd de meest hilarische oplossingen

-edit-
Er is zelfs nog een O(1) shortcut mogelijk voor dag 23:

spoiler:

a₁ = 7! + const_cpy * const_jnz
a₂ = 12! + const_cpy * const_jnz = 12! - 7! + a₁
Waarbij const_cpy en const_jnz de waardes zijn van cpy <int> c en jnz <int> d instructies in je input.

[ Voor 24% gewijzigd door Bee.nl op 23-12-2016 14:04 ]

[XiN-eViL]

Heb ook maar eens deze leaderboard gejoined . Blijkt dat ik toch mooi 2e sta nu .

Vond die van vandaag wel weer leuk trouwens.

Ohja ik heb alles in Swift gecode, maar niet altijd even netjes. Als er echt interesse is kan ik het wel online gooien.

[ Voor 31% gewijzigd door XiN-eViL op 24-12-2016 12:19 ]

[Bee.nl]

Vandaag is een combinatie van voorgaande puzzles. Mijn script doet er 6sec over. Ik heb het opgelost met

spoiler:

BFS en een TSP bruteforce

[Soultaker]

Zo doe ik het ook, en dat loopt in <150ms zonder al te veel optimalisaties.

[XiN-eViL]

Jup dat is ook mijn oplossing. Draait in <90 ms voor zowel a en b in een release-build.

[Bee.nl]

Heb het nog van van 6s naar 3.5s terug kunnen brengen met wat efficiëntere constructies, maar php (7.1) is volgens mij gewoon niet sneller.

Soultaker schreef op zaterdag 24 december 2016 @ 13:09:
Zo doe ik het ook, en dat loopt in <150ms zonder al te veel optimalisaties.

Wat ziet python er toch altijd mooi kort en bondig uit. Misschien moet ik dat ook eens gaan leren.

[Daos]

Ik heb dag 24 met alleen de

spoiler:

BFS (mijn level voor level variant)

Duurt bij mij 1 seconde voor a en 2 seconden voor b.

Ook klaar met de rest

[JackBol]

veldsla schreef op vrijdag 23 december 2016 @ 11:06:
Woah...damn. Ik zou vast iets met die dag 23 tip moeten doen, maar mijn baksel harkt die 3501374000 iteraties er gewoon in 19s doorheen :-) dat is 184 miljoen per seconde!

Knap! Ik heb een dag besteedt aan het 'reverse engineeren' van de BunnyCode maar ik kreeg em niet genoeg geoptimaliseerd. Ik zag al wel snel genoeg een patroon in register 'c' en op basis daarvan de bruteforce van mijn baksel doorgerekend (2 dagen). Aangezien ik met kerst toch geen tijd had, heb ik het maar besloten om ster 2 te bruteforcen. Uiteindelijk heeft mijn laptop 1,7 dagen over gedaan.

[farlane]

Eindelijk klaar.