2
\$\begingroup\$

Hello everyone this is my first post here so please do critique my post if there's anything.

I have made a program intended to pass a programming challenge on open.kattis.com, here. It should do as title says, but with the conditions that each traversal follows the rules of a "Knight" from chess, that being plus/minus two columns/rows and plus/minus one column/row.

  1. _read method: I attempted to solve this making a Node class and passing coordinate and char data into each instance of a Node object for each coordinate.

  2. _adjacencify method: Thereafter, I found adjacencies (neighbours) of all Node objects, with the aforementioned condition of a chess Knight.

  3. _jump method: Lastly, I used a BFS implementation in order to find the shortest path from the source (root) to the terminal (here represented as 'K').

  4. find_path: Wraps everything up.

Here's the code I ended up with:

class Nite
  #attr_accessor :char, :col, :row
  class Node
    attr_accessor :char, :col, :row, :disc, :parent
    attr_reader :adjies
    def initialize(char, col, row)
      @char = char
      @col = col
      @row = row
      @adjies = [] # adjacencies
      @disc = false
      @parent = nil
    end
    def add(value)
      @adjies << value
    end
  end

  def _read
    # assign each coord. to a Node-object
    n = gets.to_i
    nodes = Array.new
    n.times do |x|
      temp = gets.strip.to_s
      temp.size.times do |y|
        node = Node.new(temp[y], x, y)
        nodes << node
      end
    end

    nodes
  end

  def _adjacencify(nodes)

    nodes.each do |x|
      nodes.each do |y|
        if y.col == x.col && y.row == x.row || y.char == '#'
          next
        end

        # logic

        if x.row == (y.row - 1) # y.row + 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row+1)
          elsif x.col == (y.col + 2) # y.col - 2
            x.add(y) # (col-2, row+1)
          end
    
        elsif x.row == (y.row + 1) # y.row - 1

          if x.col == (y.col - 2) # y.col + 2
            x.add(y) # (col+2, row-1)
          elsif x.col == (y.col + 2) # y.col - 2)
            x.add(y) # (col-2, row-1)
          end
    
        end

        if x.row == (y.row - 2) # y.row + 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row+2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row+2)
          end
    
        elsif x.row == (y.row + 2) # y.row - 2

          if x.col == (y.col - 1) # y.col + 1
            x.add(y) # (col+1, row-2)
          elsif x.col == (y.col + 1) # y.col - 1
            x.add(y) # (col-1, row-2)
          end

        end

      end
    end

    nodes
  end

  def _jump(nodes)

    nodes = _adjacencify(nodes)

    q = Queue.new
    root = nodes[0]
    root.disc = true
    q << root

    while !q.empty? do
      v = q.pop
      if v.char == 'K'
        steps = 0
        until v.parent == nil do
          if !v.nil?
          end
          steps += 1
          v.parent = v.parent.parent
        end
        return steps
      end
      v.adjies.each do |w|
        if w.disc == false
          w.parent = v
          w.disc = true
          q << w
        end
      end
    end
    return -1

  end

  def find_path
    _jump(_read)
  end

end

nite = Nite.new
puts nite.find_path

I suspect of course that the _adjacencify method is super time consuming, and that some loops are way too time consuming. I failed the <1.00s time requirement in order to pass the challenge.

I want all types of criticism on my code, and I want tips and also, if anyone wants, different implementations that perform better. Especially Ruby convention is something I want critique on, considering I am coming from a Java and Python background and I'm fairly fresh in Ruby.

Please tell me if I should edit anything in this post to make anything clearer.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome, and very good post. \$\endgroup\$ Jan 27, 2021 at 3:12

2 Answers 2

3
\$\begingroup\$

and welcome!

Things I really like

  • Using standard Ruby indention (2 spaces)
  • Using the attr_accessor and attr_reader helpers instead of hand-rolling these methods
  • Using n.times do to loop.
  • Using next at the top of a loop body instead of a nested if
  • Short, focused methods
  • Great use of functional decomposition (goes along with the focused methods)

