// Input: nothing for zero (intial step) or // an integer between zero and seven. // Created for this challenge: // https://www.sololearn.com/post/457386 // [Challenge] // Cut a board of 22*13 tiles into 7 // rectangular pieces so that no piece can // contain another one (for instance, a 6x8 // rectangle completely covers a 4x7 // rectangle). No tile may be broken. // Method to extend Int class with selecting // the larger of both integers. fun Int.max(other: Int) = Math.max(this, other) // Method to extend Int class with selecting // the smaller of both integers. fun Int.min(other: Int) = Math.min(this, other) // 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 // Data class to hold a location within the // area. Properties are row and column. data class Point(var row: Int, var column: Int) // Data class to hold a rectangle to be // fitted into our area. Properties are the // height, width, and number to display. data class Rectangle(val height: Int, val width: Int, val number: Int = height) // Class to arrange the rectangles into our // area. Properties are the height, width, // the number to display, the parent block, // the location, and whether the block was // used for a rectangle. class Block(var height: Int, var width: Int) { var number = 0 var previous: Block? = null val spot = Point(0, 0) var used = false // Class wide properties of a complete list // of instances, our horizontal size, and // our vertical size. companion object { val blocks = mutableListOf() var horizontal = 0 var vertical = 0 // Class wide method to display all the // blocks. fun display() { // Display the blocks as used. // Allocate our matrix to store the // blocks within. For each block, // store its characters. println("Passed: "+blocks.joinToString( ", ")) val matrix = List(vertical) { Array(horizontal) { '0' } } for (block in blocks) // For each row used by the block, // store its characters. for (row in block.spot.row until block.height+block.spot.row) // For each column used by the // block, store a character into // the selected spot. Used spots // get numbers, while unused get // letters. for (column in block.spot.column until block.width+ block.spot.column) matrix[row][column] = if (block.used) '0'+block.number else 'a'+block.number // Display the matrix. println(matrix.joinToString("\n", transform = { it.joinToString( "") })) println() } // display // Method to create our rectangles from // our list and insert them into our area. fun fit(list: List): Boolean { // Allocate our list of rectangles and // sort it so our largest dimension is // first. While our list still has // something left, pick our next one // to place. val shapes = MutableList(list.size) { Rectangle(list.size-it, list[it]) } shapes.sortByDescending { it.width.max(it.height) } while (shapes.isNotEmpty()) { // Select our next target area to // fill. Default to nothing fits. // For all rectangles remaining, // pick our first fit or perfect fit. // If the rectangle's height exactly // matches the target areas' height // or width and it fits in the area, // it is perfect. Otherwise, the // first one that fits is used. val space = next() var shape: Rectangle? = null for (block in shapes) if (block.height <= space.height && block.width <= space.width || block.width <= space.height && block.height <= space.width) { if (shape == null || space.width == block.height || space.height == block.height) shape = block } // if // If we failed to get a rectangle, // this combination is not our // answer so abort. if (shape == null) return false // We have a rectangle so now we // must figure out how to place it. // If needed, rotate its height and // width to fit the area. Get the // parent that created this area. with (shape) { val (h, w) = if (height <= space.height && width <= space.width) Pair(height, width) else Pair(width, height) val parent = space.previous // Get the row. We might need to // shift to the bottom because it // was the cause that limited our // width. val r = if (parent == null || space.height == h || parent.spot.row <= space.spot.row) space.spot.row else parent.spot.row+ parent.height-h // Get the column. We might need to // shift to the right because it // was the cause that limited our // height. val c = if (parent == null || space.width == w || parent.spot.column <= space.spot.column) space.spot.column else parent.spot.column+ parent.width-w // Put our rectangle in place // breaking out any part not needed // as a new area. Remove the // rectangle. space.split(Point(r, c), h, w, number) shapes.remove(this) } // with } // while return true } // fit // Method to return the unused area with // the smallest dimension. Join it with // any intersection that makes sense. fun next(): Block { blocks.sortBy { it.width.min(it.height) } val selected = blocks.filter { !it.used }[0] selected.join() return selected } // next // Class wide method to reset the class // wide properties so we can process a // second test case. fun reset() { blocks.clear() horizontal = 0 vertical = 0 } // reset } // object // Constructor to update our class wide // list of instances. If our first // instance, remember our rectangle // dimensions in class wide properties. init { blocks.add(this) if (horizontal+vertical == 0) { horizontal = width vertical = height } // if } // init // Method to combine adjacent blocks // together to maximize the usable space. fun join() { // Find any unused blocks that intersect // vertically. val columns = blocks.filter { val columns = it.spot.column until it.spot.column+it.width it != this && !it.used && spot.column in columns && spot.column+width-1 in columns }.sortedBy { it.spot.row } // Find any unused blocks thar intersect // horizontally. val rows = blocks.filter { val rows = it.spot.row until it.spot.row+it.height it != this && !it.used && spot.row in rows && spot.row+height-1 in rows }. sortedBy { it.spot.column } // If only one set of intersections // exist, use it. Otherwise, use the // smaller dimension even when both // are empty. For each overlap, see // if it can be used. val overlaps = if ((width > height || columns.size == 0) && rows.size > 0) rows else columns for (overlap in overlaps) // When the overlap is above the // selected block and it is adjacent, // remove the overlapped area from // the overlap and add it to the // selected block. when { overlap.spot.row < spot.row && overlap.spot.row+overlap.height == spot.row -> { overlap.width -= width height += overlap.height spot.row -= overlap.height } // up // When the overlap is below the // selected block and it is adjacent, // remove the overlapped area from // the overlap and add it to the // selected block. overlap.spot.row > spot.row && overlap.spot.row == spot.row+ height -> { overlap.width -= width height += overlap.height overlap.spot.column += width } // down // When the overlap is left of the // selected block and it is adjacent, // remove the overlapped area from // the overlap and add it to the // selected block. overlap.spot.column < spot.column && overlap.spot.column+overlap.width == spot.column -> { overlap.height -= height width += overlap.width spot.column -= overlap.width overlap.spot.row += height } // left // When the overlap is right of the // selected block and it is adjacent, // remove the overlapped area from // the overlap and add it to the // selected block. overlap.spot.column > spot.column && overlap.spot.column == spot.column+width -> { overlap.height -= height width += overlap.width } // right } // when } // join // Method to break up a block into three // pieces: the used piece, the vertical // unused piece, and the horizontal // unused piece. These pieces might be // non-existant due all the area being // used. The intersection of the unused // pieces goes to the one with the smaller // dimension. fun split(s: Point, h: Int, w: Int, n: Int) { // Save this so we have access within // the with statements. Figure out // if the horizontal dimension gets // the intersection. val that = this val default = height.min(width-w) > width.min(height-h) // If there is a vertical piece left // over, allocate and fill it in. // The intersection goes to the // horizontal by default, but if // this width is smaller than that // piece's height, we take it. if (width-w > 0) with (Block( if (default && height-h > 0) h else height, width-w)) { spot.row = that.spot.row spot.column = if (s.column > that.spot.column) that.spot.column else that.spot.column+w previous = that number = blocks.size-1 } // with // If there is a horizontal piece left // over, allocate and fill it in. We // get the intersection by default, but // if our height is bigger the other's // width, they get it. if (height-h > 0) with (Block(height-h, if (default || width-w <= 0) width else width-w)) { spot.row = if (s.row > that.spot.row) that.spot.row else that.spot.row+h spot.column = that.spot.column previous = that number = blocks.size-1 } // with // Update the instance to hold only the // rectangle selected for it. used = true spot.row = s.row spot.column = s.column number = n height = h width = w } // split // Method to generate the display string. override fun toString() = "${height}x$width" } // Block // Function to process some combinations // selected by choice. Each resets the // class, sets up the output matrix, // tries to fit the seven rectangles into // the matrix, and displays the result. fun combinations(choice: Int) { // Function to try out the first set of // combinations. fun first() { println("Checking first group of six"+ " combinations.\n") for (test in listOf( listOf(7, 8, 9, 10, 14, 20, 22), listOf(7, 8, 9, 10, 15, 19, 21), listOf(7, 8, 9, 10, 16, 17, 22), listOf(7, 8, 9, 10, 16, 18, 20), listOf(7, 8, 9, 11, 12, 21, 22), listOf(7, 8, 9, 11, 13, 20, 21))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 2.") } // first // Function to try out the second set of // combinations. fun second() { println("Checking second group of six"+ " combinations.\n") for (test in listOf( listOf(7, 8, 9, 11, 14, 18, 22), listOf(7, 8, 9, 11, 14, 19, 20), listOf(7, 8, 9, 11, 15, 17, 21), listOf(7, 8, 9, 11, 15, 18, 19), listOf(7, 8, 9, 11, 16, 17, 18), listOf(7, 8, 9, 12, 13, 18, 21))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 3.") } // second // Function to try out the third set of // combinations. fun third() { println("Checking third group of six"+ " combinations.\n") for (test in listOf( listOf(7, 8, 9, 12, 14, 16, 22), listOf(7, 8, 9, 12, 14, 17, 20), listOf(7, 8, 9, 12, 15, 16, 19), listOf(7, 8, 9, 13, 14, 15, 20), listOf(7, 8, 9, 13, 14, 16, 18), listOf(7, 8, 10, 11, 12, 19, 21))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 4.") } // third // Function to try out the fourth set of // combinations. fun fourth() { println("Checking fourth group of six"+ " combinations.\n") for (test in listOf( listOf(7, 8, 10, 11, 13, 17, 22), listOf(7, 8, 10, 11, 13, 18, 20), listOf(7, 8, 10, 11, 14, 16, 21), listOf(7, 8, 10, 11, 14, 17, 19), listOf(7, 8, 10, 11, 15, 16, 18), listOf(7, 8, 10, 12, 13, 15, 22))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 5.") } // fourth // Function to try out the fifth set of // combinations. fun fifth() { println("Checking fifth group of six"+ " combinations.\n") for (test in listOf( listOf(7, 8, 10, 12, 13, 16, 20), listOf(7, 8, 10, 12, 13, 17, 18), listOf(7, 8, 10, 12, 14, 15, 19), listOf(7, 8, 10, 12, 14, 16, 17), listOf(7, 8, 11, 12, 13, 14, 19), listOf(7, 8, 11, 12, 13, 15, 17))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 6.") } // fifth // Function to try out the sixth set of // combinations. fun sixth() { println("Checking sixth group of six"+ " combinations.\n") for (test in listOf( listOf(7, 9, 10, 11, 12, 16, 21), listOf(7, 9, 10, 11, 12, 17, 19), listOf(7, 9, 10, 11, 13, 14, 22), listOf(7, 9, 10, 11, 13, 15, 20), listOf(7, 9, 10, 11, 13, 16, 18), listOf(7, 9, 10, 11, 14, 15, 17))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nRun once more with a 7.") } // sixth // Function to try out the seventh set of // combinations. fun seventh() { println("Checking seventh group of six"+ " combinations.\n") for (test in listOf( listOf(7, 9, 10, 12, 13, 14, 18), listOf(7, 9, 10, 12, 13, 15, 16), listOf(8, 9, 10, 11, 12, 13, 20), listOf(8, 9, 10, 11, 12, 14, 18), listOf(8, 9, 10, 11, 12, 15, 16), listOf(8, 9, 10, 11, 13, 14, 15))) { Block.reset() Block(22, 13) if (Block.fit(test)) Block.display() else println("Failed: "+test. joinIndexedToString(transform = { index, it -> "${7-index}x$it" })) } // for println("\nAll combinations have been"+ " processed.") } // seventh // Try out the requested set of // combinations or complain. when (choice) { 1 -> first() 2 -> second() 3 -> third() 4 -> fourth() 5 -> fifth() 6 -> sixth() 7 -> seventh() else -> { println("Invalid choice (0 to 7 "+ "only)!\n") sixth() } // else } // when } // combinations // Function to check for possible combinations. fun possibilities() { // Class to hold a shape. class Shape(val height: Int, var width: Int) { val area: Int get() = height*width } // Shape // Allocate our shapes, calculate the area // available, and zero our count of choices. val shapes = List(7) { Shape(7-it, 0) } val available = 22*13 var choices = 0 // Function to verify this possible shape // does not fit inside another or can not // fit another inside it. fun check(height: Int, width: Int): Boolean { for (other in shapes) if (other.width != 0) if (height <= other.width && width <= other.height || other.height <= width && other.width <= height || width <= other.width) return false return true } // check // Recursive function to figure shape // combinations that might work. fun shape(size: Int) { // Calculate the area currently used. If // we have selected each size shape, it // is time to decide based on using all // of the area. If we have used the area, // generate the list code to be used for // the future steps and count it. val used = shapes.sumBy { it.area } if (size == 0) { if (available == used) { println(shapes.joinToString(", ", " listOf(", "),", transform = { "${it.width}" })) choices++ } // if // Otherwise, we need to select one or // more shapes so for all possible // width choices, if it does not overlap // and it does not overfull our target, // try it out. We try it out by setting // our width to the choice, recursing // to the smaller height, and once back // reset our width. } else { for (choice in 1..22) if (check(size, choice) && used+size*choice <= available) { shapes[7-size].width = choice shape(size-1) shapes[7-size].width = 0 } // if } // if } // shape // Recursively select combinations that // satisfy the rules and yield the right // area. State the total found and suggest // checking them in the next run. println("Figuring out combinations that"+ " fit the rules and achieve the "+ "required area.\n") shape(7) println("Combinations found: "+choices) println("\nRun once more with a 1.") } // possibilities // Main function for this challenge. Read an // integer or default to zero. If zero, list // the possible choices. Otherwise, process // some of them. fun main(args: Array) { val choice = readLine()!!.toIntOrNull() ?: 0 if (choice == 0) possibilities() else combinations(choice) } // main

Rectangles ch