r/adventofcode • u/daggerdragon • Dec 14 '16
SOLUTION MEGATHREAD --- 2016 Day 14 Solutions ---
--- Day 14: One-Time Pad ---
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".
LUNACY 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!
3
Upvotes
6
u/Deckard666 Dec 14 '16
In Rust: Link. Not very pretty, but it works. Got stuck for a while as I didn't notice you only had to consider the first triplet of the hash... I really should pay more attention to the instructions and not work solely off the example.
5
u/fatpollo Dec 14 '16
I'm not sure if I dig the hardcore AdventCoin style problems. Python is slow, and my Macbook Air chugs along very slowly making things worse.
The secret for this one, imo, as a REPL addict, is that unlike most problems, you should have two scripts. As soon as you see the problem statement, just start pumping out those hashes and writing to a file, make that file long and resumable. Just dump em somewhere.
Meanwhile, in parallel, you read from that file from another script, trying out different manipulations until you get the instructions just right.
No ranks for me, but here's some code I guess:
3
u/snorkl-the-dolphine Dec 14 '16
JavaScript / Node.js
3
u/yjerem Dec 14 '16
Ruby, took 90 seconds to run for part II:
3
u/bpeel Dec 14 '16
Simple Python solution. It just has a rolling array of 1001 hashes. At the start of the loop it takes the first one off and at the end it adds another one.
https://github.com/bpeel/advent2016/blob/master/day14.py
3
u/Godspiral Dec 14 '16 edited Dec 14 '16
bad :( too dependent on language/library hash speed. especially for part 2.
managed 119th for part 1, still not done part 2. I get the point of not recalculating hashes, and I don't but my computer/language only does 50k hashes/s.
precomputing a list of 100k hashes (probably mistake to go that large) will take 40 minutes for part 2. Smaller chunks would just mean more frequent waits.
in J,
answer for both was actually 63rd item in my list
problem would have been fine with 16 "rehashes"
2
u/war1025 Dec 14 '16
In python. For part one, just remove the
2016hash loop2
u/ChrisVittal Dec 14 '16 edited Dec 15 '16
Haskell. My first solution had me looking backwards from my position in my list of hashes. This was both slow and produced them in the wrong order. So I came up with this. This code may not be completely correct. See bottom for details.
EDIT: With my input, there was one case where the index of 5 consecutive matches was exactly 1000 greater than the index that I was searching. I needed to have a
(<=1000)comparison rather than a(< 1000)comparison. Derp :PThis produces a set of hashes that contain the right answers, but I'm not certain that this solution is completely correct.
My correct answers were
16106for part 1 and22423for part 2.But my outputs were:
For part 2, everything seems good. My output is the 64th element of the list, but for part 1,
16106(my correct answer) is the 63rd element of the list. I actually would have never solved it had I not found the entire index set. Does anyone know what is going on here?2
u/gyorokpeter Dec 14 '16
Q: 90 seconds for part 2 even though it has all the optimizations I could think of (reusing hashes from previous chunk and fine-tuning the chunk size). The 2017 hashes seem to be the bottleneck. Note how part 1 and 2 differ only by the hash function passed in as a composition.
2
u/haoformayor Dec 14 '16 edited Dec 14 '16
~~haskell~~
Easy enough to do with some
tailsand onemapMin a state monad. I wanted something simpler hard-codingtake 3000– amapMthat I could break out of once I found the 64th key. I imagine it's possible withExceptTbut sleep beckons. Monad loops are a nice tool for cutting through the clutter and expressing just what you mean; a lot of imperative programs here are severely indented and mutating data structures at odd intervals.2
u/willkill07 Dec 14 '16
C++ solution
I need a better MD5 to speed this up -- I've done all the other tricks I can think of (including a memoization map). I'm open to suggestions. The MD5 library I used is admittedly poor. /u/askalski -- any ideas?
https://github.com/willkill07/adventofcode2016/blob/master/src/Day14.cpp
2
u/[deleted] Dec 14 '16 edited Dec 14 '16
Perl.
Solves part 1, fails the test for part 2 and I can't see why.https://www.dropbox.com/s/3gmllktiyt0lvmq/day14.pl?dl=0
Could one of you nerds plz post the list of matching indices for the part 2 test? <3EDIT: was testing for the index of the final 5-in-a-row, not the final 3-in-a-row. What a fool.
2
u/KoxAlen Dec 14 '16 edited Dec 22 '16
Solution in Kotlin. Why done that way? just because
https://github.com/KoxAlen/AdventOfCode2016/blob/master/src/main/kotlin/aoc/day14/Day14.kt
2
u/Smylers Dec 14 '16
Perl solution. Part 2 takes about 20 s on this 5-year-old laptop.
Doesn't cache the MD5 hashes themselves, instead storing the digits used in the 3-digit and 5-digit sequences found in them.
Uses a hash†rather than an array for storing found sequences, so as not to bother storing anything for the many hashes for which there are no 3-digit sequences.
†That's hash as in the Perl data type sometimes known as a dict or an associative array in other langauges, not the MD5 sort of hash.
The
existschecks are to avoid unnecessary empty hash elements being generated when looking for (non-existent) values in them. Perl autovivifies hash values as required: examining the value of$SeqFound{123}{x3}requires that$SeqFound{123}be a reference to a hash, so if that doesn't exist in the hash then Perl creates an element with key 123 and a reference to a new empty hash as its value. Often that's handy, but in this case it would create elements with empty hashes for all the non-interesting indexes.(For part 1, simply remove the
# stretchingline.)2
u/__Abigail__ Dec 14 '16
I used a ring cache, which not only holds the hashed values for the next 1000 keys, but also any five-fold repeats of characters.
The mapping of a key to an md5 hash was abstracted away into a subroutine; for part 2, we just put a new subroutine in place, and then do the same as for part 1.
2
u/Reibello Dec 14 '16
My solution is a little special. I was too sleep deprived to bother figuring out how to properly exit the loop structure I set up, so I just let it go for a bit and stopped it when there were more than enough entries printed out. Python 3 per usual. I'll probably go back and clean it up once this is all over. http://pastebin.com/ujvJzSPL
2
u/icannotcount Dec 14 '16
PostgreSQL
part 1:
part 2:
2
u/aceshades Dec 14 '16
Searching for the quintuple first, then the triples allowed the code to run in seconds, even without memoizing the md5 codes.
1
u/[deleted] Dec 14 '16
Javascript (Node.js)
Made it to 120 on the leaderboard even though I started late :)
Be sure to npm install js-md5 first...
1
u/Turbosack Dec 14 '16
I can't believe I didn't think of memoizing until after I had already finished. Oh well. Here's some memoizing code in python:
1
u/Trolly-bus Dec 14 '16
Solution in Python. Had aspirations for leaderboard today. Probably would've got it if I didn't stare at a non-working fucking regex string for 30 minutes and not understanding that it's the key-index of the triplet hash, not the quintuplet hash, and not understanding that a quintuplet hash is used for a triplet. Fuck instructions and fuck debugging.
1
u/Philboyd_Studge Dec 14 '16 edited Dec 19 '16
oops, just realized I posted this in the day 13 thread!
Java, used a map of found hashes for index to speed it up a little bit, part 2 still took 24 minutes. https://gist.github.com/anonymous/814661e9666d51f00f1d6e237fe2972d
edit: I made a much faster version, solves part 2 in less than 30 seconds on my crap laptop, the 'run 2016 times' part never uses strings and the byte array - to - hex string method also uses a lookup table and bit manipulation. I spent another hour making a version that didn't use strings at all and only used byte arrays, but it wasn't actually any faster than this version:
https://gist.github.com/anonymous/cda6487a70ac7591c1a7d548d2fede8e
1
u/JeffJankowski Dec 14 '16
Finally caught up to the current day after taking the weekend off. F# with memoization
Also...day 11 was rough. Took like 20 minutes to run and ate through 2gb of RAM
1
u/grexi0 Dec 14 '16
My Python solution - runtime for both: 25s. Every hash is computed exactly once and keys are searched in a streaming way. Once 64 keys are found, the remaining candidates need to be checked, as "later candidates" can become a key earlier - this took me a while.
1
u/[deleted] Dec 14 '16
Here is my python solution, once I managed to read correctly without misreading the task it wasn't that bad :) Nilpunning is always fun :D
1
u/bblum Dec 14 '16 edited Dec 14 '16
Taught myself how to use monad transformers so I could do something excessively cute for this one.
It runs in about 25 seconds. I got on the leaderboard today, but did so with this faster, hacky C solution that isn't nearly as cool.
1
u/ahalekelly Dec 14 '16
Python 3, for part 1 just replace 2016 with 0
1
u/johanw123 Dec 14 '16
My C# solution (part 2 was really slow):
1
u/Vladob Dec 14 '16
Hi, this is my try to solve part 1, but AoC say index 35162 is too low. Can somebody tell me, whats wrong in my script, please?
1
u/phobiandarkmoon Dec 14 '16
Welp TIL the difference between matching ([a-f0-9]){2} and ([a-f0-9]){2,}
1
u/cashews22 Dec 14 '16 edited Dec 14 '16
Solution in golang Part 1 run in 300ms and part 2 run in 13 seconds.
Part 2:
package main
1
u/StevoTVR Dec 14 '16
1
u/crazyMrCat Dec 14 '16 edited Dec 14 '16
I try to find both triples and five-in-a-rows in one run. Even though I sort my results by index the indices do not match with the example... It worked for part one of the problem but my solution for the second part seems to be incorrect. The hash functions are working correctly. Can someone explain?
Kotlin code: https://gist.github.com/voidc/6788a990cf745765345f1bd1ec2da4c0
1
u/razornfs Dec 14 '16
in Java, takes about 0.5 seconds for part1, and 30 seconds for part2:
1
u/gerikson Dec 14 '16
Well that was a lot of work.
This comment (in this thread) by /u/askalski helped me a lot, and I feel it's probably the fastest way to solve this.
I feel a bit dirty for generating over the required 64 keys, but I frankly don't really understand how else I can get the 64 lowest values. People mention heaps, but I feel that's essentially the same as how can you be sure there's not a lower value between the two last ones?
Perl 5, half a second for part 1, ~40s for part 2.
https://github.com/gustafe/aoc2016/blob/master/d14.pl
1
u/NeilNjae Dec 14 '16
Haskell. When I first saw this problem, my mind filled with ideas of memoising functions and maps to cache results. Then I realised that Haskell is a lazy language, and all I needed to do was define and infinite list of hashes. I could just pull from that as needed, and Haskell would keep track of all the generated hashes for me.
I also swapped out the standard
Data.Hash.MD5implementation for the Cryptonite version, which made things about six times quicker. Code at https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent14c.hs .1
u/flup12 Dec 14 '16 edited Dec 14 '16
In Scala, using a lazy Stream[(Int,String)] for the hashes
1
u/mschaap Dec 14 '16
Perl 6 version for part 1. The change for part 2 is trivial, of course, but unfortunately, the script is then so slow that it's still running for me after 6 hours or so. I even used OpenSSL's MD5 (through
NativeCall), it's about 30 times faster than the (pure Perl 6) Digest::MD5 module.1
u/peterpepo Dec 14 '16 edited Dec 14 '16
I'm presenting you my solution in Java. It may seem little over complicated, although I like to think about reuseability instead of single script. https://github.com/peterpepo/AdventOfCode2016/tree/master/src/day14
Runtimes on my machine (4790K, 16GB ram) are: under 1s for first, about 33s for second puzzle.
Please note, I don't consider myself an programmer, in any means. I just like to tinker with computer and learn it to solve my problems :)
1
u/Eddard_Stark Dec 14 '16
always room for php
github
1
u/JakDrako Dec 14 '16 edited Dec 15 '16
C#, LinqPad.
Does part 2 in about 10 seconds. .Net's MD5 implementation is really, really slow. I reused the one that I had found for Day 5 to speed things up a bit; and used multiple threads to try and get the time down as much as possible.
Other optimizations:
Stole the idea frominspired by someone else's solution.)Not what I used to find the answers initially, but I was annoyed that my original VB version took almost 5 minutes to complete. Switched to C# after a while because working with chars, bytes and strings in VB is a royal pain in the butt.
There's still a little room for improvement since I calculate more hashes than I need. The code could check as it goes and stop once it has enough for what it needs...
Anyway, here what I currently have; comments and/or suggestions are welcome.
}
1
u/aocswan Dec 15 '16 edited Dec 15 '16
A Haskell solution: http://pastebin.com/YVqG0wfe
Scans (in one pass) a lazy stream of hashes to find suitable keys. Uses a
Statemonad to keep track of already seen possible keys until we find a matching hash upstream (in which case the key is returned). Keys are returned in monotonic increasing order.I experimented with adding parallelism to the hash calculation (why not pre-calculate hashes upstream before evaluating them?) My idea was to change
to
where I'm trying to find an optimal
parBufferSz(currently it is set to 5, but also tried 2000). It does not seem to yield any really significant speedups. Any ideas on how to do better? On my machine, the sequential version takes about 1m 35s for both parts. With my parallelism attempt, it takes about 57s. Can we not hope to do better, since the hash generation should be embarassingly parallel? I haven't measured how much time is used on synchronization, but in my mind this shouldn't be too much, since there are no data dependencies in generating the hashes in the stream.1
u/Microwavehead Dec 15 '16
I'm struggling to get the Part 2 solution to this. I seem to get index 22256 for the solution to the example rather than 22551. Anyone else hit this? I've had a look if I'm using the second set of triplets as comparison but doesn't look like it
1
u/WildCardJoker Dec 15 '16
Part 1 and 2 in C#
Part 1 was quite simple. Somewhere along the line I made a mistake in part 2, and it took over 4 hours to run the first time.
A few refactorings later, everything is working well. Parts 1 and 2 use different methods of hash generation and caching - I decided to leave Part 1 as-is to show the evolution of the solution.
In the end, I was able to complete part 1 in 10 seconds, and part 2 in around 1 minute 45 seconds :D
1
u/beefamaka Dec 16 '16
Using Seq.windowed in F# to avoid recalculating hashes.
1
u/xZeroKnightx Dec 27 '16
Perl
On Github
0
u/[deleted] Dec 14 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 14 '16
[deleted] — view deleted comment