Advent of Code 2016

[Lye]

Vandaag toch eindelijk een wat hoger niveau, al was het nog steeds niet heel lastig. Alsnog te lang bezig geweest met het gebruiken van streams. Uiteindelijk maar genoegen genomen met mijn huidige oplossing. Ben er niet helemaal tevreden over, maar heb er vandaag ook geen tijd voor.

[farlane]

Caelorum schreef op woensdag 7 december 2016 @ 19:52:
Ik zie gewoon niet wat ik fout doe bij dag 2. De test input geeft het correcte resultaat, maar de echte input niet Iemand zin om mee te kijken?

Wild guess : Ik weet niet of in F# casin wat uitmaakt maar:

F#:

let (|Valid|Invalid|) n = if (n > 0) && (n < 10) then Valid else Invalid

let handleMove n c =
    match n+c with
    | Valid -> n+c
| invalid -> n

Bij de match gebruik je invalid ipv Invalid ...

[edit]
Owh wacht, je had het al gevonden

[ Voor 3% gewijzigd door farlane op 07-12-2016 23:21 ]

[Caelorum]

farlane schreef op woensdag 7 december 2016 @ 23:19:
[...]
Wild guess : Ik weet niet of in F# casin wat uitmaakt maar:[...]

Nee, maakt blijkbaar in dit geval niet uit. Ik ben er ook nog maar net mee bezig, maar heb al gemerkt dat F# ook wel wat eigenaardigheden kent.
Zo pin ik liever niet variables vast op een type, maar als je het niet af en toe doet in f# worden de errors die je eventueel krijgt echt wazig en worst case komt de compiler er niet eens meer uit ^^

[farlane]

Zit te kijken naar jouw code Soultaker en ben verbaasd over het feit dat je de haken in 7a niet belangrijk vond, getuige je replace.
Het gaat blijkbaar goed, maar was er ergens medegedaald dat de ipv7 adressen nooit met een hypernet sequence begint, of dat er 2 achter elkaar komen?

[Soultaker]

farlane schreef op woensdag 7 december 2016 @ 23:33:
Het gaat blijkbaar goed, maar was er ergens medegedaald dat de ipv7 adressen nooit met een hypernet sequence begint, of dat er 2 achter elkaar komen?

Nee, ik had er gewoon niet aan gedacht, eerlijk gezegd. Het wordt in de opgave inderdaad niet genoemd.

[ThaStealth]

Tegenvaller vandaag, moeilijkste was de input interpreteren, redelijk wat string splits nodig gehad. Leuke toevoeging was opdracht B, al was die kinderlijk eenvoudig

[farlane]

Soultaker schreef op donderdag 8 december 2016 @ 01:01:
Nee, ik had er gewoon niet aan gedacht, eerlijk gezegd. Het wordt in de opgave inderdaad niet genoemd.

Ah okay. Vind je code net een cadeautje, alleen de strik mist.

[P_Tingen]

Ik zit op Reddit te kijken omdat ik deel 2 eerst fout had, maar het lijkt alsof er verschillende input files zijn. Ik zie nml verschillende uitkomsten. Maar *#&$^#(^$, ik ga die ontwikkelaar van Advent of Code kielhalen als ik hem zie.

Zonder de oplossing te verklappen, maar wat maken we van deze letter:

code:

 #  # 
 #  # 
 #  # 
 #  # 
 #  # 
  ##

Ik had deze als een V geïnterpreteerd omdat er - voor een U - rechtsonder eigenlijk nog een # had moeten staan, dus zo:

code:

 #  # 
 #  # 
 #  # 
 #  # 
 #  # 
  ###

Maar het bleek dus wel degelijk een U te zijn.

[Radiant]

Bitmasks olé

[vliegnerd]

