Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# Problem:
# Balance all boxes with the minimum number of moves. Each
# move is the operation of taking N from one box and distributing
# it to other boxes equally.
# 30, 50, 45, 40, 35
#
# 1st move: take 12 from third box [45], and give other boxes +3
# 33, 53, 33, 43, 38
#
# 2nd move: take 16 from second box [53], and give other boxes +4
# 37, 37, 37, 47, 42
#
# 3rd move: take 4 from fifth box [42], and give other boxes +1
# 38, 38, 38, 48, 38
#
# 4th move: take 8 from the fourth box [48], and give other boxes +2
# 40, 40, 40, 40, 40
import time
import statistics
import random
real_ctx = [30, 50, 45, 40, 35]
n_members = len(real_ctx)
ctx_average = statistics.mean(real_ctx)
iterations = 0
n_best_moves, best_moves = 1000, None
start_time = time.monotonic()
while True:
fake_ctx = real_ctx.copy()
moves = []
counter = 0
while counter < n_best_moves and not all(item == ctx_average for item in fake_ctx):
# select a random box, and a random number of items
# to take from that box
selected_index = random.randrange(0, n_members)
selected_item = fake_ctx[selected_index]
selected_value = random.randrange(0, selected_item + 1, n_members - 1)
# distribute that taken items into other boxes
balancing_value = selected_value // (n_members - 1)
fake_ctx = [item + balancing_value for item in fake_ctx]
fake_ctx[selected_index] -= balancing_value * n_members
# record the moves
moves.append((selected_item, selected_value))
counter += 1
if counter < n_best_moves:
best_moves = moves
n_best_moves = counter
iterations += 1
if iterations % 50000 == 0:
print(
"iterations: ",
iterations,
n_best_moves,
best_moves,
f"{time.monotonic() - start_time} seconds"
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment