[puzzle]

[Anton Vredegoor]

"Terry Reedy" <tjreedy at udel.edu> wrote:

>I don't know what 'Glen Wheeler's problem' is, what your 'antonian' numbers
>are, what 'ISTMT' abbreviates, nor precisely what 'sorted reflected' means
>to your without an example, so I won't try to solve your puzzle.  I will
>just comment on the class definition.

a) Glen Wheeler's problem:

see a recent thread here on c.l.py with subject:

"How to use a 5 or 6 bit integer in Python?"

b) antonian numbers (base 10 example,last column):

 0 <=>  0
 1 <=>  1
 2 <=>  2
 3 <=>  3
 4 <=>  4
 5 <=>  5
 6 <=>  6
 7 <=>  7
 8 <=>  8
 9 <=>  9
10 <=> 00
11 <=> 01
12 <=> 02
13 <=> 03
14 <=> 04
15 <=> 05
16 <=> 06
17 <=> 07
18 <=> 08
19 <=> 09

c) ISTMT: ISTM *that* 

d) "sorted reflected" an analogy to the binary reflected gray code
sequence, in this case a permutation of a set of integers which
corresponds to a lexicographic ordering of a list of lists containing
the digits of antonian numbers.

>> 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()
>
>The generation will go faster if you delete the above three line and change
>'gen' to 'iter' in the next.

Yes, but speed is not important in this stage. Keeping open options
is. This way it would be possible to replace the generator with
another. Maybe your solution works for that too. Anyway, I just cut
and pasted something I saw in a post by Michele Simionato and hacked
it into something simpler, perhaps without really understanding what
the original purpose of the code was. Welcome to postmodernism.

>
>>     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[:]
>
>Making __iter__ itself a generator function (which returns an iterator, as
>__iter__ should) is the smoothest way to use generators with classes.
>Wrapping genit.next with a regular function undoes perhaps half the speed
>benefit of generators.  They are fast partly because they do not have to
>stash and retrieve local in the instance and partly because they resume
>without the normal (slow) function call process.  Writing __iter__ as
>generator also make the instance reiterable.

Yes, I see that now. Thanks for explaining.

>
>In this case, I do not see any reason to wrap the generator in a class
>instead of calling it directly, but perhaps you have a usage in mind where
>persisting the instance after the generator run makes sense.

The main reason to use a class was that it makes it possible to access
self.state from outside the object, for example to prune states with
an illegal predecessor. Here's a script I wrote some time ago, it does
about the same as Bengts script in the Wheeler thread.

It's about trying to count all possible paths a fly can take along the
edges of a hyperdimensional cube where all corner points should be
visited only once (not necessarily ending in a position adjacent to
the starting corner):

class Treecount:
    
    def __init__(self,limits):
        self.limits = limits
        self.state = []
        self.iterator = self.__gen__()
        self.pruned = False

    def __iter__(self):  return self
    def next(self):  return self.iterator.next()    
    def prune(self):  self.pruned = True        

    def __gen__(self):
        state, limits = self.state, self.limits
        while 1:
            if len(state) < len(limits) and not self.pruned:
                state.append(0)
            else:                     
                i = len(state)-1
                while i > 0 and state[i] == limits[i]:
                    state.pop()
                    i -= 1        
                if state[i] < limits[i]:
                    state[i] += 1
                else:
                    raise StopIteration
            self.pruned = False
            yield state[:]
                
def jumps(n):
    nc = 2**n
    res = []
    for i in range(nc):
        neighbours = []
        for j in range(n):
            v = i ^ (1<<j)
            neighbours.append(v)
        res.append(neighbours)
    res.append(range(nc))
    return res

def check(J,L):
    it = iter(L)
    x = J[-1][it.next()]
    seen = {x:True}
    for i in it:
        y = J[x][i]
        if y in seen:
            return False
        else:
            seen[y]=True
            x=y
    return True

def test():
    n = 3
    nc = 2**n
    J = jumps(n)
    for jump in J:  print jump
    limits = [nc-1]+[n-1 for i in range(nc-1)]
    print
    print limits
    print
    T = Treecount(limits)
    cnt = 0
    for x in T:
        if not check(J,x):  T.prune()
        elif len(x) == nc:
            cnt+=1
            print cnt, x
    print
    print cnt

if __name__=='__main__':
    test()

This probably does the same as Bengts script, but slower. The
advantage was supposed to be that it is not recursive and so it would
be more amenable to splitting it up among a cluster of computers.
Remember that Glen was aiming at N=5 or N=6. It would be possible to
assign a starting and ending tuple to a computer and let it search for
the corresponding hamilton paths within the sequence.

Some time later I noticed that the generated tuples where identical to
the set of tuples antonian numbers use as digits, only permutated.
After seeing that it would be even easier to distribute integer ranges
instead of starting and ending tuples I set myself the task of
generating antonian digit tuples in a permutated order.

I noticed that in order to do that it was necessary to set limits to
the range of generated tuples or else the "sorted" sequence would just
generate longer and longer lists of zero's like this:

[0]
[0,0]
[0,0,0]
[0,0,0,0]
...

Obviously you haven't got the time nor the inclination to follow me in
my weird explorations and are also handicapped by my suboptimal
linguistic skills and idiosyncratic terminologies. So let me just
explain my general predisposition to this newsgroup as a source of
interesting programming problems and mathematical, linguistical and
philosophical diversions. That may be a bit different from the general
use as a forum for answering user questions. However, being an amateur
combinatorics enthousiast and hobby programmer this is the way I see
Python: as a tool to explore these kind of subjects, and appropriate
or not c.l.py is just the right kind of inspiration for me, not too
abstract and theoretical as for example mathematics newsgroups and at
the same time full of interesting -and more importantly: framed in an
executable pseudocode language- new concepts.

It being a shame that hobbyprogrammers are not recognized for their
programming skills -if static typing chauvinists are all you are
worried about, consider yourself lucky- so that it is hard to get a
programming job, the next best thing -or even the better thing if you
can afford it- is to program in Python in an unbounded and free
exploratory fashion, inspired by the people that so generously donate
their ideas to this newsgroup, hoping to get solutions to problems or
presenting them just as ideas to be shared and enjoyed.

The nice thing about posting it here is that even if nobody
understands what I'm rambling about now, someone else possibly will,
maybe even years and years later, if it is intelligible at all of
course. Another nice thing is that as soon as one hits the send button
the errors immediately appear and disturb one's sleep. This however is
a bit more of an ambiguous advantage. If my posts have reached the
level of unintelligibility of the Ruebot please inform me that I'm
sending spam and if this is backed up by other posters I will find
another place to exhibit my products. At least the code runs, ISTM.

Anton