class Graph(val grid: List<String>) {
    private val rows = grid.size
    private val cols = grid[0].length
    private val overlapX = cols - 1
    private val overlapY = rows - 1
    private val up = Pair(0, -1)
    private val down = Pair(0, 1)
    private val left = Pair(-1, 0)
    private val right = Pair(1, 0)
    val floors = mutableSetOf<Pair<Int, Int>>()
    val neighbors = mutableMapOf<Pair<Int,Int>, MutableList<Pair<Int, Int>>>()

    init {
        fillGraph()
    }

    private fun constrainX(x: Int) =
            when {
                x < 0 -> overlapX
                x > overlapX -> 0
                else -> x
            }
    private fun constrainY(y: Int) =
            when {
                y < 0 -> overlapY
                y > overlapY -> 0
                else -> y
            }

    private fun addToTheGraph(floorPoint: Pair<Int, Int>, dir: Pair<Int, Int>) {
        val x = floorPoint.first
        val y = floorPoint.second
        val newPair = Pair(constrainX(x + dir.first), constrainY(y + dir.second))
        if (grid[newPair.second][newPair.first] != ' ')
            return
        neighbors[floorPoint]!!.add(newPair)
    }

    private fun fillGraph() {
        grid.forEachIndexed { y, row ->
            row.forEachIndexed x@{ x, value ->
                if (value == '#')
                    return@x
                val floorPoint = Pair(x, y)
                floors.add(floorPoint)
                neighbors[floorPoint] = mutableListOf()
                addToTheGraph(floorPoint, up)
                addToTheGraph(floorPoint, down)
                addToTheGraph(floorPoint, left)
                addToTheGraph(floorPoint, right)
            }
        }
    }

    fun bfs(start: Pair<Int, Int>, end: Pair<Int, Int>) : Int {
        val queue = mutableListOf<Pair<Int, Int>>()
        val visited = mutableListOf<Pair<Int, Int>>()
        queue.add(start)
        visited.add(start)
        val parents = mutableMapOf<Pair<Int, Int>, Pair<Int, Int>>()
        while (queue.isNotEmpty()) {
            val current = queue.removeAt(0)
            if (current == end)
                return countParents(current, parents)
            neighbors[current]?.forEach {
                if (!visited.contains(it)) {
                    queue.add(it)
                    visited.add(it)
                    parents[it] = current
                }
            }
        }
        return 0
    }


    fun distanceMatrix() : Map<Pair<Int, Int>, Map<Pair<Int, Int>, Int>> {
        val map = mutableMapOf<Pair<Int, Int>, MutableMap<Pair<Int, Int>, Int>>()
        var skipped = 0
        var calculated = 0
        var precalculated = 0
        floors.forEach { start ->
            map[start] = mutableMapOf()
            floors.forEach { end ->
                if (start != end) {
                    if (map[end] != null) {
                        map[start]!![end] = map[end]!![start]!!
                        skipped++
                    } else {
                        val myNeighbors = neighbors[end]!!
                        val neighborsToStart = myNeighbors.mapNotNull { n -> map[start]!![n] }
                        if (neighborsToStart.isEmpty() || neighborsToStart.size < myNeighbors.size) {
                            map[start]!![end] = bfs(start, end)
                        } else {
                            val shortest = neighborsToStart.min()!!
                            map[start]!![end] = shortest + 1
                            precalculated += 1
                        }
                        calculated++
                    }
                }
            }
        }
        println("Skipped: $skipped")
        println("Calculated: $calculated")
        println("Pre-calculated: $precalculated")
        /**
        map.forEach { e ->
            e.value.forEach {
                println("Distance between ${e.key} to ${it.key}: ${it.value}")
            }
        }**/
        return map
    }

    private fun countParents(start: Pair<Int, Int>, parents: Map<Pair<Int, Int>, Pair<Int, Int>>) : Int {
        var count = 0
        var parent = parents[start]
        while (parent != null) {
            count++
            parent = parents[parent]
        }
        return count
    }


}