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.