[Tutor] How to solve it ...

[Tim Peters]

[Gregor Lingl]
> 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!

Me too -- it was fun.  I think it may be too hard for a beginner, though --
hard to visualize and hard to motivate.  Puzzles about how to get a fox and
some chickens across a river in a small boat are more like it.

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

It takes years of practice to make easy things look easy <0.9 wink>.

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

Thank you, but it was just the elegance of unembellished brute force <0.5
wink>.

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

You did at least one smart thing I didn't do:  you represented the basic
codes by single characters, where I used pairs.  The instances of "-2" and
"2" in my program were inelegant.

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

Sure.

> ...
> P.S:  As far as I see, the line
>
>> states = range(2, 15)
>
> in your code should read:
>
>     states = range(1, 15)

Ack, yes.  I was playing with it and forgot to revert that change.  Because
of the symmetry arguments I mentioned in the first reply, it's actually
enough to leave this line at

states = 1, 3, 9

but not enough to use (just) any two of those.  It runs so fast, though,
that I don't notice the difference in runtime between (1, 3, 9) and range(1,
15).

Easy exercise (if you've done it before <wink>):  change any of these
programs to generate all solutions, in increasing order of length.  Doing it
with Python's generators (the "yield" statement) is very easy.

Hard:  any sequence of codes takes a state to a set of states.  Do that 14
times (once for each initial state), and the effect of a sequence of codes
can be completely described by a tuple with 14 elements, where the first
element is a tuple giving the states that state #1 maps to, and so on.

Now you can use strings of codes, and tuples, as dict keys, so you can
maintain dictionaries mapping code strings to their effects, and vice versa.

Then you can write a driver that generates all possible sequences of codes
in increasing order of length, but able to recognize (by using the dicts
above) when a sequence has exactly the same effect as some sequence you've
already seen.  There's no point looking further at such redundant sequences
(or at any sequences starting with a redundant sequence).

When adding a new code at the end of a sequence, you can also look up the
effect of the first N-1 codes, and just do the work needed to figure out
what the single new code does beyond that.

This leads to an extremely efficient program that not only finds "the
answer", but also finds all distinct solutions regardless of length.  If you
don't screw it up <wink -- but this involves some intricate programming, and
isn't easy>, you'll find that there are surprisingly few distinct sequences
of codes (where "distinct" means they have a different effect on at least
one initial state).

Another harder problem:  the original asked for the shortest sequence of
codes guaranteed to solve every initial state.  Assuming that each initial
state is equally likely, what's the shortest sequence of codes that
minimizes the *average* number of codes executed before the lock opens?  A
mathematical logician in a hurry may well prefer that answer <wink>.