[puzzle]

Anton Vredegoor anton at vredegoor.doge.nl
Mon Dec 29 02:35:30 CET 2003


While trying to solve Glen Wheelers problem I discovered an
interesting puzzle. I'm going away for a day or so and it would be
nice to have it solved when I'm back.

It's about a different way to generate the so-called antonian numbers
(still trying to find a better name) but now in lexicographically
sorted order. I have found a generator for them but as yet I have no
way to directly compute "sorted reflected" integers from a normal
integer sequence. I hope my code is more clear than my question ...

One hint, ISTMT in order to get at a "sorted reflected" integer
sequence there has to be a fixed maximum number, while the antonian
digits function is infinite. Anyway, it's much too late and I had too
much coffee, so maybe it's trivial ...

Anton  

class AntonianSorted:
    
    def __init__(self, n, k):
        self.limits = [k for i in range(n)]
        self.state = []
        self.iterator = self.__gen__()

    def __iter__(self):  return self
    def next(self):  return self.iterator.next()    

    def __gen__(self):
        state, limits = self.state, self.limits
        while 1:
            if len(state) < len(limits):
                state.append(0)
            else:                     
                i = len(state)-1
                while i > 0 and state[i] == limits[i]-1:
                    state.pop()
                    i -= 1        
                if state[i] < limits[i]-1:
                    state[i] += 1
                else:
                    raise StopIteration
            yield state[:]
                
def antonianvalue(seq, base):
    return reduce(lambda x,y: x*base+y+1,seq,0)-1
 
def antoniandigits(val, base):
    res = []
    while val > -1:  
        res.append(val % base)
        val = val/base-1
    res.reverse()
    return res

def product(L):   return reduce(lambda x,y: x*y,L,1)

def xproduct(n,k):
    res = 0
    for i in range(1,n+1):
        res += product([k]*i)
    return res

def test():
    ndigits, base = 3,3
    A = AntonianSorted(ndigits,base)
 
    for i,x in enumerate(A):
        a = antonianvalue(x, base)
        d = antoniandigits(i, base)
        print "%2i <==> %2i        %9s <==> %9s" %(i,a,x,d)
    print
    
    for i in xrange(xproduct(ndigits,base)):
        print "%2i <==> ??" %(i)
        
if __name__=='__main__':
    test()





More information about the Python-list mailing list