DEV Community 👩‍💻👨‍💻

Cover image for Advent of Code 2015 - Day 4
Jules
Jules

Posted on • Updated on

Advent of Code 2015 - Day 4

For Day 4, I was very glad of a standard library I had not previously used in Python. Here's the first part of the puzzle:

Screenshot of Advent of Code puzzle

With a quick Google, I found out that Python provides a standard library for hashing, appropriately called hashlib. It wraps lots of standard hash algorithms, such as SHA1, SHA224, SHA256, SHA384, SHA512, and of course, MD5.

Getting a string into the module and getting a hex value out aren't as straightforward as you might hope, but the documentation is pretty clear. First the string must be turned into a bytes object (s.encode()) before it can be passed to md5(). Then the return value has to be converted to hex using the hexdigest() function.

I ended up with solve() as a function because it can then be used to solve for any number of leading zeroes. Remember, always be thinking ahead to Part 2!

import hashlib

def solve(key, zeroes):

    n = 1
    prefix = zeroes * '0'

    while True:
        s = key + str(n)
        h = hashlib.md5(s.encode()).hexdigest()[:zeroes]
        if h == prefix:
            return n
        n += 1

print(solve('yzbqklnj', 5))
Enter fullscreen mode Exit fullscreen mode

I wasn't overly thrilled about while True, but couldn't see an alternative, besides setting an arbitrarily high upper bound. I saw code like for i in range(1, 1000000) and even for i in itertools.count() in the megathread, which didn't seem much better. The good thing about puzzle solving is knowing there is a solution, so you do know you'll exit the loop at some point.

The code solved for five leading zeroes in about 0.8s, which is more down to the implementation of hashlib than anything I was doing, which is essentially brute force.

Part 2 was the shortest extension so far, and one of the shortest I've ever seen:

Now find one that starts with six zeroes.

Having a generic solve() function meant that writing Part 2 was as simple as changing one character:

print(solve('yzbqklnj', 6))
Enter fullscreen mode Exit fullscreen mode

This ran quite a bit slower, but I was expecting this and reasonably happy that it solved in under 30s.

And the real Python programmers?

Most Pythonistas solved it much the same way I had, but there are a couple of solutions that used multi-threading to spread the brute force over several CPU's. I've never done any multi-threading before, so this is probably something I should look at.

Over just four days, I've realised there are several areas of standard Python that I need to spend some time getting to grips with, otherwise I'll keep solving puzzles as though I'm still writing in Basic:

  • zip()
  • sets
  • multi-threading
  • iterators

Top comments (0)

🔠 Find your favorite font

 
You can change your default font in Settings.