# Find integer sequence of canonical de Bruijn sequences  D Billings  Oct 2009
# 
# substrings of length k yield a cyclical string of length 2^k
# e.g. context length k = 2, unique solution is 0011 = 0110 = 1001 = 1100
# e.g. for k = 3, '00010111' = 23 and '00011101' = 29 are de Bruijn 3
# 0000100110101111 = 2479 is de Bruijn 4 (16 distinct bit strings in total)

numterms = 9

hex2bin = {'0':'0000','1':'0001','2':'0010','3':'0011','4':'0100','5':'0101',
           '6':'0110','7':'0111','8':'1000','9':'1001','a':'1010','b':'1011',
           'c':'1100','d':'1101','e':'1110','f':'1111'}

def dec2bits(number,bits):
    """Convert an integer to a padded bit string of given length"""
    bitstr = ''.join([hex2bin[i] for i in '%x' % number]).lstrip('0')
    bitstr = '0' * (bits - len(bitstr)) + bitstr
    return bitstr

def build_counters():
    """Construct substring count tables"""
    global count
    count = [{} for x in range(numterms+1)]
    for k in range(numterms+1):
        for i in range(2**k):
            bstr = dec2bits(i,k)
            count[k][bstr] = 0
    return

def testdb(k,bitstr):
    """Test if the given bit string is de Bruijn with substring length k"""
    global count
    for key in count[k]:
        count[k][key] = 0
    isdb = True
    teststr = bitstr + bitstr[:k-1]
    for i in range(len(bitstr)):
        count[k][teststr[i:i+k]] += 1
        if (count[k][teststr[i:i+k]] > 1):
            isdb = False
            break
    if isdb:
        for key in count[k]:
            if (count[k][key] != 1):
                isdb = False
                print 'testdb: verify failed on second pass:', key
                break
    return isdb

def flipbitstr(bitstr):
    """Return complement bitstring and its integer value"""
    flipstr = bitstr.replace('0','z').replace('1','0').replace('z','1')
    value = int(flipstr,2)
    return flipstr, value

def db_all(k,soln,rem):
    """Find all de Bruijn sequences by recursive descent"""
    global bcount, solutions
    bcount += 1
    # base case
    if (rem == []):
        solution = ''.join(soln[:-(k-1)])
        solutions.append(solution)
    # recursive case (fails silently if it runs out of candidates)
    for i in range(len(rem)):
        if (soln[-(k-1):] == rem[i][:(k-1)]):
            db_all(k, soln+[rem[i][-1]], rem[:i]+rem[i+1:])
    return

def db(k,soln,rem):
    """Find the first de Bruijn sequence by recursive descent"""
    global bcount, solutions
    bcount += 1
    # base case
    if (rem == []):
        solution = ''.join(soln[:-(k-1)])
        solutions.append(solution)
        return 1
    # recursive case (fails silently if it runs out of candidates)
    done = 0
    for i in range(len(rem)):
        if (not(done) and (soln[-(k-1):] == rem[i][:(k-1)])):
            done = db(k, soln+[rem[i][-1]], rem[:i]+rem[i+1:])
    return done

def dbk(k,all):
    global bcount, count, solutions
    bcount = 0
    solutions = []
    sstrs = count[k].keys()
    sstrs.sort()
    prefix = list(sstrs[0] + '1')
    sstrs = sstrs[2:]
    rem = []
    for i in sstrs:
        rem.append(list(i))
    rem.sort()
    if (k == 1):
        solutions = ['01']
    elif all:
        db_all(k,prefix,rem)
    else:
        db(k,prefix,rem)
    print 'made', bcount, 'calls to db()\n'
    first = solutions[0]
    compl = first[:]
    compl = compl.replace('0','z').replace('1','0').replace('z','1')
    if testdb(k,first):
        print first, '=\n', int(first,2), 'is de Bruijn', k
        print
        print compl, '=\n', int(compl,2), 'is de Bruijn', k
        print
    # print '\n %d solutions =' % len(solutions)
    # print solutions
    return

build_counters()
for i in range(1,numterms+1):
    dbk(i,0)