12 Marbles Problem

12marbles.py

from collections import Counter, defaultdict
from itertools import combinations_with_replacement, product

def sgn(x):
    """Return -1, 0, or 1, whichever matches the sign of x."""
    if x < 0: return -1
    if x > 0: return 1
    return 0

# generate the layouts and make it easy to find the signatures.
masses = [Counter(k) for k in combinations_with_replacement(range(1,7),12)]

mass_breakdowns = defaultdict(list)

for mass in masses:
    signature = tuple(v for k,v in sorted(mass.items()))
    mass_breakdowns[signature].append(sorted(mass.keys()))

print("Building ambiguous piles.")

ambiguous_piles = []
for breakdown, mass_piles in mass_breakdowns.items():
    if len(mass_piles) == 1: continue
    measurement_piles = defaultdict(list)
    # generate the complete list of weighings.
    balance_counts = [list(range(-k, k+1)) for k in breakdown]
    for mass_pile in mass_piles:
        val = 0
        for power,balance_placement in enumerate(product(*balance_counts)):
            # I don't care about weighings that don't include something on each side.
            if max(balance_placement) <= 0 or min(balance_placement) >= 0:
                continue
            # weigh the boxes.  Use the result as a balanced ternary digit.
            val += 3**power * sgn(sum(bp*m for bp, m in zip(balance_placement, mass_pile)))
        # put the layout into a bin based on the results of all the weighings.
        measurement_piles[val].append(mass_pile)
    for measurement_pile in measurement_piles.values():
        # find result sets that show up more than once.
        if len(measurement_pile) > 1:
            ambiguous_piles.append((breakdown,measurement_pile))

print("Ambiguous Piles Built.")

# check more obvious ambiguous piles first.
ambiguous_piles.sort(key=lambda k: (len(k[0]), k)) 

for reference_weight in range(1,25): # I know that anything over 24 can't tell the difference between all 1s and all 2s.
    # now, let's do the same thing and add a reference weight in on one side of the scale.
    for breakdown, mass_piles in ambiguous_piles:
        measurement_piles = defaultdict(list)
        balance_counts = [list(range(-k, k+1)) for k in breakdown]
        for mass_pile in mass_piles:
            val = 0
            for power,balance_placement in enumerate(product(*balance_counts)):
                val += 3**power * sgn(reference_weight + sum(bp*m for bp, m in zip(balance_placement, mass_pile)))
            measurement_piles[val].append(mass_pile)
        # this is a bit of a workaround for only having single level break.
        # first I check whether anything meets the failure criteria - whether there's still an ambiguous pile
        if any(len(v) > 1 for v in measurement_piles.values()):
            #then if so I'll find that ambiguous pile and report it.
            for measurement_pile in measurement_piles.values():

                if len(measurement_pile) > 1:
                    print(reference_weight, breakdown, measurement_pile)
                    break
            break
    else: # getting here means we didn't break in the loop, so we've won.
        print(str(reference_weight) + " is a usable reference weight.")

# print(ambiguous_piles)