Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Selection solution in Clear category for Loading Cargo by PositronicLlama
import itertools
import math
class BruteForcePartition:
"""
Solve the balance problem using a brute force approach.
"""
def time(self, stones):
return 1 << (len(stones) - 1)
def min_diff(self, stones):
best = None
total = sum(stones)
# Only need to consider sets up to size of half
max_size = math.ceil(len(stones) / 2)
for s in itertools.chain.from_iterable(itertools.combinations(stones, r) for r in range(1, max_size + 1)):
part = sum(s)
diff = abs(2 * part - total)
if best is None or diff < best:
best = diff
return best
class DynamicPartition:
"""
Solve the balance problem using a dynamic programming approach.
See: http://en.wikipedia.org/wiki/Partition_problem
"""
def time(self, stones):
total = sum(stones)
return total * len(stones) / 2
def min_diff(self, stones):
total = sum(stones)
x_size = len(stones) + 1
y_size = math.floor(total / 2) + 1
table = [False] * (x_size * y_size)
table[0] = True
def index(x, y):
return x + x_size * y
for x, s in enumerate(stones, 1):
for y in range(y_size):
v = table[index(x - 1, y)]
if not v and s <= y:
v = table[index(x - 1, y - s)]
table[index(x, y)] = v
# Print table (for debugging)
#for y in range(y_size):
# print(''.join(['X' if table[index(x, y)] else ' ' for x in range(x_size)]), y)
best = math.floor(total / 2)
while not table[index(x_size - 1, best)]:
best = best - 1
return abs(2 * best - total)
def checkio(stones):
'''
Minimal possible weight difference between stone piles.
'''
# Select the best algorithm for this dataset.
ALGORITHMS = [BruteForcePartition(), DynamicPartition()]
approach = min(ALGORITHMS, key=lambda algorithm: algorithm.time(stones))
# Compute the result
return approach.min_diff(stones)
# Possible approaches:
# Brute force - O(2^N)
# Dynamic programming - O(total * N), cheaper unless total is big
# Best solution - select based on total and N
if __name__ == '__main__':
assert checkio([10, 10]) == 0, 'First, with equal weights'
assert checkio([10]) == 10, 'Second, with a single stone'
assert checkio([5, 8, 13, 27, 14]) == 3, 'Third'
assert checkio([5, 5, 6, 5]) == 1, 'Fourth'
assert checkio([12, 30, 30, 32, 42, 49]) == 9, 'Fifth'
assert checkio([1, 1, 1, 3]) == 0, "Six, don't forget - you can hold different quantity of parts"
assert checkio([9, 9, 7, 6, 5]) == 0, "Seven, don't be greedy"
# Added this test case to force the dynamic programming approach.
assert checkio([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]) == 0, "Primes"
print ('All is ok')
Dec. 6, 2012
Comments:
