The power of generic algorithms

In computer science, there is this tension between creating generic algorithms applicable to different situations and optimising an algorithm to solve a specific problem.

Generic algorithms make it possible to find similarities between problems that, at first glance, may seem completely unrelated. This is especially interesting when those problems belong to different domains. When this happens, the nature of the problem is better understood and ideas from one domain can be transferred to another.

However, algorithms need to be executed in physical machines and therefore limitations of time and space must be taken into account. Unfortunately, many optimised algorithms have little resemblance to its generic version. In a way, information is lost when moving from a generic algorithm to its optimised version.

The aim of this post is to illustrate the use of a generic algorithm to solve problems as disparate as:

  • chess knight problem: given a chessboard, find the shortest distance (minimum number of steps) to move a knight from a square to another.
  • problem of the knight’s tour: find the sequence of moves of a knight on a chessboard such that the knight visits every square only once
  • minimum coin change: find the minimum number of coins (of certain denominations) that add up to a given amount of money
  • representation of an integer in base -2: instead of the normal binary base (2), it’s possible to use negative bases like -2

Graph representation

In order to solve these problems, we will use a common representation for all of them, namely: a graph. Therefore, the first step will be to define a way to traverse the graph.

 

trait GraphTraversal[T] {

  type Vertex = T
  //Path to a Vertex
  type Path = List[Vertex]

  def findPath(from: Seq[Path]): Path = {

    val paths: ListBuffer[Path] = ListBuffer() ++= from

    def next(): Path = paths.headOption match{
      case None => Nil
      case Some(currentVertexPath) =>
        if(isSolution(currentVertexPath)) currentVertexPath.reverse
        else {
          val currentVertex = currentVertexPath.head
          val neighbourVertices = neighbours(currentVertex).filter(isVertexEligibleForPath(_, currentVertexPath))
          val pathsToNeighbourVertices = neighbourVertices.map(_ :: currentVertexPath)
          paths.remove(0)
          addNeighbours(paths, pathsToNeighbourVertices)
          next()
        }
    }
    next()
  }

  def neighbours(vertex: Vertex): Seq[Vertex]
  def addNeighbours(verticesToExplore: ListBuffer[Path], neighbours: Seq[Path]): Unit
  def isSolution(path: Path): Boolean
  def isVertexEligibleForPath(vertex: Vertex, path: Path): Boolean

 

The method findPath, starting at the vertices from, traverses the graph and as it does so, builds all possible paths until finding the solution as per the definition of the method isSolution. This method defines the condition to be met by the path, e.g. the path must pass through an specific vertex or through all the vertices.

The process to calculate the neighbours of a given vertex depends on the topology (“shape”) of the graph and is implemented by the method neighbours.

The method isVertexEligibleForPath filters the neighbours that are eligible to be included in a path (for instance, in most cases it is desirable not to visit twice the same vertex and consequently vertices already visited are discarded).

The method addNeighbours adds the neighbours of the current vertex to the list of remaining vertices to explore and determines the way the graph is traversed: depth-first or breadth-first (depending on whether the new vertices are added at the front or at the back of the list, respectively)

 

Again, I cannot stress enough that the implementation of findPath is very generic and therefore sub-optimal for the problems mentioned above.

 

The following sections show how to solve said problems.

Before getting started, here’s some definitions that will be needed later on:

type Coin = Int
type Coordinate = (Int, Int)

implicit class RichTuple2(coordinate: Coordinate){
  def +(other: Coordinate) = (coordinate._1 + other._1, coordinate._2 + other._2)
  def -(other: Coordinate) = (coordinate._1 - other._1, coordinate._2 - other._2)
}

 

Chess knight problem

Probably, this is the most intuitive of the problems as it is easy to imagine the chessboard like a graph where the squares are the vertices that are connected by the moves of the knight. With this in mind, we can represent an infinite chessboard like:

trait InfiniteChessBoard extends GraphTraversal[Coordinate]{

  //knight moves
  val moves: List[Coordinate] = List((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))

  override def neighbours(coordinate: Coordinate): Seq[Coordinate] = moves.map( coordinate + _)

  /**
    * The shortest path cannot include the same vertex twice
    */
  override def isVertexEligibleForPath(vertex: Coordinate, path: Path): Boolean = !path.contains(vertex)
}

 

The remaining methods are defined in another trait describing the nature of the problem:

  • the method addNeighbours must implement a breadth-first search in order to find the shortest path
  • the method isSolution ensures that the solution path contains the destination
trait ShortestPath extends GraphTraversal[Coordinate]{

  self: Destination[Coordinate] =>

  override def addNeighbours(verticesToExplore: ListBuffer[Path], neighbours: Seq[Path]): Unit =
    verticesToExplore ++= neighbours

  override def isSolution(path: Path): Boolean = path.head == to
}

trait Destination[T]{
  def to(): T
}

 

Finally, the class implementing the solution can be defined by stacking all these traits:

case class ShortestPathInInfiniteBoard(to: Coordinate) extends InfiniteChessBoard with ShortestPath with Destination[Coordinate]

 

Example:

test("shortest path between (0,0) -> (3,3)"){
  val from = (0,0)
  val to = (3,3)
  val solution = List((0,0), (2,1), (3,3))
  assert(ShortestPathInInfiniteBoardApp(to).findPath(List(List(from))) == solution)
}

 

Knight’s tour

The first thing to consider here is that the chessboard must be finite, what can be achieved by overwriting the trait InfiniteChessBoard to restrict the moves of the knight to the dimensions of the board. The original implementation of isVertexEligibleForPath is still valid as the knight’s path cannot visit the same square twice.

trait FiniteChessBoard extends InfiniteChessBoard{

