Memory Reallocation

In [57]:

    

def reallocate(val, pos, n):
        l = [val // n] * n
        r = val % n
        for i in range(r):
            l[(pos + i + 1) % n] += 1
        return l

def update(b):
    blocks = sorted(list(enumerate(b)), key=lambda v: (v[1], -v[0]), reverse=True)
    pos = blocks[0][0]
    val = blocks[0][1]
    c = [b[i] if i != pos else 0 for i in range(len(b))]
    l = reallocate(val, pos, len(b))
    for i, v in enumerate(c):
        c[i] += l[i]
    return c

def count_until_loop(b):
    count = 0
    previous = set()
    h = hash(tuple(b))
    while h not in previous:
        previous.add(h)
        count += 1
        b = update(b)
        h = hash(tuple(b))
    return count


    

In [76]:

    

assert(count_until_loop([0, 2, 7, 0]) == 5)


    

In [78]:

    

input_blocks = [11, 11, 13, 7, 0, 15, 5, 5, 4, 4, 1, 1, 7, 1, 15, 11]
count_until_loop(input_blocks)


    

    
Out[78]:





4074

In [79]:

    

def loop_size(b):
    count = 0
    last_seen = {}
    h = hash(tuple(b))
    while h not in last_seen:
        last_seen[h] = count
        count += 1
        b = update(b)
        h = hash(tuple(b))
    return count - last_seen[h]


    

In [81]:

    

assert(loop_size([0, 2, 7, 0]) == 4)


    

In [82]:

    

input_blocks = [11, 11, 13, 7, 0, 15, 5, 5, 4, 4, 1, 1, 7, 1, 15, 11]
loop_size(input_blocks)


    

    
Out[82]:





2793