One Problem -- how to implement in three programming paradigms in Python
Bengt Richter
bokr at oz.net
Tue Jun 17 00:19:29 EDT 2003
On 17 Jun 2003 01:20:20 GMT, bokr at oz.net (Bengt Richter) wrote:
>On Mon, 16 Jun 2003 22:29:12 +0200, "Ludger.Humbert" <Ludger.Humbert at cs.uni-dortmund.de> wrote:
>
>>Steven Taschuk schrieb:
>>> Quoth Ludger.Humbert:
>>> [...]
>>>> http://in.hagen.de/~humbert/vortraege/F.Grundkonzepte_html/22.html
>>>
>>> I'd be happy to throw in my two cents, but I'm afraid I don't know
>>> German. Is there an English translation? (Or could some helpful
>>> bilingual Pythonista provide one?)
>>
>>I'll give it a try (but my english is'nt that good):
>>the above mentioned page should explain the question in itself ..
>>how is it possible to find a way through the maze (labyrinth in german)
>>the picture/image is there to show one possible concrete example.
>>
>>Problem:
>>how to find a way through a given maze.
>>
>Here is one barely-tested go at it:
>
[... snip old version ...]
This is more fun, see result ;-)
====< maze.py >======================================================
#! /usr/bin/python
# Assuming a rectangular board with squares identified by row,col coordinates
# with 1,1 as the upper left square, and 1,2 as the square to the right
# of the first and 2,1 as the square below the first, then we can
# describe the maze by a short string that says how it is possible
# to move from each square that participates in the paths.
# The possibilities are up,down,left,right,and additionally start and finish
# for entry and exit squares. Thus square (1,1):'dr' says that we can
# go down or right from square 1,1. That happens to be the format for
# a python dict literal entry, so we can easily describe the maze with
# a dict.
# the maze at http://in.hagen.de/~humbert/vortraege/F.Grundkonzepte_html/22.html
maze = {
(1,1):'rd', (1,2):'lr', (1,3):'lr', (1,4):'lr', (1,5):'ld', (1,7):'d',
(2,1):'ud', (2,3):'d', (2,5):'urd', (2,6):'l', (2,7):'ud', (2,8):'d',
(3,1):'ud', (3,3):'ur', (3,4):'lr', (3,5):'uld', (3,7):'udr', (3,8):'ul',
(4,1):'udr',(4,2):'lr', (4,3):'ld', (4,4):'d', (4,5):'ur', (4,6):'ldr', (4,7):'lu',
(5,1):'ud', (5,3):'ud', (5,4):'ud', (5,6):'ud',
(6,1):'u', (6,3):'u', (6,4):'ur', (6,5):'lr', (6,6):'lu'
}
class Solution(Exception): pass
class Mazer(object):
# row,col deltas for the moves
moves = {'u':(-1,0),'d':(1,0),'r':(0,1),'l':(0,-1)}
start = (2,8)
finish = (6,1)
def __init__(self, maze):
self.maze = maze
def search(self, here, path='', beenthere={}):
if here in beenthere: return
if here == beenthere['finish']: raise Solution(path)
beenthere[here]=1
for direction in maze[here]:
ud,lr = self.moves[direction]
hrow,hcol = here
self.search((hrow+ud,hcol+lr),path+direction, beenthere)
def solpic(self, maze, start, finish, path):
# make walled squares first
# get maze dimensions (assume top/left justified)
ncols = max([c for r,c in maze.keys()])
nrows = max([r for r,c in maze.keys()])
rowtopbot = '+---'*ncols+'+'
rowcenter = '| '*ncols+'|'
rows = [list(rowtopbot)]
for r in xrange(nrows):
rows.append(list(rowcenter))
rows.append(list(rowtopbot))
for rc,dirs in maze.items():
ixr = 2*rc[0]-1
ixc = 4*rc[1]-2
for dr in dirs:
if dr == 'u': rows[ixr-1][ixc-1:ixc+2] = [' ', ' ', ' ']
elif dr == 'd': rows[ixr+1][ixc-1:ixc+2] = [' ', ' ', ' ']
elif dr == 'l': rows[ixr][ixc-2] = ' '
elif dr == 'r': rows[ixr][ixc+2] = ' '
# do path
def mark(r, c, m, d='c'):
ixr=2*r-1; ixc=4*c-2
rows[ixr][ixc]=m
if d=='c': return
elif d=='u': rows[ixr+1][ixc]='^'
elif d=='d': rows[ixr-1][ixc]='v'
elif d=='l': rows[ixr][ixc+1:ixc+4] = [' ', '<', '-']
elif d=='r': rows[ixr][ixc-3:ixc] = ['-', '>', ' ']
r,c = start
mark(r, c, 'S')
for d in path:
dr,dc = self.moves[d]
r,c = r+dr,c+dc
mark(r,c,'*', d)
mark(r,c,'F')
# return board pic
return '\n'.join([''.join(r) for r in rows])
def solve(self, start, finish):
try:
self.search(start, '', {'start':start, 'finish':finish})
except Solution, s:
return (
'The solution path from start at %s to finish at %s is\nS%sF'% (start, finish, s),
self.solpic(maze, start, finish, s.args[0])
)
else:
return 'No path found.','(no pic)'
if __name__=='__main__':
import sys
args = map(int,sys.argv[1:]) # Srow Scol Frow Fcol
start = tuple(args[:2])
finish = tuple(args[2:4])
if len(start)!=2: start = (2,8) # default
if len(finish)!=2: finish = (6,1) # default
mazer = Mazer(maze)
try:
msg, pic = mazer.solve(start, finish)
print msg
print pic
except KeyError, e:
print e, 'not reachable.'
if len(args)<4:
print """
You can specify start and end positions by typing
[python] maze.py startRow startCol finishRow finishCol
"""
=====================================================================
Result or running plain (indented one space to avoid quote char coloring)
[21:18] C:\pywk\maze>maze.py
The solution path from start at (2, 8) to finish at (6, 1) is
SdldlluuulllldddddF
+---+---+---+---+---+---+---+---+
| * <-* <-* <-* <-* | | | |
+ v +---+---+---+ ^ +---+ +---+
| * | | | | * | | S |
+ v +---+ +---+ ^ +---+ + v +
| * | | * | | * <-* |
+ v +---+---+---+ ^ +---+ v +---+
| * | | * <-* <-* | |
+ v +---+ + +---+ +---+---+
| * | | | | | | | |
+ v +---+ + +---+ +---+---+
| F | | | | | |
+---+---+---+---+---+---+---+---+
You can specify start and end positions by typing
[python] maze.py startRow startCol finishRow finishCol
So we try it in reverse ;-)
[21:18] C:\pywk\maze>maze.py 6 1 2 8
The solution path from start at (6, 1) to finish at (2, 8) is
SuuuuurrrrdddrruruF
+---+---+---+---+---+---+---+---+
| *-> *-> *-> *-> * | | | |
+ ^ +---+---+---+ v +---+ +---+
| * | | | | * | | F |
+ ^ +---+ +---+ v +---+ + ^ +
| * | | * | | *-> * |
+ ^ +---+---+---+ v +---+ ^ +---+
| * | | *-> *-> * | |
+ ^ +---+ + +---+ +---+---+
| * | | | | | | | |
+ ^ +---+ + +---+ +---+---+
| S | | | | | |
+---+---+---+---+---+---+---+---+
or
[21:20] C:\pywk\maze>maze.py 6 3 4 4
The solution path from start at (6, 3) to finish at (4, 4) is
SuulluuurrrrdddrddlluuF
+---+---+---+---+---+---+---+---+
| *-> *-> *-> *-> * | | | |
+ ^ +---+---+---+ v +---+ +---+
| * | | | | * | | |
+ ^ +---+ +---+ v +---+ + +
| * | | * | | |
+ ^ +---+---+---+ v +---+ +---+
| * <-* <-* | F | *-> * | |
+ +---+ ^ + ^ +---+ v +---+---+
| | | * | * | | * | | |
+ +---+ ^ + ^ +---+ v +---+---+
| | | S | * <-* <-* | | |
+---+---+---+---+---+---+---+---+
Regards,
Bengt Richter
More information about the Python-list
mailing list