  self: BoardDim =>

  override def neighbours(coordinate: Coordinate): Seq[Coordinate] =
    super.neighbours(coordinate).filter{ case (v, w) => v >= 0 && v<x && w >=0 && w<y }
}

trait BoardDim{
  def x(): Int
  def y(): Int
}

 

The nature of the problem is represented by the following trait:

  • the traversal of the graph is done in a depth-first fashion
  • the solution is the path that visits all vertices
trait KnightTour extends GraphTraversal[Coordinate]{

  self: FiniteChessBoard with BoardDim =>

  override def addNeighbours(verticesToExplore: ListBuffer[Path], neighbours: Seq[Path]): Unit =
    verticesToExplore.prependAll(neighbours) //depth-first search

  override def isSolution(path: Path): Boolean = path.length == x * y
}

 

Finally, the solution is

case class KnightTourInFiniteBoard(x: Int, y: Int) extends KnightTour with FiniteChessBoard with BoardDim

 

Example:

test("tour in a board of dimensions (8,8) starting at (0,0)"){
  val dim = (8,8)
  val from = (0,0)
  val solution = List((0,0), (2,1), (4,2), (6,3), (7,5), (6,7), (4,6), (2,7), (0,6), (1,4), (3,5), (5,6), (7,7), (6,5), (5,7), (3,6), (1,7), (0,5), (2,6), (4,7), (5,5), (7,6), (6,4), (4,5), (6,6), (5,4), (3,3), (2,5), (3,7), (1,6), (0,4), (1,2), (2,4), (0,3), (1,1), (3,0), (2,2), (1,0), (0,2), (2,3), (4,4), (3,2), (4,0), (6,1), (7,3), (5,2), (7,1), (5,0), (3,1), (4,3), (5,1), (7,0), (6,2), (7,4), (5,3), (7,2), (6,0), (4,1), (2,0), (0,1), (1,3), (3,4), (1,5), (0,7))
  assert(KnightTourInFiniteBoardApp(dim._1, dim._2).findPath(List(List(from))) == solution)
}

 

Minimum coin change problem

Surprisingly, or maybe not if you are familiar with this problem, the optimal change can be represented as a graph. Each vertex represents the face value of a coin and the solution is a path such that the sum of its vertices equals the original amount. For instance, for a set of coins [1,4,6], the amount 8 is represented by the path 0 -> 4 -> 4

Optimal change graph representation
Optimal change graph representation

 

After the picture, it’s easy to implement GraphTraversal

trait OptimalChange extends GraphTraversal[Coin]{

  self: Coins with Amount =>

  val moves: List[Coin] = coins

  override def neighbours(vertex: Int): Seq[Vertex] = moves

  /**
    * The nature of the problem requires a breadth-first search in order to find the shortest path (minimum number of coins)
    */
  override def addNeighbours(verticesToExplore: ListBuffer[Path], neighbours: Seq[Path]): Unit =
    verticesToExplore ++= neighbours

  override def isSolution(path: Path): Boolean = amount == path.sum

  override def isVertexEligibleForPath(vertex: Int, path: Path): Boolean = (amount - path.sum) >= vertex
}

trait Coins {
  def coins(): List[Coin]
}

trait Amount {
  def amount(): Int
}

 

And the solution is

class OptimalChangeApp(val coins: List[Coin], val amount: Int) extends OptimalChange with Coins with Amount{
  def optimalChange() = findPath(List(List(0))) match{
    case Nil => Nil
    case xs => xs.tail //to remove the first 0
  }
}

 

Example:

test("change of 8 with set of coins (1,4,6)"){
  assert(OptimalChangeApp(List(1,4,6),8).optimalChange() == List(4,4))
}

 

Representation of an integer in base -2

In base -2, integers are represented by sequences of bits in the following way. Sequence S of N bits represents the number

\sum_{j=0}^{N-1}{S_j(-2)^j}

For instance,

-9 = 1 * (-2)^0 + 1 * (-2)^1 + 0 * (-2)^2 + 1 * (-2)^3

Negative binary base graph representation
Negative binary base graph representation

 

trait NegativeBinary extends GraphTraversal[Int]{

  self: Amount =>

  val moves: List[Int] = List(0, 1)

  override def neighbours(vertex: Vertex): Seq[Vertex] = moves

  override def addNeighbours(verticesToExplore: ListBuffer[Path], neighbours: Seq[Path]): Unit =
    verticesToExplore ++= neighbours

  override def isSolution(path: Path): Boolean =
    path.reverse.zipWithIndex.foldLeft(0){case (acc, (vertex, idx)) => acc + vertex * BigInt(-2).pow(idx).toInt} == amount

  override def isVertexEligibleForPath(vertex: Vertex, path: Path): Boolean = true
}

trait Amount {
  def amount(): Int
}

 

And the solution is

class NegativeBinaryApp(val amount: Int) extends NegativeBinary with Amount{

  def findShortestBinaryRepresentation() = findPath(List(List(0),List(1)))
}

 

Example:

test("-9 == {1,1,0,1}"){
  val number = -9
  assert(NegativeBinaryApp(number).findShortestBinaryRepresentation() == List(1,1,0,1))
}

 

The code of all the examples presented in this post can be found on https://github.com/falvarezb/blog-bytecode/tree/graphs

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.