Advent of Code 2016 - Day 5

Day 5: How About a Nice Game of Chess?

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

MD5 HashinghashlibString ManipulationLooping

Problem Intro

In this Advent of Code puzzle, we are tasked with finding an eight-character password for a security door. The password is generated by repeatedly hashing a combination of a “Door ID” (our puzzle input) and an incrementing integer (nonce). A character is revealed if the hexadecimal representation of the MD5 hash starts with five zeroes.

For example, if the Door ID is abc:

• The first hash starting with five zeroes might be for abc3231929, and its sixth character (the one after the five zeroes) would be the first character of the password.

Our goal is to find this eight-character password.

Part 1: Simple Password Construction

The first part requires us to construct the password by taking the sixth character of each valid hash (those starting with five zeroes) in the order they are found.

Solution Approach

1. Iterate and Hash: We start with a nonce of 0 and increment it in each iteration. We concatenate the door_id with the current nonce to form a string.
2. MD5 Hashing: We compute the MD5 hash of this combined string. The hashlib module in Python is used for this purpose.
3. Check for Five Zeroes: We convert the hash to its hexadecimal representation and check if it starts with “00000”.
4. Extract Character: If the hash is valid, we take its sixth character (index 5) and append it to our password string.
5. Repeat: We continue this process until we have collected eight characters for the password.

Code Snippet (Part 1)

import hashlib
import logging

def main():
    # ... (file reading and setup) ...
    door_id = "your_door_id_from_input"
    logging.info(f"Door ID: {door_id}")

    # Part 1
    pwd = ""
    nonce = 0
    while len(pwd) < 8:
        data = door_id + str(nonce)
        hash_hex = hashlib.md5(data.encode()).hexdigest()
        
        if hash_hex.startswith("00000"):
            pwd = pwd + hash_hex[5]
            logging.debug(f"Found {hash_hex} with data {data}.")
            logging.info(f"Pwd is: {pwd}")
            
        nonce += 1
    # ...

Part 2: Positional Password Construction

The second part introduces a twist: the password characters are placed at specific positions. The sixth character of a valid hash now indicates the position (0-7) in the password, and the seventh character is the actual character to be placed at that position. If a position is already filled, we ignore subsequent attempts to fill it.

Solution Approach

1. Initialize Password: We start with an empty password represented by a placeholder, e.g., "________".
2. Iterate and Hash (Same as Part 1): We continue to generate MD5 hashes using the door_id and incrementing nonce.
3. Check for Five Zeroes: Valid hashes are those starting with “00000”.
4. Determine Position and Character: For a valid hash:
   • The sixth character (index 5) is interpreted as the target position in the password. We only consider positions from ‘0’ to ‘7’.
   • The seventh character (index 6) is the character to be placed at that position.
5. Fill Password: If the determined position is valid and has not yet been filled in the password, we place the character at that position.
6. Repeat: We continue until all eight positions in the password are filled.

Code Snippet (Part 2)

import hashlib
import logging

def main():
    # ... (Part 1 code) ...

    # Part 2
    pwd = "________"
    nonce = 0
    while "_" in pwd:
        data = door_id + str(nonce)
        hash_hex = hashlib.md5(data.encode()).hexdigest()
        
        if hash_hex.startswith("00000"):
            position = hash_hex[5]
            if position in "01234567": # Check if position is a valid digit 0-7
                position = int(position)
                if pwd[position] == "_": # Only fill if position is not already taken
                    pwd = pwd[:position] + hash_hex[6] + pwd[position+1:]
                    
                    logging.debug(f"Found {hash_hex} with data {data}.")
                    logging.info(f"{pwd}")
        
        nonce += 1
    # ...

Conclusion

This puzzle is a straightforward application of MD5 hashing and string manipulation. The core challenge lies in efficiently generating and checking a large number of hashes. Part 2 adds a layer of complexity by introducing positional requirements and the need to handle already-filled positions, making it a good exercise in careful state management during iteration. The hashlib module in Python provides a convenient way to perform the necessary cryptographic hashing operations.

‹›