Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Gready with Rebalance solution in Uncategorized category for Loading Cargo by octo
# migrated from python 2.7
class Hand:
def __init__(self, name):
self.name = name
self.sum = 0
self.stones = []
def add(self, stone):
self.sum += stone
self.stones.append(stone)
def xchg(self, myidx, other_hand, other_idx):
my_stone = self.stones[myidx]
self.sum -= my_stone
other_stone = other_hand.stones[other_idx]
other_hand.sum -= other_stone
self.stones[myidx] = other_stone
self.sum += other_stone
other_hand.stones[other_idx] = my_stone
other_hand.sum += my_stone
def __str__(self):
return '%s{%d: %s}' % (self.name, self.sum, self.stones)
def sort_hands(h1, h2):
if h2.sum > h1.sum:
return h1, h2
else:
return h2, h1
def checkio(stones):
l,r = initial_partition(stones)
print_state(l, r)
l,r = balance(l, r)
l,r = balance(l, r)
print_state(l, r)
return abs(l.sum - r.sum)
def print_state(l, r):
print("%s\n%s\n=>%d" % (l, r, abs(l.sum - r.sum)))
def balance(l, r):
s, b = sort_hands(l, r)
for i in range(0, len(s.stones)):
for j in range(0, len(b.stones)):
if s.stones[i] < b.stones[j] and b.stones[j] - s.stones[i] < b.sum - s.sum:
s.xchg(i, b, j)
continue
return s, b
def initial_partition(stones):
l = Hand('left')
r = Hand('right')
stones.sort()
stones.reverse()
for s in stones:
if l.sum <= r.sum:
l.add(s)
else:
r.add(s)
return l, r
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, "Hidden failed"
assert checkio([588, 128, 93, 963, 346, 66, 41, 466, 214, 894, 72, 104, 790, 870, 325, 547, 936, 214,
118, 265, 298, 515, 235, 153, 275, 923, 396,
15, 118, 768, 279, 441, 421, 743, 218, 401, 850, 361, 488, 841, 461, 804, 137, 17, 235, 349, 377, 135,
666, 634, 498, 660, 375, 851, 537, 155, 336, 274, 399, 404, 751, 787, 972, 586, 635, 991, 121,
263, 802, 129, 203, 68, 435, 127, 451, 267, 555, 681, 169, 376, 339, 376, 344, 711, 910, 693,
26, 35, 918, 801, 720, 463]) == 0, "Random List"
print('All is ok')
Dec. 27, 2012
