// Inputs: nothing to process examples listed below // or two or more lines each containing the same // number of integers (two minimum) in the range of // 0 to 65535. // Created for this code golf: // https://codegolf.stackexchange.com/questions/180119 // 2-Dimensional Bubble Sort // Sorting makes no sense for a 2-dimensional // array... or does it? // Your task is to take an input grid and apply a // bubble-sort-like algorithm to it until all values // in the grid are non-decreasing from left to right // and top to bottom along every row and column. // The algorithm works as follows: // Each pass goes row by row, top to bottom, // comparing/swapping each cell with its right // and below neighbors. // - if the cell is greater than only one of its // right and below neighbors, swap with the one // that it is greater than // - if the cell is greater than both its right // and below neighbors, swap with the smaller // neighbor // - if the cell is greater than both its right // and below neighbors, which are the same // value, then swap with the below neighbor. // - if the cell is not greater than either of // its right and below neighbors, do nothing // Continue this until no swaps are made throughout // the entire pass. This will be when every row and // column are in order, left to right and top to // bottom. // Example // 4 2 1 // 3 3 5 // 7 2 1 // The first row of the pass will swap the 4 and // the 2, then the 4 with the 1. // 2 1 4 // 3 3 5 // 7 2 1 // When we get the the middle 3, it will be swapped // with the 2 below // 2 1 4 // 3 2 5 // 7 3 1 // Then the 5 gets swapped with the 1 below // 2 1 4 // 3 2 1 // 7 3 5 // The last row of the first pass moves the 7 all // the way to the right // 2 1 4 // 3 2 1 // 3 5 7 // Then we go back to the top row again // 1 2 1 // 3 2 4 // 3 5 7 // And continue row by row... // 1 2 1 // 2 3 4 // 3 5 7 // ... until the grid is "sorted" // 1 1 2 // 2 3 4 // 3 5 7 // Another Example // 3 1 1 // 1 1 1 // 1 8 9 // becomes // 1 1 1 // 1 1 1 // 3 8 9 // rather than // 1 1 1 // 1 1 3 // 1 8 9 // because the downward swap takes priority when // both the right and below neighbors of a cell // are equal. // A step-by-step reference implementation can be // found here. // Test cases // 5 3 2 6 7 3 1 0 // 3 2 1 9 9 8 3 0 // 3 2 2 8 9 8 7 6 // becomes // 0 0 1 1 2 2 3 6 // 2 2 3 3 6 7 8 8 // 3 3 5 7 8 9 9 9 // 2 1 2 7 8 2 1 0 // 2 2 2 2 3 2 1 0 // 1 2 3 4 5 4 3 2 // 9 8 7 6 5 4 3 6 // 6 5 4 3 2 2 1 0 // becomes // 0 0 0 1 1 1 2 2 // 1 1 2 2 2 2 2 2 // 2 2 2 2 3 3 3 3 // 3 4 4 4 4 5 6 6 // 5 5 6 7 7 8 8 9 // Rules // You can take the input grid in any convenient // format // You may assume the grid values are all // non-negative integers in the unsigned 16-bit // range (0-65535). // You may assume the grid is a perfect rectangle // and not a jagged array. The grid will be at // least 2x2. // If you use another algorithm of sorting, you // must supply a proof that it will always // produce the same resulting order as this // particular brand of 2D bubble sorting, no // matter what the input is. I expect this to be // a non-trivial proof, so you're probably better // off using the described algorithm. // Happy Golfing! // Method to extend the List class to convert into // an array when containing integers. fun List.toArray() = Array(this.size) { this[it] } // Method to extend the MutableList class to convert // into an array when containing arrays of integers. fun MutableList>.toArray() = Array(this.size) { this[it] } // Function to process sorting the array. This is // an expanded version of the lambda with comments. // Note: this code works on a jagged array and 1x1 // fine. It supports all negative values up to 65535. fun process(matrix: Array>) { // Function to return the matrix element, if it is // valid, or larger than maximum allowable value. // This is an expanded version of the nested lambda. // If both indexes less than their array size, they // are valid and the element can be returned. fun value(row: Int, column: Int) = if (row < matrix.size && column < matrix[row].size) matrix[row][column] else 65536 // While we might have something to swap, find and // swap it. do { // Default to nothing swapped (0>1 saves 2 bytes // over false.) For each row, process it. var swapped = 0 > 1 for (row in matrix.indices) // For each column, check to see if we need to // swap it. for (column in matrix[row].indices) when { // When this element is greater than the // one below and the one below is less // than or equal to the one to the right, // swap this with the one below and note // we swapped something. Note: if the // indices are out of range, we get a // number greater that our maximum allowed. // 0<1 saves a byte over true. The also // method makes use of a temporary to // save the original value prior to // executing the lambda followed by // returning the temporary. value(row, column) > value(row+1, column) && value(row+1, column) <= value(row, column+1) -> matrix[row][column] = matrix[row+1][column].also { matrix[row+1][column] = matrix[row][column] swapped = 0 < 1 } // When this element is greater than the // right one and the right one is less // than the one below, swap this with // the right one and note we swapped // something. Note: the previous notes // also apply here. value(row, column) > value(row, column+1) && value(row, column+1) < value(row+1, column) -> matrix[row][column] = matrix[row][column+1].also { matrix[row][column+1] = matrix[row][column] swapped = 0 < 1 } } // when } while (swapped) } // process // Function to display the matrix. fun display(matrix: Array>) { // Get the largest value in the matrix. Each row // returns it's largest. The matrix returns the // row that has the largest. Then, we get the // largest from that row. Note: we have to ignore // the null possiblities at each step. val maximum = matrix.maxBy { it.max()!! }!!.max()!! // Get the number of columns required to display // our maximum without touching the number before // it. val width = when { maximum < 10 -> 2 maximum < 100 -> 3 maximum < 1000 -> 4 maximum < 10000 -> 5 else -> 6 } // when // For each row in the matrix, display it. for (row in matrix) { // For each column in the row, if it isn't the // first, we need all of the width so use it // to display the value. Otherwise, the first // column doesn't need a leading space so display // the value without it. for ((index, column) in row.withIndex()) if (index > 0) print("%${width}d".format(column)) else print("%${width-1}d".format(column)) // Finish off the line for the row. println() } // for // Display an empty line after the matrix. println() } // display // Main function to sort the user's matrix or our // test case ones. fun main(args: Array) { // Lambda function to sort the matrix. See // expanded version above for explaination. val p = // 325 bytes {m:Array>->val v={r:Int,c:Int->if(r1 for(r in m.indices)for(c in m[r].indices)when{v(r,c)>v(r+1,c)&&v(r+1,c)<=v(r,c+1)->m[r][c]=m[r+1][c].also{m[r+1][c]=m[r][c] s=0<1} v(r,c)>v(r,c+1)&&v(r,c+1)m[r][c]=m[r][c+1].also{m[r][c+1]=m[r][c] s=0<1}}}while(s)} // Try reading the user's matrix and, if successful, // process it, otherwise, throw an exception. try { // Default the list to empty and row size to // zero. While there are lines to read, do so. // Note: we break out of the infinite loop, when // done. val list = MutableList(0) { Array(0) { 0 } } var size = 0 while (true) { // Read the next line. Break out of loop on // end of file or empty line. val input = readLine() ?: break if (input.length == 0) break // Make an array of the integers of the line. // Split on space into a list, map list to // convert to integer (throwing exception on // non-digits or out of valid range,) and // convert list to array. val array = input.split(" ").map { val value = it.toInt() if (value in 0..65535) value else throw IllegalArgumentException( "Bad input integer!") }.toArray() // If second or later row and it's size doesn't // match the previous or there are less than // two columns, throw an exception. if (size != 0 && array.size != size || array.size < 2) throw IllegalArgumentException( "Bad input columns!") // Save this row's size and add the row to the // list. size = array.size list.add(array) } // while // If there are not two or more rows, throw an // exception. if (list.size < 2) throw IllegalArgumentException( "Bad input rows!") // Make the list of rows into an array matrix, // display it, sort it, and display the updated // result. val matrix = list.toArray() println("Input:") display(matrix) p(matrix) println("Output:") display(matrix) // On exception, complain and process the defaults. // For each test case, display it's matrix, sort // the matrix, and display the updated matrix. // Note: the four test cases match challenge // examples in comments above. } catch (error: Throwable) { println("Bad inputs using defaults!") for (matrix in listOf(arrayOf( arrayOf(4, 2, 1), arrayOf(3, 3, 5), arrayOf(7, 2, 1)), arrayOf(arrayOf(3, 1, 1), arrayOf(1, 1, 1), arrayOf(1, 8, 9)), arrayOf(arrayOf(5, 3, 2, 6, 7, 3, 1, 0), arrayOf(3, 2, 1, 9, 9, 8, 3, 0), arrayOf(3, 2, 2, 8, 9, 8, 7, 6)), arrayOf(arrayOf(2, 1, 2, 7, 8, 2, 1, 0), arrayOf(2, 2, 2, 2, 3, 2, 1, 0), arrayOf(1, 2, 3, 4, 5, 4, 3, 2), arrayOf(9, 8, 7, 6, 5, 4, 3, 6), arrayOf(6, 5, 4, 3, 2, 2, 1, 0)))) { println("Input:") display(matrix) p(matrix) println("Output:") display(matrix) } // for } // try } // main

bubblesort cg sr