Advent of Code 2016

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