Create a gist now

Instantly share code, notes, and snippets.

anonymous /dmitriynagirnyak.rb Secret
Created Jan 6, 2010

What would you like to do?
# Solution for the Ruby Challenge:
# 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
# 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
break if @start && @end
throw'No start and/or end positions provided on the maze') if !@start || !@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
# Returns true if there is a path from A to B. Otherwise false.
def solvable?
steps > 0
# 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 = {|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
# Returns the new coordinates with the given offset
def move(pos, down, right)
[pos[0] + down, pos[1] + right]
# Sugar - position on the left from current
def from_left(cur)
move(cur, 0, -1)
# Sugar - position on the right from current
def from_right(cur)
move(cur, 0, 1)
# Sugar - position on the front from current
def from_up(cur)
move(cur, -1, 0)
# Sugar - position on the back from current
def from_dn(cur)
move(cur, 1, 0)
# 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)
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment