2
\$\begingroup\$

Your task is to print all unique ways to climb a staircase of length n where, from each step, you can take steps of size x where x is an integer value from an array For example: if you want to climb a staircase of length 3 and you can move [1, 2] steps from each stair, the output should be

 [1, 1, 1]
 [1, 2]
 [2, 1]

Note the order is important and hence [1, 2] is different to [2, 1].

Is this the fastest way to solve this problem (without using built in libraries such as itertools)?

def valid_moves(position, target, legal, path, permutations):
    if position > target:
        return
    if position == target:
        permutations.append(path)
        return 
    for move in legal:
        valid_moves(position + move, target, legal, path + [move], permutations)
    return permutations


start = 0
length_staircase = 3
legal_moves = [1, 2]

print(*valid_moves(start, length_staircase, legal_moves, [], []), sep="\n")

\$\endgroup\$
  • \$\begingroup\$ How general is the problem you are trying to resolve? Most of the problems with your approach only shows up in the more complicated and larger cases, so if you are only trying to resolve problems close to the scale in the example, then the more advanced methods might have too much overhead. \$\endgroup\$ – Ninetails Jul 17 at 14:36
  • \$\begingroup\$ I am trying to solve the problem for the most general case. \$\endgroup\$ – EML Jul 17 at 14:37
1
\$\begingroup\$

Performance Problems

Your current solution works decent for small cases, but there are a few problems when the problem starts to scale up, which causes the performance to drop. I will mention the two biggest I have found.

  1. You construct all paths toward the goal, even the unviable ones, in full until you remove them. This causes an exponential amount of extra paths to tried (though you might also have exponential amount of results).
  2. The + on lists causes full rebuilding of the lists, which causes a single path to cost O(n^2) to construct. Note that this cost is shared with some of the other paths investigated, which may cause the amortized cost to still be O(n) when you share it with exponential amount of paths.

Note that the first problem may overshadow the second, and that if the smallest move is a common divisor of all the other moves and the result, then early prunning of paths is impossible (because they may only make a mistake on the last step).

Solution

We seperate the solution into the subsections that resolve each of the problems mentioned in the problem section, and a subsection for the combined result. The way presented here is just one way to solve the above mentioned problem in a way that remains close to the OP.

Early Prunning

To solve the problem of exponentially many paths that lead to no result, we can try to find a way to early stop a path early on if we know that it cannot possible lead to a result. If we have a function that tells us whether we can walk a certain distance we can implement valid_moves in this simple form (note I changed the names valid_moves->valid_paths, legal->moves, and permutations->results and I will be using these names going forward):

def valid_paths(position, target, moves, path, results, is_legal=lambda x: x >= 0):
    for move in moves:
        new_position = position + move
        if is_legal(target - new_position):
            new_path = path + [move]
            if new_position == target:
                results.append(new_path)
            else:
                valid_moves(new_position, target, moves, new_path, results)
    return results

So how do we construct a usefull is_legal function? One way to do this is to construct all the reachable path lengths and check if the remaining distance is such a reachable path. The way I will show here to construct all the reachable paths lengths is through dynamic programming:

def construct_is_legal(moves, distance):
    if not moves:
        return lambda length: length==0
    lengths_to_check = [move for move in moves]
    lengths_reachable = {move for move in moves}

    min_length = min(lengths_to_check) # used by shortcut
    if distance % min_length  and all(move % min_length  == 0 for move in moves):
        return lambda length: length >= 0 and length % min_length

    while lengths_to_check:
        move = lengths_to_check.pop()
        lengths_to_add = []
        for length in lengths_reachable:
            new_length = length+move
            if new_length not in lengths_reachable and new_length <= distance:
                lengths_to_add.append(new_length)
        for new_length in lengths_to_add:
            lengths_to_check.append(new_length)
            lengths_reachable.add(new_length)

    lengths_reachable.add(0) # we can always reach the same place
    return lambda length: length in lengths_reachable

