Advent of Code: Day 10

For Day 10, the challenge is to hash a string using a "knot-based" hash algorithm. My Python solution is below:

from functools import reduce

class CircularList(list):
    def __getitem__(self, x):
        return super(CircularList, self).__getitem__(x % len(self))

    def __setitem__(self, x, v):
        super(CircularList, self).__setitem__(x % len(self), v)

    def __getslice__(self, i, j):
        for n in range(i, j):
            yield self[n]

    def __setslice__(self, i, j, v):
        v = list(v)
        for iterator, n in enumerate(range(i, j)):
            self[n] = v[iterator]

with open("input.txt", "r") as i:
    list_size = int(i.readline().strip())

    # This was for part 1
    # input_lengths = [int(l.strip()) for l in i.readline().split(",") if l]
    input_lengths = [l for l in i.readline()]

def run(lst, input_lengths, current_position=0, skip_size=0):
    for length in input_lengths:
        lst[current_position:current_position + length] = reversed(list(lst[current_position:current_position + length]))
        current_position += length + skip_size
        skip_size += 1
    return lst, current_position, skip_size

def hash(list_size, input):
    input_lengths = [ord(str(i)) for i in input] + [17, 31, 73, 47, 23]

    lst = CircularList(range(list_size))
    current_position = 0
    skip_size = 0

    for i in range(64):
        lst, current_position, skip_size = run(lst, input_lengths, current_position, skip_size)

    # Split into chunks of 16
    chunks = [lst[x:x+16] for x in xrange(0, len(lst), 16)]
    # XOR the chunks together
    chunks = [reduce((lambda acc, n : acc ^ n), chunk) for chunk in chunks]
    # Turn them into hex
    chunks = ["{:02x}".format(chunk) for chunk in chunks]
    return "".join(chunks)

# part1, _, _ = run(CircularList(range(list_size)), input_lengths)
# print "Part 1", part1[0] * part1[1]
print "Part 2", hash(list_size, input_lengths)

The most interesting part of this solution I think is the CircularList class. It only implements simple slices (no skipping, reversing, etc.) but it supports enough for this problem. Creating that class first means that the code inside run can be a lot cleaner as it doesn't need to worry about wrapping around.

Advent of Code runs every day up to Christmas, you should join in!.

Show Comments

Get the latest posts delivered right to your inbox.