-
-
Save christiankn/c14a6cca2f782e2b4c3c 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
class Maze | |
attr_reader :maze | |
HEIGHT = 13 | |
WIDTH = 38 | |
def initialize(maze_as_string) | |
@maze = Array.new(HEIGHT) | |
parse(maze_as_string) | |
solve | |
end | |
def solvable? | |
symbol_is_on_path?("A") | |
symbol_is_on_path?("B") | |
end | |
def steps | |
steps=0 | |
y=0 | |
while(y<HEIGHT) do | |
x=0 | |
while(x<WIDTH) do | |
if @maze[y][x] == " " | |
steps+=1 | |
end | |
x+=1 | |
end | |
y+=1 | |
end | |
unless steps==0 | |
steps+=1 # For the final step onto finish | |
end | |
return steps | |
end | |
def parse(maze_as_string) | |
i=0 | |
maze_as_string.each do |line| | |
@maze[i] = line.chars.to_a | |
i+=1 | |
end | |
end | |
def solve | |
while(find_and_fill_dead_ends!=0) do | |
find_and_fill_dead_ends | |
end | |
end | |
def symbol_is_on_path?(symbol) | |
location = find_symbol(symbol) | |
return true if @maze[location[0]+1][location[1]] == " " | |
return true if @maze[location[0]-1][location[1]] == " " | |
return true if @maze[location[0]][location[1]+1] == " " | |
return true if @maze[location[0]][location[1]-1] == " " | |
return false | |
end | |
def find_symbol(symbol) | |
symbol_position = [] | |
y=0 | |
while(y<HEIGHT) do | |
x=0 | |
while(x<WIDTH) do | |
symbol_position = [y, x] if @maze[y][x] == symbol | |
x+=1 | |
end | |
y+=1 | |
end | |
return symbol_position | |
end | |
def find_and_fill_dead_ends | |
y=0 | |
filled_spaces = 0 | |
HEIGHT.times do | |
x=0 | |
WIDTH.times do | |
filled_spaces+=1 if fill_if_dead_end?(y, x) | |
x+=1 | |
end | |
y+=1 | |
end | |
return filled_spaces | |
end | |
def fill_if_dead_end?(y, x) | |
if @maze[y][x] == " " | |
wall_count = 0 | |
wall_count += 1 if @maze[y-1][x] == "#" | |
wall_count += 1 if @maze[y+1][x] == "#" | |
wall_count += 1 if @maze[y][x+1] == "#" | |
wall_count += 1 if @maze[y][x-1] == "#" | |
if wall_count >= 3 | |
@maze[y][x] = "#" | |
return true | |
end | |
end | |
end | |
def to_s | |
y=0 | |
HEIGHT.times do | |
x=0 | |
WIDTH.times do | |
print @maze[y][x] | |
x+=1 | |
end | |
y+=1 | |
end | |
end | |
end |
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
require 'spec' | |
require 'Maze' | |
MAZE1 = %{##################################### | |
# # # #A # # # | |
# # # # # # ####### # ### # ####### # | |
# # # # # # # # # | |
# ##### # ################# # ####### | |
# # # # # # # # # | |
##### ##### ### ### # ### # # # # # # | |
# # # # # # B# # # # # # | |
# # ##### ##### # # ### # # ####### # | |
# # # # # # # # # # # # | |
# ### ### # # # # ##### # # # ##### # | |
# # # # # # # | |
#####################################} | |
# Maze 1 should SUCCEED | |
MAZE2 = %{##################################### | |
# # # # # # | |
# ### ### # ########### ### # ##### # | |
# # # # # # # # # # | |
# # ###A##### # # # # ### ########### | |
# # # # # # # # # | |
####### # ### ####### # ### ####### # | |
# # # # # # # # | |
# ####### # # # ####### # ##### # # # | |
# # # # # # # # # # # | |
# ##### # # ##### ######### # ### # # | |
# # # # #B# | |
#####################################} | |
# Maze 2 should SUCCEED | |
MAZE3 = %{##################################### | |
# # # # # | |
# ### # ####### # # # ############# # | |
# # # # # # # # # # | |
### ##### ### ####### # ##### ### # # | |
# # # # A # # # # # | |
# ######### ##### # ####### ### ### # | |
# ### # # # # # | |
# ### ### ####### ####### # # # # ### | |
# # # # # #B# # # # # # # | |
# # # ##### ### # # # # ### # ##### # | |
# # # # # # | |
#####################################} | |
# Maze 3 should FAIL | |
describe "Maze" do | |
context "when being initialized" do | |
before(:each) do | |
@maze = Maze.new(MAZE1) | |
end | |
it "should take a string as a parameter" do | |
end | |
it "should have a method called parse" do | |
@maze.should respond_to(:parse) | |
end | |
it "should contain the maze as an array" do | |
@maze.should respond_to(:maze) | |
@maze.maze.should be_kind_of(Array) | |
end | |
it "should be a todimentional array" do | |
@maze.maze[0].should respond_to("[]") | |
end | |
end | |
context "to rule out single dead ends" do | |
before(:each) do | |
@maze = Maze.new(MAZE1) | |
end | |
it "should fill in the first dead end" do | |
@maze.fill_if_dead_end?(1,1) | |
@maze.maze[1][1].should match("#") | |
end | |
it "should fill in an opposite dead end" do | |
@maze.fill_if_dead_end?(3,3) | |
@maze.maze[3][3].should match("#") | |
end | |
end | |
context "to find all first-level dead ends" do | |
before(:each) do | |
@maze = Maze.new(MAZE1) | |
end | |
it "should call a method to loop through all characters" do | |
@maze.find_and_fill_dead_ends | |
end | |
it "should fill in dead ends" do | |
@maze.find_and_fill_dead_ends | |
@maze.maze[1][1].should match("#") | |
@maze.maze[3][3].should match("#") | |
end | |
it "should pass the koordinates on to fill_if_dead_end?" do | |
@maze.should_receive(:fill_if_dead_end?).exactly(494).times | |
@maze.find_and_fill_dead_ends | |
end | |
end | |
context "to find start and ending points" do | |
before(:each) do | |
@maze1 = Maze.new(MAZE1) | |
@maze2 = Maze.new(MAZE2) | |
end | |
it "should find the starting-point" do | |
@maze1.find_symbol("A").should eql([1,13]) | |
end | |
it "should find starting point of other mazes as well" do | |
@maze2.find_symbol("A").should eql([4,7]) | |
end | |
it "should find the end point of both mazes" do | |
@maze1.find_symbol("B").should eql([7,23]) | |
@maze2.find_symbol("B").should eql([11,35]) | |
end | |
end | |
context "to verify that both a start and end-point are on the solvable path" do | |
before(:each) do | |
@maze1 = Maze.new(MAZE1) | |
end | |
it "start should have a blank neighbour after being saved" do | |
@maze1.solve | |
@maze1.find_symbol("A").should eql([1,13]) | |
@maze1.maze[1][14].should eql(" ") | |
end | |
it "should check to see if both start and finish is on the path" do | |
@maze1.symbol_is_on_path?("A").should be_true | |
@maze1.symbol_is_on_path?("B").should be_true | |
end | |
it "should be solvable if both A and B is on the path" do | |
@maze1.solvable?.should be_true | |
end | |
end | |
context "valid mazes" do | |
it "should work" do | |
Maze.new(MAZE1).solvable?.should be_true | |
Maze.new(MAZE2).solvable?.should be_true | |
end | |
it "should return number of steps to end of maze" do | |
Maze.new(MAZE1).steps.should eql(44) | |
Maze.new(MAZE2).steps.should eql(75) | |
end | |
end | |
context "invalid mazes" do | |
it "should be unsolvable" do | |
Maze.new(MAZE3).solvable?.should be_false | |
end | |
it "should return 0 steps for invalid mazes" do | |
Maze.new(MAZE3).steps.should eql(0) | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment