// Input: nothing for the default cases or // Two matrices separated by a blank line. // Each matrix is one or more lines of // space separated integers. Each line // of the matrix will be zero filled to // make all lines the same size. // Created for this challenge: // https://www.sololearn.com/post/139811 // Find Matching Sum // Given two matrices, find the largest total // count of elements that produce a matching // sum and display the count, sum, and those // subsets. Each subset must be a rectangular // grouping, not random disjoint elements. // Given matching count, the largest sum // should be picked. // Example (largest count): // 1, 1, 1 // 1, 1, 1 // 6, 2, 2, 2 // 1, 2, 2, 1 // 10, 6 // 1, 1, 1 // 1, 1, 1 // -, -, -, - // 1, 2, 2, 1 // Instead of these smaller element counts. // 7, 6 // 1, 1, 1 // 1, 1, 1 // 6, -, -, - // -, -, -, - // 9, 6 // 1, 1, 1 // 1, 1, 1 // -, 2, 2, 2 // -, -, -, - // Example (matching count largest sum): // 1, 6, 9 // 1, 5 // 8, 3 // 3, 9 // -, -, 9 // 1, - // 8, - // Instead of this smaller sum. // 3, 6 // -, 6, - // 1, 5 // -, - // Got idea doing sayan chandra challenge: // https://www.sololearn.com/post/139340 // Method to extend Int class to return the // columns needed to display the integer. fun Int.size() = "$this".length // Method to extend Int class to return the // absolute value of the integer. fun Int.abs() = Math.abs(this) // Data class to hold the number of // elements sum within the rectangle // specified by the indexes: top, bottom, // left, and right. data class Sum(val elements: Int, val sum: Int, val top: Int, val bottom: Int, val left: Int, val right: Int) // Function to process the matrix looking // for the sub-matrix with the best sum. fun process(first: List>, second: List>) { // Function to find the largest size // required for all of the elements // of the matrix. For each element in // the matrix, if it needs more than // our current maximum, that becomes // the new maximum. fun size(matrix: List>): Int { var max = 0 for (line in matrix) for (element in line) { val needs = element.size() if (needs > max) max = needs } // for return max } // size // Function to display the matrix. fun display(matrix: List>, vertical: IntRange, horizontal: IntRange) { // Get our required spacing, set up // our format, and for each line in // the matrix, display it. val space = size(matrix) val format = "%${space+1}d" for ((row, line) in matrix.withIndex()) { // For each column in the line, figure // put what to display. for ((column, element) in line.withIndex()) { // If this is not the first column, // we need to display a comma // between the previous and this // one. if (column > 0) print(',') // If this element is within our // rectangle, display it. Otherwise, // display a dash. Both use our // required spacing. if (row in vertical && column in horizontal) print(format.format(element)) else print(" ".repeat(space)+"-") } // for // Finish the line's display, println() } // for } // display // Function to sum the elements in // the current sub-matrix. For each // element in the sub-matrix, add it // to our sum. Return a data class // with the sum and our sub-matrix // indices. fun sum(matrix: List>, top: Int, bottom: Int, left: Int, right: Int): Sum { var result = 0 for (row in top..bottom) for (column in left..right) result += matrix[row][column] return Sum((bottom-top+1)*(right-left+1), result, top, bottom, left, right) } // sum // Function to create a list of all // possible combinations. fun combinations(matrix: List>): MutableList { // Default the list to empty. For all // combinations of sub-matrices, figure // out the sum and add it to our list. // The top and left go for all possible // indices. The bottom and right go from // the top and left to the maximum // allowable. val list = MutableList(0) { Sum(0, 0, 0, 0, 0, 0) } for (top in 0 until matrix.size) for (bottom in top until matrix.size) for (left in 0 until matrix[top].size) for (right in left until matrix[top].size) { val current = sum(matrix, top, bottom, left, right) list.add(current) } // for return list } // combinations // Display the inputs. println("Input:") display(first, first.indices, first[0].indices) println() display(second, second.indices, second[0].indices) println() // Generate a list of all possible // combinations for both matrices. val one = combinations(first) val two = combinations(second) // Make a pairing of any matching sums // and add them to our list. val list = MutableList(0) { Pair(Sum(0, 0, 0, 0, 0, 0), Sum(0, 0, 0, 0, 0, 0)) } for (left in one) for (right in two) if (left.sum == right.sum) list.add(Pair(left, right)) // Find the maximum element count in // our pairings. var max = 0 for ((left, right) in list) if (left.elements+right.elements > max) max = left.elements+right.elements // Default our result to empty. For // each pairing, if it produces our // maximum elements and it has a higher // sum, it becomes our new result. var result = Pair(Sum(0, 0, -1, -1, -1, -1), Sum(0, 0, -1, -1, -1, -1)) for (element in list) { val (first, second) = element val (one, two) = result if (first.elements+second.elements == max && first.sum > one.sum) result = element } // for // Display the results. val (left, right) = result println("$max, ${left.sum}") display(first, left.top..left.bottom, left.left..left.right) println() display(second, right.top..right.bottom, right.left..right.right) println() } // process // Main function for this challenge. fun main(args: Array) { // Try reading an matrix from the user. try { // Default our first matrix to empty. // While there is user data, read it, // convert it to integers, and add it // to the matrix. val first = MutableList(0) { List(0) { 0 } } while (true) { val input = readLine() ?: break if (input.isEmpty()) break val data = input.split(" ").map { it.toInt() } first.add(data) } // while // If we didn't get any data, throw // an exception. if (first.size == 0) throw IllegalArgumentException( "Bad input!") // Find out the longest line so we can // make them all that size. var max = 0 for (line in first) if (line.size > max) max = line.size // Convert our matrix to a fixed size. val one = List(first.size) { row -> List(max) { if (it >= first[row].size) 0 else first[row][it] } } // Default our second matrix to empty. // While there is user data, read it, // convert it to integers, and add it // to the matrix. val second = MutableList(0) { List(0) { 0 } } while (true) { val input = readLine() ?: break val data = input.split(" ").map { it.toInt() } second.add(data) } // while // If we didn't get any data, throw // an exception. if (second.size == 0) throw IllegalArgumentException( "Bad input!") // Find out the longest line so we can // make them all that size. max = 0 for (line in second) if (line.size > max) max = line.size // Convert our matrix to a fixed size. // Process both matrices. val two = List(second.size) { row -> List(max) { if (it >= second[row].size) 0 else second[row][it] } } process(one, two) // On exception, complain and process // our test cases. } catch (error: Throwable) { for ((first, second) in listOf( Pair(listOf( listOf(1, 1, 1), listOf(1, 1, 1)), listOf( listOf(6, 2, 2, 2), listOf(1, 2, 2, 1))), Pair(listOf( listOf(1, 6, 9)), listOf( listOf(1, 5), listOf(8, 3))))) process(first, second) } // try } // main

match ch