secret
Created — forked from /dmitriynagirnyak.rb

  • Download Gist
dmitriynagirnyak.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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
# 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
StartMark = 'A'
EndMark = 'B'
SpaceMarks = [' ', EndMark, StartMark]
 
# Initializes the solver accepting the maze as a string.
# The string can be contain number of rows separated by '\n' character. The length of the rows can be different.
# The rows of the string are separted by a newline character; start and end position are marked with A and B respectively.
# Movable area is the one that space or A and 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 == StartMark
@end = [ri,ci] if c == EndMark
break if @start && @end
end
break if @start && @end
end
throw ArgumentError.new('No start and/or end positinos 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 minumal 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 shortest 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
# Suger - position on the left from current
def from_left(cur)
move(cur, 0, -1)
end
# Suger - position on the right from current
def from_right(cur)
move(cur, 0, 1)
end
# Suger - position on the fron from current
def from_up(cur)
move(cur, -1, 0)
end
# Suger - 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)
return false if pos[0] < 0 || pos[1] < 0
return false if pos[0] >= @area.length
row = @area[pos[0]]
return false if pos[1] >= row.length
SpaceMarks.include? from_area(pos)
end
# Returns the mark located at the given position of the area.
# It doesn't check out-of-bouns conditions. Use can_move_to for that.
def from_area(pos)
@area[pos[0]][pos[1]]
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.