// Input: nothing for default test cases or // a space separated list of integer pairs // separated by a comma (e.g. 0,0 0,3 3,0 3,3). // Each integer must be between -10,000 and // 10,000. There must be one or more pairs. // Created for this challenge: // https://www.sololearn.com/post/216760 // COUNTING RECTANGLES [CODING CHALLENGE] // You receive 2D coordinates of unordered // points. Your task is to count how many // rectangles (with vertical and horizontal // sides only) are created by those points. // Simple examples: // [(0,0),(0,3),(1,3),(1,0),(3,0)] // make 1 rectangle // [(0,0),(0,3),(1,3),(1,0),(3,0),(3,3)] // make 3 rectangles (squares are rectangles // too) // testCases: // [(0,1),(0,3),(2,2),(2,3),(3,1),(3,2),(3,3), // (3,4),(5,1),(5,3),(5,4)] // -> 6 // [(-3,-2),(-3,2),(-1,0),(-1,2),(0,0),(0,2), // (0,4),(2,-3),(2,0),(2,2),(2,4),(2,7), // (4,-2),(4,2),(5,-3),(5,0),(5,2),(5,4), // (7,-3),(7,2),(7,7)] // -> 20 // from random import choices // [choices(range(10000),k=2) for i in // range(100000)] // -> 3000 (+ or - 300) (statistical value) // (that's python syntax for a choice of // 100.000 random points which 2D coordinates // are between 0 and 10000). // Try to keep a low complexity. // Function to return a random number in the // range. fun rand(range: IntRange) = java.util.Random().nextInt( range.endInclusive-range.start+1)+ range.start // Function to process our challenge. fun process(test: List>): Int { // Sort our points and make a set of them. // Put those points into two maps. First, // all the rows each with a set of the // columns they have. Second, all the // columns each with a set of the rows // they have. val values = test.sortedBy { it[0]*20000+it[1] }.toSet() val x = mutableMapOf>() val y = mutableMapOf>() for ((row, column) in values) { if (row in x.keys) x[row]!!.add(column) else x.put(row, mutableSetOf(column)) if (column in y.keys) y[column]!!.add(row) else y.put(column, mutableSetOf(row)) } // for // Default the count to zero. For each // point in our set, for each column spot // in our map's row set ignoring our // current column, for each line in our // map's column set ignoring our current // row, if our line has a map entry and // the spot exists in our map for the // line, we have a rectangle so count it. // Remove the point from the sets of both // the row and column maps. var count = 0 for ((row, column) in values) { for (spot in x[row]!!) if (spot != column) for (line in y[column]!!) if (line != row) if (x.containsKey(line) && spot in x[line]!!) count++ x[row]!!.remove(column) y[column]!!.remove(row) } // for return count } // process // Function to display the inputs and outputs // for our challenge. Limit the print of the // pairs to the first 50. fun display(test: List>) { if (test.size <= 50) println(test) else println(test.joinToString(", ", "[", "]", 50)) println(process(test)) println() } // 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 { pair -> pair.split(",").map { it.toInt() } } for (pair in test) if (pair.size != 2 || pair.size != pair.filter { it in -10000..10000 }.size) throw IllegalArgumentException( "Bad input!") display(test) // On exception, complain and process our // test cases. Either a random one or the // examples. } catch (error: Throwable) { println("Bad input using defaults!") if (rand(0..2) == 0) display(List(rand(1..10000)) { List(2) { rand(-100..100) } }) else for (test in listOf(listOf(listOf(0, 0), listOf(0, 3), listOf(1, 3), listOf(1, 0), listOf(3, 0)), listOf(listOf(0, 0), listOf(0, 3), listOf(1, 3), listOf(1, 0), listOf(3, 0), listOf(3, 3)), listOf(listOf(0, 1), listOf(0, 3), listOf(2, 2), listOf(2, 3), listOf(3, 1), listOf(3, 2), listOf(3, 3), listOf(3, 4), listOf(5, 1), listOf(5, 3), listOf(5, 4)), listOf(listOf(-3, -2), listOf(-3, 2), listOf(-1, 0), listOf(-1, 2), listOf(0, 0), listOf(0, 2), listOf(0, 4), listOf(2, -3), listOf(2, 0), listOf(2, 2), listOf(2, 4), listOf(2, 7), listOf(4, -2), listOf(4, 2), listOf(5, -3), listOf(5, 0), listOf(5, 2), listOf(5, 4), listOf(7, -3), listOf(7, 2), listOf(7, 7)))) display(test) } // try } // main

rectangles ch