Learn You Scala for Great Good! Part 6

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