Minimum Steps to One to find minimum operations to transform n to 1 I was solving this dynamic programming problem, and I was wondering if I can get any code review and feedback. You can find this problem online.


#  Coding Problem: Minimum Steps to One
#
#  Prompt:    Given a positive integer, you can perform any combination of these 3 steps:
#             1.) Subtract 1 from it.
#             2.) If its divisible by 2, divide by 2.
#             3.) If its divisible by 3, divide by 3.
#
#             Find the minimum number of steps that it takes get from N to1
#



def min_steps_to_one(n):
    work = [0, 0]

    for i in range(2, n+1):
        min_choice = work[i-1]

        if i % 3 == 0:
          divide_by_three = work[i//3]
          min_choice = min(min_choice, divide_by_three)

        if i % 2 == 0:
          divide_by_two = work[i//2]
          min_choice = min(min_choice, divide_by_two)

        work.append(min_choice + 1)

    return work[n]


I also include some test cases for Minimum Steps to One Tests


true: should return 3 for 10
true: should return 0 for 1  
true: should work for large numbers PASSED: 3 / 3




def expect(count, name, test):
    if (count is None or not isinstance(count, list) or len(count) != 2):
        count = [0, 0]
    else:
        count[1] += 1

    result = 'false'
    error_msg = None
    try:
        if test():
            result = ' true'
            count[0] += 1
    except Exception as err:
        error_msg = str(err)

    print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
    if error_msg is not None:
        print('       ' + error_msg + '\n')


print('Minimum Steps to One Tests')
test_count = [0, 0]

def test():
  example = min_steps_to_one(10)
  return example == 3
expect(test_count, 'should return 3 for 10', test)

def test():
  example = min_steps_to_one(1)
  return example == 0
expect(test_count, 'should return 0 for 1', test)

def test():
  example = min_steps_to_one(1334425)
  return example == 22
expect(test_count, 'should work for large numbers', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')
Overall this looks very good. It's even fits nicely with PEP 8 guidelines.

I would suggest preallocating your array, with something like work = [0] * (n + 1) to help slightly with speed and memory use. append is slightly wasteful in that regard because it keeps resizing the array and copying its contents elsewhere.

In terms of naming, i could perhaps helpfully be renamed something like candidate and work could do with being renamed too. Nothing is that unclear though. 

It's good to see tests along with the code, and particularly good to see 1 tested. However, it's better to prefer standard testing libraries such as unittest to writing your own test routines. It's particularly hard to read code that redefines functions as you go, so if you must roll your own I'd strongly suggest redoing expect to take the input and expected output rather than some freshly defined test function. (But really, use a library!)



Finally, a comment on the underlying algorithm. The bottom up algorithm here is simple, thorough, and correct which are all good things. However, it is potentially wasteful because it has to check every number up to the target. 

Consider that every number is either even or is 1 away from being even. Therefore you can always either divide or divide next time. That means that, even without the rule about 3s, you should expect the solution to take at worst \$ 2 log_2(n) \$ steps. That in turn indicates that at almost all of the second half of your work list for large numbers is guaranteed to be unused: you can't divide to it (because you can't divide by less than 2) and it's not worth stepping to it 1 element at a time because that would quickly overshoot the logarithmic lower bound. (Experimentally, if you check the value for say 10,000,000 then over 70% of entries in your cache have paths at least as long as your target path and so are useless to you.)

Therefore, consider instead using a top-down dynamic programming approach instead of a bottom up one to avoid storing results that you are never going to use. (Essentially, this works out as a breadth first search.)