# Maze solver for 2D matrix in Ruby

I got rejected for a junior Ruby job entry where I had to solve a 2D matrix as a maze with walls.

This is the main class:

solver.rb

require 'json'

class MazeSolver

def initialize(file)
@file = file
@data = ""
@table = Array.new
@table_reversed = Array.new
@table_merged = Array.new
@table_convert = Array.new
@nodes = Array.new
@step = 1
@start_node = 999
@goal_node =  999
@current_node = 999
@table_x = 0
@table_y = 0
@unvisited_set = Array.new
@node_list = Array.new
@shortest_path = Array.new
@shortest_path_coords = Array.new
@backtrack = Array.new
parse_maze
create_nodes
end

# convert the maze string to an array of arrays
def parse_maze

k = 0
@data.strip.split(/[\l|\n\/]/).each do |line|
@row = Array.new
line.split(/ /).each do |item|
@row << item
# append an incremental number for each node, for example
# [0,0] becomes 0, [0,1] becomes 1, [0,2] becomes 2 etc.
@nodes << k
k = k + 1
end
@table << @row
end

# flip table values horizontally
@table_reversed = @table.reverse

# search for start node but not for the goal node
# the robot does not know where the goal node is but we need to find out
# where to start at
x = 0
y = 0
z = 0 # will be used as a node number
@table_reversed.each do |row|
row.each do |item|
k = @nodes[z]
@start_node = z if item == "S"

# create a simple array with all values
@table_merged << item
@table_convert << [item, [x,y]]
y = y + 1
z = z + 1
end
x = x + 1
y = 0
end

# set table size values
@table_x = @table_reversed[0].size
@table_y = @table_reversed.size

# create the unvisited set of nodes but remove walls
@unvisited_set = @nodes.map { |r| r if @table_merged[r] != "X" }
@unvisited_set.delete(nil)

return @table_reversed
end # parse_maze

# initialize nodes structure
def create_nodes

nodes = Array.new
previous_node = nil

# set the current node as the start one
@current_node = @start_node
unvisited_set = @unvisited_set.dup

# iterate until there are no unvisited nodes
while unvisited_set.size > 0 do

# set the current node as the first element of the list and remove it
@current_node = unvisited_set.shift

# set values for neighbours
neighbours = []
left_node = @current_node - @step
top_node = @current_node + @table_x
right_node = @current_node + @step
bottom_node = @current_node - @table_x

# check If neighbours are not in the edges
if left_node > 0 && @current_node % @table_x != 0 && @table_merged[left_node] != "X"
neighbours << left_node
end
if top_node < (@table_x * @table_y) && @table_merged[top_node] != "X"
neighbours << top_node
end
if bottom_node - @table_x >= 0 && @table_merged[bottom_node] != "X"
neighbours << bottom_node
end
if (@current_node + @step) % @table_x != 0 && @table_merged[right_node] != "X"
neighbours << right_node
end
# check If the current node is the goal node
@goal_node = @current_node if @table_merged[@current_node] == "G"

# We should assign to every node a tentative distance value: set it to
# zero for our initial node and to Float::INFINITY for all other nodes.
# In our case we know that there is a standard distance between
# neighbours (1).
@current_node == @start_node ? @distance = 0 : @distance = @step

# Create a Hash for current node and append each node to a table.
# For the current node, consider all of its unvisited neighbors and
# calculate their tentative distances. In the current solver
# all distances of the neighbour nodes are 1.
@node_list << {
:id => @current_node,
:neighs => neighbours,
:dist => @distance,
:prev => previous_node
}
end

return @node_list
end # create nodes

# does what it says !
def solve_dijkstra

unvisited_set = @unvisited_set.dup

# create a queue for nodes to check
@queue = Array.new
current_node = @start_node
@queue << current_node

# Stop If there are no unvisited nodes or the queue is empty
while unvisited_set.size > 0 && @queue.size > 0 do

# set the current node as visited and remove it from the unvisited set
current_node = @queue.shift

# remove visited node from the list of unvisited nodes
unvisited_set.delete(current_node)

