[Tutor] How to solve it ...
Gregor Lingl
glingl@aon.at
Tue Feb 18 10:19:01 2003
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