the path complexity (fastest route) to any given number in python

Question

Today I went to a math competition and there was a question that was something like this:

You have a given number n, now you have to like calculate what's the shortest route to that number, but there are rules.

1. You start with number 1
2. You end when you reach n
3. You can get to n either by doubling your previous number, or by adding two previous numbers.

Example: n = 25

Slowest route : 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25 (You just keep adding 1)

Fastest route : 1,2,4,8,16,24,25, complexity = 6

Example: n = 8 Fastest route : 1,2,4,8, complexity = 3

Example : n = 15 Fastest route : 1,2,3,6,9,15, complexity = 5

How do I make a program that can calculate the complexity of a given number n (with n <= 32)?

I already know that for any given number n ( n <= 32 ) that the complexity is lower that 1.45 x 2log(n). So now I only need to calculate all the routes with complexity below 1.45 x 2log(n) and than compare them and see which one is the fastest 'route'. But I have no idea how to put all the routes and all this in python, because the number of routes changes when the given number n changes.

This is what I have for now:

number = raw_input('Enter your number here : ')
startnumber = 1
complexity = 0

while startnumber <= number

Answer 1

I accept the challenge :)

The algorithm is relatively fast. It calculates the complexity of the first 32 numbers in 50ms on my computer, and I don't use multithreading. (or 370ms for the first 100 numbers.)

It is a recursive branch and cut algorithm. The _shortest function takes 3 arguments: the optimization lies in the max_len argument. E.g. if the function finds a solution with length=9, it stops considering any paths with a length > 9. The first path that is found is always a pretty good one, which directly follows from the binary representation of the number. E.g. in binary: 111001 => [1,10,100,1000,10000,100000,110000,111000,111001]. That's not always the fastest path, but if you only search for paths that are as least as fast, you can cut away most of the search tree.

#!/usr/bin/env python

# Find the shortest addition chain...
# @param acc List of integers, the "accumulator". A strictly monotonous
#        addition chain with at least two elements.
# @param target An integer > 2. The number that should be reached.
# @param max_len An integer > 2. The maximum length of the addition chain
# @return A addition chain starting with acc and ending with target, with
#         at most max_len elements. Or None if such an addition chain
#         does not exist. The solution is optimal! There is no addition
#         chain with these properties which can be shorter.
def _shortest(acc, target, max_len):
    length = len(acc)
    if length > max_len:
        return None
    last = acc[-1]
    if last == target:
        return acc;
    if last > target:
        return None
    if length == max_len:
        return None
    last_half = (last / 2)
    solution = None
    potential_solution = None
    good_len = max_len

    # Quick check: can we make this work?
    # (this improves the performance considerably for target > 70)
    max_value = last
    for _ in xrange(length, max_len):
        max_value *= 2
        if max_value >= target:
            break
    if max_value < target:
        return None

    for i in xrange(length-1, -1, -1):
        a = acc[i]
        if a < last_half:
            break

        for j in xrange(i, -1, -1):
            b = acc[j]
            s = a+b
            if s <= last:
                break

            # modifying acc in-place has much better performance than copying
            # the list and doing
            #   new_acc = list(acc)
            #   potential_solution = _shortest(new_acc, target, good_len)

            acc.append(s)
            potential_solution = _shortest(acc, target, good_len)
            if potential_solution is not None:
                new_len = len(potential_solution)
                solution = list(potential_solution)
                good_len = new_len-1

            # since we didn't copy the list, we have to truncate it to its
            # original length now.
            del acc[length:]

    return solution

# Finds the shortest addition chain reaching to n.
# E.g. 9 => [1,2,3,6,9]
def shortest(n):
    if n > 3:
        # common case first
        return _shortest([1,2], n, n)
    if n < 1:
        raise ValueError("n must be >= 1")
    return list(xrange(1,n+1))

for i in xrange(1,33):
    s = shortest(i)
    c = len(s) - 1
    print ("complexity of %2d is %d: e.g. %s" % (i,c,s))