There's a lot of nit-picky things to follow, so don't be discouraged. Many of these things are minor, and I'm mostly pointing out Ruby idioms or practices you have no way to know yet. Due to time constraints, I am not going to address the algorithm itself, nor look for any major improvements. I will mostly point out the things that catch my eye as a Ruby programmer.

Naming things

  def _read
    # assign each coord. to a Node-object

Does the comment indicate that "read" could use a better name?

    nodes.each do |x|
      nodes.each do |y|

x and y are frequently used as coordinate names for a Cartesian grid, which a chessboard is. Here, x and y are nodes, not coordinates. Better names would be a and b, or perhaps origin and destination.

@adjies = [] # adjacencies

Probably just name the variable @adjacencies so you can lose the comment, and the code will be clearer throughout. Someone reading the code who hasn't seen this comment yet will be confused.

Formatting

    end
    def add(value)
      @adjies << value
    end
  end

Standard Ruby formatting separates methods with a blank line. I also prefer a blank line between a method and the end of the class:

    end

    def add(value)
      @adjies << value
    end

  end

but the more common practice is to have no blank line after the last method in a class:

    end

    def add(value)
      @adjies << value
    end
  end

Idiomatic private methods in Ruby

def _jump(nodes)

Standard Ruby does not use the underscore conversion for private methods. Instead, private methods can follow the private keyword:


private

def jump(nodes)

Note that all methods that follow "private" will be private, so you don't have to use it before every private method. Standard Ruby practice is to just give the "private" keyword once, and then follow that with all of the private methods.

Omit the "return" keyword in the last expression in a method.

   return -1

The result of a Ruby method is the value of the last expression in the method. So unless returning early, we usually omit the "return" keyword when it's on the last line:

    -1

You omit the "return" keyword elsewhere, so I assume this is just an oversight.

Don't compare to true or false

if w.disc == false

In Ruby, true and false are a little different than in Java. Ruby considers anything that is either nil or false to be "falsey", and everything else is "truthy". Therefore, it is bad practice to compare a value with false, since this comparison will fail if the value is actually nil.

So instead of comparing with false, do this:

if !w.disc

But even better, Ruby has a negating form of "if" called "unless". Idiomatic Ruby would be:

unless w.disc

Getting the first element of an array or enumeration

root = nodes[0]

This is fine, but this also works:

root = nodes.first

Ruby likes you to have multiple ways to do a thing, a philosophical shift from Python.

Redundant #to_s

     temp = gets.strip.to_s

The result of String#strip is a String, so there's no need for .to_s here.

Use Array instead of Queue (for this application)

q = Queue.new

Queue is intended for multi-threaded applications; it includes locking to prevent race conditions. For a single-threaded application, you can and should just use Array. The minor reason is performance (avoid the locking). The major reason is communication: A Ruby programmer seeing Queue is going to start looking for the threading in your program.

Since the methods you are calling on q (<< and pop) are also implement on Array and have the same meaning, you can do this instead:

q = []

Create empty arrays with []

nodes = Array.new

There's nothing wrong with this, but you will more often see a new, empty array created using the array literal syntax:

nodes = []
\$\endgroup\$
5
  • \$\begingroup\$ "Instead, private methods can follow the private keyword" – Module#private is a bog-standard method, not a keyword. \$\endgroup\$ Jan 27, 2021 at 8:41
  • \$\begingroup\$ This is really good feedback. I thought that I could save some space and indicate the nested class better by omitting white space, but I understand that I should follow convention there. Regarding 'private', should I keep all private methods at the end of the class, so that all methods above 'private' are considered public? \$\endgroup\$
    – ma22om
    Jan 27, 2021 at 15:53
  • \$\begingroup\$ @martyro Thank you, I'm glad this is helpful to you. Yes, putting all private methods at the end of the class it the usual practice \$\endgroup\$ Jan 27, 2021 at 16:08
  • \$\begingroup\$ @JörgWMittag I considered making that distinction, but then thought it might be better to gloss over that detail since it's not really important to someone learning Ruby basics. \$\endgroup\$ Jan 27, 2021 at 16:13
  • \$\begingroup\$ Excellent answer, in part because your points are so well-written. \$\endgroup\$ Jan 30, 2021 at 22:03
