[puzzle]

[Anton Vredegoor]

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 lexicographical ly
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.n ext()

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(s eq, 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__=='__ma in__':
test()

[Terry Reedy]

Re: [puzzle]


"Anton Vredegoor" <anton@vredegoo r.doge.nl> wrote in message
news:3fef8612$0 $117$3a628fcd@r eader2.nntp.hcc net.nl...
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.
[color=blue]
> 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.n ext()[/color]

The generation will go faster if you delete the above three line and change
'gen' to 'iter' in the next.
[color=blue]
> 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[:][/color]

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.

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.

Terry J. Reedy

[Anton Vredegoor]

Re: [puzzle]

"Terry Reedy" <tjreedy@udel.e du> wrote:
[color=blue]
>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.[/color]

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.
[color=blue][color=green]
>> 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.n ext()[/color]
>
>The generation will go faster if you delete the above three line and change
>'gen' to 'iter' in the next.[/color]

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.
[color=blue]
>[color=green]
>> 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[:][/color]
>
>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.[/color]

Yes, I see that now. Thanks for explaining.
[color=blue]
>
>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.[/color]

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 hyperdimensiona l 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,l imits):
self.limits = limits
self.state = []
self.iterator = self.__gen__()
self.pruned = False

def __iter__(self): return self
def next(self): return self.iterator.n ext()
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.appe nd(v)
res.append(neig hbours)
res.append(rang e(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(limit s)
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__=='__ma in__':
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 hobbyprogrammer s 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 unintelligibili ty 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

[Bengt Richter]

Re: [puzzle]

On Mon, 29 Dec 2003 23:44:07 +0100, anton@vredegoor .doge.nl (Anton Vredegoor) wrote:
[color=blue]
>"Terry Reedy" <tjreedy@udel.e du> wrote:
>[color=green]
>>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.[/color]
>[/color]
[... discussion, code to look at later ;-) ...]
[color=blue]
>
>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.[/color]
After Glen posted
"""
G(1) = 2
G(2) = 8 (as you show below)
G(3) = 144
G(4) = 91 392
G(5) = 187 499 658 240 (I can calculate this in under 8 hours)
G(6) = ?? (but it's around 10^24)
"""
I gave up on brute force counting ;-)
I did/do-n't have time to pursue it, but I was toying with recursively
breaking it down into combinations of subspace paths and inter-connections,
but I got lost in space ;-) Anyway, I wonder if there could be a closed form
formula for G(n), and if the formula could be computed somehow, manipulating terms,
etc., and then evaluated. Just a fantasy ;-)

[...][color=blue]
>
>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
>philosophica l diversions. That may be a bit different from the general
>use as a forum for answering user questions. However, being an amateur
>combinatoric s 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 hobbyprogrammer s 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 unintelligibili ty 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.
>[/color]

FWIW, I enjoy your posts, even when I don't fully understand. I think
it's worth while to have seen an alternate approach to a problem, even
if not fully understood or explored. It can help contribute
to an aha moment later when exploring similar territory.

Happy New Year, Anton, don't go away ;-)

Regards,
Bengt Richter