Gisteren erg weinig tijd voor dag 7 (hypernet TLS/SSL: Dat was niet moeilijk maar ik had er veel code voor nodig. Komt vooral omdat ik niet goed ben ik regex.

Maar ik vond vandaag heel leuk! Natuurlijk is deel B een makkie (ik had de code al gemaakt om deel 1 te testen). Wel numpy gebruikt om het mijzelf gemakkelijk te maken: (python numpy)

EDIT: @Soultaker: Wat een mooie functionele oplossing van dag7.

[ Voor 8% gewijzigd door vliegnerd op 08-12-2016 13:17 ]

[Soultaker]

farlane schreef op donderdag 8 december 2016 @ 10:03:
Vind je code net een cadeautje, alleen de strik mist.

Je hebt gelijk; ik heb het uit principe toch maar even gefixt. (Wat een mooie manier om kritiek te verwoorden, trouwens.)

vliegnerd schreef op donderdag 8 december 2016 @ 11:43:
Maar ik vond vandaag heel leuk! Natuurlijk is deel B een makkie (ik had de code al gemaakt om deel 1 te testen). Wel numpy gebruikt om het mijzelf gemakkelijk te maken: (python numpy)

Netjes Ik kwam zelf op ongeveer dezelfde code uit met Numpy. (Het kan ook prima zonder, maar Numpy is uitermate geschikt voor dit soort problemen.)

Ik ben niet heel erg tevreden over het parsen. Dit is iets waar Perl juist heel goed in zou zijn:

Perl:

while (<>) {
  if (/rect (\d+)x(\d+)/) {
    FillRect($1, $2);
  } elsif (/rotate row y=(\d+) by (\d+)/) {
    RotateRow($1, $2);
  } elsif (/rotate column x=([0-9]+) by ([0-9]+)/) {
    RotateColumn($1, $2);
  } else {
    die "Unrecognized command line: $_"
  }
}

Maar ja, dan de rest in Perl doen, is nog niet zo eenvoudig.

[ Voor 64% gewijzigd door Soultaker op 08-12-2016 16:03 ]

[vliegnerd]

Soultaker schreef op donderdag 8 december 2016 @ 14:27:
Ik ben niet heel erg tevreden over het parsen. Dit is iets waar Perl juist heel goed in zou zijn:

O, dat is idd heel fijn. Helaas ben ikzelf een totale regex n00b, zodat perl ook helemaal niks is. Ik kan jouw code net aan lezen, maar ik zou het zeker niet makkelijk zelf kunnen construeren.

Dus ik hou het maar bij een stapel split()s in python.

[Mawlana]

Die van vandaag ga ik niet 'ff' doen vrees ik. Ik kijk er vanavond wel naar. Of denk ik te moeilijk?

[vliegnerd]

sylvesterrr schreef op vrijdag 9 december 2016 @ 08:56:
Die van vandaag ga ik niet 'ff' doen vrees ik. Ik kijk er vanavond wel naar. Of denk ik te moeilijk?

Hoewel deel A gemakkelijk gaat met een "naieve oplossing", krijg ik direct `maximum recursion depth exceeded` als ik deel B probeer. Nu ff geen tijd om dat anders op te lossen.

spoiler:

Ik ben nu echt de string aan het "decompressen". Je kunt natuurlijk gewoon de lengte tellen.

[P_Tingen]

Ja, ik heb ook problemen met deel 2. Deel 1 had ik redelijk snel en ik dacht slim te zijn door op het einde van mijn 'decompress' functie even te checken of er nog haakjes in staan om dan recursief zichzelf aan te roepen.

In theorie kan dat, maar na een dik kwartier stampen krijg ik een error op te lange strings. Hmmm. Toch nog even over nadenken, misschien dan maar niet recursief oplossen. Of de tussenresultaten opslaan.

[ZieglerNichols]

Deel 1 ook 'naief' gedaan, werkt goed. Voor deel 2 heb ik dat niet eens geprobeerd vanwege de waarschuwing in de opdracht. Uiteindelijk had ik het antwoord op deel 2 sneller dan deel 1 ;-)

spoiler:

Recursief lengtes tellen!

[ Voor 23% gewijzigd door ZieglerNichols op 09-12-2016 11:15 ]

[vliegnerd]

Nadat ik een domme bug had gefixed, bleek er helemaal geen recursion depth probleem te zijn...

De oplossing voor A is bijna gelijk aan B (python).

