*Shamelessly stolen from Here :)*

Your server has sixteen memory banks; each memory bank can hold any number of blocks. You must write a routine to balance the blocks between the memory banks.

The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.

We need to know how many redistributions can be done before a blocks-in-banks configuration is produced that has been seen before.

For example, imagine a scenario with only four memory banks:

* The banks start with 0, 2, 7, and 0 blocks (`[0,2,7,0]`). The third bank has the most blocks (7), so it is chosen for redistribution.
* Starting with the next bank (the fourth bank) and then continuing one block at a time, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2.
* Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3.
* Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4.
* The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1.
* The third bank is chosen, and the same thing happens: 2 4 1 2.
At this point, we've reached a state we've seen before: 2 4 1 2 was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is 5.

Return the number of redistribution cycles completed before a configuration is produced that has been seen before.

People seem to be struggling, so here's a visual walkthrough of the above example: http://oi65.tinypic.com/dmshls.jpg

Note: Remember, memory access is very fast. Yours should be too.

**Hint for those who are timing out:** Look at the number of cycles happening even in the sample tests. That's a _lot_ of different configurations, and a lot of different times you're going to be searching for a matching sequence. Think of ways to cut down on the time this searching process takes.

Please upvote if you enjoyed! :)

Difficulty: EASY
Tags: Fundamentals

Data structures
Skill types: Data structures

Starter code:
def mem_alloc(banks):
	

Solutions:
def mem_alloc(banks):
	seen = set()
	while tuple(banks) not in seen:
		seen.add(tuple(banks))
		number = max(banks)
		index = banks.index(number)
		banks[index] = 0
		while number:
			index = (index + 1) % 16
			banks[index] += 1
			number -= 1
	return len(seen)


def mem_alloc(banks):
	(banks, redist) = (tuple(banks), set())
	while banks not in redist:
		redist.add(banks)
		blocks = max(banks)
		(index, div, mod) = (banks.index(blocks), *divmod(blocks, 16))
		banks = tuple(((i != index and bank) + div + ((i - index - 1) % 16 < mod) for (i, bank) in enumerate(banks)))
	return len(redist)


def mem_alloc(banks):
	(seen, turn) = (set(), 0)
	while 1:
		saw = tuple(banks)
		if saw in seen:
			return turn
		seen.add(saw)
		(im, m) = max(enumerate(banks), key=lambda it: (it[1], -it[0]))
		(n, r) = divmod(m, len(banks))
		banks[im] = 0
		banks = [v + n for (i, v) in enumerate(banks)]
		for i in range(1, r + 1):
			banks[(i + im) % len(banks)] += 1
		turn += 1


from operator import itemgetter

def mem_alloc(banks):
	cache = set()
	count = 0
	while tuple(banks) not in cache:
		cache.add(tuple(banks))
		count += 1
		(ind, val) = max(enumerate(banks), key=itemgetter(1))
		banks[ind] = 0
		for i in range(val):
			ind += 1
			banks[ind % len(banks)] += 1
	return count


def mem_alloc(t):
	(visited, l) = (set(), len(t))
	while 1:
		m = max(t)
		ind = t.index(m)
		(t[ind], put) = (0, m // l)
		for i in range(l):
			t[i] += put
		for i in range(ind + 1, ind + (m - put * l) + 1):
			t[i % l] += 1
		m = tuple(t)
		if m in visited:
			return len(visited) + 1
		visited.add(m)


def mem_alloc(block):
	common_set = set()
	new_list = tuple(block)
	while not new_list in common_set:
		common_set.add(new_list)
		new_list = list(new_list)
		max_num = max(new_list)
		len_list = len(new_list)
		(base_num, len_mod_num) = divmod(max_num, len_list)
		len_div_num = len_list - len_mod_num
		ind = new_list.index(max_num)
		new_list[ind] = 0
		pattern_num = [base_num] * len_div_num + [base_num + 1] * len_mod_num
		pattern_num = pattern_num[ind::-1] + pattern_num[len_list:ind:-1]
		for i in range(len_list):
			new_list[i] += pattern_num[i]
		new_list = tuple(new_list)
	return len(common_set)


def mem_alloc(banks):
	banks = banks[:]
	d = set()
	n = 0
	L = len(banks)
	while tuple(banks) not in d:
		d |= {tuple(banks)}
		n += 1
		(i, m) = (0, 0)
		for (j, v) in enumerate(banks):
			if v > m:
				m = v
				i = j
		(a, b) = divmod(m, L)
		banks[i] = 0
		for _ in range(L):
			banks[_] += a
		for _ in range(b):
			banks[(i + _ + 1) % L] += 1
	return n


def mem_alloc(banks):
	seen = set()
	while tuple(banks) not in seen:
		seen.add(tuple(banks[:]))
		num = max(banks)
		i = banks.index(num)
		banks[i] = 0
		while num:
			i = (i + 1) % len(banks)
			banks[i] += 1
			num -= 1
	return len(seen)


def mem_alloc(banks):
	(banks, memo, size) = (tuple(banks), set(), len(banks))
	while banks not in memo:
		memo.add(banks)
		i = max(range(size), key=banks.__getitem__)
		(q, r) = divmod(banks[i], size)
		(x, y) = (r + i, r + i - size)
		banks = tuple((q if i == j else banks[j] + q + (i < j <= x or j <= y) for j in range(size)))
	return len(memo)