// В тексте нет слов, начинающихся одинаковыми буквами. Напечатать слова текста в таком порядке, чтобы последняя буква
// каждого слова совпадала с первой буквой последующего слова. Если все слова нельзя напечатать в таком порядке, найти
// такую цепочку, состоящую из наибольшего количества слов.

// The WordChainFinder class takes a list of words and finds the longest word chain
class WordChainFinder(private val words: List<String>) {

    // A recursive method to find a word chain given a current chain and a list of remaining words
    private fun findWordChain(currentChain: List<String>, remainingWords: List<String>): List<String> {
        // If there are no remaining words, return the current chain
        if (remainingWords.isEmpty()) {
            return currentChain
        }

        // Get the last letter of the last word in the current chain
        val lastLetter = currentChain.last().last()

        // Find the candidate words in the remaining words that start with the last letter of the current chain
        val candidates = remainingWords.filter { it.first() == lastLetter }

        // If there are no candidates, return the current chain
        if (candidates.isEmpty()) {
            return currentChain
        }

        // For each candidate word, extend the current chain with the candidate and remove it from the remaining words
        val chains = candidates.map { candidate ->
            val newRemainingWords = remainingWords.toMutableList().apply { remove(candidate) }
            findWordChain(currentChain + candidate, newRemainingWords)
        }

        // Return the longest chain found among the chains extended with the candidates
        return chains.maxByOrNull { it.size } ?: currentChain
    }

    // The findLongestWordChain method finds the longest word chain by starting a search from each word in the list
    fun findLongestWordChain(): List<String> {
        return words.map { word ->
            val remainingWords = words.toMutableList().apply { remove(word) }
            findWordChain(listOf(word), remainingWords)
        }.maxByOrNull { it.size } ?: emptyList()
    }
}

fun task1V3() {
    // Provide an example input text
    val text = "java android kotlin rust"

    // Split the input text into words
    val words = text.split(" ")

    // Create a WordChainFinder object with the list of words
    val wordChainFinder = WordChainFinder(words)

    // Call the findLongestWordChain method to find the longest chain of words
    val longestWordChain = wordChainFinder.findLongestWordChain()

    // Print the longest word chain to the console
    println("Longest word chain: ${longestWordChain.joinToString(", ")}")
}
// В тексте нет слов, начинающихся одинаковыми буквами. Напечатать слова текста в таком порядке, чтобы последняя буква
// каждого слова совпадала с первой буквой последующего слова. Если все слова нельзя напечатать в таком порядке, найти
// такую цепочку, состоящую из наибольшего количества слов.

// The WordChainFinder class takes a list of words and finds the longest word chain
class WordChainFinder(private val words: List<String>) {

    // A recursive method to find a word chain given a current chain and a list of remaining words
    private fun findWordChain(currentChain: List<String>, remainingWords: List<String>): List<String> {
        // If there are no remaining words, return the current chain
        if (remainingWords.isEmpty()) {
            return currentChain
        }

        // Get the last letter of the last word in the current chain
        val lastLetter = currentChain.last().last()

        // Find the candidate words in the remaining words that start with the last letter of the current chain
        val candidates = remainingWords.filter { it.first() == lastLetter }

        // If there are no candidates, return the current chain
        if (candidates.isEmpty()) {
            return currentChain
        }

        // For each candidate word, extend the current chain with the candidate and remove it from the remaining words
        val chains = candidates.map { candidate ->
            val newRemainingWords = remainingWords.toMutableList().apply { remove(candidate) }
            findWordChain(currentChain + candidate, newRemainingWords)
        }

        // Return the longest chain found among the chains extended with the candidates
        return chains.maxByOrNull { it.size } ?: currentChain
    }

    // The findLongestWordChain method finds the longest word chain by starting a search from each word in the list
    fun findLongestWordChain(): List<String> {
        return words.map { word ->
            val remainingWords = words.toMutableList().apply { remove(word) }
            findWordChain(listOf(word), remainingWords)
        }.maxByOrNull { it.size } ?: emptyList()
    }
}

fun task1V3() {
    // Provide an example input text
    val text = "java android kotlin rust"

    // Split the input text into words
    val words = text.split(" ")

    // Create a WordChainFinder object with the list of words
    val wordChainFinder = WordChainFinder(words)

    // Call the findLongestWordChain method to find the longest chain of words
    val longestWordChain = wordChainFinder.findLongestWordChain()

    // Print the longest word chain to the console
    println("Longest word chain: ${longestWordChain.joinToString(", ")}")
}