Output:

complexity of  1 is 0: e.g. [1]
complexity of  2 is 1: e.g. [1, 2]
complexity of  3 is 2: e.g. [1, 2, 3]
complexity of  4 is 2: e.g. [1, 2, 4]
complexity of  5 is 3: e.g. [1, 2, 4, 5]
complexity of  6 is 3: e.g. [1, 2, 4, 6]
complexity of  7 is 4: e.g. [1, 2, 4, 6, 7]
complexity of  8 is 3: e.g. [1, 2, 4, 8]
complexity of  9 is 4: e.g. [1, 2, 4, 8, 9]
complexity of 10 is 4: e.g. [1, 2, 4, 8, 10]
complexity of 11 is 5: e.g. [1, 2, 4, 8, 10, 11]
complexity of 12 is 4: e.g. [1, 2, 4, 8, 12]
complexity of 13 is 5: e.g. [1, 2, 4, 8, 12, 13]
complexity of 14 is 5: e.g. [1, 2, 4, 8, 12, 14]
complexity of 15 is 5: e.g. [1, 2, 4, 5, 10, 15]
complexity of 16 is 4: e.g. [1, 2, 4, 8, 16]
complexity of 17 is 5: e.g. [1, 2, 4, 8, 16, 17]
complexity of 18 is 5: e.g. [1, 2, 4, 8, 16, 18]
complexity of 19 is 6: e.g. [1, 2, 4, 8, 16, 18, 19]
complexity of 20 is 5: e.g. [1, 2, 4, 8, 16, 20]
complexity of 21 is 6: e.g. [1, 2, 4, 8, 16, 20, 21]
complexity of 22 is 6: e.g. [1, 2, 4, 8, 16, 20, 22]
complexity of 23 is 6: e.g. [1, 2, 4, 5, 9, 18, 23]
complexity of 24 is 5: e.g. [1, 2, 4, 8, 16, 24]
complexity of 25 is 6: e.g. [1, 2, 4, 8, 16, 24, 25]
complexity of 26 is 6: e.g. [1, 2, 4, 8, 16, 24, 26]
complexity of 27 is 6: e.g. [1, 2, 4, 8, 9, 18, 27]
complexity of 28 is 6: e.g. [1, 2, 4, 8, 16, 24, 28]
complexity of 29 is 7: e.g. [1, 2, 4, 8, 16, 24, 28, 29]
complexity of 30 is 6: e.g. [1, 2, 4, 8, 10, 20, 30]
complexity of 31 is 7: e.g. [1, 2, 4, 8, 10, 20, 30, 31]
complexity of 32 is 5: e.g. [1, 2, 4, 8, 16, 32]

Answer 2

A brute force technique that simply searches through all the possible paths until it reaches its target. It is extremely fast as it does not evaluate numbers that have been reached with a lower complexity, but is guaranteed to find the optimal path.

# Use a node class that contains the number as well as a pointer to its parent
class Node:
    def __init__(self, number, parent):
        self.number = number
        self.parent = parent

    # get a list of all the numbers to reach this node
    def getPath(self):
        path = [self.number]
        parent = self.parent
        while parent != None:
            path.append(parent.number)
            parent = parent.parent
        return path

def solve(start, target):    
    currentList = []                                    # List of visited nodes in the previous round
    nextList = [Node(start, None)]                      # List of visited nodes in the next round (start with at least one number)
    seen = set([start])                                 # store all number that have already been seen in the previous round

    while nextList:                                     # continue until the final number has reached, on each iteration the complexity grows
        currentList = nextList                          # swap the lists around
        nextList = []

        for n in currentList:
            path = n.getPath()                          # fetch all the number that are needed to reach this point
            if n.number == target:                      # check of we have reach our target
                return path[::-1]                       # the path is in reverse at this point, so reverse it back
            for a in path:                              # for any combination of the last number and a previous number (including the last, which is the same as multiplying it by 2)
                newnumber = a + path[0]
                if newnumber <= target and newnumber not in seen:   # only evaluate the new number if is is not yet seen already on a lower complexity 
                    nextList.append(Node(newnumber, n))

        for n in nextList:                              # update the seen list
            seen.add(n.number)
    return []                                           # if the destination could not be reached

