Home  Forums  Reviews  Guides  Newsgroups  Register  Search 
Thread Tools 
Ruby Quiz
Guest
Posts: n/a

Wow, these solutions are great fun to play with. I think next week's quiz needs
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*h1), 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 # ... 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[i] = 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[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 # ... 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*h1 # 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 ce=@neighbors_cache[p]; return ce; end res=[pw, p+w] res << p1 if p%w > 0 res << p+1 if p%w < w1 @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 p2p1==w # check north wall of p2 @data[p2] & 1 > 0 elsif p2p1==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 p2p1==w # set north wall of p2 @data[p2] = 1 elsif p2p1==1 # set west wall of p2 @data[p2] = 2 end nil end def unset_wall(p1, p2) p1, p2=[p1, p2].sort if p2p1==w # unset north wall of p2 @data[p2] &= ~1 elsif p2p1==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 notyetvisited 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 deadends. 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... 




Ruby Quiz 


 
Dominik Bathon 


 
Clifford Heath
Guest
Posts: n/a

Ruby Quiz wrote:
> Below, I want to look into Dominik Bathon's code. Nicely coded, I enjoyed learning some Ruby tricks. Unfortunately if you look at the mazes this algorithm generates, you'll see a serious flaw. They always seem to "fan out" from the start position  in other words there is not a random nature to the shape of the paths away from the start position. It makes the mazes much easier to solve. I made the same mistake when I first wrote a maze generator. The commonly accepted alternative method (which produces *random* mazes) is to number every square with a distinct number 0..N, then choose a random wall which divides two cells having different numbers. Throughout the maze, change the higher number to the lower number, and repeat until the whole maze is numbered 0. This takes exactly N cycles. The search for a random wall requires a circular search around the maze from a randomlychosen start position, until a suitable wall is found. Clifford Heath. 




Clifford Heath 
Martin DeMello
Guest
Posts: n/a

Ruby Quiz <(EMail Removed)> wrote:
> > 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 Wonder if http://blade.nagaokaut.ac.jp/cgibin...bytalk/133202 would be an optimisation. martin 




Martin DeMello 
Dominik Bathon
Guest
Posts: n/a

On Fri, 13 May 2005 06:35:28 +0200, Martin DeMello
<(EMail Removed)> wrote: > Ruby Quiz <(EMail Removed)> wrote: >> >> 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 > > Wonder if > http://blade.nagaokaut.ac.jp/cgibin...bytalk/133202 would > be an optimisation. Yes, I know about rbtree, but it isn't in the stdlib, so I didn't want to use it for the quiz. Ruby really lacks a nice sorted set out of the box (SortedSet in set.rb uses rbtree, if it is installed, otherwise it just resorts the elements, when they changed and it has no accessor for the min/max elements). And as I said in my other reply, for this special problem the priority queue isn't necessary at all. Dominik 




Dominik Bathon 
Martin DeMello
Guest
Posts: n/a

Dominik Bathon <(EMail Removed)> wrote:
> > Yes, I know about rbtree, but it isn't in the stdlib, so I didn't want to > use it for the quiz. Ruby really lacks a nice sorted set out of the box > (SortedSet in set.rb uses rbtree, if it is installed, otherwise it just > resorts the elements, when they changed and it has no accessor for the > min/max elements). Ah  yes, good point. But rbtree really ought to make it into the stdlib, IMO. Having it in there would promote good algorithmic practices. martin 




Martin DeMello 
Ara.T.Howard@noaa.gov
Guest
Posts: n/a

On Fri, 13 May 2005, Martin DeMello wrote:
> Dominik Bathon <(EMail Removed)> wrote: >> >> Yes, I know about rbtree, but it isn't in the stdlib, so I didn't want to >> use it for the quiz. Ruby really lacks a nice sorted set out of the box >> (SortedSet in set.rb uses rbtree, if it is installed, otherwise it just >> resorts the elements, when they changed and it has no accessor for the >> min/max elements). > > Ah  yes, good point. But rbtree really ought to make it into the > stdlib, IMO. Having it in there would promote good algorithmic > practices. i've reccomended this many times  an RCR? a  ================================================== =============================  email :: ara [dot] t [dot] howard [at] noaa [dot] gov  phone :: 303.497.6469  renunciation is not getting rid of the things of this world, but accepting  that they pass away. aitken roshi ================================================== ============================= 




Ara.T.Howard@noaa.gov 
Clifford Heath
Guest
Posts: n/a

