Minimal steps down to 1: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
(Add Kotlin implementation) |
||
Line 1,319: | Line 1,319: | ||
There are 1 with 24 steps for start between 1 and 20000: [19681] |
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] |
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> |
</pre> |
||