Ik heb voor deel A eerst de hele string berekend (day9.py) maar bij deel B overgestapt op de meer verstandige manier (zie spoilers hierboven) (day9b.py). Daarna samengevoegd tot een enkele oplossing voor deel A en B.

[Radiant]

Ik had 'm heel defensief al zonder recursie gebouwd, maar ook met recursie lijkt de diepte best mee te vallen inderdaad (na alle optimalisaties).

[renebe]

Het was mij niet duidelijk hoe de recursieve decompressie zou moeten werken. De makkelijke versie is

code:

repeat*decompress(subsequence)

De lastige versie is

code:

decompress(subsequence*repeat)

Als je bijvoorbeeld als input (6x2)A(6x2) hebt, dan wordt dat in de moeilijke versie A(6x2)A(6x2) na een enkele decompressie stap. Dat blijft zich oneindig lang herhalen .
Ik heb maar voor de makkelijke variant gekozen en dat werd gelukkig geaccepteerd.

[P_Tingen]

Damn, dat duurde langer dan gedacht. Mijn eerste oplossing ging prima, maar werkte niet meer bij deel 2 want te lange strings. Ik heb hem een paar uur laten draaien op de achtergrond, maar ik denk dat hij er niet uitgekomen zou zijn. Back to the drawing board (en reddit) en het blijkt dus wel sneller te kunnen

Uiteindelijke berekening duurde 71 msec

[Varienaja]

Met mij ook, dag 9. Onderdeel a in no time opgelost. Onderdeel b inderdaad met een OutOfMemory. Daarna slimmer geprogrammeerd, dacht ik: computer heeft uren staan rekenen. Dit ook maar afgebroken en nóg slimmer geprogrammeerd: goede uitkomst in 3 minuten. Daarna een paar duidelijk slome stukken code verbeterd en hop: het juiste antwoord in 30ms.

[Bee.nl]

Bij AoC zit het er vaak dik in dat een naïeve implementatie bij deel 1 niet meer werkt voor deel 2. Zodra de executietijd langer dan 1min is, is dat vaak een teken dat je algoritme niet goed (genoeg) is.

Zodoende had ik bij deel 1 al meteen een parsertje gemaakt ipv simpel strings repeaten. Deel 2 volgende dan gelukkig relatief makkelijk door een stukje te vervangen met recursie. De meeste tijd was ik eigenlijk nog kwijt aan het priegelen met de string pointer. Mijn php-oplossing voor dag 9 doet er ~2ms over.

[veldsla]

Leuk probleem vandaag. Uiteindelijk B heel anders opgelost dan A. Ik twijfelde in het begin nog of ik een volledige decompressor zou maken omdat ik verwachtte die bij B nodig te hebben. Gelukkig niet gedaan

Unfortunately, the computer you brought probably doesn't have enough memory to actually decompress the file;

Hier zou het wel passen. Kwam op een dikke 10GB uit . Runtijd niet meetbaar. (edit- oke...als ik de input*10000 doe dan duurt het bijna 6s, dus 0.6ms zou een aardige gok zijn)

[ Voor 7% gewijzigd door veldsla op 09-12-2016 21:39 ]

[Bee.nl]

Dag 10 is wel aardig. Het lijkt op het eerste gezicht moeilijk met het lange verhaal, maar het valt eigenlijk nogal mee. Mijn php-oplossing is in ~5ms klaar. De oplossing volgt uit

spoiler:

het steeds wegstrepen van instructies nadat ze uitgevoerd zijn, totdat er geen meer over zijn. Een instructie kan alleen uitgevoerd worden wanneer 1) het een input is of 2) de bot 2 chips heeft. De instructies staan dus niet in de juiste volgorde.

[Rips10]

Bee.nl schreef op zaterdag 10 december 2016 @ 12:03:
Dag 10 is wel aardig. Het lijkt op het eerste gezicht moeilijk met het lange verhaal, maar het valt eigenlijk nogal mee. Mijn php-oplossing is in ~5ms klaar. De oplossing volgt uit

spoiler:

