// Created for this challenge: // https://www.sololearn.com/post/771683 // SudoMino // Given are this stones // 0 0 // 0 1 1 1 // 0 2 1 2 2 2 // 0 3 1 3 2 3 3 3 // 0 4 1 4 2 4 3 4 4 4 // 0 5 1 5 2 5 3 5 4 5 5 5 // 0 6 1 6 2 6 3 6 4 6 5 6 6 6 // Place them to get this matrix. // 4 3 4 6 5 0 6 6 // 3 5 3 3 5 0 2 6 // 3 4 5 1 0 5 6 0 // 1 1 5 1 2 4 2 4 // 6 3 0 3 0 2 5 1 // 5 4 0 6 2 0 1 2 // 1 6 2 3 1 4 4 2 // Expected is program like a SudokuSolver // Hint: Find 00 11 22 33 44 55 66 horizontal // or vertical. If this structures are // unique, the stone is to be placed there. // Do like this with every stone. // Second task: Create a SudoMino-Generator // Place the stones randomly into a 7x8 // shape and print the matrix like above. // Typealias to shorten the access to // Java's random class. typealias Random = java.util.Random // Extend Iterable with a shuffled method. // 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 = count() val list = MutableList(count) { -1 } for (loop in 0 until count) { var index = Random().nextInt(count) while (list[index] != -1) index = (index+1)%count list[index] = loop } // for return List(count) { index -> elementAt(list[index]) } } // shuffled // Extend MutableList with a shuffle function. // Use the shuffled method to get a randomized // list and change the original to match. fun MutableList.shuffle() { val list = shuffled() for (loop in 0 until size) this[loop] = list[loop] } // shuffle // Type aliases require to get our map type // to fit on one line. <> does not support // spliting the definition onto multiple // lines. typealias Pairs = Pair typealias Spots = MutableList typealias Maps = MutableMap // Enumerate class to specify the stone // orientation. enum class Direction { NORTH, EAST, SOUTH, WEST; // Static method to randomly pick a // direction. companion object { fun random() = values()[Random().nextInt(4)] // Static method to randomly pick a // vertical direction. fun vertical() = values()[Random().nextInt(2)*2] // Static method to randomly pick a // horizontal direction. fun horizontal() = values()[Random().nextInt(2)*2+1] } // object } // Direction // Data class to hold a point in the pattern. // Properties are the row and column within // the pattern. data class Point(var row: Int, var column: Int) { // Method to update the point. fun update(r: Int, c: Int) { row = r column = c } // update } // Point // Class to hold the stone. Properties are // the low side value, the high side value, // the direction the stone is orientated, // the top left spot, and the bottom right // spot. The last three are modified to // place the stone into the pattern. class Stone(val low: Int, val high: Int) { var direction = Direction.NORTH val spot = Point(0, 0) val second = Point(0, 0) // Method to generate the stone's display // string. override fun toString() = when (direction) { Direction.NORTH -> "+=+\n|$low|\n|-|\n|$high|\n+=+" Direction.EAST -> "+===+\n|$high!$low|\n+===+" Direction.SOUTH -> "+=+\n|$high|\n|-|\n|$low|\n+=+" Direction.WEST -> "+===+\n|$low!$high|\n+===+" } // when } // Stone // Class to deal with the matrix pattern by // either generating stone placement randomly // or detect how the stones can be place to // match a target pattern. Property is the // list of stones to handle. For the element // number, calculate the two sides of our // stone starting with [0, 0] to [0, 1], // [1, 1], [0, 2]... and ending with [6, 6]. // Allocate the new stone. class Matrix { val stones = List(28) { val high = when (it) { 0 -> 0 1, 2 -> 1 in 3..5 -> 2 in 6..9 -> 3 in 10..14 -> 4 in 15..20 -> 5 else -> 6 } val low = when (it) { 27 -> 6 20, 26 -> 5 14, 19, 25 -> 4 9, 13, 18, 24 -> 3 5, 8, 12, 17, 23 -> 2 2, 4, 7, 11, 16, 22 -> 1 else -> 0 } Stone(low, high) } // Method to randomly generate a stone // pattern. Note: this code is not perfect. // It occasionally ends up with one space // not touching the other so the last few // stones can not be placed. In that case, // we recurse to generate another pattern. fun generate() { // Allocate our matrix as all available // spaces. Clone the stones into a new // list we can modify. val matrix = List(7) { Array(8) { -1 } } val list = MutableList(stones.size) { stones[it] } // Function to figure out a random // direction. If we can go both down // and right, pick a random direction // out of all four. If we can only go // down, pick a random vertical. If // we can only go right, pick a random // horizontal. Otherwise, we have a // single space so throw an exception // to try again. fun orientate(row: Int, column: Int) = when { row+1 in matrix.indices && column+1 in matrix[row]. indices && matrix[row][ column+1] == -1 -> Direction.random() row+1 in matrix.indices -> Direction.vertical() column+1 in matrix[row].indices && matrix[row][column+1] == -1 -> Direction.horizontal() else -> throw IllegalStateException( "No spot for stone!") } // when // Function to update the stone's // placement and put it into our matrix. // Update both points in our stone. The // second is either down or right of // the first based on direction. Place // its two values into the matrix. // Which goes where is also based on // direction. fun place(stone: Stone, row: Int, column: Int) { stone.spot.update(row, column) when (stone.direction) { Direction.NORTH -> { stone.second.update(row+1, column) matrix[row][column] = stone.low matrix[row+1][column] = stone.high } // NORTH Direction.EAST -> { stone.second.update(row, column+1) matrix[row][column] = stone.high matrix[row][column+1] = stone.low } // EAST Direction.SOUTH -> { stone.second.update(row+1, column) matrix[row][column] = stone.high matrix[row+1][column] = stone.low } // SOUTH Direction.WEST -> { stone.second.update(row, column+1) matrix[row][column] = stone.low matrix[row][column+1] = stone.high } // WEST } // when } // place // Try making our pattern. Randomize our // list of stones. For each spot in our // matrix, if it is unused, try putting // a stone there. try { list.shuffle() for (row in matrix.indices) for (column in matrix[row].indices) if (matrix[row][column] == -1) { // If there isn't a stone to // place, cause an exception. // Grab the first stone removing // it from the list. Figure a // random placement and put it // there. if (list.size == 0) throw IllegalStateException( "No stone to place!") val stone = list.removeAt(0) stone.direction = orientate(row, column) place(stone, row, column) } // if // Display the finished pattern. println("Random:") display() // On exception, try once more by // recursing. } catch (error: Throwable) { generate() } // try } // generate // Method to display the pattern. fun display() { // Allocate our output matrix filled // with spaces. Each stone displays // as three by three per side. Two // stones next to each other overlap // so 7x8 becomes 14x16 plus one extra // side. For each stone, draw it. val output = List(15) { Array(17) { ' ' } } for (stone in stones) { // Split the stones display string // into lines. Calculate the offset // to map the matrix position to // output position. For each line // to display, for each character // in the line, place it. val lines = stone.toString(). split("\n") val ofs = stone.spot.row*2 val offset = stone.spot.column*2 for (row in lines.indices) for (column in 0 until lines[row].length) // Ignore any position out of // our output matrix. if (ofs+row !in output.indices || offset+column !in output[0].indices) { // If the output matrix does not // have a stone's character placed // there, put the current character // in place. } else if (output[ofs+row][ offset+column] == ' ') output[ofs+row][offset+column] = lines[row][column] // If the current character is a // plus sign, overwrite what ever // was there. else if (lines[row][column] == '+') output[ofs+row][offset+column] = lines[row][column] } // for // Display the output matrix. println(output.joinToString("\n", transform = { it.joinToString("") })) println() } // display // Method to figure out the target pattern. fun solve(model: List>) { // Clone our target model into our // matrix. Allocate an empty map for // our stones to positions they might // use. val matrix = List(model.size) { row -> Array(model[row].size) { column -> model[row][column] } } val map: Maps = mutableMapOf() // Function to update the map and return // a sorted list of keys. fun spots(): List { // Function to return the element // requested or minus one for off // the pattern. fun spot(row: Int, column: Int) = if (row !in matrix.indices || column !in matrix[row].indices) -1 else matrix[row][column] // For each stone, allocate its list // of possible spots. for (stone in stones) { // Allocate the list and store it // in the stone. For each element // in the matrix, see if it matches // our stone's low value. val list: Spots = mutableListOf() map[stone] = list for (row in matrix.indices) for (column in matrix[row].indices) // If we got a match with our // low vslue, check each spot // our high value could be. // If both match, we have a // possible so add it to the // list. if (stone.low == spot(row, column)) { if (stone.high == spot(row, column-1)) list.add(Pair(Point(row, column), Point(row, column-1))) if (stone.high == spot(row, column+1)) list.add(Pair(Point(row, column), Point(row, column+1))) if (stone.high == spot(row-1, column)) list.add(Pair(Point(row, column), Point(row-1, column))) if (stone.high == spot(row+1, column)) list.add(Pair(Point(row, column), Point(row+1, column))) } // if } // for // Make a list of our keys from the // ones with the least possibilities // to those with the most. Take our // map and make it a list. Sort the // new list based on the number of // possibilities. Convert that list // into a single list of keys. return map.toList().sortedBy { (_, v) -> v.size }.map { (k, _) -> k } } // spots // Recursive function to traverse the // keys to find the correct placement // of the stones. fun traverse(keys: List): Boolean { // If there is no more keys, we got // a winner so display it and abort // out. if (keys.size == 0) { display() return true // Otherwise, we have more keys to // process so get the first one and // for each possible placement test // it for working. } else { val stone = keys[0] for ((low, high) in map[stone]!!) // If this possibility is still // available, try it. if (matrix[low.row][low.column ] >= 0 && matrix[high.row][ high.column] >= 0) { // Note we are using these two // spots. Figure out the // direction the stone must // go. matrix[low.row][low.column] = -1 matrix[high.row][high.column ] = -1 stone.direction = when { low.column < high.column -> Direction.WEST low.column > high.column -> Direction.EAST low.row < high.row -> Direction.NORTH else -> Direction.SOUTH } // when // Base on the direction, the // stone placement of its low // and high values change. if (stone.direction in listOf(Direction.EAST, Direction.SOUTH)) { stone.spot.update(high.row, high.column) stone.second.update(low.row, low.column) } else { stone.spot.update(low.row, low.column) stone.second.update(high.row, high.column) } // if // Recurse on the next key in // the list. If they found a // valid combination, abort. if (traverse(keys.drop(1))) return true // Put the original values // back into the matrix. matrix[low.row][low.column] = stone.low matrix[high.row][high.column ] = stone.high } // if // If we ran out of possibilities, // some placement above was wrong // so tell the previous call to try // again. return false } // if } // traverse // Generate a map of stones to the // possible placements. These get // turned into a sorted list of keys // based on the number of places it // might fit. Recursively process the // keys until a valid combination is // found to match the target. println("Solution:") traverse(spots()) } // solve } // Matrix // Main function for this challenge. Allocate // our matrix, ask it to solve our pattern, // and ask it to generated a random pattern. fun main(args: Array) { val matrix = Matrix() matrix.solve(listOf( listOf(4, 3, 4, 6, 5, 0, 6, 6), listOf(3, 5, 3, 3, 5, 0, 2, 6), listOf(3, 4, 5, 1, 0, 5, 6, 0), listOf(1, 1, 5, 1, 2, 4, 2, 4), listOf(6, 3, 0, 3, 0, 2, 5, 1), listOf(5, 4, 0, 6, 2, 0, 1, 2), listOf(1, 6, 2, 3, 1, 4, 4, 2))) matrix.generate() } // main

domino ch