R

#### Ruby Quiz

to give me a little man icon and some controls! Throw in some doors, some keys,

and little critters to chase me around and there's simply no chance at all I

would get a summary written next week. Hmm, maybe it's not such a good idea.

Jokes aside, do run the solutions a few times each this week. It's fun to see

what they build. Then peek inside the code and read the comments. Good stuff

in there.

Below, I want to look into Dominik Bathon's code. It is a nice search and

lightning quick! On my machine, it makes and solves quizzes faster than the

other solutions can just make them. Even better, it uses a complex internal

representation (mainly for speed), yet still comes out with clean algorithms. I

was quite impressed by that.

Let's get to the code. Dominik starts off by defining a helper method in Hash:

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

# ...

The comment pretty much explains what's going on there. Each pair of the Hash

is compared by value. The pair with the lowest value is deleted and the key for

that value is returned.

On to the interesting parts. Here's the start of the main class used by the

solution:

# 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

@[email protected]*@h

@neighbors_cache={}

set_all_walls

end

# ...

I know that section is mostly a comment, but you'll want to read through it.

It's interesting information and it introduces you to the internal format the

code uses.

After that, we see some readers defined and some simple initialization work.

Set a width and height, ensuring they are both at least 1. Nice use of max()

there. Calculate width times height or the total number of cells, initialize a

cache and call set_all_walls().

That means we need some more code:

# ...

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

# ...

Okay, now we start to get tricky. Remember the initial comment about using bits

for the walls. We're only tracking two walls here, north and west. Of course

cells can still have up to four walls, but your east wall is just your

neighbor's west wall and your south wall is the north wall for the cell below

you.

Now, what do you get if you turn two bits on? 3. The set_all_walls() method

just translates that to a character and duplicates it for every cell. That

gives us a String representing the entire maze with all the walls turned on.

That should make clear_all_walls() more obvious. This time we want no walls so

we don't set any bits. Translate 0 to a character and duplicate. However, we

still need the edges of the maze. All cells in the top row need a north wall

(set the 1 bit). Then all the cells in the first column need a west wall (set

the 2 bit). That makes up the rest of the method.

Ready for the next chunk?

# ...

# positions in path will be printed as "X"

def to_s(path=[])

ph={}