Note that we use sets to have fast checks for inclusion (they are implemented kind of like hash-tables under the hood according to this answer), so we can expect the assymtotic cost to be below of the brute force test of each possible path, as we only check once for each reached position and not for every way to reach said position. Also note that I added some special cases (no results and every number divisiable by the lowest move), so we do not do all the extra work when there is a simple solution to the problem.

Delayed Concatenation

To solve the problem of O(n^2) cost for building a result (now more relevant since we have cut out the extra false paths it might have been sharing the cost with), we need to ensure we do not have to build the full list when we branch out several versions of it. We can do this by reversed directed linked tree, where each node is a move and point toward the move it took previously. Here is a simple implementation of it:

class Path:
    def __init__(self,value, prev=None):
        self.value = value
        self.prev = prev

    def to_list(self):
        result = [self.value]
        prev = self.prev
        while previs not None:
            result.append(prev.value)
            prev = parent.prev
        result.reverse()
        return result

We can then replace the new_path = path + [move] with new_path = Path(move, prev=path), and when we add a result we also need to replace results.append(new_path) with results.append(new_path.to_list()). We could also just add the Path objects and let the user convert them to lists of moves when they need to, since the space complexity of storing many similar paths is much lower due to reuse of space for shared parts of the paths.

Combined

We now need to combine the parts into a whole solution. For convinience I have combined many of the tedious parts of the original into a function, which handle the combined solution:

class Path:
    def __init__(self,value, prev=None):
        self.value = value
        self.prev = prev

    def to_list(self):
        result = [self.value]
        prev = self.prev
        while previs not None:
            result.append(prev.value)
            prev = parent.prev
        result.reverse()
        return result


def construct_is_legal(moves, distance):
    if not moves:
        return lambda length: length==0
    lengths_to_check = [move for move in moves]
    lengths_reachable = {move for move in moves}

    min_length = min(lengths_to_check) # used by shortcut
    if distance % min_length  and all(move % min_length  == 0 for move in moves):
        return lambda length: length >= 0 and length % min_length

    while lengths_to_check:
        move = lengths_to_check.pop()
        lengths_to_add = []
        for length in lengths_reachable:
            new_length = length+move
            if new_length not in lengths_reachable and new_length <= distance:
                lengths_to_add.append(new_length)
        for new_length in lengths_to_add:
            lengths_to_check.append(new_length)
            lengths_reachable.add(new_length)

    lengths_reachable.add(0) # we can always reach the same place
    return lambda length: length in lengths_reachable


def list_paths(position, target, moves, path, results, is_legal=lambda x: x >= 0):
    for move in moves:
        new_position = position + move
        if is_legal(target - new_position):
            new_path = Path(move, prev=path)
            if new_position == target:
                results.append(new_path.to_list())
            else:
                valid_moves(new_position, target, moves, new_path, results)
    return results


def valid_paths(target, moves, start=0):
    is_legal = construct_is_legal(moves, target-start)
    if is_legal(target-start): 
        return list_paths(start, target, moves, path=None, result=[], is_legal=is_legal)
    else:    
        return [] # no paths exist


if __name__ == '__main__':
    print(*valid_paths(3, [1, 2]), sep='\n')

Note that we have wrapped many of the annoying parts of the interface into the new valid_paths, and had it also handle the special case of no possible results early on.

Alternative

You may have noticed that the construction in is_legal is fairly close to actually solving the full problem, and we can indeed solve the entire problem with this dynamic programming approach by changing the set lengths_reachable from a set to a dictionary of combinations we can reach a given length with. Once we have such a dictionary we can easily list the paths by going from the full distance and recursively divide up the problem into the possible subpaths and then combine all the results. Here is an implementation:

def chain(*generators):
    for generator in generators:
        yield from generator


