TreeChoping.kt

TreeChoping.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(7, mutableListOf(5,1,1,2,2,7))
    run(length, input)


}


fun run(length: Int,input: MutableList<Int>) {
    try{
      // create a tree based on our numbers (it only contains some of the nodes)
        val tempNode = input.toMutableList()
        var nodes = mutableListOf<Node>()
        tempNode.sort()
        tempNode.forEachIndexed { index , number ->
            if (index == 0) {
                nodes.add(Node(number,mutableListOf<Int>()))
            } else if (nodes.last().root != number) {
                                nodes.add(Node(number,mutableListOf<Int>()))
            } else if (tempNode[index - 1] == number) {
              // if the number is repeated then it has more than 1 leaf
                nodes.last().numberOfConnection++
            }
        }
        
        // the last number in input get one extra value for numberOfConnection so it needs to be decreased
        for (node in nodes) {
            if (input.last() == node.root) {
                node.numberOfConnection--
                break
            }
        }
        
        val tempSet = input.toSet()
        //println(tempSet)

        tempSet.forEach { i ->
            val temp = nodes.find { it ->
                it.root == i
            }
            nodes.remove(temp)
            nodes.add(0, temp!!)
        }
        
        // these are nodes that must have at least one leaf
        var previousNodes = mutableListOf<Int>()
        // these are only leafs
        var onlyLeafs = mutableSetOf<Int>()
        var onlyLeafsThatAreUsedBefore = mutableSetOf<Int>()
        for (n in 1 .. length) onlyLeafs.add(n)
        input.forEach {
            if(onlyLeafs.contains(it))
            	onlyLeafs.remove(it)
        }
        //println(onlyLeafs)

        nodes[0].leafs.add(nodes[1].root)
        //nodes = nodes.reversed().toMutableList()
        // every node has some potantional candidate for being its leaf and it's called possibleLeafs
        nodes.forEachIndexed { index, node ->
            previousNodes.add(node.root)
            if (index != 0) {
                if (index != nodes.size-1)
                	node.leafs.add(nodes[index+1].root)
                for (n in 1 .. 6) {
                    var canBeAdded = true
                    nodes.forEach { node_ ->
                        if (node_.root == n) canBeAdded = false
                    }
                    if (canBeAdded) node.possibleLeafs.add(n)
                }
            }
        }
        
        nodes = nodes.reversed().toMutableList()
        nodes.forEachIndexed { index, node ->
            while(node.leafs.size < node.numberOfConnection-1) {
                val min = node.possibleLeafs.minOrNull()!!
                if (!onlyLeafsThatAreUsedBefore.contains(min)) {
                    node.leafs.add(min)
                    node.onlyLeafs.add(min)
               		onlyLeafsThatAreUsedBefore.add(min)
            		onlyLeafs.remove(min)
              	 	//println(onlyLeafs)
             	    //println(nodes)
                }
            	node.possibleLeafs.remove(min)
            }
            if (index != nodes.size -1) {
                node.leafs.add(nodes[index+1].root)
            }
            	
        }
        //printImportantThings(nodes)
        
        // now we have the original tree so we can start to cut the smaller leafs
        
        var finalOutput = mutableListOf<Int>()
        val tempNodess = nodes.toMutableList()
        while (finalOutput.size < length-1) {
            //printImportantThings(tempNodess)
            //println("\n-------------\n")
            
            var minOnlyLeaf = length + 1
            var nodeToChange: Node? = null
            
            tempNodess.forEach { node ->
                if (node.onlyLeafs.isEmpty() && node.leafs.size == 1) {
                   if (node.root < minOnlyLeaf) {
                        minOnlyLeaf = node.root
                        nodeToChange = node
                    }
                }
                node.onlyLeafs.minOrNull()?.let {
               	    if (it < minOnlyLeaf) {
                        minOnlyLeaf = it
                        nodeToChange = node
                    }
              	}
           	}
            if (nodeToChange!!.onlyLeafs.isEmpty() && nodeToChange!!.leafs.size == 1) tempNodess.remove(nodeToChange!!)
            else {
                nodeToChange!!.onlyLeafs.remove(minOnlyLeaf)
                nodeToChange!!.leafs.remove(minOnlyLeaf)
            }
            finalOutput.add(minOnlyLeaf)
            tempNodess.forEach { node ->
                node.leafs.remove(minOnlyLeaf)
            }
//             printImportantThings(tempNodess)
//             println("-------------")
        }

        //printImportantThings(nodes)
        if(finalOutput.size != length-1) println("Error")
        else {
            finalOutput.forEach{println(it)}
        }
    }catch(e: Exception){
        println("Error")
    }
}



fun printImportantThings(nodes: List<Node>) {
    nodes.forEach {
        println("root :" + it.root)
        println("leafs" + it.leafs)
        println("only leafs :" + it.onlyLeafs)
        println("========")
    }
}

data class Node(val root: Int, var leafs: MutableList<Int>, var numberOfConnection: Int = 2, 
                var possibleLeafs: MutableList<Int> = mutableListOf<Int>(),var onlyLeafs: MutableList<Int> = mutableListOf()) {
    
}