# find the current node's neighbours and add them to the queue
rolling_node = @node_list.find { |hash| hash[:id] == current_node }
rolling_node[:neighs].each do |p|
# only add them if they are unvisited and they are not in the queue
if unvisited_set.index(p) && !@queue.include?(p)
@queue << p
# set the previous node as the current for its neighbours
change_node = @node_list.find { |hash| hash[:id] == p }
change_node[:prev] = current_node
# increase the distance of each node visited
change_node[:dist] = rolling_node[:dist] + @step
end
end

if current_node == @goal_node

# go backwards to retrieve the shortest path
@backtrack = Array.new
@backtrack << current_node

# iterate until we arrive at the start node
while rolling_node[:prev] != nil do
temp_node = @node_list.find { |hash| hash[:id] == rolling_node[:prev] }
@backtrack << temp_node[:id]
rolling_node = temp_node
end

# create a table with the 1d and the 2d array node values
@shortest_path = Array.new
count = 0

@backtrack.each do |p|
@shortest_path << [p, @table_convert[p]]
@shortest_path_coords << @table_convert[p][1]
end

# break the loop
return @shortest_path_coords
break
end
end
end # solve_dijkstra

# prints the reversed table
def print_table_reverse
z = 0 # will be used as a node number
@table_merged.each do |item|
node = @nodes[z]
print "#{item} (#{node}) \t"
z = z + 1
puts if z % @table_x == 0
end
end # print_table_reverse

# prints stats.. what else ?
def print_stats
puts @data
puts "~" * 50
puts "Start node: #{@start_node}"
puts "Goal node: #{@goal_node}"
puts "Backtrack: #{@backtrack.inspect}"
puts "Shortest Path: "
@shortest_path.each do |p|
puts "#{p[0]} \t #{p[1]}"
end
puts "~" * 50
puts
end # print_stats

def print_nodes_final
puts
puts @node_list
puts
end

end


main.rb

require_relative "solver.rb"

system('clear')
puts "~" * 50
puts "MazeSolver"
puts "~" * 50
end

if __FILE__ == \$0
case ARGV[0]
when nil
puts "ERROR: You didn't choose a file with data!"
puts
else
case File.exist?(ARGV[0])
when true
solve_my_maze = MazeSolver.new(ARGV[0])
result = solve_my_maze.solve_dijkstra

case ARGV[1]
when "ptr"
# print the table and the 1d numbers generated
puts result.inspect

when "pst"
# print final stats
solve_my_maze.print_stats

when "pnf"
# print the final node set with distances and previous nodes
solve_my_maze.print_nodes_final

when "ptr"
# print the table and the 1d numbers generated
solve_my_maze.print_table_reverse
when "out"
# returns the result of the solution in array format
puts result.inspect

else
puts "ERROR: Wrong arguments"
puts
end
else
puts "ERROR: File does not exist."
puts
end
end
end


I want to know if I did anything wrong and what possibly could be the reason I got rejected, considering that it was only related to the code and this is a junior position.

I think your code shows ability of writing readable code, understanding and implementing algorithms, writing helpful comments, and if the code works like I believe it does, providing a working solution to the problem.

The only major issue about your solution I can think of is that perhaps they expected you to take a more modular and object oriented approach to the problem.

Now your MazeSolver class handles all tasks: reading a file, modelling the problem domain, solving the maze and printing the solution. Instead you could write classes like

• Maze
• MazeFile
• MazeSolution
• MazeSolver

This kind of approach would lead to solving the problem by having objects process and encapsulate different bits of the problem and communicating through simple and well defined interfaces.

The key benefit of modularity is that it makes it easier to make changes to a program. If, for instance, you needed to support another maze file format or try out another maze solving algorithm, then having separate modules or classes for handling files and solving mazes would help.

Ok, since you asked for an example, here's an example of splitting the functionality you've already written to several classes:

class Maze
# 1. Encapsulate the in-memory maze data here.
# 3. Provide methods to initialize the maze data. A constructor could work.
end

class MazeFile
# 1. Move reading and parsing a maze file here.
# 2. Parsing a file should produce a Maze object.
end

class MazeSolution
# 1. Encapsulate data that describes a solution to a maze.
# 2. Provide methods to initialize and/or build a solution step by step.
# 3. Provide a method that returns the solution as a formatted string
end