def dynamic_build(moves, distance):
    """ Build a dictionary of possible subpath decomposition up to distance"""
    lengths_to_check = [move for move in moves]
    lengths_reachable = {move:{move} for move in moves}

    while lengths_to_check:
        move = lengths_to_check.pop()
        lengths_to_add = {}
        for length in lengths_reachable:
            new_length = length+move
            lower, upper = (move, length) if move <= length else (length, move)
            if new_length <= distance:
                if new_length in lengths_reachable:
                    lengths_reachable[new_length].add((lower,upper))
                else:
                    if new_length in lengths_to_add:
                        lengths_to_add[new_length] = {(lower, upper)}
                    else:
                        lengths_to_add[new_length].add((lower, upper))
        for new_length in lengths_to_add:
            lengths_to_check.append(new_length)
            lengths_reachable[new_length]= lengths_to_add[new_length]

    return lengths_reachable


def list_paths(lengths_reachable, target):
    main_node = lengths_reachable[target]
    results = []
    for way in main_node:
        if len(way) == 1:
              results.append([way])
        else:
            lower, upper = way
            lower_results = list_paths(lengths_reachable, lower)
            upper_results = list_paths(lengths_reachable, upper)
            for low_path in lower_results:
                for high_path in upper_results:
                    results.append(chain(low_path, high_path))
                    results.append(chain(high_path, low_path))
    return results


def valid_paths(target, moves, start=0):
    distance = target - start
    lengths_reachable = dynamic_build(moves, distance)
    if distance not in lengths_reachable:
        return [] 
    return list(map(list, list_paths(lengths_reachable, distance)))


if __name__ == '__main__':
    print(*valid_paths(3, [1, 2]), sep='\n')

While the work of the alternative is about as much as the other solution, it does provide some more information about the solution, which may be usefull in related problems.

Notes

It should be noted that both the original and the solutions provided here all make use of recoursion. The problem is that python does not really like deep recursion (it has poor performance, to the point where the recursion stack is limited to about 1000). This problem is close to exponential in this depth though, so we need some fairly special cases for us to not run into other problems first. If we are indeed in such special cases, then we would need to change the above algorithms from recursive formulation to loop based versions or find a new alternative of this form.

\$\endgroup\$
3
\$\begingroup\$

I have a few suggestions for you:

  • You should get in the habit on wrapping all code that isn't in a function in a main guard, to ensure that that code only runs if that file is running, and to protect it from import mishaps
  • Running your code with pylint, a few warnings that popped up were:
    • Returns: All return statements should return something or none of them should return anything. Since you are returning permutations, the other return's should just return None.
    • Module Docstring: Your function should contain a docstring describing what the function does, even if it's very obvious. These will help any documentation.
    • Constant variable names: Since the three variables in the main guard do not change, they should be in all UPPERCASE to make it clear that they are constants.

Refactored code:

def valid_moves(position, target, legal, path, permutations):
    """ Returns unique ways to climb a staircase with passed length `target` """
    if position > target:
        return None
    if position == target:
        permutations.append(path)
        return None
    for move in legal:
        valid_moves(position + move, target, legal, path + [move], permutations)
    return permutations

if __name__ == '__main__':
    START = 0
    STAIRCASE_LENGTH = 3
    LEGAL_MOVES = [1, 2]

    print(*valid_moves(START, STAIRCASE_LENGTH, LEGAL_MOVES, [], []), sep="\n")
\$\endgroup\$
  • \$\begingroup\$ I disagree with the change of the input variables to the function being in CONSTANT style, since they aren't supposed to be referenced directly as constants, they are just variables that happen to live in the global space that does not need to change their value. To see whether a variable should be in CONSTANT style, we simply need to consider whether they would still work if the global code they work on was isolated inside a function (effectively extracting the __name__ == '__main__' into a ´main()` function, if they still work (they do) then they are not true global constants. \$\endgroup\$ – Ninetails Jul 18 at 8:14

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.