secret
anonymous / radek kotlarek.rb
Last active

  • Download Gist
radek kotlarek.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 101 102
# Constans defining maze dimensions
ROWS=13
COLS=37
 
class Maze
attr_reader :maze, :a, :b
# Remove end of line characters
# Verify we have a valid maze
# What are our A & B coordinates?
def initialize(maze)
@maze = maze.gsub(/[\n\r]/,'')
raise "Maze must have #{COLS} columns and #{ROWS} rows" if @maze.size != COLS*ROWS
@a = position_to_coordinates(@maze.index('A'))
@b = position_to_coordinates(@maze.index('B'))
end
def solvable?
build_space(*@a)
return true if @space.include?(@b)
false
end
def steps
return 0 unless solvable?
@distances={@a=>0}
calculate_cost(@a)
@distances[@b]
end
private
# calculate distance for node's neighbourhouds
def calculate_cost(node)
cost=@distances[node]+1
neighbours(*node).each do |n|
next if @distances[n] and @distances[n] < cost
@distances[n]=cost
calculate_cost(n)
end
end
# build space for (x,y) - all possible fields we can move
def build_space(x,y)
@space = @space || []
surrounding(x,y).each do |s|
next if @space.include? s
@space << s
build_space(*s)
end
@space
end
# what cells can we move to from (x,y)
def neighbours(x,y)
results=[]
results << [x+1,y] if @space.include? [x+1,y]
results << [x-1,y] if @space.include? [x-1,y]
results << [x,y-1] if @space.include? [x,y-1]
results << [x,y+1] if @space.include? [x,y+1]
results
end
# all surrounding cells to (x,y)
def surrounding(x,y)
results=[]
rows=case y
when 1 then [1,2]
when ROWS then [ROWS-1,ROWS]
else [y-1,y,y+1]
end
columns=case x
when 1 then [1,2]
when COLS then [COLS-1, COLS]
else [x-1,x,x+1]
end
rows.each do |row|
columns.each do |col|
next if col==x and row==y
results << [col,row] if movable?(col,row)
end
end
results
end
# transition of index to (x,y) coordinates
def position_to_coordinates(pos)
x = pos % COLS
y = (pos-x)/COLS
x+=1
y+=1
[x,y]
end
# returns what is in the maze on (x,y)
def cell(x,y)
@maze[(COLS*(y-1)+x)-1].chr
end
# is (x,y) something we can move to?
def movable?(x,y)
[' ','A','B'].include? cell(x,y)
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.