package knightsmetric

fun main(args: Array<String>) {
    println("(0,0) -> (0,0) in ${getMoves(0, 0)} moves")
    println("(0,0) -> (3,7) in ${getMoves(3, 7)} moves")
    println("(0,0) -> (0,1) in ${getMoves(0, 1)} moves")
    println("(0,0) -> (5,3) in ${getMoves(5, 3)} moves")
    println("(0,0) -> (7,4) in ${getMoves(7, 4)} moves")
    println("(0,0) -> (9,9) in ${getMoves(9, 9)} moves")
}

data class Node(val id: Int, val parent: Node?, val value: IntArray)

fun getMoves(x: Int, y: Int) : Int {
    val root = Node(0, null, intArrayOf(0,0))
    val goal = initGoal(abs(x), abs(y))

    return getMovesFromNode(root, goal)
}

fun initGoal(x: Int, y: Int) : IntArray = if(x >= y) intArrayOf(x, y) else intArrayOf(y, x)

fun getMovesFromNode(source: Node, destination: IntArray) : Int {
    val moves = getMovesList()
    var queue = mutableListOf(source)
    var visited = mutableSetOf<Int>()
    var dist = mutableMapOf<Pair<Int, Int>, Int>()
    var cur = source
    var i = 0

    dist.put(Pair(source.id, source.id), 0)

    while(!queue.isEmpty()) {
        cur = queue.removeAt(0)

        if(coordinateCompare(cur.value, destination)) {
            break
        }

        if(!visited.contains(cur.id))  {
            visited.add(cur.id)
            for(move: IntArray in moves) {
                var nextCoord = coordinateAdd(cur.value, move)
                var d = (dist.get(Pair(source.id, cur.id)))!!
                var next = Node(++i, cur, nextCoord)

                if((next.value[0] < -1 || next.value[1] < -1)) {
                    continue
                }

                queue.add(next)
                dist.put(Pair(source.id, next.id), ++d)
            }   
        }
    }
    return dist.get(Pair(source.id, cur.id))!!
}

fun getMovesList() : Array<IntArray> = arrayOf(
    intArrayOf(1, 2), intArrayOf(2, 1), intArrayOf(-1, 2), 
    intArrayOf(-2, 1), intArrayOf(1, -2), intArrayOf(2, -1)
)

fun abs(a: Int) : Int = if(a < 0) a * -1 else a
fun coordinateCompare(a: IntArray, b: IntArray) : Boolean = a[0] == b[0] && a[1] == b[1]
fun coordinateAdd(a: IntArray, b: IntArray) : IntArray = intArrayOf(a[0] + b[0], a[1] + b[1])