Minimal steps down to 1: Difference between revisions
→{{header|jq}}
(Add Kotlin implementation) |
|||
Line 1,153:
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>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
<syntaxhighlight lang="jq">
### Generic functions
def array($n): . as $in | [range(0;$n)|$in];
def max(stream): reduce stream as $x (-infinite; if $x > . then $x else . end);
def plural: if . == 1 then " " else "s" end;
### Minimal Steps
# Input: { divs, subs, limit, mins }
# where .divs and .subs are the arrays of divisors and subtractors respectively,
# and .limit the value specified for task/1;
# .mins should be an array of arrays.
def minsteps($n):
if $n == 1
then .mins[1] = []
else .min = .limit
| .p = 0
| .q = 0
| .op = ""
| reduce .divs[] as $div (.;
if ($n % $div == 0)
then (($n/$div)|floor) as $d
| (.mins[$d]|length + 1) as $steps
| if $steps < .min
then .min = $steps
| .p = $d
| .q = $div
| .op = "/"
end
end )
| reduce .subs[] as $sub (.;
($n - $sub) as $d
| if $d >= 1
then (.mins[$d]|length + 1) as $steps
| if $steps < .min
then .min = $steps
| .p = $d
| .q = $sub
| .op = "-"
end
end)
| .mins[$n] = ["\(.op)\(.q) -> \(.p)"] + .mins[.p]
end ;
def task($limit):
range(0;2) as $r
| { divs: [2, 3],
subs: (if $r == 0 then [1] else [2] end),
mins: [],
$limit
}
| "\nWith: Divisors: \(.divs), Subtractors: \(.subs) =>",
" Minimum number of steps to diminish the following numbers down to 1 is:",
( foreach range(1; 1+$limit) as $i (.;
minsteps($i) # sets .min[$i]
| if ($i <= 10)
then (.mins[$i]|length) as $steps
| .emit = " \($i): \($steps) step\($steps|plural): \(.mins[$i] | join(", "))"
else .emit = null
end;
select(.emit).emit,
# ... and when all is done:
(select($i==$limit)
| foreach (2000, 20000, $limit) as $lim (.;
.max = max( .mins[0: 1 + $lim][] | length)
| .maxs = []
| .i = 0
| reduce .mins[0: 1 + $lim][] as $min (.;
if ($min|length) == .max then .maxs += [.i] end
| .i += 1 )
| .nums = (.maxs|length)
| (if .nums == 1 then "is" else "are" end) as $are
| (if .nums == 1 then "has" else "have" end) as $have
| .emit = " There \($are) \(.nums) number\(.nums|plural) in the range 1-\($lim)"
| .emit += " that \($have) maximum 'minimal steps' of \(.max):"
| .emit += "\n \(.maxs)";
.emit) ) ) )
;
task(50000)
</syntaxhighlight>
{{output}}
<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>
| |||