[QUIZ] Amazing Mazes (#31)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Matt Linnell

We've had crosswords, cryptograms, chess puzzles, madlibs ... so why don't we
try our hand at mazes? We can define the two basic components of this problem
as:

- Generating the maze
- Solving the maze

* Generating the maze *

The maze is to be rectangular in shape, with the height and width determined at
run time. All nodes of the maze must be reachable from any point. In other
words, if one were to randomly pick a start/stop, the maze is always solvable.
Furthermore, let us enforce that only 1 viable solution for the maze exists for
any given start/stop (you cannot reach the same destination from 2 different
routes). Generate an ASCII output representing the maze.

* Solving the Maze *

Given a maze produced from your above code, find the solution. Produce ASCII
output to demonstrate/visualize solution.

* Bonus Points *

1) Calculate which pair of start/stop points in the maze which gives
you the longest possible path.
2) Calculate which pair of start/stop points in the maze which gives
the most complicated path (involves the most turns)

Example command line execution:

$> ruby maze.rb {height} {width} [ {start} {stop} ]

 

[James Edward Gray II]

Thank you for the quiz,

I took great pleasure in this quiz...

Brian, simply amazing. You're work is always a pleasure to look
through and you're write-ups always help me get right to the good stuff.

Thanks!

James Edward Gray II

 

[Dominik Bathon]

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 |= 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=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

 

[Markus Koenig]

Hello,

here is another solution. The maze generation part really took me a
while, but I finally got it, although my solution performs very badly
compared to the others. Maybe I should just go and read the page
Dominik suggested ...

Again, this taught me that one should just use Hashes to get better
performance, as I have done in the Visit class.

Thanks for this quiz which prevented my lessons from being boring

Markus


#!/usr/bin/env ruby

# This is an ugly hack to redeem us from checking indices all the time
def nil.[](i)
nil
end

# Visit encapsulates a selection of fields
class Visit < Array
attr_accessor :turns

def initialize
@included = {}
end

def [](x, y)
@included[y][x]
end

def add(x, y)
if (@included[y] ||= {})[x]
false
else
self << [x, y]
@included[y][x] = true
end
end

# from Latin "pons", bridge
# select a random bridge
def pons(other)
xarr = []
yarr = []
dirarr = []
each do |x, y|
if other[x - 1, y]
xarr << x
yarr << y
dirarr << :left
end
if other[x, y - 1]
xarr << x
yarr << y
dirarr << :up
end
if other[x + 1, y]
xarr << x
yarr << y
dirarr << :right
end
if other[x, y + 1]
xarr << x
yarr << y
dirarr << :down
end
end
# yield a bridge if there is at least one
if dirarr.empty?
return false
else
i = rand(dirarr.length)
yield xarr, yarr, dirarr
return true
end
end
end

# Obviously encapsulates a maze
class Maze
attr_reader :width, :height
attr_accessor :selection

def initialize(width, height)
# initialize instance variables
@width = width
@height = height
@go_right = Array.new(height) {Array.new(width, false)}
@go_down = Array.new(height) {Array.new(width, false)}

# generate the maze
combs = combinations.sort_by{rand}
until combs.empty?
cur_comb = combs.shift
unless add_path(*cur_comb)
combs.push cur_comb
end
end
end

def add_path(x0, y0, x1, y1)
neigh0 = neighbors(x0, y0)
# return true if one can go from x0|y0 to x1|y1
if neigh0[x1, y1]
true
else
# remove the wall if we can
neigh0.pons(neighbors(x1, y1)) do |x, y, dir|
case dir
when :left
@go_right[y][x - 1] = true
when :up
@go_down[y - 1][x] = true
when :right
@go_right[y][x] = true
when :down
@go_down[y][x] = true
end
end
end
end

def combinations
max_index = @width * @height - 1
arr = []

max_index.times do |i0|
x0 = i0 % @width
y0 = i0 / @width
(i0+1).upto(max_index) do |i1|
x1 = i1 % @width
y1 = i1 / @width
arr << [x0, y0, x1, y1]
end
end

return arr
end

def display
curses = MazeCurses.new(5 * @width + 1, 3 * @height + 1)

# draw the stipples
if @selection
@selection.each do |x, y|
curses.stipple 5 * x, 3 * y, 6, 4
end
end

# draw the outer border
curses.box

