Advent of Code - Year 2015, Day 04
Problem statement: http://adventofcode.com/2015/day/4
Part A
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.
Part B
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.
C#
source
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
(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 0
.
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.
F#
source
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 Seq.map
.
Second, as expected, Seq.take
and Seq.truncate
are the F# version of Enumerable.Take()
; Seq.where
and Seq.filter
are the same function and both are the same as Enumerable.Where()
; Seq.head
is the same as Enumerable.First()
; and Seq.exists
is the same as Enumerable.Any()
.
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 GetBytes()
or 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.