Measuring arbitrary times using arbitrary hourglasses

hourglass.py

def print_target_moves(aTimeCapacity, bTimeCapacity, targetTime):
    '''
    Given two hourglasses with respective time capacities,
    print out a process for measuring the given target time
    without going over that time.
    An hour glass can only be flipped when any of them have run out.
    TODO: generalize to multiple hour-glasses
    '''
    moves = []

    # given the times left on the hourglass, make a decision on which ones to flip right now.
    # (it is assumed that a legal flip can be made at the time this function is called)
    def make_flip_decision(aTimeLeft, bTimeLeft, timeElapsed):
        
        # help function for logging a successful move.
        def add_move(desc):
            moves.append("%ds: (%d, %d): %s" % (timeElapsed,aTimeLeft,bTimeLeft, desc)
        
        # time is overshot, return failure.
        if timeElapsed > targetTime:
            return False
            
        # time is met, return success.
        if timeElapsed == targetTime:
            add_move('success')
            return True

        # Given the time left on the given hourglasses, advance to the next closest time when a legal flip can be made.
        def progress_to_next_possible_flip(_aTimeLeft, _bTimeLeft):
            
            # Get valid decision times > 0.
            # (We don't consider a decision at 0 seconds, because we're exploring that moment in time already)
            decisionTimes = (t for t in (_aTimeLeft,_bTimeLeft) if t > 0)
            
            # Having no valid decision times means that all timers have run out, and we're doing nothing.
            # This constitutes us stopping the game, therefore a failure.
            if not decisionTimes:
                return False
            
            # Get the closest time that we can make a decision.
            waitTime = min(decisionTimes)
            
            return make_flip_decision(_aTimeLeft-waitTime, _bTimeLeft-waitTime, timeElapsed+waitTime)
            
        # Try four possible flips.

        # flip neither
        if progress_to_next_possible_flip(aTimeLeft,bTimeLeft):
            add_move('pass')
            return True

        # flip a
        if progress_to_next_possible_flip(aTimeCapacity-aTimeLeft,bTimeLeft):
            add_move('flip a')
            return True

        # flip b
        if progress_to_next_possible_flip(aTimeLeft,bTimeCapacity-bTimeLeft):
            add_move('flip b')
            return True

        # flip a,b
        if progress_to_next_possible_flip(aTimeCapacity-aTimeLeft,bTimeCapacity-bTimeLeft):
            add_move('flip both')
            return True

        return False

    make_flip_decision(aTimeCapacity, bTimeCapacity, 0)
    for move in reversed(moves):
        print move