[Tutor] How to solve it ...

[Tim Peters]

[Gregor Lingl]
> Hi Pythonistas, now for something completely different ...
>
> The following problem is taken from "Spektrum der Wissenschaft", Feb.
> 2003 (which is the German edition of Scientific American):
>
> Coded entry
>
> To cut costs for a doorguard who asks silly mathematical riddles,
> the union of mathematical logicians has devised a sophisticated locking
> apparatus for their union's home.
> The lock of the door is controlled by four simple switches, which are
> arranged in a square. The door opens if all the switches are "on"
> or if all of them are "off". When a member arrives to enter, the door
> always is locked, which means that some switches are in the on position
> and some are off.
> No one who wants to enter can see the switches or touch them directly.
> Instead, there are four buttons on the door, labelled "P", "D",
> "1" and "2".
> If you press "P", a pair of two switches in a horizontal or
> vertical row is randomly selected. If you press "D" a pair of diagonally
> arranged switches is randomly selected.
> After this selection has taken place, pushing button "1" randomly
> selects one of the previously selected switches and changes its
> position.
> Contrary to that, pushing "2" switches both of them. The sequence
> "letter, digit" may be repeated until the door opens (or you lose
> patience).
> Find the shortest complete code which opens the door with certainty,
> regardless of the original position of the four switches.
>
> How would you solve this with Python (- just for your amusement)?

How would you solve it without Python, i.e. "by hand"?  Answer that, and
then you can use Python to automate the tedious parts.

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".  There's no guarantee in advance
that this will finish in a reasonable amount of time, and indeed there's no
guarantee in advance that a solution even exists.  Luckily for this most
brutish of brute-force approaches, a solution to this problem is found in
reasonable time.

Refinements of the brute force approach can find all possible non-isomorphic
solutions (and regardless of length) in a few seconds.  These require
thinking about the problem, to limit the amount of brute-force work
required.  For example, D1 and P1 both pick one switch at random and flip
it, so you can pretend that one of them doesn't exist (they have exactly the
same effect).  This cuts the number of sequences of length N from 4**N to
3**N, and that's a huge savings in the space that needs to be searched.

Symmetry arguments can also cut the amount of work, by a constant factor.
For example, a little thought should convince you that if you have a
sequence S that solves the case where only the upper left switch is on at
the start, then S must also solve the other 3 initial states with only one
switch on at the start.  Deeper thought will go on to convince you that if S
solves initial states with only 1 switch on, S must also solve all initial
states with only 1 switch off (because "all on" and "all off" are both
winning states, and the operations (D1 etc) don't know the difference
between "on" and "off").  Similarly, if S solves the initial state where
just the top 2 switches are on, it must also solve all initial states where
just the 2 switches in a row or column are on.  The only initial states
remaining then are the two where just the switches on a diagonal are on, and
again by symmetry those two states are equivalent.  So you don't really have
to check that all 14 initial states are solved, there are just 3 initial
states that aren't equivalent under rotations, reflections, and exchanging
the meanings of "on" and "off".

Another thing to note is that if you find a sequence T that has the same
effect on all initial states as a shorter sequence S, there's no point
looking at any sequence U beginning with T:  U could be changed to an
equivalent but shorter sequence by replacing its start with S.  You can find
such equivalent pairs by thinking, but it's easier to write a program to
find them.  For example, the sequence P2P2P2 has the same effect on all
initial states as P2 by itself, so there's no point looking at any sequence
starting with P2P2P2.

A different approach is to start at the other end, looking at the final
states (all off and all on), and working backward to deduce how you could
get there.

A third approach is to burn the candle at both ends, moving forward from the
initial states and backward from the final states, a bit of each at a time,
until they meet in the middle.  This can get pretty complicated, though!

One thing all approaches need is a good way to represent the possible
states.  For example, assign a different power of 2 to each switch location:

   1 2
   4 8

Then the integers in 0 through 15 represent all 16 possible switch states,
where, for example, 9=1+8 represents the state where the just the switches
on the main diagonal are on, and 15 represents the state where all switches
are on.  This is particularly convenient because "flipping a swtich"
corresponds to doing an exclusive-or of the integer representing the state
with the power of 2 representing the switch to be flipped.  For example, the
effect of D2 is to xor the state with 1+8=9 or with 2+4=6.  So the possible
effects of D2 on the state 3 (= 1+2 = top two switches on) are

>>> 3 ^ 9
10          # = 2+8 = right column of switches on
>>> 3 ^ 6
5           # = 1+4 = left column of switches on
>>>

Putting this all together in a program isn't an easy task -- unless you've
done things "like it" a dozen times before.