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

[Bengt Richter]

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:

====< 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):'dS',
  (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):'uF',             (6,3):'u',  (6,4):'ur', (6,5):'lr',  (6,6):'lu'
}

# row,col deltas for the moves
moves = {'u':(-1,0),'d':(1,0),'r':(0,1),'l':(0,-1),'S':(0,0),'F':(0,0)}
start = (2,8)

class Solution(Exception):
    pass

def search(here, path='', beenthere={}):
    if here in beenthere: return
    beenthere[here]=1
    for direction in maze[here]:
        if direction=='F': raise Solution(path+'F')
        elif direction=='S': continue
        ud,lr = moves[direction]
        search((here[0]+ud,here[1]+lr),path+direction, beenthere)

if __name__=='__main__':
    try:
        search(start,'S')
    except Solution, s:
        print 'The solution path from start at %s is %s'% (start, s)
    else:
        print 'No path found.'
=====================================================================
Result:
[18:22] C:\pywk\maze>maze.py
The solution path from start at (2, 8) is SdldlluuulllldddddF

Not sure how it would do with cycles in the maze ;-)

Regards,
Bengt Richter