Instantly share code, notes, and snippets.

# anonymous/radek kotlarek.rbSecret Created Jan 14, 2010

What would you like to do?
 # 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
to join this conversation on GitHub. Already have an account? Sign in to comment