[Tutor] How to solve it ...
Gregor Lingl
glingl@aon.at
Sun Feb 16 15:12:02 2003
This is a multi-part message in MIME format.
--------------020800090302020309090203
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
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)?
I append a quick script which simulates the behaviour of this lock - if you
consider it helpful for grasping the problem to have something like this
at hand.
Gregor
--------------020800090302020309090203
Content-Type: text/plain;
name="lock.py"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="lock.py"
"""Simulation to explore the behaviour of the lock
from the following problem (taken from Spektrum der Wissenschaft 2/2003):
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.
Author: Gregor Lingl, glingl@aon.at
Date: 16. 2. 2003
Filename: lock.py
"""
from Tkinter import Button, Canvas, Frame, Label, Tk
from Tkconstants import *
from random import randrange,choice
import sys
class Lock(Canvas):
"""Implement graphical representation of 4-switch-lock along with
(1) methods to change its state
(2) memory to store sequence of operations
(3) method to repeat the operations of the stored sequence"""
def __init__(self,root,**args):
"""Create graphical elements"""
Canvas.__init__(self,root, **args)
# self.switches = [0,0,0,0]
self.memory = ""
self.replay = 0
self.squares=[self.create_rectangle( 45, 45,175,175, width=15),
self.create_rectangle(225, 45,355,175, width=15),
self.create_rectangle( 45,225,175,355, width=15),
self.create_rectangle(225,225,355,355, width=15)]
self.txt = self.create_text( 200, 200, font=("Courier",16,"bold"),
anchor=CENTER, fill="white", text="")
self.reset()
def reset(self):
"""Reset lock to a random closed state"""
self.selected = ()
self.switched = ()
self.settext("")
self.switches = [randrange(2), randrange(2), randrange(2), randrange(2)]
while self.isopen():
self.switches[randrange(4)] = randrange(2)
self.update()
def update(self):
"""Update graphical representation according to state of switches
and current selection or recent changes as well as state of the lock"""
for i in range(4):
sq = self.squares[i]
if self.switches[i]:
self.itemconfig(sq,fill = "yellow")
else:
self.itemconfig(sq,fill = "blue")
if i in self.selected:
self.itemconfig(sq, outline = "gray")
elif i in self.switched:
self.itemconfig(sq, outline = "white")
else:
self.itemconfig(sq, outline = "black")
if self.isopen():
self["background"] = "green"
else:
self["background"] = "red"
Canvas.update(self)
if self.replay: self.after(1500)
def select(self, switches):
"""Mark a pair of *switches* as selected"""
self.selected = switches
self.switched = ()
self.update()
def switch(self, count):
"""Perform switching of *count* switches of the current selection"""
if count == 1:
self.switched = (choice(self.selected),)
else:
self.switched = self.selected
for switch in self.switched:
self.switches[switch] = not self.switches[switch]
self.selected = ()
self.update()
def isopen(self):
"""Return state of the lock"""
return self.switches in [ [0,0,0,0], [1,1,1,1] ]
def settext(self, txt, append = 0):
"""Helper method: display actions in replay-mode"""
tx = self.itemcget(self.txt,"text")
if append:
self.itemconfig(self.txt, text = tx + txt)
else:
self.itemconfig(self.txt, text = txt)
def p(self):
"""Select a pair of switches in a row or a column"""
self.select(choice([(0,1),(2,3),(0,2),(1,3)]))
if not self.replay: self.memory += "P"
def d(self):
"""Select a pair of switches arranged diagonally"""
self.select(choice([(0,3),(1,2)]))
if not self.replay: self.memory += "D"
def s1(self):
"""Switch randomly one of the selected switches"""
self.switch(1)
if not self.replay: self.memory += "1"
def s2(self):
"""Switch both of the selected switches"""
self.switch(2)
if not self.replay: self.memory += "2"
def clear(self):
"""Clear the lock's memory for operations"""
self.memory=""
self.settext("")
def play(self):
"""Replay operations stored in the lock's memory"""
action = {"P":self.p, "D":self.d, "1":self.s1, "2":self.s2}
APPEND = 1
self.replay = 1
self.settext("")
for t in self.memory:
self.settext(t, APPEND)
action[t]()
if self.isopen():
break
if not self.isopen():
self.settext("")
self.replay = 0
def activate(buttons):
"""Helper function: activate exactly *buttons*"""
for button in [pairButton, diagButton, oneButton, twoButton,
clearButton, playButton]:
if button in buttons:
button["state"] = ACTIVE
else:
button["state"] = DISABLED
def updateGUI(buttons):
"""Update GUI in direct (i.e. non-replay-) mode by acticating *buttons*"""
if not lock.replay:
commandSequence["text"] = lock.memory
activate(buttons)
def p():
"""Eventhandler for pair-button"""
lock.p()
updateGUI([oneButton,twoButton])
def d():
"""Eventhandler for diagonal-button"""
lock.d()
updateGUI([oneButton,twoButton])
def s1():
"""Eventhandler for one-button"""
lock.s1()
updateGUI([pairButton,diagButton, clearButton, playButton])
def s2():
"""Eventhandler for two-button"""
lock.s2()
updateGUI([pairButton,diagButton, clearButton, playButton])
def resetprog():
"""Eventhandler for clear-button: clear the lock's memory"""
lock.clear()
updateGUI([pairButton, diagButton])
def play():
"""Eventhandler for play-button: replay stored sequence od operations"""
activate([])
lock.play()
if lock.isopen():
activate([clearButton])
else:
activate([pairButton,diagButton, clearButton, playButton])
def reset():
"""Eventhandler for reset-button: reset lock to a closed state"""
lock.reset()
commandSequence["text"] = lock.memory
if lock.memory:
activate([pairButton,diagButton, clearButton, playButton])
else:
activate([pairButton,diagButton])
# Assemble GUI:
root = Tk()
lock = Lock(root, width=400, height=400, background="red")
lock.pack()
buttonFont = ("Arial", 10, "bold")
switchFrame = Frame(root)
pairButton = Button(switchFrame, text= "pair", width=10, font = buttonFont, command = p)
diagButton = Button(switchFrame, text= "diagonal", width=10, font = buttonFont, command = d)
oneButton = Button(switchFrame, text= "1", width=10, font = buttonFont, command = s1)
twoButton = Button(switchFrame, text= "2", width=10, font = buttonFont, command = s2)
playFrame = Frame(root)
clearButton = Button(playFrame, text = "clear -->", font = buttonFont, command = resetprog)
commandSequence = Label(playFrame, text = "", bg = "white", fg = "blue",
font=("Courier",10,"bold"), width = 20)
playButton = Button(playFrame, text = "<-- play", font = buttonFont, command=play)
controlFrame = Frame(root)
resetButton = Button(controlFrame,text = "reset", width=20, font = buttonFont, command = reset)
exitButton = Button(controlFrame,text = "exit", width=20, font = buttonFont, command = sys.exit)
controls = [pairButton, diagButton, oneButton, twoButton,
clearButton, commandSequence, playButton,
resetButton, exitButton]
frames = [switchFrame, playFrame, controlFrame]
for control in controls:
control.pack(side=LEFT, fill = X, expand=1)
for frame in frames:
frame.pack(side=TOP, fill = X, expand=1)
reset()
root.mainloop()
--------------020800090302020309090203--