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

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

For instance,

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

4931total visits,10visits today