Anonymous user
Pancake numbers: Difference between revisions
→{{header|Kotlin}}: Adds exhaustive search
SqrtNegInf (talk | contribs) (→{{header|Perl}}: upgraded to meet task specs) |
(→{{header|Kotlin}}: Adds exhaustive search) |
||
Line 483:
=={{header|Kotlin}}==
===Maximum number of flips only===
{{trans|C}}
<lang
var gap = 2
var sum = 2
Line 511:
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre>
===Maximum number of flips plus examples using exhaustive search===
Using classic breadth-first search with running queue.
<lang kotlin>data class PancakeResult(val example: List<Int>, val depth: Int)
fun pancake(n: Int): PancakeResult {
fun List<Int>.copyFlip(spatula: Int) = toMutableList().apply { subList(0, spatula).reverse() }
val initialStack = List(n) { it + 1 }
val stackFlips = mutableMapOf(initialStack to 1)
val queue = ArrayDeque(listOf(initialStack))
while (!queue.isEmpty()) {
val stack = queue.removeFirst()
val flips = stackFlips[stack]!! + 1
for (spatula in 2 .. n) {
val flipped = stack.copyFlip(spatula)
if (stackFlips.putIfAbsent(flipped, flips) == null) {
queue.addLast(flipped)
}
}
}
return stackFlips.maxByOrNull { it.value }!!.run { PancakeResult(key, value) }
}
fun main() {
for (i in 1 .. 10) {
with (pancake(i)) { println("pancake($i) = $depth. Example: $example") }
}
}
</lang>
{{out}}
<pre>
pancake(1) = 1. Example: [1]
pancake(2) = 2. Example: [2, 1]
pancake(3) = 4. Example: [1, 3, 2]
pancake(4) = 5. Example: [4, 2, 3, 1]
pancake(5) = 6. Example: [5, 1, 3, 2, 4]
pancake(6) = 8. Example: [5, 3, 6, 1, 4, 2]
pancake(7) = 9. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 10. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 11. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]
pancake(10) = 12. Example: [1, 3, 2, 4, 6, 8, 10, 5, 7, 9]
</pre>
=={{header|MAD}}==
| |||