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 Hashinghashlib

Page Navigation

• Problem Intro
• Part 1
• Part 2
• Results

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

Given the actual Door ID, what is the password?

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

Given the actual Door ID and a new hashing method, what is the password??

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.

For example, if the Door ID is abc:

• If a hash is 000001..., the sixth character is 1, so this is for position 1 of the password.
• If a hash is 000001a..., the seventh character is a, so the character for position 1 is a.
• If a hash is 000008..., the sixth character is 8, which is an invalid position, so this hash is ignored.
• If we find a hash for a position that is already filled, we ignore it and continue searching for hashes for the remaining empty positions.

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
    # ...

In-depth Explanation

Let’s break down the key parts of the Part 2 solution:

• while "_" in pwd:: This is the main loop that continues as long as there are still unfilled positions in the password (represented by the underscore _ character).

• if position in "01234567":: This is a concise way to check if the position character is one of the valid digits from ‘0’ to ‘7’. It’s more readable than checking the integer value against a range.

• if pwd[position] == "_":: This checks if the character at the given position in the pwd string is still the placeholder _. This ensures that we only fill each position once, with the first valid hash we find for it.

• pwd = pwd[:position] + hash_hex[6] + pwd[position+1:]: This line is where the password string is updated. It uses string slicing to construct a new password string. Let’s look at how this works:

  • pwd[:position]: This slice takes all the characters in the pwd string before the position.
  • hash_hex[6]: This is the new character that we want to insert.
  • pwd[position+1:]: This slice takes all the characters in the pwd string after the position.

  By concatenating these three parts, we effectively replace the character at position with the new character, while keeping the rest of the string unchanged. This is the standard way to “modify” a character in a string in Python, as strings themselves are immutable.

Results

The final code is as follows:

import logging
import os
import time
import hashlib

# pylint: disable=logging-fstring-interpolation

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
SAMPLE_INPUT_FILE = "input/sample_input.txt"

def main():
    logging.basicConfig(level=logging.INFO, format="%(asctime)s:%(levelname)s:	%(message)s")
        
    # input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    with open(input_file, mode="rt") as f:
        door_id = f.read()
    
    logging.info(f"Door ID: {door_id}")

    # Part 1
    pwd = ""
    nonce = 0
    while len(pwd) < 8:
        data = door_id + str(nonce)
        # Create byte equivalent of input string, then generate md5 hexdigest.
        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
    pwd = "________"
    nonce = 0
    while "_" in pwd:
        data = door_id + str(nonce)
        # Create byte equivalent of input string, then generate md5 hexdigest.
        hash_hex = hashlib.md5(data.encode()).hexdigest()
        
        if hash_hex.startswith("00000"):
            position = hash_hex[5]
            if position in "01234567":
                position = int(position)
                # Check we haven't already filled this position
                if pwd[position] == "_":
                    pwd = pwd[:position] + hash_hex[6] + pwd[position+1:]
                    
                    logging.debug(f"Found {hash_hex} with data {data}.")
                    logging.info(f"{pwd}")
        
        nonce += 1


if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

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.

‹›