# draw the inner borders
@height.times do |y|
@width.times do |x|
unless @go_right[y][x]
curses.mvvline 5 * (x + 1), 3 * y, 4
end
unless @go_down[y][x]
curses.mvhline 5 * x, 3 * (y + 1), 6
end
end
end

# throw the thing at stdout
curses.wnoutrefresh
end

def go(x, y, direction)
# try to go into a direction
case direction
when :left
yield x - 1, y if @go_right[y][x - 1]
when :up
yield x, y - 1 if @go_down[y - 1][x]
when :right
yield x + 1, y if @go_right[y][x]
when :down
yield x, y + 1 if @go_down[y][x]
end
end

def neighbors(x, y)
neigh = Visit.new
neigh.add x, y

# add all neighbors
done = false
until done
done = true
neigh.each do |x, y|
# try to go left
if @go_right[y][x - 1] and neigh.add(x - 1, y)
done = false
end
# try to go up
if @go_down[y - 1][x] and neigh.add(x, y - 1)
done = false
end
# try to go right
if @go_right[y][x] and neigh.add(x + 1, y)
done = false
end
# try to go down
if @go_down[y][x] and neigh.add(x, y + 1)
done = false
end
end
end

# the neighborhood is complete
return neigh
end

def path(x0, y0, x1, y1, curdir = nil)
# find a way from x0|y0 to x1|y1
# this uses depth-first search

if x0 == x1 and y0 == y1
way = Visit.new
way.add x0, y0
way.turns = 0
return way
end

case curdir
when :left
directions = [:left, :up, :down]
when :up
directions = [:left, :up, :right]
when :right
directions = [:up, :right, :down]
when :down
directions = [:left, :right, :down]
else
directions = [:left, :up, :right, :down]
end

directions.each do |direction|
go x0, y0, direction do |x2, y2|
way = path(x2, y2, x1, y1, direction)
if way
way.add x0, y0
unless direction == curdir
way.turns += 1
end
return way
end
end
end

return nil
end
end

# A way to draw fancy or sludgy ASCII graphics
class MazeCurses
# This has *nothing* to do with the curses library!

def initialize(width, height)
@width = width
@height = height
@matrix = Array.new(height) {' ' * width}
end

def box
# draw a box around the edges of the matrix
mvhline 0, 0, @width
mvhline 0, @height-1, @width
mvvline 0, 0, @height
mvvline @width-1, 0, @height
end

def mvaddch(x, y, ch)
case ch
when ?-
if @matrix[y][x] == ?|
@matrix[y][x] = ?+
elsif @matrix[y][x] != ?+
@matrix[y][x] = ?-
end
when ?|
if @matrix[y][x] == ?-
@matrix[y][x] = ?+
elsif @matrix[y][x] != ?+
@matrix[y][x] = ?|
end
else
@matrix[y][x] = ch
end
end

def mvhline(x, y, n)
n.times do |i|
mvaddch x + i, y, ?-
end
end

def mvvline(x, y, n)
n.times do |i|
mvaddch x, y + i, ?|
end
end

def stipple(left, top, width, height)
top.upto(top+height-1) do |y|
left.upto(left+width-1) do |x|
@matrix[y][x] = ?:
end
end
end

def wnoutrefresh
puts @matrix
puts
end
end


if ARGV.length != 2
puts 'usage: ruby maze.rb {height} {width}'
exit
end

maze = Maze.new(ARGV[1].to_i, ARGV[0].to_i)
all_paths = maze.combinations.map{|x| maze.path(*x)}

puts "== Upper left to lower right =="
maze.selection = maze.path(0, 0, maze.width - 1, maze.height - 1)
maze.display

puts "== Longest path =="
maze.selection = all_paths.sort_by{|x| x.length}.last
maze.display

puts "== Most complicated path =="
maze.selection = all_paths.sort_by{|x| x.turns}.last
maze.display

 

[Dave Burt]

I've spent enough time on this

I have 2 maze creation algorithms, and 2 maze solving algorithms.

I didn't implement a command-line options interface, but that would be
trivial to do. I think it's a decent enough API.

I don't like my solution because it has too many capital letters, due to the
fact that methods are not first-class objects and I wanted to pass around
the building and solving algorithms.

http://www.dave.burt.id.au/ruby/maze.rb

Cheers,
Dave