[puzzle]

Discussion in 'Python' started by Anton Vredegoor, Dec 29, 2003.

  1. 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 == limits-1:
    state.pop()
    i -= 1
    if state < limits-1:
    state += 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()
     
    Anton Vredegoor, Dec 29, 2003
    #1
    1. Advertising

  2. Anton Vredegoor

    Terry Reedy Guest

    "Anton Vredegoor" <> wrote in message
    news:3fef8612$0$117$...
    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.

    > 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.

    > 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 == limits-1:
    > state.pop()
    > i -= 1
    > if state < limits-1:
    > state += 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.

    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
     
    Terry Reedy, Dec 29, 2003
    #2
    1. Advertising

  3. "Terry Reedy" <> 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 == limits-1:
    >> state.pop()
    >> i -= 1
    >> if state < limits-1:
    >> state += 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 == limits:
    state.pop()
    i -= 1
    if state < limits:
    state += 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]
    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
     
    Anton Vredegoor, Dec 29, 2003
    #3
  4. On Mon, 29 Dec 2003 23:44:07 +0100, (Anton Vredegoor) wrote:

    >"Terry Reedy" <> 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.

    >

    [... discussion, code to look at later ;-) ...]

    >
    >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.

    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 ;-)

    [...]
    >
    >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.
    >


    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
     
    Bengt Richter, Dec 30, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Earl Teigrob
    Replies:
    3
    Views:
    6,670
    Nedu N
    Aug 6, 2003
  2. dwa

    Design Puzzle!

    dwa, Jun 10, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    380
    Cowboy \(Gregory A. Beamer\) [MVP]
    Jun 10, 2004
  3. Shankara Narayanan

    Booking puzzle....

    Shankara Narayanan, Jun 17, 2004, in forum: ASP .Net
    Replies:
    20
    Views:
    945
    bredal Jensen
    Jun 30, 2004
  4. VB Programmer
    Replies:
    2
    Views:
    434
    Alan Lambert
    Nov 4, 2004
  5. G. Stewart

    regex puzzle!

    G. Stewart, Nov 23, 2004, in forum: ASP .Net
    Replies:
    8
    Views:
    526
    G. Stewart
    Nov 25, 2004
Loading...

Share This Page