Solution for Advent of Code 2017 - Day 10: Knot Hash

Link to the puzzle text

Part 1

In this puzzle, we have a description of an hash algorithm. We start with a list of all numbers between 0 and 255 and a current position marker. Given an input, a list of lengths, we reverse part of the list start at the current position and advance the position marker. This is repeated of all lengths in the input. The answer is the result of multiplying the first two numbers in the list.

The  hash function was straight forward to implement.

def hash_string(array, lengths):
    current_position = 0
    skip_size = 0
    for length in lengths:
        sublist = (array + array)[current_position: current_position + length]
        for pos, value in enumerate(reversed(sublist)):
            pos = (current_position + pos) % LIST_SIZE
            array[pos] = value
        current_position = (current_position + length + skip_size) % LIST_SIZE
        skip_size += 1
    return array

 

Part 2

In part 2, we complicate the hash function to get a hex string. The hash function should now run 64 rounds. The input should also be treated as a list of characters converted into bytes instead of a list of lengths. Finally the resulting list is converted into a hex string by XOR each block of 16 elements.

We first extend the hash_string function from before to include a num_rounds parameter. The rest was just calling the previous function with new parameters.

lengths = [ord(c) for c in input_line]
lengths += [17, 31, 73, 47, 23]
array = list(range(LIST_SIZE))

s = hash_string(array, lengths, 64)
return sparse_to_dense(s)

The  sparse_to_dense function does the blockwise XORing:

def sparse_to_dense(sparse):
    hex_string = []
    for x in range(16):
        subslice = sparse[16 * x:16 * (x + 1)]
        hex_string.append('%02x' % reduce((lambda x, y: x ^ y), subslice))
    return "".join(hex_string)

Link to my solutions