Minimal steps down to 1: Difference between revisions
Add Kotlin implementation
m (→{{header|Wren}}: Minor tidy) |
(Add Kotlin implementation) |
||
Line 1,319:
There are 1 with 24 steps for start between 1 and 20000: [19681]
There are 1 with 26 steps for start between 1 and 50000: [45925]
</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="Kotlin">
fun main() {
runTasks(getFunctions1())
runTasks(getFunctions2())
runTasks(getFunctions3())
}
fun runTasks(functions: List<Function>) {
val minPath = getInitialMap(functions, 5)
// Task 1
val max = 10
populateMap(minPath, functions, max)
println("\nWith functions: $functions")
println(" Minimum steps to 1:")
for (n in 2..max) {
val steps = minPath[n]?.size ?: 0
println(" %2d: %d step%s: %s".format(n, steps, if (steps == 1) "" else "s", minPath[n]))
}
// Task 2
displayMaxMin(minPath, functions, 2000)
// Task 2a
displayMaxMin(minPath, functions, 20000)
// Task 2a +
displayMaxMin(minPath, functions, 100000)
}
fun displayMaxMin(minPath: MutableMap<Int, List<String>>, functions: List<Function>, max: Int) {
populateMap(minPath, functions, max)
val maxIntegers = getMaxMin(minPath, max)
val maxSteps = maxIntegers.removeAt(0)
val numCount = maxIntegers.size
println(" There ${if (numCount == 1) "is" else "are"} $numCount number${if (numCount == 1) "" else "s"} in the range 1-$max that have maximum 'minimal steps' of $maxSteps:\n $maxIntegers")
}
fun getMaxMin(minPath: Map<Int, List<String>>, max: Int): MutableList<Int> {
var maxSteps = Int.MIN_VALUE
val maxIntegers = mutableListOf<Int>()
for (n in 2..max) {
val len = minPath[n]?.size ?: 0
if (len > maxSteps) {
maxSteps = len
maxIntegers.clear()
maxIntegers.add(n)
} else if (len == maxSteps) {
maxIntegers.add(n)
}
}
maxIntegers.add(0, maxSteps)
return maxIntegers
}
fun populateMap(minPath: MutableMap<Int, List<String>>, functions: List<Function>, max: Int) {
for (n in 2..max) {
if (n in minPath) continue
var minFunction: Function? = null
var minSteps = Int.MAX_VALUE
for (f in functions) {
if (f.actionOk(n)) {
val result = f.action(n)
val steps = 1 + (minPath[result]?.size ?: 0)
if (steps < minSteps) {
minFunction = f
minSteps = steps
}
}
}
minFunction?.let {
val result = it.action(n)
val path = mutableListOf(it.toString(n))
path.addAll(minPath[result] ?: emptyList())
minPath[n] = path
}
}
}
fun getInitialMap(functions: List<Function>, max: Int): MutableMap<Int, List<String>> {
val minPath = mutableMapOf<Int, List<String>>()
for (i in 2..max) {
for (f in functions) {
if (f.actionOk(i)) {
val result = f.action(i)
if (result == 1) {
minPath[i] = listOf(f.toString(i))
}
}
}
}
return minPath
}
fun getFunctions1(): List<Function> = listOf(
Divide3Function(),
Divide2Function(),
Subtract1Function()
)
fun getFunctions2(): List<Function> = listOf(
Divide3Function(),
Divide2Function(),
Subtract2Function()
)
fun getFunctions3(): List<Function> = listOf(
Divide2Function(),
Divide3Function(),
Subtract2Function(),
Subtract1Function()
)
abstract class Function {
abstract fun action(n: Int): Int
abstract fun actionOk(n: Int): Boolean
abstract fun toString(n: Int): String
}
class Divide2Function : Function() {
override fun action(n: Int) = n / 2
override fun actionOk(n: Int) = n % 2 == 0
override fun toString(n: Int) = "/2 -> ${n / 2}"
override fun toString() = "Divisor 2"
}
class Divide3Function : Function() {
override fun action(n: Int) = n / 3
override fun actionOk(n: Int) = n % 3 == 0
override fun toString(n: Int) = "/3 -> ${n / 3}"
override fun toString() = "Divisor 3"
}
class Subtract1Function : Function() {
override fun action(n: Int) = n - 1
override fun actionOk(n: Int) = true
override fun toString(n: Int) = "-1 -> ${n - 1}"
override fun toString() = "Subtractor 1"
}
class Subtract2Function : Function() {
override fun action(n: Int) = n - 2
override fun actionOk(n: Int) = n > 2
override fun toString(n: Int) = "-2 -> ${n - 2}"
override fun toString() = "Subtractor 2"
}
</syntaxhighlight>
{{out}}
<pre>
With functions: [Divisor 3, Divisor 2, Subtractor 1]
Minimum steps to 1:
2: 1 step: [-1 -> 1]
3: 1 step: [/3 -> 1]
4: 2 steps: [/2 -> 2, -1 -> 1]
5: 3 steps: [-1 -> 4, /2 -> 2, -1 -> 1]
6: 2 steps: [/3 -> 2, -1 -> 1]
7: 3 steps: [-1 -> 6, /3 -> 2, -1 -> 1]
8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1]
9: 2 steps: [/3 -> 3, /3 -> 1]
10: 3 steps: [-1 -> 9, /3 -> 3, /3 -> 1]
There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
[863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943]
There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20:
[12959, 15551, 17279, 18143, 19439]
There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 24:
[77759]
With functions: [Divisor 3, Divisor 2, Subtractor 2]
Minimum steps to 1:
2: 1 step: [/2 -> 1]
3: 1 step: [-2 -> 1]
4: 2 steps: [/2 -> 2, /2 -> 1]
5: 2 steps: [-2 -> 3, -2 -> 1]
6: 2 steps: [/3 -> 2, /2 -> 1]
7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1]
8: 3 steps: [/2 -> 4, /2 -> 2, /2 -> 1]
9: 2 steps: [/3 -> 3, -2 -> 1]
10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1]
There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 17:
[1699]
There is 1 number in the range 1-20000 that have maximum 'minimal steps' of 24:
[19681]
There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 28:
[98413]
With functions: [Divisor 2, Divisor 3, Subtractor 2, Subtractor 1]
Minimum steps to 1:
2: 1 step: [-1 -> 1]
3: 1 step: [-2 -> 1]
4: 2 steps: [/2 -> 2, -1 -> 1]
5: 2 steps: [-2 -> 3, -2 -> 1]
6: 2 steps: [/2 -> 3, -2 -> 1]
7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1]
8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1]
9: 2 steps: [/3 -> 3, -2 -> 1]
10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1]
There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 13:
[1943]
There are 2 numbers in the range 1-20000 that have maximum 'minimal steps' of 17:
[17495, 19439]
There are 22 numbers in the range 1-100000 that have maximum 'minimal steps' of 19:
[58319, 69983, 76463, 77759, 78623, 87479, 89423, 90071, 90287, 90359, 90383, 90395, 91259, 91355, 91367, 93311, 95255, 95471, 95903, 96119, 96191, 98171]
</pre>
| |||