path.each { |i| ph

# set west walls of col 0

h.times { |i| @data[i*w] |= 2 }

nil

end

# ...

Okay, now we start to get tricky. Remember the initial comment about using bits

for the walls. We're only tracking two walls here, north and west. Of course

cells can still have up to four walls, but your east wall is just your

neighbor's west wall and your south wall is the north wall for the cell below

you.

Now, what do you get if you turn two bits on? 3. The set_all_walls() method

just translates that to a character and duplicates it for every cell. That

gives us a String representing the entire maze with all the walls turned on.

That should make clear_all_walls() more obvious. This time we want no walls so

we don't set any bits. Translate 0 to a character and duplicate. However, we

still need the edges of the maze. All cells in the top row need a north wall

(set the 1 bit). Then all the cells in the first column need a west wall (set

the 2 bit). That makes up the rest of the method.

Ready for the next chunk?

# ...

# 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

# ...

The to_s() method draws mazes. The first two lines fill a Hash with the

solution path, if one is given. The Hash is indexed identically as the maze

String and values can be true (if it's on the path) or the default nil, (when

it's not).

The rest of that method does the drawing. It walks row by row with h.times(),

down the maze drawing cells. The first w.times() call handles the north walls.

First it adds a "+", then it adds "---" if the 1 bit is set or " " if it's

not. Next we need another "+" and a "\n". Now the second w.times() block

handles the west wall and path. First it checks to see if the 2 bit is set for

the current cell, outputting "|" if it is and " " if it's not. Then the path is

checked. If this cell is on the path, it's filled with " X " and if it's not,

the code adds a " ".

The last two lines of the method are important. They ensure a final "|" is

always added to the end of a row and a final "+---" is placed at the end each

column of the maze. This handles the east and south borders of the maze, which

are not covered by the bits.

The other method, inspect(), just returns a class name, width and height.

# ...

# 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

# ...

These convertors were explained in the initial comment and they are explained

again here. No surprises there.

# returns valid neighbors to p, doesn't care about walls

def neighbors(p)

if [email protected]_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

This returns the indices of the up to four neighboring cells. It caches this

lookup the first time it does it, since it will never change. The first line

just uses the cache if it has already been figured. The second line adds the

cell above and the cell below. Note that these numbers are found by simple math

and could be outside the bounds of the maze. The next two lines add the left

and right cells. We're more careful with our math here, because a wrong answer

could look right: The last cell of the first row is "left" of the first cell of

the second row, in our one dimensional String that holds the maze data. The

final line, stores the indices to the cache and returns them, after using

find_all() to eliminate any bogus number that crept in.

# ...

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

# ...

These three methods are all very similar. Given two cells, the first checks if

there is a wall between them, the second sets the wall between them, and the

third unsets it. The if's just figure out if we are talking about a north wall

or a west wall. The rest is bit testing or setting.

On to maze generation:

# ...

# 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

# ...

This algorithm came out very clean, I think. Not a bit operation in sight.

First it turns all the walls on. Then it sets up an Array for tracking visited

cells and another as a stack to drive the process. While there is something on

the stack, the code looks at each not-yet-visited neighbor. If there are no

neighbors in that set, the stack is popped and the routine moves on. However,

if there are, one is chosen at random and the wall is knocked out between them.

If that neighbor was the last unvisited one for this cell, the code pops the

current cell off the stack. The neighbor cell is set to visited and pushed onto

the stack, moving the build process to that location for the next iteration.

That covers creation. Now we need a solver:

# ...

# 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

# ...

I really don't think I need to launch into too deep an explanation here as the

comments guide you right through it. The short story is that this method

branches out from a starting cell, walking to each neighbor and always counting

its steps. While doing this, it is building the Hash described in the first

comment, which points to the cell that came before on the shortest path. Using

that Hash, returned by this method, you can easily construct the shortest path

to any cell the algorithm visited. Handy stuff! Let's see how it gets put to

use:

# ...

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

# ...

Given a starting and ending cell, this returns just what the name implies. It

builds the magic Hash we just looked at on the first line, then just walks the

path in reverse until it reaches the start (nil in the Hash). Again, clean and

simple. Nice coding Dominik.

Let's look at the other search the code provides:

# ...

# 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

# ...

This method walks the maze, looking for cells that are dead-ends. From each of

those, it builds the path Hash and checks the lengths of each path found. In

the end, it will return the longest path it saw.

Just a little more code is needed for human interface:

# ...

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

This is just option parsing and display. The code checks for a special first

"-l" option, which just sets a flag to add the long search.

The next chunk reads a width and height then builds and displays a maze of the

indicated size. The code next reads from and to cells for a solution search,

if they where provided. Random coordinates are used when from or to cells are

absent. Note the use of the coord2pos() convertor in here.

Finally, the shortest path is displayed. The longer search is also added, if

requested. Dominik uses an unusual Ruby idiom here, "string" "string". Ruby

will concatenate these, even without the + between them. (I didn't know this!)

However, the rumor is that this feature may vanish in a future version of Ruby,

so it's probably not a good habit to get into.

My thanks to those who braved the mazes this week. Really interesting (and

fun!) solutions were given by all.

Tomorrow's quiz is a little client and server fun, care of Pat Eyler's

children...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

# ...

The to_s() method draws mazes. The first two lines fill a Hash with the

solution path, if one is given. The Hash is indexed identically as the maze

String and values can be true (if it's on the path) or the default nil, (when

it's not).

The rest of that method does the drawing. It walks row by row with h.times(),

down the maze drawing cells. The first w.times() call handles the north walls.

First it adds a "+", then it adds "---" if the 1 bit is set or " " if it's

not. Next we need another "+" and a "\n". Now the second w.times() block

handles the west wall and path. First it checks to see if the 2 bit is set for

the current cell, outputting "|" if it is and " " if it's not. Then the path is

checked. If this cell is on the path, it's filled with " X " and if it's not,

the code adds a " ".

The last two lines of the method are important. They ensure a final "|" is

always added to the end of a row and a final "+---" is placed at the end each

column of the maze. This handles the east and south borders of the maze, which

are not covered by the bits.

The other method, inspect(), just returns a class name, width and height.

# ...

# 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

# ...

These convertors were explained in the initial comment and they are explained

again here. No surprises there.

# returns valid neighbors to p, doesn't care about walls

def neighbors(p)

if [email protected]_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

This returns the indices of the up to four neighboring cells. It caches this

lookup the first time it does it, since it will never change. The first line

just uses the cache if it has already been figured. The second line adds the

cell above and the cell below. Note that these numbers are found by simple math

and could be outside the bounds of the maze. The next two lines add the left

and right cells. We're more careful with our math here, because a wrong answer

could look right: The last cell of the first row is "left" of the first cell of

the second row, in our one dimensional String that holds the maze data. The

final line, stores the indices to the cache and returns them, after using

find_all() to eliminate any bogus number that crept in.

# ...

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

# ...

These three methods are all very similar. Given two cells, the first checks if

there is a wall between them, the second sets the wall between them, and the

third unsets it. The if's just figure out if we are talking about a north wall

or a west wall. The rest is bit testing or setting.

On to maze generation:

# ...

# 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

# ...

This algorithm came out very clean, I think. Not a bit operation in sight.

First it turns all the walls on. Then it sets up an Array for tracking visited

cells and another as a stack to drive the process. While there is something on

the stack, the code looks at each not-yet-visited neighbor. If there are no

neighbors in that set, the stack is popped and the routine moves on. However,

if there are, one is chosen at random and the wall is knocked out between them.

If that neighbor was the last unvisited one for this cell, the code pops the

current cell off the stack. The neighbor cell is set to visited and pushed onto

the stack, moving the build process to that location for the next iteration.

That covers creation. Now we need a solver:

# ...

# 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

# ...

I really don't think I need to launch into too deep an explanation here as the

comments guide you right through it. The short story is that this method

branches out from a starting cell, walking to each neighbor and always counting

its steps. While doing this, it is building the Hash described in the first

comment, which points to the cell that came before on the shortest path. Using

that Hash, returned by this method, you can easily construct the shortest path

to any cell the algorithm visited. Handy stuff! Let's see how it gets put to

use:

# ...

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

# ...

Given a starting and ending cell, this returns just what the name implies. It

builds the magic Hash we just looked at on the first line, then just walks the

path in reverse until it reaches the start (nil in the Hash). Again, clean and

simple. Nice coding Dominik.

Let's look at the other search the code provides:

# ...

# 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

# ...

This method walks the maze, looking for cells that are dead-ends. From each of

those, it builds the path Hash and checks the lengths of each path found. In

the end, it will return the longest path it saw.

Just a little more code is needed for human interface:

# ...

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

This is just option parsing and display. The code checks for a special first

"-l" option, which just sets a flag to add the long search.

The next chunk reads a width and height then builds and displays a maze of the

indicated size. The code next reads from and to cells for a solution search,

if they where provided. Random coordinates are used when from or to cells are

absent. Note the use of the coord2pos() convertor in here.

Finally, the shortest path is displayed. The longer search is also added, if

requested. Dominik uses an unusual Ruby idiom here, "string" "string". Ruby

will concatenate these, even without the + between them. (I didn't know this!)

However, the rumor is that this feature may vanish in a future version of Ruby,

so it's probably not a good habit to get into.

My thanks to those who braved the mazes this week. Really interesting (and

fun!) solutions were given by all.

Tomorrow's quiz is a little client and server fun, care of Pat Eyler's

children...