Skip to content

Instantly share code, notes, and snippets.

@gotohr
Last active February 14, 2016 17:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gotohr/fc485a458fe19fca71cd to your computer and use it in GitHub Desktop.
Save gotohr/fc485a458fe19fca71cd to your computer and use it in GitHub Desktop.
chess jumper problem - find shortest path from A to B
case class Position(x:Int, y:Int) {
def posibleMove(p:Position) = Position(this.x + p.x, this.y + p.y)
def distance(p:Position) = {
Math.sqrt(
Math.pow(Math.abs(p.x - this.x).toDouble, 2)
+ Math.pow(Math.abs(p.y - this.y).toDouble, 2)
)
}
def equal(p: Position) = this.x == p.x && this.y == p.y
def oddCase(t: Position) = {
(Math.abs(this.x - t.x) == 1 && this.y == t.y) ||
(Math.abs(this.y - t.y) == 1 && this.x == t.x)
}
def sameAxis(t: Position) = this.y == t.y || this.x == t.x
}
trait Figure {
val start: Position
val target: Position
def isOnBoard(p:Position) = p.x > 0 && p.x < 9 && p.y > 0 && p.y < 9
}
case class Jumper(
start: Position
, target: Position
) extends Figure {
var positions: List[Position] = start :: Nil
val deltas = Seq(
Position(1, 2), Position(2, 1)
, Position(2, -1), Position(1, -2)
, Position(-1, -2), Position(-2, -1)
, Position(-2, 1), Position(-1, 2)
)
def availableMoves(pos: Position): Seq[Position] = {
deltas
.map(pos.posibleMove)
.filter(isOnBoard)
.filter(p => !positions.contains(p))
.sortWith(
(p1, p2) => p1.distance(target) < p2.distance(target)
)
}
def onDestination = positions.head.equals(target)
}
object Chess extends App {
val target = Position(4, 3)
val j = Jumper(Position(1, 1), target)
var cnt = 0
import scala.util.control.Breaks._
breakable {
while(!j.onDestination) {
val moves = j.availableMoves(j.positions.head)
// is next closest near target and on same axis?
val nextPosition = if (moves.head.oddCase(target))
moves.tail
// select next posible move that is not on same axis
.find(p => !p.sameAxis(target))
// take that move or go with first next to closest
.getOrElse(moves.tail.head)
else moves.head
j.positions = nextPosition :: j.positions
cnt += 1
if (cnt >= 100) break
}
}
j.positions.reverse.foreach(println)
println(cnt)
}
/*
(1, 1) -> (2, 1)
8
7
6
5
4
3zxy
2y zx
1SEx z
12345678
*/
/*
(1, 1) -> (3, 1)
8
7
6
5
4
3 x
2 x
1S E x
12345678
*/
/*
(1, 1) -> (4, 1)
8
7
6
5
4
3 x
2 x
1S E
12345678
*/
/*
(1, 1) -> (4, 2)
8
7
6
5
4
3 x
2 E
1S
12345678
*/
/*
(1, 1) -> (4, 3)
8
7
6
5
4
3 E
2 x
1S x
12345678
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment