fork download
copy 
  1. package knightsmetric
  2.  
  3. fun main(args: Array<String>) {
  4.     println("(0,0) -> (0,0) in ${getMoves(0, 0)} moves")
  5.     println("(0,0) -> (3,7) in ${getMoves(3, 7)} moves")
  6.     println("(0,0) -> (0,1) in ${getMoves(0, 1)} moves")
  7.     println("(0,0) -> (5,3) in ${getMoves(5, 3)} moves")
  8.     println("(0,0) -> (7,4) in ${getMoves(7, 4)} moves")
  9.     println("(0,0) -> (9,9) in ${getMoves(9, 9)} moves")
  10. }
  11.  
  12. data class Node(val id: Int, val parent: Node?, val value: IntArray)
  13.  
  14. fun getMoves(x: Int, y: Int) : Int {
  15.     val root = Node(0, null, intArrayOf(0,0))
  16.     val goal = initGoal(abs(x), abs(y))
  17.  
  18.     return getMovesFromNode(root, goal)
  19. }
  20.  
  21. fun initGoal(x: Int, y: Int) : IntArray = if(x >= y) intArrayOf(x, y) else intArrayOf(y, x)
  22.  
  23. fun getMovesFromNode(source: Node, destination: IntArray) : Int {
  24.     val moves = getMovesList()
  25.     var queue = mutableListOf(source)
  26.     var visited = mutableSetOf<Int>()
  27.     var dist = mutableMapOf<Pair<Int, Int>, Int>()
  28.     var cur = source
  29.     var i = 0
  30.  
  31.     dist.put(Pair(source.id, source.id), 0)
  32.  
  33.     while(!queue.isEmpty()) {
  34.         cur = queue.removeAt(0)
  35.  
  36.         if(coordinateCompare(cur.value, destination)) {
  37.             break
  38.         }
  39.  
  40.         if(!visited.contains(cur.id))  {
  41.             visited.add(cur.id)
  42.             for(move: IntArray in moves) {
  43.                 var nextCoord = coordinateAdd(cur.value, move)
  44.                 var d = (dist.get(Pair(source.id, cur.id)))!!
  45.                 var next = Node(++i, cur, nextCoord)
  46.  
  47.                 if((next.value[0] < -1 || next.value[1] < -1)) {
  48.                     continue
  49.                 }
  50.  
  51.                 queue.add(next)
  52.                 dist.put(Pair(source.id, next.id), ++d)
  53.             }   
  54.         }
  55.     }
  56.     return dist.get(Pair(source.id, cur.id))!!
  57. }
  58.  
  59. fun getMovesList() : Array<IntArray> = arrayOf(
  60.     intArrayOf(1, 2), intArrayOf(2, 1), intArrayOf(-1, 2), 
  61.     intArrayOf(-2, 1), intArrayOf(1, -2), intArrayOf(2, -1)
  62. )
  63.  
  64. fun abs(a: Int) : Int = if(a < 0) a * -1 else a
  65. fun coordinateCompare(a: IntArray, b: IntArray) : Boolean = a[0] == b[0] && a[1] == b[1]
  66. fun coordinateAdd(a: IntArray, b: IntArray) : IntArray = intArrayOf(a[0] + b[0], a[1] + b[1])
Success #stdin #stdout 0.14s 4382720KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
(0,0) -> (0,0) in 0 moves
(0,0) -> (3,7) in 4 moves
(0,0) -> (0,1) in 3 moves
(0,0) -> (5,3) in 4 moves
(0,0) -> (7,4) in 5 moves
(0,0) -> (9,9) in 6 moves
https://ideone.com/ADr8sQ
language:
Kotlin (kotlin 1.3.21)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!