Minimal steps down to 1
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.
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]
</lang>
- Output:
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))