Sean McLemon | Advent of Code

2017-12-14 - Disk Defragmentation

(original .ipynb)

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

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 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
    

def knot_hash(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()


def part_one(input_str):
    total_hash = []
    for n in range(128):
        h = knot_hash(f"{input_str}-{n}")
        total_hash += [c for c in "".join([bin(int(c, 16))[2:].zfill(4) for c in h])]
    
    return sum(1 for c in total_hash if c == "1")


assert 8108 == part_one("flqrgnkx")

print("part one:", part_one("ljoxqyyw"))

part one: 8316

from advent import neighbours4

def part_two(input_str):
    hash_grid = []
    for n in range(128):
        h = knot_hash(f"{input_str}-{n}")
        hash_grid.append([c for c in "".join([bin(int(c, 16))[2:].zfill(4) for c in h])])
    
    current_group = 0
    visited = set()
    for r,row in enumerate(hash_grid):
        for c,col in enumerate(row):
            if col == "0":
                visited.add((r,c))
                continue
            
            if (r,c) in visited:
                continue
            
            queue = [(r,c)]
            while len(queue) > 0:
                qr,qc = queue.pop(0)
                if (qr,qc) in visited:
                    continue
                
                visited.add((qr,qc))
                if hash_grid[qr][qc] == "0":
                    continue
                
                for nr,nc in neighbours4(hash_grid, qr, qc):
                    queue.append((nr,nc))
            
            current_group += 1
            
    return current_group


assert 1242 == part_two("flqrgnkx")

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

part two: 1074