Problem statement: http://adventofcode.com/2015/day/4
Fundamentally, this problem statement is very straight forward. Count from 1 to infinity until you get a number which when concatenated with the
input and then hashed starts with leading zeros. There are a couple of ways to verify leading zeros; my first draft in 2015 converted the byte array of the hash into a string and compared the characters to zero; other postings online use fixed matching of bytes 0, 1, and 2. In my current solution I abstracted
HasLeadingZeros() which can test any number of leading zeros.
Since the only addendum for part B is to check for 6 zeros instead of 5, I am easily able to adapt by calling
HasLeadingZeros() with 6 zeros instead of 5.
There are two important things to note about
HasLeadingZeros(). First, since we are primarily working on Intel machines, we can make the assumption that the first
0 is in the top half of the first byte. So, on even
i % 2 == 0), we want to extract the top half of the byte by using
0xf0, and the bottom half (
0x0f) on odd
i. This requires knowledge about how bits are stored in memory on computers (see here); knowledge about how bitwise operators work (see here); and understanding how byte arrays are printed as text.
Second, because there are two hex characters for each byte, we can take advantage of the fact that integer division does not care about remainders by using
i / 2 to index into the byte array. For example,
0 / 2 and
1 / 2 equal
Once we have the hex value we need, we can compare with zero; if we find that any of them are non-zero we can return immediately with
false and check the next number.
There should be nothing exciting about
GetPassword(); we simply count from
1 to infinity, take the number and append it to the input string, compute the hash of the result string, and check to see if it has the appropriate number of leading zeros.
Structurally, the code for the F# version is similar to the C# version. There are a few things about F# I learned in the process of developing this version. First,
Seq.initInfinite: this is an
IEnumerable way to generate numbers from 0 to infinity. It requires a function similar to
Seq.map, so you can choose to provide that function directly or have
Seq.initInfinite return the values directly and map using
Second, as expected,
Seq.truncate are the F# version of
Seq.filter are the same function and both are the same as
Seq.head is the same as
Seq.exists is the same as
I'm beginning to appreciate the
|> syntax for passing the result of a function as an argument into another function. In C#, in the middle of
GetPassword(), we don't really need to have a variable to hold the result of
ComputeHash(), but if we don't use a hash the code gets unwieldy quickly as we pass each as a parameter into the next function. F# allows us to specify them each directly one by one without keeping the intermediary variables that we don't really need.