### re: Daily Challenge #99 - Balance the Scales VIEW POST

Naive solution here - basically construct a dictionary with the sum of all possible weight combinations for initial weight a and then add all possible combinations of weights to initial weight b to determine which is the smallest number of weights to achieve equilibrium.

I will be working on refactoring to make this more efficient, but I figured I'd code out a naive implementation as a baseline first before moving on and improving time complexity.

## Python

import itertools

def balance(scaleArr):
a, b = scaleArr
weights = scaleArr
lowest_quantity = None
a_weight = None
b_weight = None
sum_dict = { a: () }
combo_dict = {}
for i in range(len(weights)):
combos = list(itertools.combinations(weights, i))
combo_dict[i] = combos
for x in range(len(combos)):
sum = a
for n in combos[x]:
sum += n
if sum == b:
lowest_quantity = i
a_weight = combos[x]
b_weight = ()
if sum in sum_dict:
if x < len(sum_dict[sum]):
sum_dict[sum] = combos[x]
else:
sum_dict[sum] = combos[x]
for i in range(len(weights)):
combos = combo_dict[i]
for x in range(len(combos)):
sum = b
for n in combos[x]:
sum += n
if sum in sum_dict:
current_quantity = i + len(sum_dict[sum])
if lowest_quantity is None or current_quantity < lowest_quantity:
lowest_quantity = current_quantity
a_weight = sum_dict[sum]
b_weight = combos[x]
if lowest_quantity is None:
return 'not possible'
left = ', '.join(str(n) for n in a_weight) if len(a_weight) else 'nothing'
right = ', '.join(str(n) for n in b_weight) if len(b_weight) else 'nothing'
return ('The fewest number of weights needed for equality is '
f'{lowest_quantity}, putting {left} on the left and {right} on the right.')

code of conduct - report abuse  