Rosetta Code

Minimal steps down to 1: Difference between revisions

Page Discussion

Minimal steps down to 1 (view source)

Revision as of 11:41, 7 February 2024

11,621 bytes added ,  4 months ago
Add Kotlin implementation
m (syntax highlighting fixup automation)
(Add Kotlin implementation)
(2 intermediate revisions by 2 users not shown)
Line 251:
There is one number below 2000 that requires 17 steps: 1699
There is one number below 20000 that requires 24 steps: 19681</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
 
const int32_t limit = 50'000;
 
std::vector<int32_t> divisors;
std::vector<int32_t> subtractors;
std::vector<std::vector<std::string>> minimums;
 
template <typename T>
void print_vector(const std::vector<T>& list) {
for ( uint64_t i = 0; i < list.size(); ++i ) {
std::cout << list[i];
if ( i < list.size() - 1 ) {
std::cout << ", ";
}
}
}
 
// Assumes that numbers are presented in ascending order up to 'limit'.
void minimum_steps(int32_t n) {
if ( n == 1 ) {
return;
}
 
int32_t minimum = limit;
int32_t p = 0;
int32_t q = 0;
std::string operator_symbol = "";
for ( int32_t divisor : divisors ) {
if ( n % divisor == 0 ) {
int32_t d = n / divisor;
int32_t steps = minimums[d].size() + 1;
if ( steps < minimum ) {
minimum = steps;
p = d;
q = divisor;
operator_symbol = "/";
}
}
}
 
for ( int32_t subtractor : subtractors ) {
int32_t d = n - subtractor;
if ( d >= 1 ) {
int32_t steps = minimums[d].size() + 1;
if ( steps < minimum ) {
minimum = steps;
p = d;
q = subtractor;
operator_symbol = "-";
}
}
}
 
minimums[n].emplace_back(operator_symbol + std::to_string(q) + " -> " + std::to_string(p));
minimums[n].insert(minimums[n].end(), minimums[p].begin(), minimums[p].end());
}
 
int main() {
for ( int32_t item : { 0, 1 } ) {
divisors = { 2, 3 };
subtractors = { item + 1 };
minimums = std::vector(limit + 1, std::vector<std::string>(0));
std::cout << "With: Divisors: { "; print_vector<int32_t>(divisors);
std::cout << " }, Subtractors: { "; print_vector<int32_t>(subtractors); std::cout << " } =>" << std::endl;
std::cout << " Minimum number of steps to diminish the following numbers down to 1 is:" << std::endl;
for ( int32_t i = 1; i < limit; ++i ) {
minimum_steps(i);
if ( i <= 10 ) {
int32_t steps = minimums[i].size();
const std::string plural = ( steps == 1 ) ? " : " : "s: ";
std::cout << " " << std::setw(2) << i << ": " << steps << " step" + plural;
print_vector<std::string>(minimums[i]); std::cout << std::endl;
}
}
 
for ( int32_t lim : { 2'000, 20'000, 50'000 } ) {
uint64_t max = 0;
for ( int32_t j = 1; j <= lim; ++j ) {
uint64_t m = minimums[j].size();
if ( m > max ) {
max = m;
}
}
std::vector<int32_t> maxs;
for ( int32_t j = 1; j <= lim; ++j ) {
if ( minimums[j].size() == max ) {
maxs.emplace_back(j);
}
}
 
int32_t size = maxs.size();
std::string verb1 = ( size == 1 ) ? "is" : "are";
std::string verb2 = ( size == 1 ) ? "has" : "have";
std::string plural = ( size == 1 ) ? "" : "s";
std::cout << " There " << verb1 << " " << size << " number" << plural << " in the range 1 - " << lim
<< " that " << verb2 << " maximum 'minimal steps' of " << max << ":" << std::endl;
std::cout << " [ "; print_vector<int32_t>(maxs); std::cout << " ]" << std::endl;
}
std::cout << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
With: Divisors: { 2, 3 }, Subtractors: { 1 } =>
Minimum number of steps to diminish the following numbers down to 1 is:
1: 0 steps:
2: 1 step : /2 -> 1
3: 1 step : /3 -> 1
4: 2 steps: /2 -> 2, /2 -> 1
5: 3 steps: -1 -> 4, /2 -> 2, /2 -> 1
6: 2 steps: /2 -> 3, /3 -> 1
7: 3 steps: -1 -> 6, /2 -> 3, /3 -> 1
8: 3 steps: /2 -> 4, /2 -> 2, /2 -> 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 are 3 numbers in the range 1 - 50000 that have maximum 'minimal steps' of 22:
[ 25919, 31103, 38879 ]
 
With: Divisors: { 2, 3 }, Subtractors: { 2 } =>
Minimum number of steps to diminish the following numbers down to 1 is:
1: 0 steps:
2: 1 step : /2 -> 1
3: 1 step : /3 -> 1
4: 2 steps: /2 -> 2, /2 -> 1
5: 2 steps: -2 -> 3, /3 -> 1
6: 2 steps: /2 -> 3, /3 -> 1
7: 3 steps: -2 -> 5, -2 -> 3, /3 -> 1
8: 3 steps: /2 -> 4, /2 -> 2, /2 -> 1
9: 2 steps: /3 -> 3, /3 -> 1
10: 3 steps: /2 -> 5, -2 -> 3, /3 -> 1
There is 1 number in the range 1 - 2000 that has maximum 'minimal steps' of 17:
[ 1699 ]
There is 1 number in the range 1 - 20000 that has maximum 'minimal steps' of 24:
[ 19681 ]
There is 1 number in the range 1 - 50000 that has maximum 'minimal steps' of 26:
[ 45925 ]
</pre>
 
=={{header|FreeBASIC}}==
Line 1,169 ⟶ 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>
 
Line 2,159 ⟶ 2,517:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var limit = 50000
Aspen138
338

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327934...354002"