<jupyter_start><jupyter_text>Disk Defragmentation Import from Day 10 "Knot Hash" problem<jupyter_code>import numpy as np
import operator
from functools import reduce

standard_suffix = [17, 31, 73, 47, 23]

def invert(a, length, head):
    r = np.roll(a, -head)
    r = np.concatenate((r[:length][::-1], r[length:]))
    return np.roll(r, head)

def transform(a, length, head, skip, size=2**8):
    r = invert(a, length, head)
    head = (head + length + skip) % size
    return r, head

def one_round(input_lengths, a=None, skip=0, head=0, size=2**8):
    if a is None:
        a = np.arange(size)
    for length in input_lengths:
        a, head = transform(a, length, head, skip, size)
        skip += 1
    return a, head, skip

def lengths_from_string(ascii_input):
    return list(map(ord, list(ascii_input))) + standard_suffix

def many_rounds(input_lengths, nruns = 2**6):
    head, skip = 0, 0
    a = np.arange(2**8)
    for _ in range(nruns):
        a, head, skip = one_round(input_lengths, a=a, skip=skip, head=head)
    return a

def dense(h):
    dense_hash = []
    for i in range(2**4):
        a = h[16 * i: 16 * (i + 1)]
        dense_hash.append(reduce(operator.xor, a, 0))
    return dense_hash

def hashing(ascii_input, size=2**8):
    lengths = lengths_from_string(ascii_input)
    dense_hash = dense(many_rounds(lengths))
    return ''.join([hex(d)[2:] if len(hex(d)) == 4 else '0' + hex(d)[2:] for d in dense_hash])<jupyter_output><empty_output><jupyter_text>Part 1<jupyter_code>from collections import Counter

def bindigits(s_hex):
    s_bin = ''
    for i, c in enumerate(s_hex):
        s_bin += '{0:04b}'.format(int(c, 16))
    return s_bin

def hextobits(key):
    base = 16
    nbits = 4
    for i in range(2**7):
        s_hex = hashing(key + '-{}'.format(str(i)))
        yield bindigits(s_hex)

def count_disk(key):
    count = 0
    for s in hextobits(key):
        count += Counter(s)['1']
    return count<jupyter_output><empty_output><jupyter_text>Test<jupyter_code>assert(count_disk('flqrgnkx') == 8108)<jupyter_output><empty_output><jupyter_text>Solution<jupyter_code>key = '<KEY>'
count_disk(key)<jupyter_output><empty_output><jupyter_text>Part 2<jupyter_code>def hextobits_matrix(key):
    m = np.empty((2**7, 2**7), dtype=np.int16)
    indices = []
    for i, row in enumerate(hextobits(key)):
        l = list(row)
        m[i,:] = np.array(l)
        for j, s in enumerate(l):
            if s == '1': indices.append((i, j))
    return m, indices

def number_components(key):
    m, indices = hextobits_matrix(key)
    matrix_map = np.zeros((2**7, 2**7), dtype=np.int16)
    count = 0
    while(indices):
        i = indices.pop()
        queue = [i]
        while(queue):
            q = queue.pop()
            matrix_map[q[0], q[1]] = count + 1
            for arrow in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                p = (q[0] + arrow[0], q[1] + arrow[1]) 
                if p in indices:
                    queue.append(p)
                    indices.remove(p)
        count += 1
    return matrix_map, count<jupyter_output><empty_output><jupyter_text>Test<jupyter_code>m, indices = hextobits_matrix('flqrgnkx')
print(m)
print(len(indices))
matrix_map, count = number_components('flqrgnkx')
print(matrix_map)
print(count)<jupyter_output>[[1237 1237    0 ..., 1229 1229    0]
 [   0 1237    0 ..., 1229    0    0]
 [   0    0    0 ...,    0    0 1222]
 ..., 
 [  39   39   39 ...,    1    0    0]
 [  39   39    0 ...,    1    0   30]
 [   0    0   29 ...,    1    1    0]]
1242<jupyter_text>Solution<jupyter_code>key = '<KEY>'
matrix_map, count = number_components(key)
print(matrix_map)
print(count)<jupyter_output>[[   0    0    0 ...,  901  901    0]
 [   0    0 1010 ...,    0    0    0]
 [ 996  996    0 ...,    0    0  901]
 ..., 
 [   0    0   20 ...,   21   21    0]
 [  29    0    0 ...,   21    0    1]
 [   0    0   20 ...,    0    1    1]]
1018
{'fraction_non_alphanumeric': 0.15384615384615385, 'fraction_numerical': 0.054945054945054944, 'mean_word_length': 2.5356820234869017, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '615695', 'license': 'MIT', 'n_tokens_mistral': 1635, 'n_tokens_neox': 1490, 'n_words': 363, 'path': '2017/ferran/day14/day14.ipynb', 'repo_name': 'bbglab/adventofcode', 'size': '3919'}