Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Crypto Mining

Advent of Code 2015 - Day 4

Day 4: The Ideal Stocking Stuffer

Useful Links

Concepts and Packages Demonstrated

hashlibMD5 hashBlockchain nonce

Problem Intro

This one is pretty simple.

We’re told that Santa needs to mine some AdventCoins. The mining process is described is one where we start with some sort of alphanumeric seed string, and then we append a number to that string. We hash the resulting string with the MD5 algorithm. The MD5 algorithm always returns a 128-bit value. We convert that 128-bit value into a 32-character hexademinal representation. (Recall that one hexademical character can represent any 4-bit sequence.)

We’re asked to find the lowest numeric suffix that, when added to the seed, generates an MD5 hash where the hexadecimal representation number of the hash begins with a fixed number of zeroes.

This is pretty similar to how proof of work cryptocurrency mining (like Bitcoin mining) is actually done!

Bitcoin mining requires that a new block of data is added to the blockchain. In a nutshell:

And this is how BTC is mined!!

Part 1

Find the lowest positive number (no leading zeroes: 1, 2, 3, …) that produces a hash where the hex representation contains five leading zeroes.

Not much to do here:

from pathlib import Path
import time
import hashlib

SCRIPT_DIR = Path(__file__).parent 
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")

def main():
    with open(INPUT_FILE, mode="rt") as f:
        hash_seed = f.read()
    
    # counter is the nonce
    counter = 1
    part1_solved = False
    while not part1_solved:
        data = hash_seed + str(counter)
        # Create byte equivalent of input string, then generate md5 hexdigest.
        hash_hex = hashlib.md5(data.encode()).hexdigest()
        
        if hash_hex.startswith(5*"0") and not part1_solved:
            print(f"Part 1. With input {data}, hash = {hash_hex}")
            part1_solved = True

        counter += 1  # increment the nonce

Part 2

Exactly the same, but now we need to find a hash that begins with six zeroes.

It’s pretty trivial to amend the code to work for both parts:

def main():
    with open(INPUT_FILE, mode="rt") as f:
        hash_seed = f.read()
    
    # counter is the nonce
    counter = 0
    part1_solved = part2_solved = False
    while not (part1_solved and part2_solved):
        data = hash_seed + str(counter)
        # Create byte equivalent of input string, then generate md5 hexdigest.
        hash_hex = hashlib.md5(data.encode()).hexdigest()
        
        if hash_hex.startswith(5*"0") and not part1_solved:
            print(f"Part 1. With input {data}, hash = {hash_hex}")
            part1_solved = True

        if hash_hex.startswith(6*"0") and not part2_solved:
            print(f"Part 2. With input {data}, hash = {hash_hex}")
            part2_solved = True

        counter += 1  # increment the nonce

And the output looks like this:

Part 1. With input yzbqklnj282749, hash = 000002c655df7738246e88f6c1c43eb7
Part 2. With input yzbqklnj9962624, hash = 0000004b347bf4b398b3f62ace7cd301
Execution time: 9.3078 seconds