Last active
February 14, 2016 17:24
-
-
Save gotohr/fc485a458fe19fca71cd to your computer and use it in GitHub Desktop.
chess jumper problem - find shortest path from A to B
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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