Today I want to finish this long talk about Haskell and Scala.  The only thing that  stays in my to-do list is  “A knight’s quest”.

Please look at my previous posts:

Learn You Scala for Great Good!

Learn You Scala for Great Good! Part 2

Learn You Scala for Great Good! Part 3

Learn You Scala for Great Good! Part 4

Learn You Scala for Great Good! Part 5

 

A knight’s quest

Here’s a problem that really lends itself to being solved with non-determinism. Say you have a chess board and only one knight piece on it. We want to find out if the knight can reach a certain position in three moves. We’ll just use a pair of numbers to represent the knight’s position on the chess board. The first number will determine the column he’s in and the second number will determine the row.

Haskell:

    type KnightPos = (Int,Int)

Then the function moveKnight defines all possible moves for this position:

    moveKnight :: KnightPos -> [KnightPos]  
    moveKnight (c,r) = filter onBoard  
        [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)  
        ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)  
        ]  
        where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]  

And, at last, we can solve our problem:

    in3 :: KnightPos -> [KnightPos]  
    in3 start = do   
        first <- moveKnight start  
        second <- moveKnight first  
        moveKnight second  

 

OK! Let’s do the same in Scala. We can determine a case class Position and the companion object for this class. I’m used to use characters from ‘a’ to ‘h’ for chess rows, but not numbers. The method set will help me to define a knight position taking pairs ('a', 1) or ('c', 4).

case class Position (x: Int, y: Int) {
  def getPos = (Position.xCoord(x - 1), y)
}

object Position {
  private val xCoord = ('a' to 'h').toSeq
  def set (x:Char, y: Int):Position = Position (xCoord.indexOf(x) + 1, y)
  def move(p:Position):List[Position] = List(Position(p.x + 2, p.y - 1), Position(p.x + 2, p.y + 1),
   Position(p.x - 2, p.y - 1), Position(p.x - 2, p.y + 1), Position(p.x + 1, p.y - 2), Position(p.x + 1, p.y +2),
   Position(p.x - 1, p.y - 2), Position(p.x - 1, p.y + 2)
 ) filter onBoard


 private def onBoard (p:Position) = 1 <= p.x && p.x <= 8 && 1 <= p.y && p.y <= 8

 def canReachIn3(start:(Char, Int), end: (Char, Int)):Boolean = {
   val s = Position.set(start._1, start._2)
   val e = Position.set(end._1, end._2)
   (for {
     first <- Position move s
     second <- Position move first
     third <- Position move second
   } yield third) contains e

 }
}

 

The method canReachIn3 can tell us if the knight that is placed into the start position reaches the end position in three moves.

val start = ('b', 5)
val end = ('a', 7)

println(Position.canReachIn3(start, end))