Algorithm help

Jeethu Rao jeethur at sancharnet.in
Wed Jan 29 09:09:24 CET 2003


For simplicity, I'd suggest a 2D array (A list of
Lists in python), with each element being either
0 or 1. The ones are the paths, the zeros are the walls.
For a compact storage of the mazes, cPickle it up and 
compress it with zlib.

A similar maze problem is discussed in Adam Drozdek's
"Data Structures and Algorithms in C++" book.

Jeethu Rao

> -----Original Message-----
> From: python-list-admin at python.org
[mailto:python-list-admin at python.org]
> On Behalf Of VanL
> Sent: Tuesday, January 28, 2003 6:52 AM
> To: python-list
> Subject: Algorithm help
> 
> Hello,
> 
> I am trying to create an internal representation of a maze in python.
> My first thought was to have a dict, with the keys being ordered
pairs,
> and the values being 1 (wall) or 0 (no wall).  That way I could pretty
> efficently construct a graph that I could search for the solution.
> 
> However, the map description file is in a little different format than
I
> expected -- I had thought that they were going to give us a file with
a
> bunch of 1s and 0s.  However, what I actually will get is a list of
> lists of ordered pairs:
> 
> POINTS=[200,20 200,200 210,200 210,20]
> POINTS=[320,20 320,200 330,200 330,20]
> 
> I am inclined to still go with the same representation, but I am
trying
> to find a way to efficiently solve the above as an inequality, to get
> every integer point within the wall.  Does anyone know a good
algorithm
> for doing so?
> 
> 
> Alternatively, can anyone suggest a better internal representation?
> 
> Thanks,
> 
> VanL






More information about the Python-list mailing list