5
\$\begingroup\$

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

  1. true: should return 3 for 10
  2. true: should return 0 for 1
  3. 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')
\$\endgroup\$
6
\$\begingroup\$

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.)

\$\endgroup\$
  • 3
    \$\begingroup\$ It's even possible to do slightly better than breadth-first search, although at the cost of more complex code. Breadth-first search is essentially Dijkstra's algorithm, but there's an admissible heuristic derived from the log base 3 which allows the use of A*. \$\endgroup\$ – Peter Taylor Aug 8 '18 at 8:43
  • 1
    \$\begingroup\$ I like that! If using dijkstra or A* approach, and so able to consider different edge weights, it is also possible to jump down to the next suitable multiple of 2 or 3 rather than adding branches for subtractions. \$\endgroup\$ – Josiah Aug 8 '18 at 11:41
2
\$\begingroup\$

after @Josiah 's answer, i'd suggest some formatting as in the case of

print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)

to

print('  {})   {} : {}'.format(str(count[1]), result, name))

string concatenation should be avoided as it obfuscates if many variables or expressions

i'd also suggest using the logging module

\$\endgroup\$
2
\$\begingroup\$

This is an alternate to your function which I made out of curiosity. It is similar to yours. It checks the 'path to minimum' with a list.

However, unlike your code, it tests from the top-down rather than from the bottom-up, as suggested by @Josiah. I find this approach way easier to follow in debug mode; checking the currentoptions list I can see where the solution is going and how close it is from getting to one.

The initial content of the list is the given number. Then, every step, it applies all the possible operations to the number/numbers in the list and stores the multiple results in the list. That way all the possible paths to one are being followed. If number 1 shows up in the list, the iterations stop.

def min_steps_to_one(n):
    if not isinstance(n, int):
        # you can raise an error here
        return None

    if n < 1:
        # you can raise an error here
        return None

    nsteps = 0
    currentoptions = [n]

    while True:
        if 1 in currentoptions:
            break

        thisround = currentoptions[:]
        currentoptions = []

        for i in thisround:

            if i % 3 == 0:
                currentoptions.append( i // 3 )
            if i % 2 == 0:
                currentoptions.append( i // 2 )
            currentoptions.append( i - 1 )

        nsteps += 1

    return nsteps
\$\endgroup\$
  • \$\begingroup\$ Fair comment - I just clarified it. \$\endgroup\$ – jberrio Aug 9 '18 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.