[Tutor] How to solve it ...

[Gregor Lingl]

Tim Peters schrieb:

>[Tim, on Gregor Lingl puzzle]
>
>>...
>>Trying the simplest thing that could possibly work is often a good
>>start: generate all possible sequences composed of {D1, D2, P1, P2}, in
>>increasing order of length, and for each one see whether it solves all
>>initial states.  The first one that does is "the answer".
>>
Hello Tim!

Many thanks for your replies to my "lock-puzzle"-question. The 
explanations of the first one
was just what I hoped to get back from the list - but I must confess I 
was not sure if the
problem was interesting enough, before I posted it. Now I'm glad, that I 
gave it a try!

I had tried to find a solution, and what I arrived at worked, but was 
rather clumsy.

When I read your solution, I was really enthusiastic about it. I 
consider it to be a real
*Python jewel*.

So what you gave to me, was not only an extrordinary lecture in 
programming in general
but also specifically a perfect example of Python programming, exemplary 
in every respect:
clear, concise, perfect style, elegant use of recursion, most efficient 
use of Python
specific features ...

Maybe these words are superfluous, as most of us won't expect anything 
else from you ;-)
Nevertheless I wish to express, that it was most rewarding for me ....


I reworked my solution  a little in the light of your remarks - and I 
also took one or
two ideas from your program - especially the use of a code-dictionary. I 
put this version
below, just for comparison  - although I know very well, that it will 
mainly serve
to demonstrate, that I'm not playing in the same league ...

Would you agree that I put your code along with some of your remarks on 
my Python-website,
of course with the due credits?

Regards, Gregor  

P.S:  As far as I see, the line

>
>
>states = range(2, 15)
>
>
in your code should read:

    states = range(1, 15)

===========================================
# Here my solution - IMO it suffers mainly from the
# ditiction between "opsequences" and "codesequences"
# Aufgabe aus Spektrum der Wissenschaft
# vom Februar 2003

start = range(1,15)
operations = ["D","P","S"]
codes = { "S" : (1,2,4,8),
          "P" : (3,5,10,12),
          "D" : (6,9) }

def cantor(sets, result = [[]]):
    """Cantorian set-product"""
    if sets == []:
        return result
    else:
        return cantor(sets[:-1],[[el]+tupl for el in sets[-1] for tupl 
in result])

def check(state,codeseq):
    "checks, if codeseq opens state"
    for code in codeseq:
       state = state ^ code
       if state in [0,15]:
           return 1
    return 0

def checkfirst(opseq):
    # if this fails, it's not necessary to do the time-consuming 
construction
    # of the cantor-product of all the codeseqs belonging to this opseq,
    codeseq = [codes[op][0] for op in opseq]
    for state in start:
        if not check(state, codeseq):
            return 0
    return 1

def checkall(opseq):
    codeseqs = cantor([codes[op] for op in opseq])
    for state in start:
        for codeseq in codeseqs:
            if not check(state,codeseq):
                return 0
    return 1

depth = 0
done = False
while not done:
    depth += 1
    print "Test sequences with %d elements ..." % depth
    opseqs = cantor([operations]*depth)
    for opseq in opseqs:
        if checkfirst(opseq):
            if checkall(opseq):
                print "Loesung:", "".join(opseq)
                done = True
                break