2
\$\begingroup\$

The problem

We are given an NxN chessboard with one cell designated as the origin and all others being open or blocked. One of the open cells is designated as the destination. If a knight begins at the origin, we wish to find the smallest number of moves among empty cells required for it to reach the destination.

Specifically, we are be given an array board containing n elements, with each element being an array of n elements. The destination is the cell [0, 0]. For each pair of indices i, 0 <= i < N and j, 0 <= j < N, board[i][j] equals:

  • '.' if the cell is open;
  • '#' if the cell is blocked; and
  • 'K' if the cell is the origin.

We wish to determine if there is a path of valid knight moves among open squares from the origin to the destination, and if there is at least one, find the shortest, the length of each path being the number board locations on the path, excluding the origin. Paths are expressed as arrays of board corrdinates, each coordinate being a 2-element array containining a row and column index.

The problem states that row and column indices are 1-based, but I will make them 0-based for convenience. If desired one could easily convert the indices to 1-based after an optimal path has been found.

Example

Let's construct a 6x6 example for illustrating the code below.

board = [
  ['.', '.', '#', '.', '.', '.'], 
  ['.', '.', '.', '.', '.', '#'], 
  ['#', '.', '.', '#', '.', '.'], 
  ['.', '#', '.', '#', 'K', '.'], 
  ['.', '.', '#', '.', '.', '.'],
  ['#', '.', '.', '#', '#', '.'],
] 

As indicated, the origin is located at [3, 4].

Is a class needed?

Though opinions may differ, I see no advantage to defining classes for this problem, such as one for the board and another for the pieces. It's a standalone problem, not part of a larger one, with only two potential types of objects, the board and the cells, with only a single board instance.

Moreover, looking ahead I see no need for instance variables.

Useful constants

Here are a few constants I suggest be defined:

OPEN = '.'
ORIGIN_CHAR = 'K'
DESTINATION = [0, 0]
MOVE_OFFSETS = [
  [-2,  1], [-1,  2], [1,  2], [2,  1],
  [-2, -1], [-1, -2], [1, -2], [2, -1]
]

MOVE_OFFSETS is represented by the eight m's in the drawing below. They are the locations the knight can move to, expressed as x-y offsets from its current location, provided, of course, that the new location is on the board.

 y
 2|     m     m  
 1|  m           m       
 0|        o     
-1|  m           m
-2|     m     m
   _______________    
    -2 -1  0  1  1  x

Determining cells to which knight can move directly from its current location

def possible_next_moves(board, current_loc)
  last_idx = board.size-1
  cx, cy = current_loc
  MOVE_OFFSETS.each_with_object([]) do |(xo,yo),possible_next_locs|
    nx = cx + xo
    ny = cy + yo 
    possible_next_locs << [nx, ny] if nx.between?(0, last_idx) &&
      ny.between?(0, last_idx) && board[nx][ny] == OPEN
   end
end

Let's try it with the example of board I gave above.

possible_next_moves(board, [3, 4]) #=> [[5, 5], [1, 3], [2, 2]]
possible_next_moves(board, [0, 5]) #=> [[1, 3], [2, 4]]   
possible_next_moves(board, [5, 0]) #=> []   
possible_next_moves(board, [0, 3]) #=> [[2, 4], [1, 1], [2, 2]]

This method and all methods below other than shortest_path should be private.

Main method

I suggest the main method be as follows.

