-
-
Save anonymous/8c0971e5745506b8e59e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Solution for the Ruby Challenge: http://rubylearning.com/blog/2009/12/27/rpcfn-mazes-5/ | |
# By Dmitriy Nagirnyak | |
# The class is responsible for solving arbitrary maze by searching for the smallest number of steps required to move from point A to B | |
class Maze | |
START_MARK = 'A' | |
END_MARK = 'B' | |
SPACE_MARKS = [' ', END_MARK, START_MARK] | |
# Initializes the solver accepting the maze as a string. | |
# The string can contain a number of rows separated by '\n' character. The length of the rows can be different. | |
# Start and end positions are marked with A and B respectively. | |
# Movable area is the one that contains space, A or B marks. | |
def initialize(maze) | |
# Build the 2D area, like this: [%w{# # #}, %w{# A #}, %w{# B #}] | |
@area = maze.split(/\r?\n/).map {|r| r.split('') } | |
#Find start & the end - 2 arrays with coordinates: [row,column] | |
@area.each_with_index do |r, ri| | |
r.each_with_index do |c, ci| | |
@start = [ri,ci] if c == START_MARK | |
@end = [ri,ci] if c == END_MARK | |
break if @start && @end | |
end | |
break if @start && @end | |
end | |
throw ArgumentError.new('No start and/or end positions provided on the maze') if !@start || !@end | |
end | |
# Returns minimal number of steps required to move from position marked as A to position B on the maze. | |
def steps | |
res = calc_steps @start, [] | |
# Always includes step for A, thus minimal value if solution exists is 2 | |
res > 0 ? res-1 : 0 | |
end | |
# Returns true if there is a path from A to B. Otherwise false. | |
def solvable? | |
steps > 0 | |
end | |
private | |
# The main worker - recursively finds the smallest number of steps | |
def calc_steps(cur, traces) | |
# Recursion bases | |
return 0 if !can_move_to? cur # hit the wall | |
return 0 if traces.include? cur #been here | |
return 1 if cur == @end #found the guy | |
# Keep the local copy of the traces, also adding current position to it | |
cur_traces = traces.map {|e| e}.push cur | |
# Recursion step | |
left = calc_steps from_left(cur), cur_traces | |
right = calc_steps from_right(cur), cur_traces | |
up = calc_steps from_up(cur), cur_traces | |
dn = calc_steps from_dn(cur), cur_traces | |
# Reject zero steps and get the minimal value if available | |
sub_steps = [left, right, up, dn].reject! {|step| step == 0 }.min | |
# return the total number of steps keeping in mind: no sub_steps means no way to the guy, thus zero | |
sub_steps ? sub_steps + 1 : 0 | |
end | |
# Returns the new coordinates with the given offset | |
def move(pos, down, right) | |
[pos[0] + down, pos[1] + right] | |
end | |
# Sugar - position on the left from current | |
def from_left(cur) | |
move(cur, 0, -1) | |
end | |
# Sugar - position on the right from current | |
def from_right(cur) | |
move(cur, 0, 1) | |
end | |
# Sugar - position on the front from current | |
def from_up(cur) | |
move(cur, -1, 0) | |
end | |
# Sugar - position on the back from current | |
def from_dn(cur) | |
move(cur, 1, 0) | |
end | |
# Checks if the given position is movable (so that a guy can step onto it) | |
def can_move_to?(pos) | |
# Check for the out-of-bounds | |
row, col = pos[0], pos[1] | |
return false if !(0...@area.length).include?(row) || !(0...@area[row].length).include?(col) | |
SPACE_MARKS.include? from_area(pos) | |
end | |
# Returns the mark located at the given position of the area. | |
# It doesn't check out-of-bounds conditions. Use can_move_to? for that. | |
def from_area(pos) | |
@area[pos[0]][pos[1]] | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment