# 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.between?(0,8) &&
space.between?(0,8)
end

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

def knight_moves(first_square,final_square)
first_children = Square.new(first_square,first_square)
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]
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, space, board)
first_child = Node.new(first_square,first_square)

# 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

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
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

• Thank you @Spike. I am still pouring through this but really appreciate you taking the time to offer feedback. – scobo Nov 21 '15 at 15:54