scales.py

from itertools import combinations, product

LOW = 1
HIGH = 40
REFERENCE_WEIGHT_COUNT = 4

def has_solution(object_weight, reference_weights):
  """returns True if there is a way to use the reference weights to correctly identify the object weight"""
  guess_range = [LOW, HIGH]  # >= low, <= high
  # we take reference weight and a sign (+/-): + means on the right side of the scale, - means on the left
  # so +3, -2, +1 means 4 lbs on the right, 2 lbs on the left, for a net of 2 on the right
  # if our object weight is < 2 lbs, the right side will fall, > 2 lbs, the left side will fall, ==, the sides will stay
  # so for each observation we adjust our guess range, or short circuit early if we luck out and find an ==

  for ref_count in xrange(1, len(reference_weights) + 1):  # we don't have to use every weight
    for weights in combinations(reference_weights, ref_count):
      for signs in product([+1, -1], repeat=ref_count):
        weights = [w * s for w, s in zip(weights, signs)]
        net = abs(sum(weights))
        if net < object_weight:  # if the object is heavier
          guess_range[0] = max(guess_range[0], net + 1)
        elif net > object_weight:  # if the object is lighter
          guess_range[1] = min(guess_range[1], net - 1)
        else:
          return True
        if guess_range[0] == guess_range[1]:
          return True
  return False

for reference_weights in combinations(xrange(LOW, HIGH + 1), REFERENCE_WEIGHT_COUNT):      
  if all(has_solution(object_weight, reference_weights) for object_weight in xrange(LOW, HIGH + 1)):
    print "woohoo!  you can use: %s" % (reference_weights,)