require 'set'
def shortest_path(board)
  origin = locate_origin(board)
  predessors = solve(board, origin)
  return nil if predessors.nil?
  construct_path(predessors, origin)
end

The method returns nil if there is no path from the origin to the destination.

I will present and discuss the three methods, locate_origin, solve and construct_path in turn. (The class Set is needed by solve.)

Locate the origin from board

Locating the origin of the path (the cell containing 'K') is straightforward.

def locate_origin(board)
  indices = (0..board.size - 1).to_a
  indices.product(indices).find { |i,j| board[i][j] == ORIGIN_CHAR }
end
locate_origin(board)
  #=> [3, 4]

See Array#product.

Find a shortest path using BFS

Since we have an undirected, unweighted graph with no negative cycles, a breadth-first search (BFS) is an efficient way of finding a shortest path from origin to DESTINATION. The method returns a hash whose keys are all locations visited and each key's value is the location on a path from the origin that immediately precedes the location given by the key.

You understand how a BFS search is performed so I won't go into details of the calculations. It terminates when the destination is found or the queue of locations to be visited becomes empty (indicating that there is no path from the origin to the destination).

def solve(board, origin)
  prev = {}
  queue = [origin]
  visited = [origin].to_set
  loop do 
    break nil if queue.empty? # no path exists
    loc = queue.shift
    next_moves = possible_next_moves(board, loc)
    if next_moves.include?(DESTINATION)
      prev[DESTINATION] = loc
      break prev # shortest path found!
    end
    next_moves.each do |next_loc|
      unless visited.add?(next_loc).nil? # loc already visited if nil
        prev[next_loc] = loc
        queue << next_loc
      end
    end
  end
end
prev = solve(board, [3,4])
  #=> {[5, 5]=>[3, 4], [1, 3]=>[3, 4], [2, 2]=>[3, 4], [4, 3]=>[5, 5],
  #    [0, 5]=>[1, 3], [2, 5]=>[1, 3], [0, 1]=>[1, 3], [2, 1]=>[1, 3],
  #    [3, 2]=>[1, 3], [0, 3]=>[2, 2], [1, 4]=>[2, 2], [1, 0]=>[2, 2],
  #    [3, 0]=>[2, 2], [4, 1]=>[2, 2], [2, 4]=>[4, 3], [3, 5]=>[4, 3],
  #    [5, 1]=>[4, 3], [0, 4]=>[2, 5], [4, 4]=>[2, 5], [0, 0]=>[2, 1]}

prev contains the information needed to construct the shortest path. Starting at the destination ([0, 0]) we backtrack to the origin ([4, 3]):

[0, 0], prev[[0, 0]] #=> [2, 1], prev[[2, 1]] #=> [1, 3],
  prev[[1, 3]] #=> [3, 4]

I made visited a set merely to speed lookups. Set#add? serves double-duty: when attempting to add a location to visited it returns nil if the set already contains the location; else it adds the location to the set and returns the set.

Build the shortest path

Lastly, we must build the shortest path from the hash returned by solve.

def construct_path(prev, origin)
  current_loc = DESTINATION
  path = [DESTINATION]
  until path.first == origin
    prev_loc = prev[current_loc]
    path.unshift(prev_loc)
    current_loc = prev_loc
  end
  path
end
construct_path(prev, [3,4])
  #=> [[3, 4], [1, 3], [2, 1], [0, 0]]

Run the method shortest_path

shortest_path(board)
  #=> [[3, 4], [1, 3], [2, 1], [0, 0]]
\$\endgroup\$
2
  • \$\begingroup\$ Nice. This solution has a kind of functional feel to it. \$\endgroup\$ Feb 1, 2021 at 16:34
  • \$\begingroup\$ Excellent! I love these solutions. I will sit down and look through this thoroughly when studies allow it. \$\endgroup\$
    – ma22om
    Feb 3, 2021 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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