Minimal steps down to 1: Difference between revisions

{{task}}

 

Given:

{{trans|Python: Tabulated}}

 

Set[Int] divs, subs

[Int] table

V mx = max(mintab.table[1..])

V ans = enumerate(mintab.table).filter((n, steps) -> steps == @mx).map((n, steps) -> n)

 

{{out}}

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

=={{header|FreeBASIC}}==

{{trans|XPL0}}

Dim Shared As Integer Subtractor '1 or 2

Dim Shared As Integer Ns(20000), Ops(20000), MinNs(20000), MinOps(20000)

ShowCount(2000) '4.

ShowCount(20000) '4a.

{{out}}

<pre>Same as XPL0 entry.</pre>

 

=={{header|Go}}==

 

import (

fmt.Println()

}

 

{{out}}

 

=={{header|Haskell}}==

import Data.List

import Data.Ord

(s, k) <- steps >>= run n

let (m, ss) = go k

 

<pre>λ> minSteps [Div 2, Div 3, Sub 1] 123

The task

 

showSteps = foldl go . show

where

head $ groupBy ((==) `on` (fst.snd)) $

sortOn (negate . fst . snd) $

 

<pre>λ> task1 [Div 2, Div 3, Sub 1]

 

Implementation:

~.((#~ 1<:]),y-/m),(#~ (=<.)),y%/n

}}

;@((<":y),,)"2((' -/'{~{.);":@{:)"1}:"2}:"1 paths

}}

 

Counting the steps is rather trivial -- we build a step function which subtracts the possible subtractors (discarding numbers which are too small) and divides by the possible divisors (discarding numbers which are not integers), then we iterate on that until we find a 1.

Task examples:

 

for_j. 1+i.10 do.

echo rplc&(' 1 steps';' 1 step')j,&":': ',(_1+#x steps y j),&":' steps.'

considering positive integers up to 20000

24 steps: 19681

 

=={{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]:

 

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

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>

<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">20000</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">50000</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

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

{{trans|Python}}

 

var table = Array(repeating: n + 2, count: n + 1)

var how = Array(repeating: [""], count: n + 2)

)

}

 

{{out}}

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