Glenn M. Lewis wrote:
> Could you please elaborate? It's been quite a while since I did this stuff, but I do recall solving the problem, and only afterwards finding some other work that reflected the same solution. It'd be very cool to do this again in Ruby with OpenGL )). The idea is to start as Dominik did, with a maze having all walls intact  every cell has two intact walls so it's closed from every other cell. Every cell is numbered, say topleft to bottomright, 0..(W*H1). This number is known as the domain number, and every cell bearing a certain number is defined to be reachable from any cell in that domain. Whenever you break a wall separating two distinct domains, you join them into one domain, because any cell in either domain can now reach any cell in the other domain. So to keep things intact, you must eliminate one domain by changing all occurrences of that number to the other one. I always eliminate the higher numbered one, so the maze ends up as one domain numbered zero. Whenever you consider a wall you might want to break, check the domain numbers on either side. If they're the same, there is already a path between the two cells, and breaking this wall will make a duplicate path  which is not what you want. If they're different however, there is no path between the two cells and it's ok to break this wall, eliminating one of the two domains. The only remaining task is to find an efficient and random search for a wall to break. The easiest way is to choose a cell at random, check both walls (in random order), and if that wall divides two domains, break it. If not, consider the next cell (circular search) until you find a wall you can break. Because you have W*H cells, there are initially that many domains, and because every break reduces the domain count by one, you must break exactly W*H1 walls to get to a maze where every cell is reachable from every other. I set my son the challenge of doing this in three dimensions, and we arranged things so the ladders (=broken floors) were much less numerous than the horizontal connections. You can do this simply by skewing the random number generator that chooses which wall to break. If it tries the north wall 45% of the time, the east wall 45%, and the floor only 10%, you get the desired outcome. Similarly in a 2D maze, you can skew the generation so that more of the paths are EW rather than NS. Then we created a 3D perspective view looking in from near one corner between two layers, so you can see all the passages, the ladders climbing up to the layer above, and the manholes where ladders appear from below, so you can wander around the maze at will. We even animated the ladder climbing using double buffering, moving the camera up past the floor to the next floor. All in TurboPascal for a year 10 assignment . My son solved a 20x20x20 maze in about 10 minutes, much to his teacher's astonishment  he has an amazing visual memory. I used to print him 2D mazes with a 1/8" cell size, full page on letter paper  perhaps 60x80 in size. When he was four years old, he complained that he needed some new ones, and my wife pointed out that he had a stack of sixty that were unmarked. He quickly went through the stack, pointing to the solution on each one. He had not only solved them all by eye, but he recognised each one and remembered its solution! Scary... Clifford Heath. 




Clifford Heath 
Clifford Heath
Guest
Posts: n/a

Glenn M. Lewis wrote:
> In honor of Clifford's very clear description of his mazegeneration > algorithm, here is my attempt at a solution, and an example output: That's even cuter than I expected it to be  well done! Note that you don't use a circular search, so especially with large mazes, your random choice is going to take longer and longer to find a valid wall. You should choose a starting position, then choose an order in which to check the two walls, check them both, and if that fails, don't choose a new random starting position but step to the very next cell and check the walls again (same or different random order is ok). Otherwise there's a real possibility of *very* long runtimes. For example, to break the last wall in a 20x20x20 maze, your random algorithm has to loop until it finds one of 167200 candidate walls out of a field that might be as small as three walls. Thanks for your kind comments. Let's hope my son is as good at relationships! He announced his engagement yesterday, at the age of 19... I can't complain, I married at 21 and still am now... . Clifford. 




Clifford Heath 
Greg Millam
Guest
Posts: n/a

On Tue, May 17, 2005 at 01:50:30AM +0900, Glenn M. Lewis wrote:
> Could you please elaborate? This sounds fascinating, > but I don't quite grok it. For example, when/how do you decide > to place or destroy a wall? > > Do you have a pointer that goes into more detail? I know I'm coming into this thread a bit late, but I just looked into it. I wrote a little lesson on this kind of thing about a year or so ago to help a codeveloper understand something I was doing. (I'm making a game that, while not a maze, does use the same wallbreaking concept and using regions as such). http://walker.deafcode.com/lessons/perfect_maze.txt In the other solutions provided here, a wall is chosen by randomly selecting cells until one is found with an unbroken wall. In my given solution above, the walls themselves are listed, shuffled (perhaps even a weighted shuffle) and then broken in order they are in the list, unless the rooms on either side of the wall are in the same area. Just some input of mine. Hope it helps.  Greg Millam 




Greg Millam 


 
Thread Tools  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Re: Amazing hardware, Amazing software, Amazing Stories  Mike Painter  HTML  0  11022006 11:18 PM 
Best Studying Matrial + Amazing Cost + 3 in price of 1  JohnCena  MCSD  1  02212006 10:42 AM 
Solving mazes!!!  Maeco  C Programming  10  11112005 05:16 PM 
[QUIZ] Amazing Mazes (#31)  Ruby Quiz  Ruby  4  05122005 02:01 PM 
Re: Bulk Newsgroup Poster  amazing result  Malke  Wireless Networking  0  01172005 01:35 AM 
Powered by vBulletin®. Copyright ©2000  2014, vBulletin Solutions, Inc..
SEO by vBSEO ©2010, Crawlability, Inc. 