Solution for Advent of Code 2016 - Day 14: One-Time Pad

Link to the puzzle text

Part 1

In this puzzle we are asked to find keys with certain conditions. Each key candidate starts with a given salt and is followed by a number. To test if a key candidate is valid, we MD5-hash the candidate and check for two conditions: First the hash should contain a triplet of characters and second the repeated char should be a five-tuplet in at least one of the next 1000 key candidates. The answer is the 64th valid key.

We iterate over all candidate and check for the two conditions:

def check_if_three_repeats(hash):
    return re.findall("(.)\\1\\1", hash)


def check_if_five_repeats(i, character):
    for j in range(i + 1, i + 1001):
        hash = create_hash(j)
        if character * 5 in hash:
            return True
    return False

Since we are rehashing the same candidates multiple times, I set up a simple caching mechanism to lookup previous hashes. This is incorporated into the create_hash function.

def create_hash(i):
    if i in hashdict.keys():
        return hashdict[i]
    hash = salt + str(i)
    hash = hashlib.md5(hash.encode()).hexdigest()
    hashdict[i] = hash
    return hash

Finally we once we hit the 64th key, we stop and return the answer.

Part 2

In part 2, we are using a more complicated version of hashing: Instead of just 1 round of MD5, we are using 2017 rounds. Therefore I included an argument num_rounds to the create_hash function to reuse the rest of the previous code.

def create_hash(i, num_rounds):
    if i in hashdict.keys():
        return hashdict[i]
    hash = salt + str(i)
    for k in range(num_rounds):
        hash = hashlib.md5(hash.encode()).hexdigest()
    hashdict[i] = hash
    return hash

Link to my solutions