4
\$\begingroup\$

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 = File.read(@file)
    @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"

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

if __FILE__ == $0
  case ARGV[0]
  when nil
    puts header
    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"
        puts header
        # print the table and the 1d numbers generated
        puts result.inspect

      when "pst"
        puts header
        # print final stats
        solve_my_maze.print_stats

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

      when "ptr"
        puts header
        # 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.

\$\endgroup\$
8
\$\begingroup\$

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.
    # 2. Provide methods giving read access to the maze data.
    # 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)
    # 1. Read command line
    # 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – COME FROM Sep 21 '15 at 11:45
  • \$\begingroup\$ Modularity is important because it makes easier to add new or change existing functionality. \$\endgroup\$ – COME FROM Sep 21 '15 at 12:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonah Sep 21 '15 at 21:23
  • \$\begingroup\$ MazeFile should be a MazeParser module, not a class. Stop misusing classes. OOP should not be applied blindly. \$\endgroup\$ – Nakilon Sep 22 '15 at 5:40
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – COME FROM Sep 22 '15 at 12:34
5
\$\begingroup\$

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
  # ... your backtracking ...
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.