Knight's Travails in ruby

The task was to build a knight_moves method which when called would display the simplest path from one given square to the other given square.

My Solution:

class Square
  attr_accessor :x, :y, :children, :parent
  def initialize(x,y, parent=nil)
    @x = x
    @y = y
    @children = []
    @parent = parent
  end
end

def create_children(board)
  potentials = []
  potentials.push(
    [board.x + 2, board.y + 1],
    [board.x + 2, board.y - 1],
    [board.x + 1, board.y + 2],
    [board.x + 1, board.y - 2],
    [board.x - 2, board.y + 1],
    [board.x - 2, board.y - 1], 
    [board.x - 1, board.y + 2], 
    [board.x - 1, board.y - 2]
    )

  valid_children = potentials.select do |space|
    space[0].between?(0,8) &&
    space[1].between?(0,8)
  end

  valid_children = valid_children.map do |space|
    Square.new(space[0], space[1], board)
  end
  @children = valid_children
end

def knight_moves(first_square,final_square)
  first_children = Square.new(first_square[0],first_square[1])
  create_children(first_children)
  bfs(final_square, @children)
end

def bfs(search_value,children)
  queue = children

  loop do 
    current = queue.shift
    if [current.x,current.y] == search_value 
      display_path(current)
      break
    else
      create_children(current).each {|child| queue << child}
    end
  end
end

def display_path(current)
  parent = current.parent
  array = []
  while !parent.nil?
    array << [parent.x,parent.y]
    parent = parent.parent
  end
  array.reverse!
  array << [current.x,current.y]
  puts "Your path is:"
  array.each {|i| p i}
end

Method Call

knight_moves([2,5],[4,7])

Bug

This:

knight_moves([2,5],[2,5])

prints:

Your path is:
[2, 5]
[4, 6]
[2, 5]

Not the shortest path. In knight_moves, simply call bfs with [first_child] as the children argument. There's no need to call create_children in knight_moves; bfs can compute the first level of the search tree the same way it computes all other levels.

Global variable

In create_children, you're setting @children which acts like a global variable as this method isn't inside a class. Simply return valid_children without setting any variables.

(You're not setting Square#children because the method isn't inside Square. You actually never use Square#children. Remove this field from Square).

Naming

Rename:

• Square -> Node (The class represents a node in the search tree. A true Square class would only have x and y fields).

• create_children -> child_nodes

• first_children -> root

• board argument -> node (or parent)

• display_path -> print_path

Missing Square class

The code sometimes uses an [x, y] array for squares, and sometimes the x and y fields of Node. This makes the code full of wrapping of unwrapping:

# lines that unwrap an [x, y] array:
Node.new(space[0], space[1], board)
first_child = Node.new(first_square[0],first_square[1])

# lines that create an [x, y] array:
if [current.x,current.y] == search_value 
array << [current.x,current.y]

You can eliminate this by creating a Square class and use it for representing squares everywhere in the code (including in Node):

class Square
  attr_reader :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end

  def ==(other)
    [self.x, self. y] == [other.x, other.y]
  end

  def to_s
    [self.x, self.y].to_s
  end
end

I already implemented equality (for the comparison in bfs) and to_s (for printing in print_path). Then change Node to use a Square: (also, use attr_reader)

class Node
  attr_reader :square, :parent
  def initialize(square, parent=nil)
    @square = square
    @parent = parent
  end
end

Now replace any [x, y] array in the code with a Square:

# in child_nodes:
square = node.square
...
Square.new(square.x + 2, square.y + 1),
...
space.x.between(0, 8) &&
...
Node.new(space, node)

# in knight_moves:
Node.new(first_square)

# in bfs:
if current.square == search_value

# in print_path:
array << parent.square
array << current.square
puts i # instead of "p i", so to_s is used

# calling knight_moves:
knight_moves(Square.new(2, 5), Square.new(4, 7))

Missing Square methods

Most of child_nodes deals with squares, so most of its functionality should be inside Square methods. The only thing it does that doesn't involve only squares is creating nodes, so it should do just that:

def child_nodes(node)
  node.square.knight_moves.map do |square|
    Node.new(square, node)
  end
end

Square#knight_moves is a new method that returns an array of the squares that can be reached from the current one. It should look something like this:

def knight_moves
  [
    Square.new(self.x + 2, self.y + 1),
    ...
  ].select { |square| square.valid? }
end

This requires adding a Square#valid? to check if a square's coordinates are legal.

Revisiting knight_moves

knights_moves does too little now, it only creates a root node and put it in a one-element array. I would remove it and move its functionality to bfs (Make bfs accept first_square and final_square as arguments, and call it directly).

Seperating logic and printing

Don't print the path in bfs, just return it (the array of squares) and let the main code print it. You can simplify the code for getting the path:

def path_from_root(current)
  array = []
  loop do
    array << current.square
    current = current.parent
    break if current.nil?
  end
  array.reverse
end

StackExchange Code Review Q#110256, answer score: 4