Page Navigation
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
- Iterate and Hash: We start with a
nonceof 0 and increment it in each iteration. We concatenate thedoor_idwith the currentnonceto form a string. - MD5 Hashing: We compute the MD5 hash of this combined string. The
hashlibmodule in Python is used for this purpose. - Check for Five Zeroes: We convert the hash to its hexadecimal representation and check if it starts with “00000”.
- Extract Character: If the hash is valid, we take its sixth character (index 5) and append it to our password string.
- 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 is1, so this is for position 1 of the password. - If a hash is
000001a..., the seventh character isa, so the character for position 1 isa. - If a hash is
000008..., the sixth character is8, 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
- Initialize Password: We start with an empty password represented by a placeholder, e.g.,
"________". - Iterate and Hash (Same as Part 1): We continue to generate MD5 hashes using the
door_idand incrementingnonce. - Check for Five Zeroes: Valid hashes are those starting with “00000”.
- 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.
- Fill Password: If the determined position is valid and has not yet been filled in the password, we place the character at that position.
- 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 thepositioncharacter 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 givenpositionin thepwdstring 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 thepwdstring before theposition.hash_hex[6]: This is the new character that we want to insert.pwd[position+1:]: This slice takes all the characters in thepwdstring after theposition.
By concatenating these three parts, we effectively replace the character at
positionwith 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.