2016 Advent of Code - Day05

Question

Day 5: How About a Nice Game of Chess?

You are faced with a security door designed by Easter Bunny engineers that seem to have acquired most of their security knowledge by watching hacking movies.

The eight-character password for the door is generated one character at a time by finding the MD5 hash of some Door ID (your puzzle input) and an increasing integer index (starting with 0).

A hash indicates the next character in the password if its hexadecimal representation starts with five zeroes. If it does, the sixth character in the hash is the next character of the password.

For example, if the Door ID is abc:

The first index which produces a hash that starts with five zeroes is 3231929, which we find by hashing abc3231929; the sixth character of the hash, and thus the first character of the password, is 1. 5017308 produces the next interesting hash, which starts with 000008f82..., so the second character of the password is 8. The third time a hash starts with five zeroes is for abc5278568, discovering the character f. In this example, after continuing this search a total of eight times, the password is 18f47a30.

Given the actual Door ID, what is the password?

Part Two

As the door slides open, you are presented with a second door that uses a slightly more inspired security mechanism. Clearly unimpressed by the last version (in what movie is the password decrypted in order?!), the Easter Bunny engineers have worked out a better solution.

Instead of simply filling in the password from left to right, the hash now also indicates the position within the password to fill. You still look for hashes that begin with five zeroes; however, now, the sixth character represents the position (0-7), and the seventh character is the character to put in that position.

A hash result of 000001f means that f is the second character in the password. Use only the first result for each position, and ignore invalid positions.

For example, if the Door ID is abc:

The first interesting hash is from abc3231929, which produces 0000015...; so, 5 goes in position 1: _5______. In the previous method, 5017308 produced an interesting hash; however, it is ignored, because it specifies an invalid position (8). The second interesting hash is at index 5357525, which produces 000004e...; so, e goes in position 4: _5__e___. You almost choke on your popcorn as the final character falls into place, producing the password 05ace8e3.

Given the actual Door ID and this new method, what is the password? Be extra proud of your solution if it uses a cinematic "decrypting" animation.

day05_test.py:

import unittest

from day05 import Checker

class CheckerTest(unittest.TestCase):

    def test_hash_from_inputs(self):
        checker = Checker()
        self.assertEqual(
            checker._hex_hash_from_inputs('abc', 3231929),
            '00000155f8105dff7f56ee10fa9b9abd'
        )

    def test_hex_hash_matches(self):
        checker = Checker()
        self.assertTrue(checker._hex_hash_matches('00000155f8105dff7f56ee10fa9b9abd'))
        self.assertFalse(checker._hex_hash_matches('0000155f8105dff7f56ee10fa9b9abd'))

    @unittest.skip("Part One")
    def test_get_door_password_part_1(self):

        checker = Checker()
        self.assertEqual(checker.get_door_password_part1('abc'), '18f47a30')

    def test_update_door_password(self):
        checker = Checker()
        self.assertEqual(checker._update_door_password('aaaaaaaa', 'b', 4), 'aaaabaaa')

    @unittest.skip("Part Two")
    def test_get_door_password_part_2(self):

        checker = Checker()
        self.assertEqual(checker.get_door_password_part2('abc'), '05ace8e3')

day05.py:

import hashlib
from datetime import datetime


class Checker:

    def _hex_hash_from_inputs(self, base, index):
        md5 = hashlib.md5()
        s = base + str(index)
        md5.update(s.encode('utf-8'))
        return md5.hexdigest()

    def _hex_hash_matches(self, hex_hash):
        if '00000' == hex_hash[0:5]:
            return True
        return False

    def get_door_password_part1(self, base):
        door_password = ''
        i = -1
        for char in range(8):
            looping = True
            while looping:
                i += 1
                h = self._hex_hash_from_inputs(base, i)
                if self._hex_hash_matches(h):
                    door_password = door_password + h[5]
                    looping = False

        return door_password

    def _update_door_password(self, door_password, new_val, new_index):
        new_index = int(new_index)
        return door_password[:new_index] + new_val + door_password[new_index + 1:]

    def get_door_password_part2(self, base):

        initial_char = '-'
        door_password = initial_char * 8
        i = -1

        pw_index_index = 5

        looping = True
        while looping:
            i += 1
            h = self._hex_hash_from_inputs(base, i)
            if self._hex_hash_matches(h):
                try:
                    pw_index = int(h[pw_index_index])
                    print('Match found for i=' + str(i) + ' and h=' + h + ' with door_password=' + door_password + ' and pw_index=' + str(pw_index))
                    if door_password[pw_index] == initial_char:
                        door_password = self._update_door_password(door_password, h[pw_index_index + 1], pw_index)
                        print('Current door password:' + door_password + ' for i=' + str(i) + ' and hash=' + h)

                except Exception as e:
                    pass

                if door_password.find(initial_char) == -1 or i == 10000000:
                    return door_password