print "path to 25  = ", solve(1, 25)
print "path to 8   = ", solve(1, 8)
print "path to 15  = ", solve(1, 15)
print "path to 500 = ", solve(1, 500)

will output the following:

path to 25  = [1, 2, 4, 8, 16, 24, 25]
path to 8   = [1, 2, 4, 8]
path to 15  = [1, 2, 4, 5, 10, 15]
path to 500 = [1, 2, 4, 8, 16, 32, 64, 96, 100, 200, 400, 500]

I've tested this method to solve variables up to 500, and it was able to solve it in 0.36 seconds.

Answer 3

There is a dynamic programming solution to your problem since you either add any two numbers or multiply a number by 2 we can try all those cases and choose the minimum one also if the complexity of 25 was 5 and the route contains 9 then we know the solution for 9 which is 4 and we can use the solution for 9 to generate the solution for 25.We also need to keep track of every possible minimum solution for m to be able to use it to use it to solve n where m < n

def solve(m):
    p = [set([frozenset([])]) for i in xrange(m+1)] #contains all paths to reach n
    a = [9999 for _ in xrange(m+1)]
    #contains all complexities initialized with a big number
    a[1] = 0
    p[1] = set([frozenset([1])])
    for i in xrange(1,m+1):
        for pos in p[i]:
            for j in pos: #try adding any two numbers and 2*any number
                for k in pos:
                    if (j+k <= m):
                        if a[j+k] > a[i]+1:
                            a[j+k] = a[i] + 1
                            p[j+k] = set([frozenset(list(pos) + [j+k])])
                        elif a[j+k] == a[i]+1:
                            p[j+k].add(frozenset(list(pos) + [j+k]))
    return a[m],sorted(list(p[m].pop()))

n = int(raw_input())
print solve(n)

this can solve up to n = 100

For larger numbers you can get a 30% or more speedup by adding a couple lines to remove some redundant calculations from the inner loop. For this the pos2 variable is created and trimmed on each iteration:

def solve(m):
    p = [set([frozenset([])]) for i in xrange(m+1)] #contains all paths to reach n
    a = [9999 for _ in xrange(m+1)]
    #contains all complexities initialized with a big number
    a[1] = 0
    p[1] = set([frozenset([1])])
    for i in xrange(1,m+1):
        for pos in p[i]:
            pos2 = set(pos)
            for j in pos: #try adding any two numbers and 2*any number
                for k in pos2:
                    if (j+k <= m):
                        if a[j+k] > a[i]+1:
                            a[j+k] = a[i] + 1
                            p[j+k] = set([frozenset(list(pos) + [j+k])])
                        elif a[j+k] == a[i]+1:
                            p[j+k].add(frozenset(list(pos) + [j+k]))
                pos2.remove(j)
    return a[m],sorted(list(p[m].pop()))

Answer 4

Brute forcing this

def solve(m, path):
    if path[-1] == m:
        return path
    if path[-1] > m:
        return False
    best_path = [i for i in range(m)]

    test_path = solve (m, path + [path[-1]*2]) 
    if test_path and len(test_path) < len(best_path):
        best_path = test_path
    for k1 in path[:-1] :
        for k2 in path[:-1] :
            test_path = solve (m, path + [path[-1] + k1 + k2]) 
            if test_path and len(test_path) < len(best_path):
                #retain best
                best_path = test_path
    return best_path 

print (solve(19, [1,2])) #[1, 2, 4, 8, 16, 19]
print (solve(25, [1,2])) #[1, 2, 4, 8, 16, 25]

Runs fairly slow, I'm pretty sure a smarter solution exist but this look semantically correct