Disk Defragmentation

In [11]:

    

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


    

In [56]:

    

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


    

In [58]:

    

assert(count_disk('flqrgnkx') == 8108)


    

In [59]:

    

key = 'hwlqcszp'
count_disk(key)


    

    
Out[59]:





8304

In [117]:

    

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


    

In [118]:

    

m, indices = hextobits_matrix('flqrgnkx')


    

In [119]:

    

print(m)
print(len(indices))


    

    




[[1 1 0 ..., 1 1 0]
 [0 1 0 ..., 1 0 0]
 [0 0 0 ..., 0 0 1]
 ..., 
 [1 1 1 ..., 1 0 0]
 [1 1 0 ..., 1 0 1]
 [0 0 1 ..., 1 1 0]]
8108

In [121]:

    

matrix_map, count = number_components('flqrgnkx')


    

In [122]:

    

print(matrix_map)
print(count)


    

    




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

In [123]:

    

key = 'hwlqcszp'
matrix_map, count = number_components(key)


    

In [124]:

    

print(matrix_map)
print(count)


    

    




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