class MazeSolver
# 1. Move the solve method here.
# The method should take a Maze as a parameter and return a MazeSolution.
# It should not mutate the Maze given as a parameter.
end

# Main program (for command line interface)
# 2. Use MazeFile to read a Maze from a file.
# 3. Use MazeSolver to produce a MazeSolution by calling the solve method
# 4. Print the solution using MazeSolutions formatting


Now, this is just one quickly sketched initial design. Refactoring your implementation to this skeleton would quickly show whether this is a good design or not. Perhaps you could do just fine with fewer classes or perhaps you would need more classes.

I don't think you need object oriented programming skills to land some entry level job. However, the lack of modularity and/or object orientation is the only major issue I can spot in your code, so it's my best guess for the reason for this rejection. Ruby is an object oriented language, and thus showing OO skills wouldn't probably hurt, even though the true advantages of object orientation don't really show in a small scale one-time program.

• Object orientation (and modularity in general) is about solving problems in smaller bits. A working solution is certainly most important but a working and a reasonably modular solution is better. I don't think all entry level jobs require these kinds of design skills, but some of them may. After all, these skills are taught in schools. – COME FROM Sep 21 '15 at 11:45
• Modularity is important because it makes easier to add new or change existing functionality. – COME FROM Sep 21 '15 at 12:00
• This is a great answer, but I disagree that the advantages of OO wouldn't show up in a problem of this size. A well-written version of the skeleton you proposed would be much more readable and easier to follow than OP's code. – Jonah Sep 21 '15 at 21:23
• MazeFile should be a MazeParser module, not a class. Stop misusing classes. OOP should not be applied blindly. – Nakilon Sep 22 '15 at 5:40
• @Nakilon It could prove beneficial to write another answer with an example that uses modules instead of (some) classes. I believe there are many ways to improve on the quick sketch I wrote. – COME FROM Sep 22 '15 at 12:34

Proper OOD is one thing, but you make mistakes on much more fundamental level. Your code contains case statements used for simple truth test. With this it would be very hard to convince interviewer you realy have any professional experience, even as a junior (and even if you in fact somehow do), especially when they gave you two days to make the code nice.

case ARGV[0]
when nil
# ...
else
case File.exist?(ARGV[0])
when true
# ...
else
# ...
end
end


This code would be much nicer using regular if-else, and, as only thing your elses are for is error handling, it is obvious use case for exceptions:

def parse_input
# ... opening and working with a file ...
case ARGV[1]
# ...
else
raise ArgumentError # or use specific, hand-made exception class
end
rescue TypeError, ArgumentError
puts "Usage: maze.rb ..."
rescue Errno::ENOENT
puts "File #{ARGV[0]} doesn't exist"
end


Even better, you should avoid case at all (case statements are sometimes even considered a code smell) and use Ruby's built in optparser, but I won't elaborate on that here, just using expections would show you are familiar with language contructs.

Similiary, this is a very bad loop:

unvisited_set = @unvisited_set.dup
while unvisited_set.size > 0 do
@current_node = unvisited_set.shift
# ...
end


It would be better to use a for, old-school while with index or anything , and in Ruby you should most definately just use each

@unvisited_set.each do |node|
# ...
end


Again, it would be hard to convince interviewer you have any programming experience with such unnecesary complicated loop, even someone unfamiliar with Ruby idioms would most likely use simple for, at very worst while with index.

Other - though much less important - problem is how long your methods are. If your method reaches 20 lines (or even much earlier, as some Ruby style fanatics would say) you should separate it in several more basic tasks. For example, you could extract backtracking from solve_dijkstra.

def shortest_path
end

def solve_dijkstra
# ... code code code ...
return shortest_path if current_node == @goal_node
# ... some more code ...
end


This improves readability, easies debugging and refactoring.

There are some other, minor style issues, like Array.new instead of [], but those are less important, there is unofficial style guide for Ruby, but don't treat it like a Bible (unless your future employer says so, ofc).

If you wan't some resources, I recommend Practical Object-Oriented Design in Ruby - possibly after some basic Ruby book or course, I understand you can code in general, so basic book can feel like an insult, but you realy need to get familiar with Ruby idioms, so even if you just skim over such book it will do you much good.