Advent of Code F# – Day 5

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.


Day 5

See details of the chal­lenge here.

Let’s start by adding a hash func­tion that’ll take an input string and return the hexdec­i­mal rep­re­sen­ta­tion of its MD5 hash.

From there, we can cre­ate an infi­nite sequence of hash val­ues gen­er­at­ed by con­cati­nat­ing the input and an increas­ing index (as per the instruc­tion). But, remem­ber, we’re only inter­est­ed in hash val­ues that starts with 5 zeroes.

Once we have this sequence of inter­est­ing hash val­ues, part 1 requires us to take the first 8 and make a pass­word out of it.


Part 2

As the door slides open, you are pre­sent­ed with a sec­ond door that uses a
slight­ly more inspired secu­ri­ty mech­a­nism. Clear­ly unim­pressed by the last
ver­sion (in what movie is the pass­word decrypt­ed in order?!), the East­er Bun­ny
engi­neers have worked out a bet­ter solu­tion.

Instead of sim­ply fill­ing in the pass­word from left to right, the hash now also
indi­cates the posi­tion with­in the pass­word to fill. You still look for hash­es
that begin with five zeroes; how­ev­er, now, the sixth char­ac­ter rep­re­sents the
posi­tion (0–7), and the sev­enth char­ac­ter is the char­ac­ter to put in that posi­tion.

A hash result of 000001f means that f is the sec­ond char­ac­ter in the pass­word.
Use only the first result for each posi­tion, and ignore invalid posi­tions.

For exam­ple, if the Door ID is abc:

The first inter­est­ing hash is from abc3231929, which pro­duces 0000015…; so, 5
goes in posi­tion 1: _5______.
In the pre­vi­ous method, 5017308 pro­duced an inter­est­ing hash; how­ev­er, it is
ignored, because it spec­i­fies an invalid posi­tion (8).
The sec­ond inter­est­ing hash is at index 5357525, which pro­duces 000004e…; so,
e goes in posi­tion 4: _5__e___.
You almost choke on your pop­corn as the final char­ac­ter falls into place,
pro­duc­ing the pass­word 05ace8e3.

Giv­en the actu­al Door ID and this new method, what is the pass­word? Be extra
proud of your solu­tion if it uses a cin­e­mat­ic “decrypt­ing” ani­ma­tion.

We can reuse the inifi­nite sequence of inter­est­ing hash val­ues we con­struct­ed ear­li­er, but this time around we need to also fil­ter out hash val­ues whose 6th char­ac­ter is not 0–7.

Addi­tion­al­ly, we need to track the first hash val­ue for each posi­tion.

The first idea I had was to use a muta­ble Option<char>[] (length 8) to rep­re­sent the pass­word, and then iter­ate over the valid hash val­ues until that array is filled with Some x. But this approach felt too imper­a­tive for my lik­ing..

I couldn’t use a fold as it will fold over all the inputs.. how­ev­er, I can use a scan which yields the inter­me­di­ate results as a sequence — which I can then skip until I have 8 hash val­ues.

I can also use an immutable Set to rep­re­sent all the posi­tions that are still unoc­cu­pied as I iter­ate through the hash val­ues.

Whilst part 1 was not com­pu­ta­tion­al­ly light, it did com­plete in a mat­ter of sec­onds on my lap­top. Part 2 took more than a minute to fin­ish so if any­one knows a good way to speed things up please leave a com­ment to this post.