Re: [QUIZ] [SOLUTION] Amazing Mazes (#31)

Hy,

here is my solution. First of all thanks for this nice quiz. After  
Knight's Travails and Barrel of Monkeys another "search the shortest path"  
quiz, so once again a nice solution to this quiz is Dijkstra's shortest  
path algorithm.
I have to admit, that I cheated a bit: I googled for the maze generation  
part and found the following page:

http://www.mazeworks.com/mazegen/mazetut/

It explains the perfect maze generation algorithm quite nice.

I solved the 1st bonus part, I didn't try the 2nd part, but I think  
searching for the most turns might be quite expensive.

Dominik

Usage:
ruby maze.rb [-l] width height [from [to]]

if -l is given, it will search for the longest shortest path and print it.
if form or to are ommitted then random positions will be used.

Examples:
$ ruby maze.rb 10 10
$ ruby maze.rb -l 10 10
$ ruby maze.rb 10 10 0,0 9,9
$ ruby maze.rb 10 10 _ 5,5   # random "from"

Complete Example:
$ ruby maze.rb -l 8 8 0,0 7,7
Maze:
+---+---+---+---+---+---+---+---+
|           |                   |
+---+---+   +   +---+---+---+   +
|           |   |       |       |
+   +---+---+   +---+   +   +---+
|           |       |   |       |
+---+---+   +---+   +   +---+   +
|   |       |   |   |   |       |
+   +   +---+   +   +   +   +   +
|   |   |               |   |   |
+   +   +---+---+---+---+   +   +
|       |           |       |   |
+   +---+   +---+   +   +---+   +
|       |   |   |   |   |   |   |
+---+   +   +   +   +   +   +   +
|           |           |       |
+---+---+---+---+---+---+---+---+

Shortest path from [0, 0] to [7, 7]:
+---+---+---+---+---+---+---+---+
| X   X   X |                   |
+---+---+   +   +---+---+---+   +
| X   X   X |   |       |       |
+   +---+---+   +---+   +   +---+
| X   X   X |       |   |       |
+---+---+   +---+   +   +---+   +
|   | X   X |   |   |   | X   X |
+   +   +---+   +   +   +   +   +
|   | X |               | X | X |
+   +   +---+---+---+---+   +   +
| X   X | X   X   X | X   X | X |
+   +---+   +---+   +   +---+   +
| X   X | X |   | X | X |   | X |
+---+   +   +   +   +   +   +   +
|     X   X |     X   X |     X |
+---+---+---+---+---+---+---+---+

Longest shortest path (from [0, 0] to [4, 1]:
+---+---+---+---+---+---+---+---+
| X   X   X | X   X   X   X   X |
+---+---+   +   +---+---+---+   +
| X   X   X | X | X   X | X   X |
+   +---+---+   +---+   +   +---+
| X   X   X | X   X | X | X   X |
+---+---+   +---+   +   +---+   +
|   | X   X |   | X | X | X   X |
+   +   +---+   +   +   +   +   +
|   | X |         X   X | X |   |
+   +   +---+---+---+---+   +   +
| X   X | X   X   X | X   X |   |
+   +---+   +---+   +   +---+   +
| X   X | X |   | X | X |   |   |
+---+   +   +   +   +   +   +   +
|     X   X |     X   X |       |
+---+---+---+---+---+---+---+---+

The performance is quite well:
$ time ruby maze.rb 30 30 > /dev/null

real    0m0.214s
user    0m0.179s
sys     0m0.008s

$ time ruby maze.rb -l 30 30 > /dev/null

real    0m4.068s
user    0m3.946s
sys     0m0.022s

$ time ruby maze.rb 100 100 > /dev/null

real    0m1.033s
user    0m0.992s
sys     0m0.011s


==============================================
maze.rb:

class Hash
       # find the key for with the smallest value, delete it and return it
       def delete_min_value
             return nil if empty?
             minkey=min=nil
             each { |k, v|
                   min, minkey=v, k if !min || v<min
             }
             delete(minkey)
             minkey
       end
end

# Maze represents the maze ;-)
#
# Cells/positions in the maze are represented by Numbers (from 0 to w*h-1),
# each position corresponds to x/y coordinates, you can convert between
# positions and coordinates by coord2pos and pos2coord.
#
# The walls for each position are stored in the String @data. The walls for
# position p are stored in the first two bits of @data[p], the other bits  
are
# unused. If bit one is set then p has a north wall, if bit two is set  
then p
# has a west wall.
#
# Maze#generate generates a (random) maze using the method described at
# http://www.mazeworks.com/mazegen/mazetut/
#
# Maze#shortest_path uses Dijkstra's shortest path algorithm, so it can not
# anly find shortest pathes in perfect mazes, but also in mazes where  
different
# pathes between two position exist.

class Maze
       attr_reader :w, :h # width, height

       def initialize(w, h)
             @w, @h=[w, 1].max, [h, 1].max
             @wh=@w*@h
             @neighbors_cache={}
             set_all_walls
       end

       def set_all_walls
             # set all bits
             @data=3.chr * (@wh)
             nil
       end
       def clear_all_walls
             # all except outer border
             @data=0.chr * (@wh)
             # set north walls of row 0
             w.times { |i| @data[i] |= 1 }
             # set west walls of col 0
             h.times { |i| @data[i*w] |= 2 }
             nil
       end

       # positions in path will be printed as "X"
       def to_s(path=[])
             ph={}
             path.each { |i| ph[i]=true }
             res=""
             h.times { |y|
                   w.times { |x|
                         res << "+" << ((@data[y*w+x] & 1 > 0) ? "---" :  
"   ")
                   }
                   res << "+\n"
                   w.times { |x|
                         res << ((@data[y*w+x] & 2 > 0) ? "|" : " ")
                         res << (ph[y*w+x] ? " X " : "   ")
                   }
                   res << "|\n"
             }
             res << ("+---"*w) << "+"
       end
       def inspect
             "#<#{self.class.name} #{w}x#{h}>"
       end

       # maze positions are cell indices from 0 to w*h-1
       # the following functions do conversions to and from coordinates
       def coord2pos(x, y)
             (y%h)*w+(x%w)
       end
       def pos2coord(p)
             [p%w, (p/w)%h]
       end

       # returns valid neighbors to p, doesn't care about walls
       def neighbors(p)
             if ce=@neighbors_cache[p]; return ce; end
             res=[p-w, p+w]
             res << p-1 if p%w > 0
             res << p+1 if p%w < w-1
             @neighbors_cache[p] = res.find_all { |t| t>=0 && t<@wh }
       end

       def wall_between?(p1, p2)
             p1, p2=[p1, p2].sort
             if p2-p1==w # check north wall of p2
                   @data[p2] & 1 > 0
             elsif p2-p1==1 # check west wall of p2
                   @data[p2] & 2 > 0
             else
                   false
             end
       end
       def set_wall(p1, p2)
             p1, p2=[p1, p2].sort
             if p2-p1==w # set north wall of p2
                   @data[p2] |= 1
             elsif p2-p1==1 # set west wall of p2
                   @data[p2] |= 2
             end
             nil
       end
       def unset_wall(p1, p2)
             p1, p2=[p1, p2].sort
             if p2-p1==w # unset north wall of p2
                   @data[p2] &= ~1
             elsif p2-p1==1 # unset west wall of p2
                   @data[p2] &= ~2
             end
             nil
       end

       # generate a (random) perfect maze
       def generate(random=true)
             set_all_walls
             # (random) depth first search method
             visited={0 => true}
             stack=[0]
             until stack.empty?
                   n=neighbors(stack.last).reject { |p| visited[p] }
                   if n.empty?
                         stack.pop
                   else
                         # choose one unvisited neighbor
                         np=n[random ? rand(n.size) : 0]
                         unset_wall(stack.last, np)
                         visited[np]=true
                         # if all neighbors are visited then here is
                         # nothing left to do
                         stack.pop if n.size==1
                         stack.push np
                   end
             end
             self
       end

       # central part of Dijkstra's shortest path algorithm:
       # returns a hash that associates each reachable (from start) position
       # p, with the previous position on the shortest path from start to p
       # and the length of that path.
       # example: if the shortest path from 0 to 2 is [0, 1, 2], then
       # prev[2]==[1, 2], prev[1]==[0, 1] and prev[0]==[nil, 0].
       # so you can get all shortest paths from start to each reachable
       # position out of the returned hash.
       # if stop_at!=nil the method stops when the previous cell on the
       # shortest path from start to stop_at is found.
       def build_prev_hash(start, stop_at=nil)
             prev={start=>[nil, 0]} # hash to be returned
             return prev if stop_at==start
             # positions which we have seen, but we are not yet sure about
             # the shortest path to them (the value is length of the path,
             # for delete_min_value):
             active={start=>0}
             until active.empty?
                   # get the position with the shortest path from the
                   # active list
                   cur=active.delete_min_value
                   return prev if cur==stop_at
                   newlength=prev[cur][1]+1 # path to cur length + 1
                   # for all reachable neighbors of cur, check if we found
                   # a shorter path to them
                   neighbors(cur).each { |n|
                         # ignore unreachable
                         next if wall_between?(cur, n)
                         if old=prev[n] # was n already visited
                               # if we found a longer path, ignore it
                               next if newlength>=old[1]
                         end
                         # (re)add new position to active list
                         active[n]=newlength
                         # set new prev and length
                         prev[n]=[cur, newlength]
                   }
             end
             prev
       end

       def shortest_path(from, to)
             prev=build_prev_hash(from, to)
             if prev[to]
                   # path found, build it by following the prev hash from
                   # "to" to "from"
                   path=[to]
                   path.unshift(to) while to=prev[to][0]
                   path
             else
                   nil
             end
       end

       # finds the longest shortest path in this maze, only works if there  
is
       # at least one position that can only reach one neighbor, because we
       # search only starting at those positions.
       def longest_shortest_path
             startp=endp=nil
             max=-1
             @wh.times { |p|
                   # if current p can only reach 1 neighbor
                   if neighbors(p).reject { |n| wall_between?(p, n)  
}.size==1
                         prev=build_prev_hash(p)
                         # search longest path from p
                         tend, tmax=nil, -1
                         prev.each { |k, v|
                               if v[1]>tmax
                                     tend=k
                                     tmax=v[1]
                               end
                         }
                         if tmax>max
                               max=tmax
                               startp, endp=p, tend
                         end
                   end
             }
             if startp # path found
                   shortest_path(startp, endp)
             else
                   nil
             end
       end
end

if $0 == __FILE__
       ARGV.shift if search_longest=ARGV[0]=="-l"
       w, h, from, to=ARGV
       m=Maze.new(w.to_i, h.to_i)
       m.generate
       puts "Maze:", m.to_s
       if from=~/(\d+),(\d+)/
             p1=m.coord2pos($1.to_i, $2.to_i)
       else
             p1=rand(m.w*m.h)
       end
       if to=~/(\d+),(\d+)/
             p2=m.coord2pos($1.to_i, $2.to_i)
       else
             p2=rand(m.w*m.h)
       end

       path=m.shortest_path(p1, p2)
       puts "\nShortest path from #{m.pos2coord(p1).inspect} to " \
       "#{m.pos2coord(p2).inspect}:", m.to_s(path)

       if search_longest
             path=m.longest_shortest_path
             puts "\nLongest shortest path (from " \
             "#{m.pos2coord(path[0]).inspect} to " \
             "#{m.pos2coord(path[-1]).inspect}:",
             m.to_s(path)
       end
end