Anonymous user
Minimal steps down to 1: Difference between revisions
→{{header|zkl}}: added code
m (→{{header|Python}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
Line 361:
=={{header|zkl}}==
<lang zkl>var minCache=Dictionary(1,T(1,"",0)); // (val:(newVal,op,steps))
<lang zkl></lang>▼
fcn buildCache(N,D,S){
<lang zkl></lang>▼
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 zkl>MAX, D,S := 50_000, T(2,3), T(1);
buildCache(MAX,D,S);
println("Divisors: %s, subtracters: %s".fmt(D.concat(","), S.concat(",")));
foreach n in ([1..10]){ println("%2d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }
do(2){
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();
print("\nBelow %,d, found %d numbers that require at least %d steps."
.fmt(MAX,biggies.len(),maxSteps));
println(" Divisors: %s, subtracters: %s".fmt(D.concat(","), S.concat(",")));
foreach n in (biggies){ println("%,6d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }
S=T(2);
minCache=Dictionary(1,T(1,"",0)); buildCache(MAX,D,S);
{{out}}
<pre>
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 at least 22 steps. Divisors: 2,3, subtracters: 1
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
Below 50,000, found 1 numbers that require at least 26 steps. Divisors: 2,3, subtracters: 2
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
</pre>
| |||