# One Problem -- how to implement in three programming paradigms in Python

Bengt Richter bokr at oz.net
Tue Jun 17 06:19:29 CEST 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

```