het steeds wegstrepen van instructies nadat ze uitgevoerd zijn, totdat er geen meer over zijn. Een instructie kan alleen uitgevoerd worden wanneer 1) het een input is of 2) de bot 2 chips heeft. De instructies staan dus niet in de juiste volgorde.

spoiler:

Wat nou als een bepaalde bot een tweede keer twee chips heeft? dan heb je de instructie al weggestreept?

[Bee.nl]

Rips10 schreef op zaterdag 10 december 2016 @ 14:12:
[...]

spoiler:

Wat nou als een bepaalde bot een tweede keer twee chips heeft? dan heb je de instructie al weggestreept?

Een valide punt De input voor dag 10 lijkt zo opgezet te zijn dat een dergelijk algoritme mogelijk is. De visualizations en solutions die ik op Reddit heb zien staan weerspiegelen dit ook. De bedenker van AoC verstopt vaak een shortcut in de puzzle. Er kunnen dus soms scherpere randvoorwaarden uit de puzzle gehaald worden door te zoeken naar patronen in de input.

Voor dag 6 was er namelijk ook zoiets mbt de minst en vaakst voorkomende letter in een reeks. Je kon daar in plaats van de letters tellen ook een polynoom opstellen doordat er een bepaald patroon in de input zat.

[Daos]

Rips10 schreef op zaterdag 10 december 2016 @ 14:12:

spoiler:

Wat nou als een bepaalde bot een tweede keer twee chips heeft? dan heb je de instructie al weggestreept?

Dan merk je vanzelf wel dat het antwoord niet klopt.

Heb jij dan ook iets ingebouwd dat

spoiler:

als de doel low of high bot al vol is een bot-regel niet/later uitgevoerd wordt? Ik kijk daar niet naar. Heeft een bot bij mij twee waardes, dan verdeelt die ze altijd over de low en high ongeacht wat daar al in staat.

[Bee.nl]

Daos schreef op zaterdag 10 december 2016 @ 14:54:
[...]


Dan merk je vanzelf wel dat het antwoord niet klopt.

Heb jij dan ook iets ingebouwd dat

spoiler:

als de doel low of high bot al vol is een bot-regel niet/later uitgevoerd wordt? Ik kijk daar niet naar. Heeft een bot bij mij twee waardes, dan verdeelt die ze altijd over de low en high ongeacht wat daar al in staat.

Dat zou inderdaad een bepaalde volgordelijkheid van de instructies impliceren wanneer je de aanname maakt zoals Rips10 die schetst. In de puzzle staat bij het voorbeeld echter het volgende: "In this configuration, bot number 2 is responsible for comparing value-5 microchips with value-2 microchips." Dat is imho indirect bewijs dat volgordelijkheid geen rol speelt. Anders had ik verwacht dat daar wel iets over gezegd zou zijn in de puzzle.

[Rips10]

Daos schreef op zaterdag 10 december 2016 @ 14:54:
[...]


Dan merk je vanzelf wel dat het antwoord niet klopt.

Heb jij dan ook iets ingebouwd dat

spoiler:

als de doel low of high bot al vol is een bot-regel niet/later uitgevoerd wordt? Ik kijk daar niet naar. Heeft een bot bij mij twee waardes, dan verdeelt die ze altijd over de low en high ongeacht wat daar al in staat.

Ik heb daar inderdaad wel rekening mee gehouden (code, regel 27), maar zolang het niet gebeurde heb ik er niks mee gedaan. Ik heb het idee dat ik vaak te lang doordenk over mogelijkheden waar het fout kan gaan (voor deze puzzels dan )

[ Voor 7% gewijzigd door Rips10 op 10-12-2016 16:45 ]

[- peter -]

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.

--edit--
Mooie code trouwens weer Soultaker. Zit daar veel refactoring in als je de oplossing eenmaal hebt? Of kom je gelijk op zulke elegante oplossingen?

[ Voor 39% gewijzigd door - peter - op 10-12-2016 23:24 ]

[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 ]

[renebe]

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 ]

[renebe]

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 ]

[renebe]

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 ]

[renebe]

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 ]