#!/usr/bin/python

# Solution to the 'find the odd ball from among N' weighing problem for
# any W
#            where N = (3**W-3) / 2
# (eg for N=12 balls (W=3) or 39 balls (W=4) or 120 balls (W=5))
#
# This is John Conway's solution, from p.87 of
# MacKay (2003) 'Information Theory, Inference, and Learning Algorithms'
# http://www.inference.phy.cam.ac.uk/mackay/itila/

# Program by David J.C. MacKay
# Thanks to Hisham Anwer Saleh Mohamed for inspiration

def balls(W):
    """
    Make a list of all the ball names of length W.
    Conway's Rule for the ball names:
    all non-constant strings of length W that have first change
    AB..    or BC..      or CA..
    >>> balls(3)
    ['AAB', 'ABA', 'ABB', 'ABC', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC', 'CCA']

    These balls are named 0,1,2,3,... during user-interaction.
    """
    a = [] ## first create ALL 3**W strings by recursion
    all_strings(W,a,"")
    d = [] ## then transfer the ones we desire to d
    for b in a:
        i = firstchange(b)
        if i == 'AB' or i == 'BC' or i == 'CA':
            d.append( b )
    return d

def firstchange(b):
    """
    return the first change in the string b
    >>> firstchange('ABB')
    'AB'
    >>> firstchange('AAC')
    'AC'
    """
    for i in range(len(b)) :
        if i == len(b)-1 :
            return 0
        elif b[i] != b[i+1] :
            return b[i]+b[i+1]

def all_strings(W,a,b):
    """
    (W=length remaining, a=list so far, b=the stub made so far)

    Recursively generates all strings

    >>> a=[]
    >>> all_strings(1,a,"")
    >>> print a
    ['A', 'B', 'C']
    >>> a=[]
    >>> all_strings(1,a,"head")
    >>> print a
    ['headA', 'headB', 'headC']
    >>> a=[]
    >>> all_strings(2,a,"")
    >>> print a
    ['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC']
    """
    if (W==0) :
        a.append(b)
    else:
        for n in ['A','B','C'] :
            all_strings(W-1,a,b+n)
        

def play(W):
    d = balls(W)
    print "There are ",len(d),"balls (labelled 0, 1, ..",len(d)-1,")"
    print "Decide which is odd, and whether it is heavy or light; "
    print "then tell me the outcomes of the",W,"weighings that follow"
    print "and I will identify the odd ball and whether it's H or L."
    wholeans = '' ; otherans = ''
    for r in range(W):
        print "On the Left pan:" # (which Conway calls Pan A)
        for b in d:
            if b[r] == 'A' : print d.index(b) ,
        print ""
        print "On the Right pan:"
        for b in d:
            if b[r] == 'B' : print d.index(b) ,
        print ""

        ans = raw_input('A (left up, right down) / B (left down, right up) / C (balance)?\n')
        wholeans = wholeans + ans.upper()
        if ans.upper() == 'A':
            otherans = otherans + 'B'
        elif ans.upper() == 'B':
            otherans = otherans + 'A'
        else:
            otherans = otherans + 'C'
    print wholeans
    if wholeans in d:
        print d.index(wholeans) , "is LIGHT"
    elif otherans in d:
        print d.index(otherans) , "is HEAVY"
    else:
        print "Something is wrong!"
    print "----------------------------------------------------------"


if __name__ == '__main__':
    import doctest
    verbose=1
    if(verbose):
        doctest.testmod(None,None,None,True)
    else:
        doctest.testmod()

play(3)
play(4)
play(5)