// Input: nothing for default test cases or // a space separated list of integers between // one and 20. // Created for this challenge: // https://www.sololearn.com/post/223223 // Given a random List of an even number // 2*n of Integers from 1 to 20. Create n // pairs so that each pair i is mapped to // one Integer m_i: Higher value of pair_i // module lower value of pair_i. Minimize // the sum of m_i for I = 1 to n. // Example // List = 9,4,6,3 has 4 Integers. 4 is even // so we can build pairs. // Optimal Pairs: 6,3 and 9,4 // Optimal sum 6%3 + 9%4 = 0+1=1 // Suboptimal Pairs: 6,4 and 9,3: // 6%4 + 9%3 = 2+0 = 2 // Variation // The number of elements maybe even or odd. // If it is odd: drop one Element. // The shorter the list....the easier the // challenge. 6 Elements seem to be a good // start. // Extend Interable with chunked method. // Figure out the number of outer lists // before creating the result. The inner // lists have the requested size elements // or what is left over. The inner list // contents are the next chunk of the // original list. fun Iterable.chunked( size: Int): List> { var count = this.count() val outer = (count+size-1)/size return List(outer) { index -> List( if (count > size) { count -= size size } else count) { this.elementAt(index*size+it) } } } // chunked // Function to return a random number in the // range. fun rand(range: IntRange) = java.util.Random().nextInt( range.endInclusive-range.start+1)+ range.start // Class to iterate over all permutations of // the values zero to size-1. Properties are // the number of value to permutate, the // index into the remaining elements having // removed any previously used ones, the // values to return next, and our having // returned all possible combinations. class Permutation(val size: Int) : Iterator> { val index = Array(size) { 0 } val value = Array(size) { it } var done = size < 1 // Method to tell whether there is any more // combinations. override fun hasNext() = !done // Method to return the combination we know // about and figure out if there is another. override fun next(): List { // Save the result as a list to return at // the end. Start at the last index to // find what needs changing next. While // the index has reached the end of // possibilities, move to the previous. val result = value.toList() var position = size-1 while (position >= 0 && index[position] == size-1-position) position-- // If we are at the end of all combinations, // we are done. if (position < 0) done = true // Otherwise, figure out our next // combination. else { // Make a list to play with. For all // previous positions that are going // to remain the same, remove the // element they currently have from // the list. val list = MutableList(size) { it } for (element in 0 until position) list.removeAt(index[element]) // Update our position that needs changing // to it's next choice for both the index // & value and remove it from our list. index[position]++ value[position] = list.removeAt(index[position]) // All remainding positions, get reset // to zero and take the first choice // removing it from the list. for (element in position+1 until size) { index[element] = 0 value[element] = list.removeAt(0) } // for } // if // Return our saved list. return result } // next } // Permutation // Function to process our challenge. fun process(test: List): Int { // Default our minimum to highest possible. // Generate our possible permutations for // our list. For each permutation, test it. var minimum = Int.MAX_VALUE; for (list in Permutation(test.size)) { // Default the sum to zero. Group the // permutation into two value groups. // For each group, if it is full, get // the indexes, lookup the values, // perform the modulo operation, and // all it to the sum. var sum = 0 for (group in list.chunked(2)) if (group.size == 2) { val (f, s) = group sum += test[f]%test[s] } // if // If this sum is less than our minimum, // save it. if (sum < minimum) minimum = sum } // for // Return that minimum. return minimum } // process // Function to display the inputs and outputs // for our challenge. fun display(test: List) { println("$test = ${process(test)}") } // display // Main function created for this challenge. fun main(args: Array) { // Try reading the user's list of integers. // Cause an exception on end of file, non // integer, or out of our supported range. // Otherwise, process it. try { val test = readLine()!!.split(" ").map { it.toInt() } if (test.size != test.filter { it in 1..20 }.size) throw IllegalArgumentException( "Bad input!") display(test) // On exception, complain and process our // test cases. } catch (error: Throwable) { println("Bad input using defaults!") for (test in listOf(listOf(3, 4, 6, 9), List(rand(4..8)) { rand(1..20) })) display(test) } // try } // main

optimum ch