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




More information about the Python-list mailing list