Expand description
Advent of Code 2015 Day 4: https://adventofcode.com/2015/day/4
This is a simple, if computationally expensive challenge. Start at 1
and append to the input string and compute the MD5 hash. If the (hex)
results has the desired number of leading 0s then you’re done,
otherwise increment the counter and try again.
A second attempt to improve the runtime of this solution maintains the same general logic as above but splits the work into parallel threads. On my machine this saw time improvements from about 10-11 seconds down to 2.5 to 3.5 seconds to compute both prefixes independently. There are probably other improvements that could be made to speed this up further (such as running both prefixes together so that we don’t have to recompute so many hashes that we know aren’t long enough, but I prefer to have each part distinct). The way that I implemented it is to spawn threads and have them work on 100,000 hashes at a time. This could (maybe) be improved by instead having a solution found mutex and having each thread work independently until it finds a solution or until the solution mutex is set or something similar. Obviously, the way I have currently done it, there is a decent amount of wasted compute if the resulting number is very small (e.g., answers less than 100,000) or even if we could find an answer early in any batch of work we could return instantly but instead need to wait for all of the threads to finish.
I didn’t try to implement the MD5 algorithm myself and instead decided
to use the md-5 crate.
Functions§
- The solution for the day four challenge.