secret
Created

  • Download Gist
README
1 2 3 4 5 6 7 8 9 10
Ruby Programming Challenge For Newbies: Mazes (#5)
 
Author: René Scheibe
Email: rene.scheibe@gmail.com
Date: January 7, 2010
Runs with: Ruby 1.9.1, JRuby 1.4
Algorithm: BFS (breadth-first search)
 
The implementation is based on the ordered Hash of Ruby 1.9.
It also assumes that the "each" method takes notice of new elements that are added during the enumeration.
maze.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
class Maze
def initialize maze_as_string
@input_string = maze_as_string
@input_string.extend(MazeString)
@waypoints = @input_string.extract_waypoints
end
 
def solvable?
steps != 0
end
 
def steps
return 0 unless valid?
 
waypoints = {@waypoints.start_position => 0}
 
waypoints.each do |current_waypoint, path_length|
return path_length if current_waypoint == @waypoints.end_position
new_waypoints = spot_new_waypoints(current_waypoint, waypoints)
new_waypoints.each{ |waypoint| waypoints[waypoint] = path_length + 1 }
end
 
0
end
 
protected
def valid?
@input_string.valid?
end
 
def spot_new_waypoints current_waypoint, visited_waypoints
row, col = current_waypoint
candidate_waypoints = [[row-1, col], [row+1, col], [row, col-1], [row, col+1]]
candidate_waypoints.select{ |waypoint| @waypoints[waypoint] && !visited_waypoints[waypoint] }
end
end
 
module MazeString
SYMBOLS = {:wall => '#', :space => ' ', :start => 'A', :end => 'B'}
 
def valid?
has_valid_symbols? and has_one_start? and has_one_end?
end
 
def extract_waypoints
waypoints = WaypointStore.new
self.split($/).each_with_index do |line, row|
line.split('').each_with_index do |char, col|
waypoints[[row, col]] = char unless char == SYMBOLS[:wall]
end
end
waypoints
end
 
protected
def has_valid_symbols?
(self =~ /^[#{SYMBOLS.values.join}]*$/) != nil
end
 
def has_one_start?
self.count(SYMBOLS[:start]) == 1
end
 
def has_one_end?
self.count(SYMBOLS[:end]) == 1
end
end
 
class WaypointStore < Hash
def start_position
@start_position ||= invert[MazeString::SYMBOLS[:start]]
end
 
def end_position
@end_position ||= invert[MazeString::SYMBOLS[:end]]
end
end
tests.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
require 'test/unit'
require 'maze'
 
class MazeUnitTest < Test::Unit::TestCase
Maze.send :public, *Maze.protected_instance_methods
 
def test_input_symbols
assert_equal true, Maze.new("# A # B").valid?
assert_equal true, Maze.new("# A \nB").valid?
assert_equal false, Maze.new("# A + B").valid?
end
 
def test_start_count
assert_equal true, Maze.new("B A ").valid?
assert_equal false, Maze.new("B ").valid?
assert_equal false, Maze.new("B AA").valid?
end
 
def test_end_count
assert_equal true, Maze.new("A B ").valid?
assert_equal false, Maze.new("A ").valid?
assert_equal false, Maze.new("A BB").valid?
end
 
def test_extract_waypoints
actual_waypoints = extract_waypoints("# A\n# B")
expected_waypoints = {[0, 1] => ' ', [0, 2] => 'A', [1, 1] => ' ', [1, 2] => 'B'}
assert_equal expected_waypoints, actual_waypoints
end
 
def test_waypoint_spotting
maze = Maze.new("# A\n# B")
actual_waypoints = maze.spot_new_waypoints([0, 1], {[0, 2] => 0, [0, 1] => 1})
expected_waypoints = [[1, 1]]
assert_equal expected_waypoints, actual_waypoints
end
 
def test_start_position
assert_equal [0, 2], extract_waypoints("##A\nB##").start_position
assert_equal nil, extract_waypoints("").start_position
end
 
def test_end_position
assert_equal [1, 0], extract_waypoints("##A\nB##").end_position
assert_equal nil, extract_waypoints("").end_position
end
 
def test_solvability
assert_equal false, Maze.new("A").solvable?
assert_equal true, Maze.new("#A \n# \n B").solvable?
end
 
def test_steps
assert_equal 0, Maze.new("").steps
assert_equal 0, Maze.new("A").steps
assert_equal 0, Maze.new("A#B").steps
assert_equal 1, Maze.new("AB").steps
assert_equal 2, Maze.new("#A \n# B").steps
end
 
def extract_waypoints maze_string
maze_string.extend(MazeString)
maze_string.extract_waypoints
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.