class Solution {
    companion object {
        private val DIRECTIONS: List<List<Int>> =
            listOf(
                listOf(1, 3),
                listOf(0, 2, 4),
                listOf(1, 5),
                listOf(0, 4),
                listOf(1, 3, 5),
                listOf(2, 4),
            )
        private val TARGET: String = "123450"

        private fun swap(
            board: String,
            i: Int,
            j: Int,
        ): String {
            val cells = board.toMutableList()

            val tmp = cells[i]
            cells[i] = cells[j]
            cells[j] = tmp

            return cells.joinToString(separator = "")
        }
    }

    fun slidingPuzzle(board: Array<IntArray>): Int {
        val startState =
            board.flatMap { it.asSequence() }.joinToString(separator = "") {
                it.toString()
            }

        val seen = mutableSetOf<String>(startState)
        val queue = ArrayDeque<String>(listOf(startState))

        var moves = 0
        while (queue.isNotEmpty()) {
            for (i in 1..queue.size) {
                val current = queue.removeFirst()
                if (current == TARGET) {
                    return moves
                }

                val zeroIdx = current.indexOf('0')
                DIRECTIONS[zeroIdx].forEach {
                    val next = swap(current, zeroIdx, it)
                    if (seen.contains(next)) {
                        return@forEach
                    }

                    seen.add(next)
                    queue.addLast(next)
                }
            }

            moves += 1
        }

        return -1
    }
}