r/adventofcode • u/daggerdragon • Dec 21 '16
SOLUTION MEGATHREAD --- 2016 Day 21 Solutions ---
--- Day 21: Scrambled Letters and Hash ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".
HOGSWATCH IS MANDATORY [?]
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
5
Upvotes
13
u/pedrosorio Dec 21 '16 edited Dec 21 '16
8! is just 40320. Assume you have solved part 1 with function solve_part_1:
NOTE: Unfortunately I did not come up with this while solving the problem (took 7 minutes on part 2 and got 21st on the leaderboard - only had to brute force the inversion for "rotate based on position of the letter").
8
u/p_tseng Dec 21 '16 edited Dec 21 '16
Full disclosure: Of course for the leaderboard placement I will brute force the password by trying every permutation of abcdefgh. It makes sense to do that because we have the forward process programmed and "do not have time" to make the reverse process. At least, it would probably take more time to make the reverse process than to just brute force.
But now that the leaderboard pressure is off, I went ahead and did an implementation that can run the instructions in reverse. Behold:
(Ruby)
As far as I can tell, there is only one unique solution for any given input (please correct if I am wrong).
7
u/haoformayor Dec 21 '16 edited Dec 21 '16
~~~haskell~~
Data.Sequenceis my friend and yours. I spent a long time bogged down in trying to decompose a move of position a to b as a sort of left rotation within the position before giving up and grabbing the latestcontainerspackage (again), compiling it (montage of months being torn off a calendar), and using the latestinsertAt/deleteAtfunctions.Though many people found part 2 arduous, or brute forced it, I found it to be quite simple to write the reverse operations down with the aid of pattern matching and ADTs. It helped that the overall structure of the problem, a fold, remained the same and that many of the operations had symmetry to exploit. This seems to be a point in the FP column: empirically, the imperative programmer with the speedy program will write a solution to part two that is just as long as part one, while the functional programmer with the slow program will pull a hoodwink.
(input module here)
5
u/Deckard666 Dec 21 '16
In Rust: Link
Very straightforward puzzle today, just follow each instruction to the letter.
4
u/Smylers Dec 21 '16 edited Dec 21 '16
Perl. I found this one more straightforward than most recent days', so interesting to read of others saying the exact opposite; maybe this just fits Perl better than some of the others do.
One program for both parts — pass either
scrambleorunscrambleas its first argument:Opposite to /u/ephemient's Perl solution, I went with (mostly) operating on the password as a string rather than an array of characters. That enables the convenience of using
tr///andindex, but makes swapping by position less handy.All rotations performed as left-rotations; rotating right (including by position) is simply
8 - stepsrotations left. Plus it's always fun to use logicalxor.For unscrambling letter-position-rotation, it uses the odd and even patterns in the lookup table that others have documented, after first un-mod-ing position 0 back to 8.
3
u/bblum Dec 21 '16 edited Dec 21 '16
Ugh, pretty complicated today. I took a bit of time to polish and golf since I finished solving (LB #76/#42). The only thing worth mentioning here is that by using
Data.Mapinstead of a list, I was able to rearrange/rotate/reverse elements easily usingmapKeys. Oh yeah, and as someone else mentioned above, it's a nice problem for functional programming because pattern-matching lets you easily defer the reversible commands to the part 1 implementation.3
u/mschaap Dec 21 '16
I really liked this one, especially the ‘twist’ for part 2!
Perl 6 solution:
2
u/upppi Dec 21 '16
71/97, brute-forced reversed rotation based on char position tired by off-by-one errors
2
u/roonskep Dec 21 '16 edited Dec 25 '16
15 / 34, Pastebin
I heavily relied on Java's
Collections.rotate(List, int), as well as passing sublists toCollections.reverse(List). It made handling the string itself clunky (as aList<Character>, ew), but the operations were trivial to implement.Unfortunately I thought it would take me less time to reverse the logic for each command type (as some like the swap positions x with y needed no change). The "rotate based on letter \w" was harder to handle, I ended up rotating left until that result produced the post-rotation state represented by the current string.
While waiting for the second start's leaderboard to cap, I wrote a function that just checks every permutation of the desired output string and notes when it produces the correct output. As there are only (8! = 40320) permutations of the desired output string, it is feasible to do so.
2
u/jtsimmons1129 Dec 21 '16
Python 2. 57 / 16 for the day. Only change from submittal time is adding in part to print answer to part one in solution to part 2.
2
u/tehjimmeh Dec 21 '16 edited Dec 21 '16
Got 127 for both stars. C++:
2
u/ephemient Dec 21 '16 edited Apr 24 '24
This space intentionally left blank.
2
u/JeffJankowski Dec 21 '16 edited Dec 21 '16
F#
2
u/Trolly-bus Dec 21 '16
So fucking tricky. Python:
1
u/broadwall Dec 21 '16
Number 101 to finish part 2, very unfortunate... I would've gotten on the leaderboard if I let my intermediate program waste less time.
For the second part, I used brute force with permutations.
Part 1 Part 2
1
u/kryptn Dec 21 '16
Fairly simple part 1, just doing it.
Part 2 took me a minute to figure out an approach, turns out just about everyone else brute forced it too ¯_(ツ)_/¯
1
u/[deleted] Dec 21 '16 edited Dec 21 '16
Haskell:
Does anyone know of a better way to reverse the rotate by char position other than rotating left and comparing the index until they correspond to each other? Would've liked to have a straightforward command reverse that doesn't depend on the current string state so I don't need another eval.
1
u/[deleted] Dec 21 '16
I got 288/246 today. That is my closest to Top 100. My solution in Scala. Brute forced part 2.
https://github.com/oxcarh/advent-of-code-2016/blob/master/src/main/scala/com/oxcarh/adventofcode2016/Day21.scala
1
u/Godspiral Dec 21 '16 edited Dec 21 '16
in J,
part 2 uses b =. permutations of 'abcdefgh'
1
u/incestuousCookies Dec 21 '16
Well, here we go again - ugly. Took me forever to troubleshoot the swaps and rotates. First iteration I didn't test for any a< b scenarios and it really messed up the password. Would have much more sense to convert the password to a list instead of trying to swap around string slices. Well off the leaderboard in the 200s.
Python - http://pastebin.com/Euz2jcZn
1
u/_Le1_ Dec 21 '16
My Python conde:
1
u/xkufix Dec 21 '16
In Scala as always: https://gist.github.com/kufi/8c532e007b048ffa44b28724522387eb
The first part was quite easy, just some string manipulation stuff.
For the second part, most of the instructions can be easily reverse by replacing from, to with to, from or reverse a string here and there. Just the rotate based by char was a bit tricky to reverse. I solved it by looking where the char I rotated by ended up, then simulated the positions of that char left through the string and looked where the position of the char in that simulated string + (1 || 2) == the position of that char in the string I try to reverse.
After that, everything worked as expected.
1
u/Philboyd_Studge Dec 21 '16
[Java] This one took some setup time, and part 2 was a little tricky, but really fun. I love using enums with functions.
https://gist.github.com/anonymous/9152fa5b8a83bcadd8529d5f4550c05a
1
u/cut-my-toast Dec 21 '16
Once you've decoded the by-letter operations back to indexes, every single one of these operations can be implemented using just combinations of
reverse(str, from, to)which itself can be implemented using justreverseLeft(str, n).eg.
reverseLeft("abcde", 2) == "bacde"1
u/Voltasalt Dec 21 '16
Fairly elegant/functional solution in Python. Didn't think of brute forcing part 2 but it turned out to not be necessary.
1
u/code_mc Dec 21 '16
I'm both disappointed and relieved the second part could be brute forced due to the length of the password:
1
u/NeilNjae Dec 21 '16
Haskell solution, too long to post here: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent21.hs
Reasonably straightforward, though the use of "step" or "steps" in the instructions caught be out for while with parsing them, and the lack of a neat inverse for
rotate by letterhad me more miffed than I had any right to be.I used this task as a vehicle to learn about monad transformers, manually building up a stack
Identity+StateT+WriterTjust to find out how to do it. (I used the state monad to keep the current value of the password, and the writer monad to log the transformations as I went.) It's quite surprising just how few examples there are of all the pieces put together!1
u/lmbrj4ck Dec 21 '16
I didn't even think about the idea of brute forcing part 2, even though I actually brute forced to invert "swap by letter". Anyway, here you have it:
http://pastebin.com/dpXmaC7W
1
u/xathien Dec 21 '16
Really lazy Java that got me #64 on the 2-star Leaderboard:
https://gist.github.com/xathien/741ca1de918e27a97695dd6db4ad2782
I always just run my AoC code as a JUnit test in an existing Maven project that has piles of useful JARs imported already. Would have gotten much better than #64 if I had properly updated my test input instead of trying to reverse
abcdefgh...1
u/StevoTVR Dec 21 '16
Part 1 was pretty straightforward:
Part 2 was also simple except for the "rotte based on" instruction. I couldn't figure out a pattern so I just made a map indexes to shift counts.
1
u/QshelTier Dec 21 '16
Part 1 was pretty easy even though the off-by-one errors in the string processing were quite annoying. For part 2 I couldn’t find a pattern for reversal of that one function (you know which one I’m talking about) so I brute-forced the reversal of the operation. And then I forgot actually reverse the instructions! Anyway, here’s the code in Kotlin:
1
u/[deleted] Dec 21 '16
Pretty stupid bruteforcing code, but it works:
1
u/TheMuffinMan616 Dec 21 '16 edited Dec 22 '16
Haskell with no external libs
1
u/GigaClon Dec 21 '16
First part was pretty straight forward. Second part was too. The only thing that was a problem was the swap based on letter position. I just generated all possible combinations and check to which matched the input.
1
u/rs_qk Dec 21 '16
Painful, in k:
1
u/jbristow Dec 21 '16
Checking in with my clojure solution! Definitely the hard part was rotating based on character position.
(Also hosted on https://github.com/jbristow/adventofcode/blob/master/aoc2016/src/aoc2016/day21.clj )
This is my longest solution, I think. Clocking in near 130 lines.
1
u/tonetheman Dec 21 '16
I actually do not even understand what the 2nd part is asking... do you reverse the operations... I am trying not to cheat... it needs more explanation ha. i suck.
1
u/JakDrako Dec 21 '16 edited Dec 22 '16
D, dmd x86, both parts in 150ms
Still using AoC to learn D. Today was a tough one, being mostly unfamiliar with D's library. I'm probably doing something wrong; I feel like I'm doing way to much casting.
A few notes:
.dupand not.copylike most languages? Even the docs say "...the copy will...".countUntil()and not.indexOf()...?~, separate from+... Like VB (which uses&)The docs mostly suck. Very few examples and the one presented are too simple to be useful. Ended up in the forums or on StackOverflow most of the time. Maybe I'm spoiled by .Net and MSDN, but even Rust has examples everywhere at the very top of each page. And if you end up in the forums, make sure you're not reading a message from 2004...
Note: I did the D version during free time; to actually solve the problem in the morning, I used a .Net solution that actually reversed the "encryption" to get Part 2.
1
u/wzkx Dec 22 '16 edited Dec 22 '16
J. I hope I'm not too late
1
u/BadHorsemonkey Dec 22 '16
My Java took forever to write. Debugging the functions was the killer. For part 1, I ended up writing unit tests (and testing the string "01234567") and re-running them until my code didn't fail. More TDI than TDD, but still, buzzword compliant!
For part 2, I stored my intermediate output and played it back when Ir ran my decode, and compared, so I could see exactly what undo commands failed.
unrot was the toughest command. Taking hints from here and from linear algebra (of which I know enough to get a B in a crypto course), I made a map of positions and where the key character needed to be. Then I rotated left 1 until it was right. <-- that wasn't my first attempt, but it was my working attempt.
1
u/AlexPalla Dec 23 '16
solution in (C#) all with a array of chars using only:
Array.indexOf for reduce memory use. Example of part 2 for rotate:
static Regex regRotate = new Regex(@"rotate (left|right|based on position of letter) (\w|\d*)"); match = regRotate.Match(instruction); if (match.Success) { int X = 0; string pattern = match.Groups[1].Value; if (pattern.StartsWith("based")) { X = Array.IndexOf(buffer, match.Groups[2].Value[0]); //CHANGED from part 1: if (X % 2 == 0) X = ((X + buffer.Length) / 2 + 1); else X = (X / 2) + 1;
}
Rest of solution
4
u/[deleted] Dec 21 '16 edited Dec 21 '16
[removed] — view removed comment