Minimal steps down to 1: Difference between revisions
m memoize |
|||
Line 187: | Line 187: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Non-recursive solution that is memoized for the count-only |
Non-recursive solution that is memoized for the count-only portions of the task. When the steps are to be printed, the solution is not memoized in order to list all possible paths of the shortest length (all solutions). 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 falure condition, which in the example is falling below 1. |
||
<lang julia>import Base.print |
<lang julia>import Base.print |
||
Revision as of 20:03, 16 December 2019
Given:
- A starting, positive integer (greater than one), N.
- A selection of possible integer perfect divisors, D.
- And a selection of possible subtractors, S.
The goal is find the minimum number of steps necessary to reduce N down to one.
At any step, the number may be:
- Divided by any member of D if it is perferctly divided by D, (remainder zero).
- OR have one of S subtracted from it, if N is greater than the member of S.
There may be many ways to reduce the initial N down to 1. Your program needs to:
- Find the minimum number of steps to reach 1.
- Show one way of getting fron N to 1 in those minimum steps.
- Examples
No divisors, D. a single subtractor of 1.
- Obviousely N will take N-1 subtractions of 1 to reach 1
Single divisor of 2; single subtractor of 1:
- N = 7 Takes 4 steps N -1=> 6, /2=> 3, -1=> 2, /2=> 1
- N = 23 Takes 7 steps N -1=>22, /2=>11, -1=>10, /2=> 5, -1=> 4, /2=> 2, /2=> 1
Divisors 2 and 3; subtractor 1:
- N = 11 Takes 4 steps N -1=>10, -1=> 9, /3=> 3, /3=> 1
- Task
Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 1:
- 1. Show the number of steps and possible way of dinminishing the numbers 1 to 10 down to 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:
- 3. Show the number of steps and possible way of dinminishing the numbers 1 to 10 down to 1.
- 4. Show a count of, and the numbers that: have the maximum minimal_steps_to_1, in the range 1 to 2,000.
- Optional stretch goal
- 2a, and 4a: As in 2 and 4 above, but for N in the range 1 to 20_000
- Reference
- Learn Dynamic Programming (Memoization & Tabulation) Video of similar task.
Go
<lang go>package main
import (
"fmt" "strings"
)
const limit = 50000
var (
divs, subs []int mins [][]string
)
// Assumes the numbers are presented in order up to 'limit'. func minsteps(n int) {
if n == 1 { mins[1] = []string{} return } min := limit var p, q int var op byte for _, div := range divs { if n%div == 0 { d := n / div steps := len(mins[d]) + 1 if steps < min { min = steps p, q, op = d, div, '/' } } } for _, sub := range subs { if d := n - sub; d >= 1 { steps := len(mins[d]) + 1 if steps < min { min = steps p, q, op = d, sub, '-' } } } mins[n] = append(mins[n], fmt.Sprintf("%c%d -> %d", op, q, p)) mins[n] = append(mins[n], mins[p]...)
}
func main() {
for r := 0; r < 2; r++ { divs = []int{2, 3} if r == 0 { subs = []int{1} } else { subs = []int{2} } mins = make([][]string, limit+1) fmt.Printf("With: Divisors: %v, Subtractors: %v =>\n", divs, subs) fmt.Println(" Minimum number of steps to diminish the following numbers down to 1 is:") for i := 1; i <= limit; i++ { minsteps(i) if i <= 10 { steps := len(mins[i]) plural := "s" if steps == 1 { plural = " " } fmt.Printf(" %2d: %d step%s: %s\n", i, steps, plural, strings.Join(mins[i], ", ")) } } for _, lim := range []int{2000, 20000, 50000} { max := 0 for _, min := range mins[0 : lim+1] { m := len(min) if m > max { max = m } } var maxs []int for i, min := range mins[0 : lim+1] { if len(min) == max { maxs = append(maxs, i) } } nums := len(maxs) verb, verb2, plural := "are", "have", "s" if nums == 1 { verb, verb2, plural = "is", "has", "" } fmt.Printf(" There %s %d number%s in the range 1-%d ", verb, nums, plural, lim) fmt.Printf("that %s maximum 'minimal steps' of %d:\n", verb2, max) fmt.Println(" ", maxs) } fmt.Println() }
}</lang>
- Output:
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]
Julia
Non-recursive solution that is memoized for the count-only portions of the task. When the steps are to be printed, the solution is not memoized in order to list all possible paths of the shortest length (all solutions). 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 falure condition, which in the example is falling below 1. <lang julia>import Base.print
struct Action
f::Function i::Int
end
struct ActionOutcome
act::Action out::Int
end
function Base.print(io::IO, ao::ActionOutcome)
print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)")
end
memoized = Dict{Int, Int}()
function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000)
solutions, numsteps = Vector{Vector{ActionOutcome}}(), 0 seqs = [ActionOutcome[ActionOutcome(Action(div, 0), start)]] if start == goal verbose && println("For start of $start, no steps needed.\n") return 0 end while numsteps < maxsteps && isempty(solutions) newsequences = Vector{Vector{ActionOutcome}}() numsteps += 1 for seq in seqs for (act, arr) in actions, x in arr result = act(seq[end].out, x) if !fails(result) newactionseq = vcat(seq, ActionOutcome(Action(act, x), result)) numsteps == 1 && popfirst!(newactionseq) if result == goal push!(solutions, newactionseq) else push!(newsequences, newactionseq) end end end if !verbose && isempty(solutions) && all(x -> haskey(memoized, x[end].out), newsequences) minresult = minimum(x -> memoized[x[end].out], newsequences) + numsteps memoized[start] = minresult return minresult end end seqs = newsequences end if verbose println("Solutions for path from $start to $goal:") for (n, sol) in enumerate(solutions) print(" Solution $n has $numsteps step(s): ") for step in sol print(step, step.out == 1 ? "\n\n" : ", ") end end end memoized[start] = numsteps return numsteps
end
failed(n) = n < 1
const divisors = [2, 3] divide(n, x) = begin q, r = divrem(n, x); r == 0 ? q : -1 end
const subtractors1, subtractors2 = [1], [2] subtract(n, x) = n - x
actions1 = Dict(divide => divisors, subtract => subtractors1) actions2 = Dict(divide => divisors, subtract => subtractors2)
function findmaxshortest(g, fails, acts, maxn)
stepcounts = [findshortest(n, g, fails, acts, false) for n in 1:maxn] maxs = maximum(stepcounts) maxstepnums = findall(x -> x == maxs, stepcounts) println("There are $(length(maxstepnums)) with $maxs steps for start between 1 and $maxn: ", maxstepnums)
end
function teststeps(g, fails, acts, maxes)
println("\nWith goal $g, divisors $(acts[divide]), subtractors $(acts[subtract]):") for n in 1:10 findshortest(n, g, fails, acts) end for maxn in maxes findmaxshortest(g, fails, acts, maxn) end
end
teststeps(1, failed, actions1, [2000, 20000, 50000]) empty!(memoized) teststeps(1, failed, actions2, [2000, 20000, 50000])
</lang>
- Output:
With goal 1, divisors [2, 3], subtractors [1]: For start of 1, no steps needed. Solutions for path from 2 to 1: Solution 1 has 1 step(s): divide 2 yields 1 Solution 2 has 1 step(s): subtract 1 yields 1 Solutions for path from 3 to 1: Solution 1 has 1 step(s): divide 3 yields 1 Solutions for path from 4 to 1: Solution 1 has 2 step(s): divide 2 yields 2, divide 2 yields 1 Solution 2 has 2 step(s): divide 2 yields 2, subtract 1 yields 1 Solution 3 has 2 step(s): subtract 1 yields 3, divide 3 yields 1 Solutions for path from 5 to 1: Solution 1 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, divide 2 yields 1 Solution 2 has 3 step(s): subtract 1 yields 4, divide 2 yields 2, subtract 1 yields 1 Solution 3 has 3 step(s): subtract 1 yields 4, subtract 1 yields 3, divide 3 yields 1 Solutions for path from 6 to 1: Solution 1 has 2 step(s): divide 2 yields 3, divide 3 yields 1 Solution 2 has 2 step(s): divide 3 yields 2, divide 2 yields 1 Solution 3 has 2 step(s): divide 3 yields 2, subtract 1 yields 1 Solutions for path from 7 to 1: Solution 1 has 3 step(s): subtract 1 yields 6, divide 2 yields 3, divide 3 yields 1 Solution 2 has 3 step(s): subtract 1 yields 6, divide 3 yields 2, divide 2 yields 1 Solution 3 has 3 step(s): subtract 1 yields 6, divide 3 yields 2, subtract 1 yields 1 Solutions for path from 8 to 1: Solution 1 has 3 step(s): divide 2 yields 4, divide 2 yields 2, divide 2 yields 1 Solution 2 has 3 step(s): divide 2 yields 4, divide 2 yields 2, subtract 1 yields 1 Solution 3 has 3 step(s): divide 2 yields 4, subtract 1 yields 3, divide 3 yields 1 Solutions for path from 9 to 1: Solution 1 has 2 step(s): divide 3 yields 3, divide 3 yields 1 Solutions for path from 10 to 1: Solution 1 has 3 step(s): subtract 1 yields 9, divide 3 yields 3, divide 3 yields 1 There are 16 with 14 steps for start between 1 and 2000: [863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943] There are 5 with 20 steps for start between 1 and 20000: [12959, 15551, 17279, 18143, 19439] There are 3 with 22 steps for start between 1 and 50000: [25919, 31103, 38879] With goal 1, divisors [2, 3], subtractors [2]: For start of 1, no steps needed. Solutions for path from 2 to 1: Solution 1 has 1 step(s): divide 2 yields 1 Solutions for path from 3 to 1: Solution 1 has 1 step(s): divide 3 yields 1 Solution 2 has 1 step(s): subtract 2 yields 1 Solutions for path from 4 to 1: Solution 1 has 2 step(s): divide 2 yields 2, divide 2 yields 1 Solution 2 has 2 step(s): subtract 2 yields 2, divide 2 yields 1 Solutions for path from 5 to 1: Solution 1 has 2 step(s): subtract 2 yields 3, divide 3 yields 1 Solution 2 has 2 step(s): subtract 2 yields 3, subtract 2 yields 1 Solutions for path from 6 to 1: Solution 1 has 2 step(s): divide 2 yields 3, divide 3 yields 1 Solution 2 has 2 step(s): divide 2 yields 3, subtract 2 yields 1 Solution 3 has 2 step(s): divide 3 yields 2, divide 2 yields 1 Solutions for path from 7 to 1: Solution 1 has 3 step(s): subtract 2 yields 5, subtract 2 yields 3, divide 3 yields 1 Solution 2 has 3 step(s): subtract 2 yields 5, subtract 2 yields 3, subtract 2 yields 1 Solutions for path from 8 to 1: Solution 1 has 3 step(s): divide 2 yields 4, divide 2 yields 2, divide 2 yields 1 Solution 2 has 3 step(s): divide 2 yields 4, subtract 2 yields 2, divide 2 yields 1 Solution 3 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, divide 3 yields 1 Solution 4 has 3 step(s): subtract 2 yields 6, divide 2 yields 3, subtract 2 yields 1 Solution 5 has 3 step(s): subtract 2 yields 6, divide 3 yields 2, divide 2 yields 1 Solutions for path from 9 to 1: Solution 1 has 2 step(s): divide 3 yields 3, divide 3 yields 1 Solution 2 has 2 step(s): divide 3 yields 3, subtract 2 yields 1 Solutions for path from 10 to 1: Solution 1 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, divide 3 yields 1 Solution 2 has 3 step(s): divide 2 yields 5, subtract 2 yields 3, subtract 2 yields 1 There are 1 with 17 steps for start between 1 and 2000: [1699] 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]
Perl 6
<lang perl6>use Lingua::EN::Numbers;
for [2,3], 1, 2000,
[2,3], 1, 50000, [2,3], 2, 2000, [2,3], 2, 50000 -> @div, $sub, $limit { my %min = 1 => {:op(), :v(1), :s(0)}; (2..$limit).map( -> $n { my @ops; @ops.push: ($n / $_, "/$_") if $n %% $_ for @div; @ops.push: ($n - $sub, "-$sub") if $n > $sub; my $op = @ops.min( {%min{.[0]}} ); %min{$n} = {:op($op[1]), :v($op[0]), :s(1 + %min{$op[0]})}; });
my $max = %min.max( {.value} ).value; my @max = %min.grep( {.value.== $max} )».key.sort(+*);
if $limit == 2000 { say "\nDivisors: {@div.perl}, subtract: $sub"; steps(1..10); } say "\nUp to {comma $limit} found {+@max} number{+@max == 1 ?? !! 's'} " ~ "that require{+@max == 1 ?? 's' !! } at least $max steps."; steps(@max);
sub steps (*@list) { for @list -> $m { my @op; my $n = $m; while %min{$n}{ @op.push: "{%min{$n}<op>}=>{%min{$n}<v>}"; $n = %min{$n}<v>; } say "($m) {%min{$m}} steps: ", @op.join(', '); } }
}</lang>
- Output:
Divisors: [2, 3], subtract: 1 (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /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 Up to 2,000 found 16 numbers that require at least 14 steps. (863) 14 steps: -1=>862, -1=>861, /3=>287, -1=>286, -1=>285, /3=>95, -1=>94, -1=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1079) 14 steps: -1=>1078, /2=>539, -1=>538, /2=>269, -1=>268, /2=>134, /2=>67, -1=>66, /2=>33, /3=>11, -1=>10, -1=>9, /3=>3, /3=>1 (1295) 14 steps: -1=>1294, /2=>647, -1=>646, /2=>323, -1=>322, /2=>161, -1=>160, /2=>80, /2=>40, /2=>20, /2=>10, -1=>9, /3=>3, /3=>1 (1439) 14 steps: -1=>1438, -1=>1437, /3=>479, -1=>478, -1=>477, /3=>159, /3=>53, -1=>52, /2=>26, /2=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1511) 14 steps: -1=>1510, /2=>755, -1=>754, /2=>377, -1=>376, /2=>188, /2=>94, -1=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1583) 14 steps: -1=>1582, /2=>791, -1=>790, -1=>789, /3=>263, -1=>262, -1=>261, /3=>87, /3=>29, -1=>28, -1=>27, /3=>9, /3=>3, /3=>1 (1607) 14 steps: -1=>1606, /2=>803, -1=>802, /2=>401, -1=>400, /2=>200, /2=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1619) 14 steps: -1=>1618, /2=>809, -1=>808, /2=>404, /2=>202, /2=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1691) 14 steps: -1=>1690, /2=>845, -1=>844, -1=>843, /3=>281, -1=>280, -1=>279, /3=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1727) 14 steps: -1=>1726, -1=>1725, /3=>575, -1=>574, -1=>573, /3=>191, -1=>190, -1=>189, /3=>63, /3=>21, /3=>7, -1=>6, /2=>3, /3=>1 (1823) 14 steps: -1=>1822, /2=>911, -1=>910, -1=>909, /3=>303, /3=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1871) 14 steps: -1=>1870, -1=>1869, /3=>623, -1=>622, -1=>621, /3=>207, /3=>69, /3=>23, -1=>22, /2=>11, -1=>10, -1=>9, /3=>3, /3=>1 (1895) 14 steps: -1=>1894, /2=>947, -1=>946, /2=>473, -1=>472, /2=>236, /2=>118, -1=>117, /3=>39, /3=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1907) 14 steps: -1=>1906, /2=>953, -1=>952, /2=>476, /2=>238, /2=>119, -1=>118, -1=>117, /3=>39, /3=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1919) 14 steps: -1=>1918, -1=>1917, /3=>639, /3=>213, /3=>71, -1=>70, /2=>35, -1=>34, /2=>17, -1=>16, /2=>8, /2=>4, /2=>2, /2=>1 (1943) 14 steps: -1=>1942, /2=>971, -1=>970, /2=>485, -1=>484, /2=>242, /2=>121, -1=>120, /2=>60, /2=>30, /3=>10, -1=>9, /3=>3, /3=>1 Up to 50,000 found 3 numbers that require at least 22 steps. (25919) 22 steps: -1=>25918, /2=>12959, -1=>12958, /2=>6479, -1=>6478, /2=>3239, -1=>3238, /2=>1619, -1=>1618, /2=>809, -1=>808, /2=>404, /2=>202, /2=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (31103) 22 steps: -1=>31102, /2=>15551, -1=>15550, /2=>7775, -1=>7774, /2=>3887, -1=>3886, /2=>1943, -1=>1942, /2=>971, -1=>970, /2=>485, -1=>484, /2=>242, /2=>121, -1=>120, /2=>60, /2=>30, /3=>10, -1=>9, /3=>3, /3=>1 (38879) 22 steps: -1=>38878, /2=>19439, -1=>19438, /2=>9719, -1=>9718, /2=>4859, -1=>4858, /2=>2429, -1=>2428, /2=>1214, /2=>607, -1=>606, /2=>303, /3=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 Divisors: [2, 3], subtract: 2 (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /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 Up to 2,000 found 1 number that requires at least 17 steps. (1699) 17 steps: -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 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
Python
Python: Recursive, with memoization
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.
<lang python> from functools import lru_cache
- %%
DIVS = {2, 3} SUBS = {1}
class Minrec():
"Recursive, memoised minimised steps to 1"
def __init__(self, divs=DIVS, subs=SUBS): self.divs, self.subs = divs, subs
@lru_cache(maxsize=None) def _minrec(self, n): "Recursive, memoised" if n == 1: return 0, ['=1'] possibles = {} for d in self.divs: if n % d == 0: possibles[f'/{d}=>{n // d:2}'] = self._minrec(n // d) for s in self.subs: if n > s: possibles[f'-{s}=>{n - s:2}'] = self._minrec(n - s) thiskind, (count, otherkinds) = min(possibles.items(), key=lambda x: x[1]) ret = 1 + count, [thiskind] + otherkinds return ret
def __call__(self, n): "Recursive, memoised" ans = self._minrec(n)[1][:-1] return len(ans), ans
if __name__ == '__main__':
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]: minrec = Minrec(DIVS, SUBS) print('\nMINIMUM STEPS TO 1: Recursive algorithm') print(' Possible divisors: ', DIVS) print(' Possible decrements:', SUBS) for n in range(1, 11): steps, how = minrec(n) print(f' minrec({n:2}) in {steps:2} by: ', ', '.join(how))
upto = 2000 print(f'\n Those numbers up to {upto} that take the maximum, "minimal steps down to 1":') stepn = sorted((minrec(n)[0], n) for n in range(upto, 0, -1)) mx = stepn[-1][0] ans = [x[1] for x in stepn if x[0] == mx] print(' Taking', mx, f'steps is/are the {len(ans)} numbers:', ', '.join(str(n) for n in sorted(ans))) #print(minrec._minrec.cache_info()) print()</lang>
- Output:
MINIMUM STEPS TO 1: Recursive algorithm Possible divisors: {2, 3} Possible decrements: {1} minrec( 1) in 0 by: minrec( 2) in 1 by: /2=> 1 minrec( 3) in 1 by: /3=> 1 minrec( 4) in 2 by: /2=> 2, /2=> 1 minrec( 5) in 3 by: -1=> 4, /2=> 2, /2=> 1 minrec( 6) in 2 by: /3=> 2, /2=> 1 minrec( 7) in 3 by: -1=> 6, /3=> 2, /2=> 1 minrec( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 minrec( 9) in 2 by: /3=> 3, /3=> 1 minrec(10) in 3 by: -1=> 9, /3=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 14 steps is/are the 16 numbers: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943 MINIMUM STEPS TO 1: Recursive algorithm Possible divisors: {2, 3} Possible decrements: {2} minrec( 1) in 0 by: minrec( 2) in 1 by: /2=> 1 minrec( 3) in 1 by: /3=> 1 minrec( 4) in 2 by: /2=> 2, /2=> 1 minrec( 5) in 2 by: -2=> 3, /3=> 1 minrec( 6) in 2 by: /3=> 2, /2=> 1 minrec( 7) in 3 by: -2=> 5, -2=> 3, /3=> 1 minrec( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 minrec( 9) in 2 by: /3=> 3, /3=> 1 minrec(10) in 3 by: /2=> 5, -2=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 17 steps is/are the 1 numbers: 1699
Python: Tabulated
The stretch goal is attempted.
The table to solve for N contains all the results from 1 up to N. This is used in the solution.
<lang python>class Mintab():
"Tabulation, memoised minimised steps to 1"
def __init__(self, divs=DIVS, subs=SUBS): self.divs, self.subs = divs, subs self.table = None # Last tabulated table self.hows = None # Last tabulated sample steps
def _mintab(self, n): "Tabulation, memoised minimised steps to 1" divs, subs = self.divs, self.subs
table = [n + 2] * (n + 1) # sentinels table[1] = 0 # zero steps to 1 from 1 how = [[] for _ in range(n + 2)] # What steps are taken how[1] = ['='] for t in range(1, n): thisplus1 = table[t] + 1 for d in divs: dt = d * t if dt <= n and thisplus1 < table[dt]: table[dt] = thisplus1 how[dt] = how[t] + [f'/{d}=>{t:2}'] for s in subs: st = s + t if st <= n and thisplus1 < table[st]: table[st] = thisplus1 how[st] = how[t] + [f'-{s}=>{t:2}'] self.table = table self.hows = [h[::-1][:-1] for h in how] # Order and trim return self.table, self.hows
def __call__(self, n): "Tabulation" table, hows = self._mintab(n) return table[n], hows[n]
if __name__ == '__main__':
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]: print('\nMINIMUM STEPS TO 1: Tabulation algorithm') print(' Possible divisors: ', DIVS) print(' Possible decrements:', SUBS) mintab = Mintab(DIVS, SUBS) mintab(10) table, hows = mintab.table, mintab.hows for n in range(1, 11): steps, how = table[n], hows[n] print(f' mintab({n:2}) in {steps:2} by: ', ', '.join(how))
for upto in [2000, 50_000]: mintab(upto) table = mintab.table print(f'\n Those numbers up to {upto} that take the maximum, "minimal steps down to 1":') mx = max(table[1:]) ans = [n for n, steps in enumerate(table) if steps == mx] print(' Taking', mx, f'steps is/are the {len(ans)} numbers:', ', '.join(str(n) for n in ans))</lang>
- Output:
MINIMUM STEPS TO 1: Tabulation algorithm Possible divisors: {2, 3} Possible decrements: {1} mintab( 1) in 0 by: mintab( 2) in 1 by: /2=> 1 mintab( 3) in 1 by: /3=> 1 mintab( 4) in 2 by: /2=> 2, /2=> 1 mintab( 5) in 3 by: -1=> 4, /2=> 2, /2=> 1 mintab( 6) in 2 by: /3=> 2, /2=> 1 mintab( 7) in 3 by: -1=> 6, /3=> 2, /2=> 1 mintab( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 mintab( 9) in 2 by: /3=> 3, /3=> 1 mintab(10) in 3 by: -1=> 9, /3=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 14 steps is/are the 16 numbers: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943 Those numbers up to 50000 that take the maximum, "minimal steps down to 1": Taking 22 steps is/are the 3 numbers: 25919, 31103, 38879 MINIMUM STEPS TO 1: Tabulation algorithm Possible divisors: {2, 3} Possible decrements: {2} mintab( 1) in 0 by: mintab( 2) in 1 by: /2=> 1 mintab( 3) in 1 by: /3=> 1 mintab( 4) in 2 by: /2=> 2, /2=> 1 mintab( 5) in 2 by: -2=> 3, /3=> 1 mintab( 6) in 2 by: /3=> 2, /2=> 1 mintab( 7) in 3 by: -2=> 5, -2=> 3, /3=> 1 mintab( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 mintab( 9) in 2 by: /3=> 3, /3=> 1 mintab(10) in 3 by: /2=> 5, -2=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 17 steps is/are the 1 numbers: 1699 Those numbers up to 50000 that take the maximum, "minimal steps down to 1": Taking 26 steps is/are the 1 numbers: 45925
zkl
<lang zkl>var minCache; // (val:(newVal,op,steps)) fcn buildCache(N,D,S){
minCache=Dictionary(1,T(1,"",0)); foreach n in ([2..N]){ ops:=List(); foreach d in (D){ if(n%d==0) ops.append(T(n/d, String("/",d))) } foreach s in (S){ if(n>s) ops.append(T(n - s,String("-",s))) } mcv:=fcn(op){ minCache[op[0]][2] }; // !ACK!, dig out steps v,op := ops.reduce( // find min steps to get to op
'wrap(vo1,vo2){ if(mcv(vo1)<mcv(vo2)) vo1 else vo2 });
minCache[n]=T(v, op, 1 + minCache[v][2]) // this many steps to get to n }
} fcn stepsToOne(N){ // D & S are determined by minCache
ops,steps := Sink(String).write(N), minCache[N][2]; do(steps){ v,o,s := minCache[N]; ops.write(" ",o,"-->",N=v); } return(steps,ops.close())
}</lang> <lang zkl>MAX, D,S := 50_000, T(2,3), T(1); buildCache(MAX,D,S);
do(2){
println("\nDivisors: %s, subtracters: %s".fmt(D.concat(","), S.concat(","))); foreach n in ([1..10]){ println("%2d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }
maxSteps:=minCache.reduce(fcn(mkv,kv){ if(mkv[1][2]>kv[1][2]) mkv else kv })[1][2]; biggies :=minCache.filter('wrap(kv){ kv[1][2]==maxSteps }).pump(List,fcn(kv){ kv[0].toInt() }).sort(); println("\nBelow %,d, found %d numbers that require %d steps (the mostest)." .fmt(MAX,biggies.len(),maxSteps)); foreach n in (biggies){ println("%,6d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }
S=T(2); buildCache(MAX,D,S);
}</lang>
- Output:
Divisors: 2,3, subtracters: 1 1: 0 steps: 1 2: 1 steps: 2 -1-->1 3: 1 steps: 3 /3-->1 4: 2 steps: 4 -1-->3 /3-->1 5: 3 steps: 5 -1-->4 -1-->3 /3-->1 6: 2 steps: 6 /3-->2 -1-->1 7: 3 steps: 7 -1-->6 /3-->2 -1-->1 8: 3 steps: 8 /2-->4 -1-->3 /3-->1 9: 2 steps: 9 /3-->3 /3-->1 10: 3 steps: 10 -1-->9 /3-->3 /3-->1 Below 50,000, found 3 numbers that require 22 steps (the mostest). 25,919: 22 steps: 25919 -1-->25918 -1-->25917 /3-->8639 -1-->8638 -1-->8637 /3-->2879 -1-->2878 -1-->2877 /3-->959 -1-->958 -1-->957 /3-->319 -1-->318 /3-->106 /2-->53 -1-->52 /2-->26 /2-->13 -1-->12 /3-->4 -1-->3 /3-->1 31,103: 22 steps: 31103 -1-->31102 -1-->31101 /3-->10367 -1-->10366 -1-->10365 /3-->3455 -1-->3454 -1-->3453 /3-->1151 -1-->1150 -1-->1149 /3-->383 -1-->382 -1-->381 /3-->127 -1-->126 /3-->42 /3-->14 /2-->7 -1-->6 /3-->2 -1-->1 38,879: 22 steps: 38879 -1-->38878 /2-->19439 -1-->19438 /2-->9719 -1-->9718 /2-->4859 -1-->4858 /2-->2429 -1-->2428 /2-->1214 /2-->607 -1-->606 /3-->202 -1-->201 /3-->67 -1-->66 /3-->22 -1-->21 /3-->7 -1-->6 /3-->2 -1-->1 Divisors: 2,3, subtracters: 2 1: 0 steps: 1 2: 1 steps: 2 /2-->1 3: 1 steps: 3 -2-->1 4: 2 steps: 4 -2-->2 /2-->1 5: 2 steps: 5 -2-->3 -2-->1 6: 2 steps: 6 /3-->2 /2-->1 7: 3 steps: 7 -2-->5 -2-->3 -2-->1 8: 3 steps: 8 -2-->6 /3-->2 /2-->1 9: 2 steps: 9 /3-->3 -2-->1 10: 3 steps: 10 /2-->5 -2-->3 -2-->1 Below 50,000, found 1 numbers that require 26 steps (the mostest). 45,925: 26 steps: 45925 -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 -2-->1