~~Little~~ Big Python Number Puzzle

Jan 28, 2020
`python`

A ~~little~~ big python puzzle given to me by a coworker.

# Problem

Given a positive integer `N`

, find the smallest number of steps it will take to reach 1.

There are two kinds of permitted steps:

- You may decrement
`N`

to`N-1`

. - If
`a * b = N`

, you may decrement`N`

to the larger of`a`

and`b`

.

For example, given 100, you can reach 1 in five steps with the following route: `100 => 9 => 3 => 2 =>1`

Another route that is also five steps: `100 => 10 => 5 => 4 => 2 => 1`

# My approach

`from math import sqrt`

```
def prime(n):
is_prime = True
for x in range(2, int(sqrt(n))+1):
if n % x == 0:
is_prime = False
return(is_prime)
```

```
def lowest_max_prime_factor_pairs(n):
max_prime_factors_pairs = list()
for x in range(1, int(sqrt(n))+1):
if n % x == 0:
max_prime_factors_pairs.append(max(x, int(n/x)))
return(min(max_prime_factors_pairs))
```

```
def puzzle_steps(n):
steps = list()
steps.append(n)
while n != 1:
if prime(n):
n = n-1
steps.append(n)
else:
n = lowest_max_prime_factor_pairs(n)
steps.append(n)
return(steps)
```

```
def print_puzzle_steps(n):
steps = puzzle_steps(n)
path_steps = str(steps[0])
for x in range(1, len(steps)):
path_steps += ' => ' + str(steps[x])
print('Number of steps: ' + str(len(steps)-1))
print('Path of steps: ' + path_steps)
```

# Examples

`print_puzzle_steps(100)`

```
Number of steps: 5
Path of steps: 100 => 10 => 5 => 4 => 2 => 1
```

`print_puzzle_steps(1001)`

```
Number of steps: 7
Path of steps: 1001 => 77 => 11 => 10 => 5 => 4 => 2 => 1
```

`print_puzzle_steps(856)`

```
Number of steps: 9
Path of steps: 856 => 107 => 106 => 53 => 52 => 13 => 12 => 4 => 2 => 1
```

# Issue…

I found an example of a number that doesn’t work with this solution: 82. The fastest path would be `82 => 81 => 9 => 3 => 2 => 1`

. Instead, my solution does `82 => 41 => 40 => 8 => 4 => 2 => 1`

.

In order to solve this, you probably need to check all possible paths. The brute force method is computationally expensive, so cutting out incorrect paths is important. Another potentially useful idea is implementing a bottom-up approach where you start from 1 and move up to your target number.

I haven’t tried to write out a full solution. This is definitely a tougher problem than I thought it was on the outset.