Minimal steps down to 1: Difference between revisions

 

Given:

 

At any step, the number may be:

* OR have one of S subtracted from it, if N is greater than the member of S.

 

Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 1:

 

:2. Show a count of, and the numbers that: have the maximum minimal_steps_to_1, in the range 1 to 2,000.

 

Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 2:

 

:4. Show a count of, and the numbers that: have the maximum minimal_steps_to_1, in the range 1 to 2,000.

 

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

 

 

 

 

 

 

 

}

}

{{out}}

 

 

 

 

=={{header|Python}}==

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}}

 

===Python: Tabulated===

The stretch goal is attempted.<br>

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}}

Those numbers up to 50000 that take the maximum, "minimal steps down to 1":

Taking 26 steps is/are the 1 numbers: 45925</pre>

 

=={{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">