chop.kt

chop.kt

/**
 * You can edit, run, and share this code.
 * play.kotlinlang.org
 */

fun main() {
    val length = readLine()?.toIntOrNull() ?: 0
    val input = mutableListOf<Int>()

    repeat(length) {
            val value = readLine()?.toIntOrNull() ?: 0
            input.add(value)
        }
    //run(length, input)
    run(6, mutableListOf(5,1,1,2,2,7))
    //run(2, mutableListOf(1,2))
}

// time complexicity = O(n^3 + n^2 + n)
fun run(length: Int,input: MutableList<Int>) {
    // for every number we are sure the previous number is connected to it
    var finalTree = mutableListOf<Node>()
    
    // onlyLeafs are the nodes that only have one connection (they're only leafs)
    var onlyLeafs = List(length) { it + 1 }.filterNot { input.contains(it) }.toMutableList()
    // we fill here with used leaf so we know that how many leafs are left to be added
    var onlyLeafsThatAreUsedBefore = mutableSetOf<Int>()
    // for loop = O(n)
    (0 .. length - 1).forEach { index ->
        if (index == 0) {
            finalTree.add(Node(input.last()))
        }
            
        else if (input[length - index - 1] != input [length - index]) {
            
            finalTree.first().connectedNodes.add(input[length - index - 1])
            val temp = finalTree.first()
            finalTree.add(0, Node(input[length - index - 1]))
            finalTree.first().connectedNodes.add(temp.root)
            finalTree.first().numberOfConnection++
            
        } else {
            finalTree.first().numberOfConnection++
        }
    }
    
    // now we need to iterate our tree again and add possbile leafs
    var finalOutPut = mutableListOf<Int>()
    
    var allNumbers = List(length) { it + 1 }.toMutableList()
    val copyOfTheFinalTree = finalTree.toMutableList()
    copyOfTheFinalTree.remove(copyOfTheFinalTree.last())
    
    // the logic behind this while loop is like this :
    // first we see if there're any avaible (free) nodes than can
    // take another leaf or branch, then we'll add that leaf and consider it as the next output
    // but if there's is a node that doesn't have any avaivle spot so we can comprare that node
    // with our remaning leafs, if it's less than them we'll consider that node as next output
    var error = false
    // while loop = O(n * (n^2 + n)) = O(n^3 + n^2)
    while (allNumbers.size != 0 && !error) {
        val allNumbersOldSize = allNumbers.size
        
        var min = onlyLeafs.minOrNull()?:200_001 // max number

        var shouldISkip = false
        // filter + find = O(n^2)
        copyOfTheFinalTree.filter {
                    it.numberOfConnection == 1
                }.minByOrNull  {
                    it.root
                }?.let { min_ ->
                    if (min_.root < min) {
                            finalOutPut.add(min_.root)
                            allNumbers.remove(min_.root)
                            copyOfTheFinalTree.find {
                                it.connectedNodes.contains(min_.root)
                            }?.let {
                                it.connectedNodes.remove(min_.root)
                                it.numberOfConnection--
                            }
                            copyOfTheFinalTree.remove(min_)
                            shouldISkip = true
                     }
                }
        
      	if (shouldISkip) {
            if (allNumbersOldSize == allNumbers.size) error = true // no min ? then it's an error
            continue 
        }
        
        onlyLeafs.remove(min)
        finalOutPut.add(min)
        // O(n)
        copyOfTheFinalTree.find {
            it.connectedNodes.size < it.numberOfConnection
        }?.let {
            it.numberOfConnection-- // we cut one leaf so we'll lose one number
                //it.connectedLeaf.add(min)
        }
        allNumbers.remove(min)
        if (allNumbersOldSize == allNumbers.size) error = true // no min ? then it's an error
    }
    if (error) println("Error")
    else finalOutPut.forEach { println(it) }
    

}

data class Node (
	val root: Int, 
    val connectedNodes: MutableList<Int> = mutableListOf(),
    val connectedLeaf: MutableList<Int> = mutableListOf(), // these are only leaf and not branch
    var numberOfConnection: Int = 1//, var possibleNodes: MutableList<Int> = mutableListOf()
)