// Created for this challenge: // https://www.sololearn.com/post/308448 // Shuffle 10 times the numbers 0..9 // That makes a 10*10 matrix // Now from each row take one number that // you take numbers 0..9. // Put a rectangle around all taken numbers. // Minimize that rectangle by a good choice. // Here two examples for 1..3 // [<1> 2 3 // <3> 1 2 optimal // <2>] 1 3 // [<1 2 3 // 3 1 <2> catastrophical // 2 1 <3>] // Edit // RKK brought me to an easier version: // Pick numbers in ascending and descending // order and calculate which order builds // the smaller rectangle. // Method to extend the Int class with an // absolute value. fun Int.abs() = Math.abs(this) // Extend Iterable with the shuffled method // available in 1.2 library. Randomly // select indexes for the list. If it is // in use, pick the next higher wrapping // around as needed. Once done, create the // new list with the selected element from // the old list. fun Iterable.shuffled(): List { val count = this.count() val list = Array(count) { -1 } for (loop in 0 until count) { var index = rand(0 until count) while (list[index] != -1) index = (index+1)%count list[index] = loop } // for return List(count) { index -> this.elementAt(list[index]) } } // shuffled // Method to extend Iterable class with a // joinToString version to allow passing // index to the transform. fun Iterable.joinIndexedToString( separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "", limit: Int = -1, truncated: CharSequence = "...", transform: ((Int, T) -> CharSequence)? = null ): String { // Start the result with the prefix. For // each element, add them to the result. var result = "$prefix" for (index in 0 until count()) { // Get the value to display either as // a string or using the transform, // when specified. val value = if (transform == null) "${elementAt(index)}" else { val temp = transform(index, elementAt(index)) "$temp" } // if // Get the separator we need. First // element needs none. The rest need // our normal one. val start = when (index) { 0 -> "" else -> "$separator" } // when // Store our element value and separator // as needed. If we reached our limit, // use our truncated string. If we // are above the limit, use nothing. // Otherwise, use our separator and // value. result += when { index == limit -> "$truncated" limit != -1 && index > limit -> "" else -> "$start$value" } // when } // for // Finish off with the postfix and return // the result. result += "$postfix" return result } // joinIndexedToString // Function to return a random number for // specified progression. Convert the // progression into how many numbers we // need, get one in that range, convert // the result into the equivalent within // the progression. fun rand(progression: IntProgression) = java.util.Random().nextInt( (progression.last-progression.first)/ progression.step+1)*progression.step+ progression.first // Data class to hold both value and index // within the matrix. data class Spot(var value: Int, var index: Int) // Function to find the best rectangle with // all numbers. fun best(matrix: List> ): List { // Ascending list of values with their // index to be shuffled into our next // attempt, the best rectangle size seen, // and the list of that rectangle. val selected = List(10) { Spot(it, matrix[it].indexOf(it)) } var size = 100 var list = List(10) { matrix[it].indexOf(it) } // Function to attempt our best within // a range. fun adjust(range: IntRange) { // For each row, see if it needs // adjustment. for (row in selected.indices) // If the row is not within the range, // try swapping it. if (selected[row].index !in range) { // Get our target value and for // each column in the range, see // if a swap with it might be // best. val first = selected[row].value for (two in range) { // Get the value we might swap, // find the row it currently is // within, and find our target // value in that row. val second = matrix[row][two] val spot = selected.indexOfFirst { it.value == second } val one = matrix[spot].indexOf( first) // If we can swap and both values // are within the range, swap // them and exit the loop. if (one in range) { selected[spot].value = first selected[spot].index = one selected[row].value = second selected[row].index = two break } // if } // for } // if } // adjust // For ranges of all combinations of two, // three, and four column groups, see if // it is our best. Adjust of selection for // this range. Calculate the size of this // attempt. If it is better, save its size // and list. Otherwise, if the range can // not beat our best, exit the loop. for (range in listOf(0..1, 1..2, 2..3, 3..4, 4..5, 5..6, 6..7, 7..8, 8..9, 0..2, 1..3, 2..4, 3..5, 4..6, 5..7, 6..8, 7..9, 0..3, 1..4, 2..5, 3..6, 4..7, 5..8, 6..9)) { adjust(range) val attempt = ((selected.maxBy { it.index }!!.index-selected.minBy { it.index }!!.index).abs()+1)*10 if (attempt < size) { size = attempt list = selected.map { it.index } } else if (range.count()*10 >= size) break } // for return list } // best // Main function created for this challenge. fun main(args: Array) { // Create our shuffled matrix, select our // ascending indices, and select our // descending indices. val matrix = List(10) { (List(10) { it }).shuffled() } val ascending = List(10) { matrix[it].indexOf(it) } val descending = List(10) { matrix[it].indexOf(9-it) } // Display our matrix, our list of // ascending indices, area, & values, and // our descending indices, area, & // values. println("Matrix:") println(matrix.joinToString("\n", transform = { it.joinToString(" ") })) println("\nAscending:") println("$ascending "+((ascending.maxBy { it }!!-ascending.minBy { it }!!).abs() +1)*10) println(ascending.joinIndexedToString( ", ", "[", "]", transform = { row, column -> "${matrix[row][column]}" })) println("\nDescending:") println("$descending "+((descending.maxBy { it }!!-descending.minBy { it }!!).abs() +1)*10) println(descending.joinIndexedToString( ", ", "[", "]", transform = { row, column -> "${matrix[row][column]}" })) // Pick the smallest rectangle and display // its indices, area, & values. val selected = best(matrix) println("\nBest:") println("$selected "+((selected.maxBy { it }!!-selected.minBy { it }!!).abs() +1)*10) println(selected.joinIndexedToString( ", ", "[", "]", transform = { row, column -> "${matrix[row][column]}" })) } // main

shuffle ch