dadsd

fun baldaSearcher(inputName: String, words: Set<String>): Set<String> {
    val root = TrieNode()
    val dictionary = arrayOfNulls<String>(words.size)
    set = TreeSet()
    var jindex = 0
    for (word in words) {
        dictionary[jindex] = word
        jindex++
    }
    val n = words.size
    for (i in 0 until n)
        insert(root, dictionary[i]!!)

    val listOfLetters = ArrayList<String>()
    val file = File(inputName).readLines()
    for (line in file) {
        listOfLetters.add(line)
    }
    val height = listOfLetters.size
    val width = listOfLetters[0].split(" ".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray().size
    M = height
    N = width
    val arrayOfLetters = Array(height) { CharArray(width) }
    for (i in 0 until height) {
        val stringLetters = listOfLetters[i].split(" ".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray()
        for (j in 0 until width) {
            arrayOfLetters[i][j] = stringLetters[j][0]
        }
    }

    findWords(arrayOfLetters, root)

    return set
}

// Alphabet size
internal val SIZE = 100000

internal var M: Int = 0
internal var N: Int = 0
internal var set: MutableSet<String> = TreeSet()

// trie Node
internal class TrieNode {
    var child = arrayOfNulls<TrieNode>(SIZE)

    // isLeaf is true if the node represents
    // end of a word
    var leaf: Boolean = false

    //constructor
    init {
        leaf = false
        for (i in 0 until SIZE)
            child[i] = null
    }
}

// If not present, inserts a key into the trie
// If the key is a prefix of trie node, just
// marks leaf node
internal fun insert(root: TrieNode, Key: String) {
    val n = Key.length
    var pChild = root

    for (i in 0 until n) {
        val index = Key[i] - 'A'

        if (pChild.child[index] == null)
            pChild.child[index] = TrieNode()

        pChild = pChild.child[index]!!
    }

    // make last node as leaf node
    pChild.leaf = true
}

// function to check that current location
// (i and j) is in matrix range
internal fun isSafe(i: Int, j: Int, visited: Array<BooleanArray>): Boolean {
    return i >= 0 && i < M && j >= 0 &&
            j < N && !visited[i][j]
}

// A recursive function to print all words present on boggle
internal fun searchWord(
    root: TrieNode, boggle: Array<CharArray>, i: Int,
    j: Int, visited: Array<BooleanArray>, str: String
) {
    // if we found word in trie / dictionary
    if (root.leaf)
        set.add(str)

    // If both I and j in  range and we visited
    // that element of matrix first time
    if (isSafe(i, j, visited)) {
        // make it visited
        visited[i][j] = true

        // traverse all child of current root
        for (K in 0 until SIZE) {
            if (root.child[K] != null) {
                // current character
                val ch = (K + 'A'.toInt()).toChar()

                // Recursively search reaming character of word
                // in trie for all 8 adjacent cells of
                // boggle[i][j]
                if (isSafe(i, j + 1, visited) && boggle[i][j + 1] == ch)
                    searchWord(
                        root.child[K]!!, boggle, i, j + 1,
                        visited, str + ch
                    )
                if (isSafe(i + 1, j, visited) && boggle[i + 1][j] == ch)
                    searchWord(
                        root.child[K]!!, boggle, i + 1, j,
                        visited, str + ch
                    )
                if (isSafe(i, j - 1, visited) && boggle[i][j - 1] == ch)
                    searchWord(
                        root.child[K]!!, boggle, i, j - 1,
                        visited, str + ch
                    )
                if (isSafe(i - 1, j, visited) && boggle[i - 1][j] == ch)
                    searchWord(
                        root.child[K]!!, boggle, i - 1, j,
                        visited, str + ch
                    )
            }
        }

        // make current element unvisited
        visited[i][j] = false
    }
}

// Prints all words present in dictionary.
internal fun findWords(boggle: Array<CharArray>, root: TrieNode) {
    // Mark all characters as not visited
    val visited = Array(M) { BooleanArray(N) }

    var str = ""

    // traverse all matrix elements
    for (i in 0 until M) {
        for (j in 0 until N) {
            // we start searching for word in dictionary
            // if we found a character which is child
            // of Trie root
            if (root.child[boggle[i][j] - 'A'] != null) {
                str += boggle[i][j]
                searchWord(
                    root.child[boggle[i][j] - 'A']!!,
                    boggle, i, j, visited, str
                )
                str = ""
            }
        }
    }
}


//TEST
assertEquals(
            setOf("ТРАВА", "КРАН", "АКВА", "НАРТЫ"),
            baldaSearcher("input/balda_in1.txt", setOf("ТРАВА", "КРАН", "АКВА", "НАРТЫ", "РАК"))
        )
        assertEquals(
            setOf("БАЛДА"),
            baldaSearcher("input/balda_in2.txt", setOf("БАЛАБОЛ", "БАЛДА", "БАЛДАЗАВР"))
        )
        assertEquals(
            setOf(
                "АПЕЛЬСИН", "МАРОККО", "ПЕРЕМЕНЫ", "ГРАВИТАЦИЯ",
                "РАССУДИТЕЛЬНОСТЬ", "КОНСТАНТИНОПОЛЬ", "ПРОГРАММИРОВАНИЕ", "ПОМЕХОУСТОЙЧИВОСТЬ", "АППРОКСИМАЦИЯ",
                "ЭЙНШТЕЙН"
            ),
            baldaSearcher(
                "input/balda_in3.txt", setOf(
                    "АПЕЛЬСИН", "МАРОККО", "ЭФИОПИЯ", "ПЕРЕМЕНЫ", "ГРАВИТАЦИЯ",
                    "РАССУДИТЕЛЬНОСТЬ", "БЕЗРАССУДНОСТЬ", "КОНСТАНТИНОПОЛЬ", "СТАМБУЛ", "ПРОГРАММИРОВАНИЕ",
                    "ПРОСТРАНСТВО", "ДИАЛЕКТИКА", "КВАЛИФИКАЦИЯ", "ПОМЕХОУСТОЙЧИВОСТЬ", "КОГЕРЕНТНОСТЬ",
                    "АППРОКСИМАЦИЯ", "ИНТЕРПОЛЯЦИЯ", "МАЙЕВТИКА", "ШРЕДИНГЕР", "ЭЙНШТЕЙН"
                )
            )
        )
        assertEquals(
            setOf("ДОБРЫЙДЕНЬ", "ДЕНЬ", "ДА", "МЕНЯ", "УТРОМ", "ЭС"),
            baldaSearcher(
                "input/balda_in4.txt",
                setOf(
                    "СТВОРКА",
                    "ДОБРЫЙДЕНЬ",
                    "ДА",
                    "МЕНЯ",
                    "УТРОМ",
                    "МЕРА",
                    "МОРТИ",
                    "ЭС",
                    "ХЕЛЛОУ",
                    "ДЕНЬ"
                )
            )
        )
        assertEquals(
            setOf("AQUA", "BUACHA", "COSMIC", "FAOWC", "KERTNOW", "KNOW", "NOW", "ROW", "WORWON"),
            baldaSearcher(
                "input/balda_in5.txt",
                setOf(
                    "AQUA",
                    "BUACHA",
                    "KERTNOW",
                    "MUST",
                    "NOW",
                    "TEST",
                    "ABUHCA",
                    "KNOW",
                    "ROW",
                    "WORWON",
                    "COSMIC",
                    "FAOWC",
                    "FHOOC"
                )
            )
        )