Minimal steps down to 1: Difference between revisions

{{task}}

 

Given:

;Reference:

* [https://www.youtube.com/watch?v=f2xi3c1S95M Learn Dynamic Programming (Memoization & Tabulation)] Video of similar task.

 

=={{header|C sharp}}==

{{works with|C sharp|7}}

using System.Collections.Generic;

using System.Linq;

 

private static string Delimit<T>(this IEnumerable<T> source) => string.Join(", ", source);

{{out}}

<pre>

There is one number below 2000 that requires 17 steps: 1699

There is one number below 20000 that requires 24 steps: 19681</pre>

 

=={{header|Go}}==

 

import (

fmt.Println()

}

 

{{out}}

[45925]

</pre>

 

=={{header|Java}}==

Algorithm works with any function that supports the <code>Function</code> interface in the code below.

 

import java.util.ArrayList;

import java.util.HashMap;

 

}

 

{{out}}

 

Implemented as a generic solution for any functions acting on an integer and taking any range of second arguments, with the goal solution also specifiable. To do so generically, it is also necessary to specify a failure condition, which in the example is falling below 1.

struct Action{T}

empty!(memoized)

teststeps(1, failed, actions2, [2000, 20000, 50000])

<pre>

With goal 1, divisors [2, 3], subtractors [1]:

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|Mathematica}}/{{header|Wolfram Language}}==

ClearAll[MinimalStepToOne, MinimalStepToOneHelper]

MinimalStepToOne[n_Integer] := Module[{res},

 

a = Last[SortBy[GatherBy[allsols, Last], First /* Last]];

{{out}}

<pre>1: (0 steps) 1

We use two recursive functions, the first one to find the minimal length sequences, the second one to find the minimal number of steps. For both, we use memoization. The program takes about 10 ms to execute.

 

 

type

run(divisors = [2, 3], subtractors = [1])

echo ""

 

{{out}}

 

=={{header|Perl}}==

 

use strict; # https://rosettacode.org/wiki/Minimal_steps_down_to_1

}

return \@solve, \@maximal;

{{out}}

<pre>

=={{header|Phix}}==

Using simple iterative (vs recursive) memoisation. To make things a bit more interesting it maintains separate caches for any&all {d,s} sets.

{{out}}

<pre>

With divisors {2,3} and subtractors {1}:

10 takes 3 steps, eg -1 -> 9,/3 -> 3,/3 -> 1

There are 5 numbers below 20000 that require 20 steps: {12959,15551,17279,18143,19439}

There are 3 numbers below 50000 that require 22 steps: {25919,31103,38879}

 

With divisors {2,3} and subtractors {2}:

10 takes 3 steps, eg /2 -> 5,-2 -> 3,/3 -> 1

There is 1 number below 2000 that requires 17 steps: {1699}

Although the stretch goal could be achieved by changing the recursion limit, it does point out a possible issue with this type of solution. But then again, this solution may be more natural to some.

 

from functools import lru_cache

 

', '.join(str(n) for n in sorted(ans)))

#print(minrec._minrec.cache_info())

 

{{out}}

The table to solve for N contains all the results from 1 up to N. This is used in the solution.

 

"Tabulation, memoised minimised steps to 1"

 

ans = [n for n, steps in enumerate(table) if steps == mx]

print(' Taking', mx, f'steps is/are the {len(ans)} numbers:',

 

{{out}}

{{works with|Rakudo|2019.11}}

 

 

for [2,3], 1, 2000,

}

}

{{out}}

<pre>Divisors: [2, 3], subtract: 1

Up to 50,000 found 1 number that requires at least 26 steps.

(45925) 26 steps: -2=>45923, -2=>45921, /3=>15307, -2=>15305, -2=>15303, /3=>5101, -2=>5099, -2=>5097, /3=>1699, -2=>1697, -2=>1695, /3=>565, -2=>563, -2=>561, /3=>187, -2=>185, -2=>183, /3=>61, -2=>59, -2=>57, /3=>19, -2=>17, -2=>15, /3=>5, -2=>3, /3=>1</pre>

 

=={{header|Wren}}==

{{trans|Go}}

{{libheader|Wren-fmt}}

 

var limit = 50000

}

System.print()

 

{{out}}

 

=={{header|XPL0}}==

Subtractor; \1 or 2

char Ns(20000), Ops(20000), MinNs(20000), MinOps(20000);

ShowCount(2000); \4.

ShowCount(20_000); \4a.

 

{{out}}

 

=={{header|zkl}}==

fcn buildCache(N,D,S){

minCache=Dictionary(1,T(1,"",0));

do(steps){ v,o,s := minCache[N]; ops.write(" ",o,"-->",N=v); }

return(steps,ops.close())

buildCache(MAX,D,S);

 

 

S=T(2); buildCache(MAX,D,S);

{{out}}

<pre style="height:45ex">