def main():
    input_s = 'ojvtpuvg'

    c = Checker()
    t1 = datetime.now()
    print('Part one:' + c.get_door_password_part1(input_s))
    t2 = datetime.now()
    delta = t2 - t1
    print('Part one time:' + str(delta.total_seconds()))

    t1 = datetime.now()
    print('Part two:' + c.get_door_password_part2(input_s))
    t2 = datetime.now()
    delta = t2 - t1
    print('Part two time:' + str(delta.total_seconds()))


if __name__ == '__main__':
    main()

Any sorts of feedback would be appreciated. Specifically curious about:

• Trying to decide about leaving both part1/part2 methods. I could combine them, but it seems to be a SRP violation, but I could also optimize all the hashing
• Seems like I could make the hashing more efficient
• I really don't like my try/except logic

Answer 1

The solution is not bad, though it is a bit verbose for my taste. I don't think that OOP helps you at all here: the self just gets in the way, and there isn't anything naturally object-oriented in the nature of the problem. The classes just act as a namespace, and you already get the namespaces for free by putting the code in two files.

I think that doctests asserting the facts stated in the examples would suffice for unit testing. If they don't give the expected results, then you can always add more tests to investigate. (You should be writing docstrings anyway.)

The solution could really benefit from generators and more idiomatic looping. In particular, setting flag variables like looping to direct the execution flow is rarely a good idea; keywords like break, continue, and return are more effective. Also, stuff like i += 1 is usually more elegantly done using itertools. Since char is never used, it is customary to use _ to indicate that it is a "throwaway" variable.

def get_door_password_part1(self, base):
    door_password = ''
    i = itertools.count()
    for _ in range(8):
        while True:
            h = self._hex_hash_from_inputs(base, next(i))
            if self._hex_hash_matches(h):
                door_password += h[5]
                break
    return door_password

But we can do even better than that, I think…

---

The task states that you want to examine MD5 hashes that start with "00000" — these hashes constitute an infinite sequence, for which you can define an interesting_hashes(door_id) generator function.

import hashlib
from itertools import islice

def interesting_hashes(door_id):
    """
    MD5 hashes of door_id followed by some increasing counter, where
    the hex representation starts with '00000'.

    >>> abc_hashes = interesting_hashes('abc')
    >>> next(abc_hashes)[:6]
    '000001'
    >>> next(abc_hashes)[:9]
    '000008f82'
    >>> next(abc_hashes)[:6]
    '00000f'
    """
    for index in count(0):
        md5 = hashlib.md5()
        md5.update((door_id + str(index)).encode('utf-8'))
        hex_hash = md5.hexdigest()
        if hex_hash.startswith('00000'):
            yield hex_hash

Using that generator, part 1 can be done as a single expression. Here, I've used itertools.islice() to take the first 8 results from interesting_hashes().

def door_password_part1(door_id, length=8):
    """
    Perform 2016 Advent of Code Day 5, Part 1.

    >>> door_password_part1('abc')
    '18f47a30'
    """
    return ''.join(
        hex_hash[5] for hex_hash in islice(interesting_hashes(door_id), length)
    )

Part 2 is naturally more complex. Since the password has to be filled in in an unpredictable order, and Python strings are immutable, you should use a list to build the result. I would initialize with None instead of -.

I'm very concerned about your use of catch Exception — a catch-all like that, especially when the exception handler consists of just a pass, could hide all kinds of weird bugs. What kinds of exceptions do you really want to catch? There is a possible failure in pw_index = int(h[pw_index_index]), if h[pw_index_index] is [a-f]. There is also an out-of-bounds error in _update_door_password() if new_index is 8 or 9. So, avoid both possible failures by parsing the character as a hex digit and checking that it is less than 8.

def door_password_part2(door_id, length=8):
    """
    Perform 2016 Advent of Code Day 5, Part 2.

    >>> door_password_part2('abc')
    '05ace8e3'
    """
    password = [None] * length
    hash_generator = interesting_hashes(door_id)
    while not(all(password)):
        position, char = next(hash_generator)[5:7]
        position = int(position, 16)
        if position < length and password[position] is None:
            password[position] = char
    return ''.join(password)

if __name__ == '__main__':
    print(door_password_part1('ojvtpuvg'))
    print(door_password_part2('ojvtpuvg'))

Note that in general, I've opted to eliminate trivial helper functions in favour of chunks of functionality (namely interesting_hashes()) that actually do make a difference.