Sean McLemon | Advent of Code

2017-12-10 - Knot Hash

(original .ipynb)

puzzle_input_str = "34,88,2,222,254,93,150,0,199,255,39,32,137,136,1,167"
test_input_str = "3,4,1,5"

full_length = 256 # lengths = [0,1,2,3...255]
test_length = 5   # lengths = [0,1,2,3,4]

def rotate_list(lst, pos, length):
    sublist = []
    wrapped = 0
    
    while length > 0:
        if pos < len(lst):
            sublist.append(lst.pop(pos))
            length -= 1
        else:
            sublist.append(lst.pop(0))
            length -= 1
            wrapped += 1

    while wrapped > 0:
        lst.insert(0, sublist.pop(0))
        wrapped -= 1

    while len(sublist) > 0:
        lst.insert(pos, sublist.pop(0))

    return lst

def perform_round(lengths, lst, pos=0, skip=0):
    for length in lengths:
        lst = rotate_list(lst, pos, length)
        pos = (pos + length + skip) % len(lst)
        skip += 1
        
    return lst, pos, skip

def part_one(input_str, list_length):
    lengths = [int(s) for s in input_str.split(",")]
    lst = list(range(0, list_length))
    hashed_lst, _, _ = perform_round(lengths, lst, list_length)
    return hashed_lst[0] * hashed_lst[1]

assert 12 == part_one(test_input_str, test_length)

print("part one:", part_one(puzzle_input_str, full_length))

part one: 54675

def hash_block(block, sparse_hash):
    idx = block*16
    values = sparse_hash[idx:idx+16]
    
    hash_block = 0
    for value in values:
        hash_block ^= value
        
    hex_hash = hex(hash_block)[2:]
    if len(hex_hash) == 1:
        return "0"+hex_hash
    return hex_hash
    
assert "40" == hash_block(0, [65, 27, 9, 1, 4, 3, 40, 50, 91, 7, 6, 0, 2, 5, 68, 22])

def part_two(input_str):
    lengths = [ ord(c) for c in input_str ] + [17, 31, 73, 47, 23]
    
    current_round = 64
    skip = 0
    pos = 0
    sparse_hash = list(range(0, full_length))
    while current_round > 0:
        current_round -= 1
        sparse_hash, pos, skip = perform_round(lengths, sparse_hash, pos, skip)
        assert 256 == len(sparse_hash)
    
    block = 0
    dense_hash_lst = []
    while block < 16:
        dense_hash_lst.append(hash_block(block, sparse_hash))
        block += 1
        
    return "".join(dense_hash_lst).strip()

assert part_two("") == "a2582a3a0e66e6e86e3812dcb672a272"
assert part_two("AoC 2017") == "33efeb34ea91902bb2f59c9920caa6cd"
assert part_two("1,2,3") == "3efbe78a8d82f29979031a4aa0b16a9d"
assert part_two("1,2,4") == "63960835bcdc130f0b66d7ff4f6a5a8e"

print("part two:", part_two(puzzle_input_str))

part two: a7af2706aa9a09cf5d848c1e6605dd2a