#!/usr/bin/python

def HD( cw1, cw2 ):
    """Returns the Hamming Distance between two codewords"""

    # do the appropriate padding so they are the same length.
    maxlength = max( len(cw1), len(cw2) )   
    cw1, cw2 = cw1.rjust( maxlength, '0' ), cw2.rjust( maxlength, '0' )

    assert len(cw1) == len(cw2), "ERROR in HD(): Codewords not same length!"

    distance = 0
    for i in range(maxlength):
        # distance gets incremented by 1 if cw1 and cw2 don't have the same position.
        if int(cw1[i] != cw2[i]):
            distance += 1

    return distance

def base10tobaseN(num,n,padding=0):
    """Converts a decimal number -> digit in base-N.  Add padding on the left if you want to do that. """

    # return a baseN of the same length as the base10
    if len(str(num)) > padding:
        padding = len(str(num))

    baseN = ''
    
    current=int(num)
    while current!=0:
        remainder=current%n
        if remainder>9:
            remainder_string='('+str(remainder)+')'
        else:
            remainder_string=str(remainder)
            baseN=remainder_string+baseN
            current=current/n

    if padding: baseN = baseN.rjust( padding, '0')
        
    return baseN


def baseN2graycode2( Nary, n ):
    """convert a base-N digit to the graycode.
    
        Nary = A digit in base-N
        n = the base of the Nary digit
    """
    # if the Nary digit is padded by 0s on the right, we will add those zeros back at the end.
    padding = len(Nary)

    # remove all padding from the Nary digit.
    Nary = Nary.lstrip('0')

    # if Nary was all zeros, it will be blank now.
    if Nary == '':
        Nary = '0'

    # graycode starts a blank list.
    graycode = []
    
    ########################################################################################################
    ###### MAIN ALGORITHM IS HERE #############
    ########################################################################################################

    # The first digit of the graycode is ALWAYS the first digit of the Nary-digit
    graycode.append( Nary[0] )

    # To generate the rest of the graycode, we enumerate from left to right over the rest of the N-ary digit...
    # index 'i' goes from 1...len(Nary)-1
    for i in range(1,len(Nary)):

        # a is the value of Nary IMMEDIATELY BEFORE index i
        a = int(Nary[i-1])
        # b is the value of Nary at index i
        b = int(Nary[i])
        
        if b > a:
            graycode_value_at_this_index = b-a
        elif b < a:
            graycode_value_at_this_index = (n+b)-a
        # occurs when b == a
        else:
            graycode_value_at_this_index = 0
        
        # append this value to the graycode
        graycode.append( graycode_value_at_this_index )
    ########################################################################################################
    
    # convert graycode from a list to a string
    graycode = ''.join(map(str,graycode))

    # add any padding back
    if padding:
        graycode = graycode.rjust( padding, '0')
        
    return graycode
    

n, padding = 3, 5
start, end = 0, 100

previousgraycode, previousbaseN = '0', '0'
print "converting digits %s-%s to base %s, padding=%s" % (start, end, n, padding)
print "----------------------------------------------------"
for dec in range(start,end):
    baseN = base10tobaseN(dec, n, padding)
    graycode = baseN2graycode2(baseN, n)

    baseNdistance = HD( previousbaseN, baseN)
    graydistance = HD( previousgraycode, graycode)

    
    previousbaseN, previousgraycode = baseN, graycode
    print "%s \t-> base%s=%s \t-> base%s_graycode=%s \t dist=%s \t graydist=%s" % (dec, n, baseN, n, graycode, baseNdistance, graydistance)