Advent of Code 2015 - Day 4

Day 4: The Ideal Stocking Stuffer

Useful Links

‹›

• 2015 Main Page
• My solution code

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:

• A set of transactions - called a block - needs to be hashed.
• A hash is only valid if the hexademical representation of the hash contains a specified number of leading zeroes.
• The required number of leading zeroes is called the block difficulty.
• An incrementing value - called the nonce - is appended to the block data prior to hashing. BTC is awarded to the miner that discovers the first valid nonce for the current block of data.

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

• We read in our seed data.
• We create a nonce called counter.
• We enter a loop, which will continue to run until we’ve found a satisfactory hash. In the loop:
  • We append the nonce to the seed.
  • We use encode() to convert seed+nonce str to a bytes representation that can be hashed using MD5.
  • We create a 128-bit hash of the encoded data, using hashlib.md5().
  • We convert the hash to a hexadecimal representation, using hexdigest()
  • We check to see if the hex representation starts with five zeroes. If it does, we’ve got what we need and we can exit the loop.

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

‹›