Skip to content

@darxriggs /README secret

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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.
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.