Skip to main content
2 of 2
added 1404 characters in body
Winston Ewert
  • 30.4k
  • 4
  • 51
  • 79

You've got tree paths encoded as integers such as: 10030201. Your code would much easier to write if instead they tuples like: (10, 03, 02, 01). If at all possible, you should change your dictionary to always use tuples. If not possible, have a function to convert the integers to tuples when you need them. If you do that, you'll find its fairly easy to devise a general implementation of your BACKS logic.

On the stylistic front: We typically use ALL_CAPS only for constants. We use lowercase_with_underscores for local variables which all of your stuff appears to be.

My solution:

def calculate_backs(source, destination):
    """
    Return how many "resets" are required to transform source into destination
    """
    
    def as_tuple(id_number):
        """
        Converts the id_number into a path sequence: 
        10010200 becomes (10, 1, 2)
        """
        pieces = []
        while id_number:
          pieces.append(id_number % 100)
          id_number /= 100
        pieces.reverse()
        
        # position 0 denotes a root node in the tree, so remove any trailing
        # zeros.
        while pieces[-1] == 0:
          pieces.pop()
        return tuple(pieces)
    
    def calculate(source, destination):
        if source and destination and source[0] == destination[0]:
            # If both source and destination agree for the first piece of the
            # path, drop that piece and determine the number of resets required
            # for the rest.
            return calculate(source[1:], destination[1:])
        else:
            # If the path disagrees on the first piece, we have to reset 
            # everything remaining in both paths.
            return len(source) + len(destination)

    return calculate(as_tuple(source), as_tuple(destination))
Winston Ewert
  • 30.4k
  • 4
  • 51
  • 79