Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
one liner using a bit field (plus expanded version explained) solution in Clear category for Loading Cargo by mu_py
checkio = lambda data: min(abs(2 * sum(data[j] for j, k in enumerate(bin(i)[2:]) if k=='1') - sum(data)) for i in range(2 ** len(data)))
"""
# and here's the 'expanded' version of the one-liner
def checkio(data):
print(f'\n\n {data} len={len(data)} sum={sum(data)}\n')
min_diff, sum_total = sum(data), sum(data)
# each item has to be either left or right,
#
# if we assign l=0 and r=1,
# then we can describe any allocation be a binary number of length len(data), which equals 2 ** len(data) decimal
#
# here we just check all possible combinations (and yes: this is NOT the most effective way)
for i in range(2 ** (len(data))):
# get the binary representation (0b01001...)
allocation = bin(i)[2:]
# the weight of left side is the sum of all positions marked "0"
sum_left = 0
for j, k in enumerate(allocation):
if k == '1':
sum_left += data[j]
# the weight of other side side is sum_total - sum_left
# sum_right = sum_total - sum_left
# hence sum_left - sum_right == sum_left - (sum_total - sum_left) == 2 * sum_left - sum_total
diff_i = abs(2 * sum_left - sum_total)
if diff_i < min_diff:
min_diff = diff_i
print(f"i={i} \t {allocation}\t l/r= {sum_left} {sum_total - sum_left}\t d={diff_i}\t min={min_diff}")
return min_diff
"""
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([10, 10]) == 0, "1st example"
assert checkio([10]) == 10, "2nd example"
assert checkio([5, 8, 13, 27, 14]) == 3, "3rd example"
assert checkio([5, 5, 6, 5]) == 1, "4th example"
assert checkio([12, 30, 30, 32, 42, 49]) == 9, "5th example"
assert checkio([1, 1, 1, 3]) == 0, "6th example"
print('Yeah!')
Oct. 28, 2022
