Google Foobar Level 2A

March 17, 2022

Here's the problem statement

I already did that

Time alloted: 7 days

Commander Lambda uses an automated algorithm to assign minions randomly to tasks, in order to keep her minions on their toes. But you've noticed a flaw in the algorithm - it eventually loops back on itself, so that instead of assigning new minions as it iterates, it gets stuck in a cycle of values so that the same minions end up doing the same tasks over and over again. You think proving this to Commander Lambda will help you make a case for your next promotion.

You have worked out that the algorithm has the following process: 1) Start with a random minion ID n, which is a nonnegative integer of length k in base b 2) Define x and y as integers of length k. x has the digits of n in descending order, and y has the digits of n in ascending order 3) Define z = x - y. Add leading zeros to z to maintain length k if necessary 4) Assign n = z to get the next minion ID, and go back to step 2

or example, given minion ID n = 1211, k = 4, b = 10, then x = 2111, y = 1112 and z = 2111 - 1112 = 0999. Then the next minion ID will be n = 0999 and the algorithm iterates again: x = 9990, y = 0999 and z = 9990 - 0999 = 8991, and so on.

Depending on the values of n, k (derived from n), and b, at some point the algorithm reaches a cycle, such as by reaching a constant value. For example, starting with n = 210022, k = 6, b = 3, the algorithm will reach the cycle of values [210111, 122221, 102212] and it will stay in this cycle no matter how many times it continues iterating. Starting with n = 1211, the routine will reach the integer 6174, and since 7641 - 1467 is 6174, it will stay as that value no matter how many times it iterates.

Given a minion ID as a string n representing a nonnegative integer of length k in base b, where 2 <= k <= 9 and 2 <= b <= 10, write a function solution(n, b) which returns the length of the ending cycle of the algorithm above starting with n. For instance, in the example above, solution(210022, 3) would return 3, since iterating on 102212 would return to 210111 when done in base 3. If the algorithm reaches a constant, such as 0, then the length is 1.

And here are the assigned test cases

    Input:
    solution.solution('1211', 10)
    Output: 1

    Input:
    solution.solution('210022', 3)
    Output: 3

I wrote a simple while loop to iterate through the logic of deriving the x and y from the original number, then checking if the whole sequence is looping around a fixed set of numbers.

Here's the entire solution:

    # solution 

    def getAscSortDigits(number):
        asc = [i for i in str(number)]
        asc.sort()
        return ''.join(asc)

    def getDescSortDigits(number):
        asc = [i for i in str(number)]
        asc.sort(reverse=True)
        return ''.join(asc)

    def convDecToBaseB(number, baseB):
        numberInBaseB = ''
        while (number > 0):
            res = divmod(number, baseB)
            numberInBaseB += str(res[1]) if (res[1] < 10) else  chr(ord('a')+res[1]-10)
            number = res[0]
        return numberInBaseB[::-1]

    def padStringWithZeroes(string, length):
        return string.rjust(length, '0');

    def diffInBaseB(descNum, ascNum, baseB):
        differenceInDecimal = int(descNum, baseB) - int(ascNum, baseB)
        differenceInBaseb   = convDecToBaseB(differenceInDecimal, baseB)
        return padStringWithZeroes(differenceInBaseb, len(descNum))

    def lookForCycleIndex(needle, hayStack):
        if needle in hayStack:
            return hayStack.index(needle)
        else:
            return False

    def solution(n, b):
        n = str(n)
        baseB = int(b)

        try:
            cntr = 0
            breakLoop = False
            listOfZs = [n]      

            while (breakLoop == False) :
                descNum   = getDescSortDigits(listOfZs[cntr])
                ascNum    = getAscSortDigits(listOfZs[cntr])
                zb        = diffInBaseB(descNum, ascNum, baseB)
                matchIndx = lookForCycleIndex(zb, listOfZs)

                if (matchIndx == False):
                    listOfZs.append(zb.lower())
                    cntr += 1
                elif ((matchIndx+1)==len(listOfZs)):
                    return 1
                elif (cntr >= 2147483645):
                    breakLoop = True
                    return 0
                else:
                    breakLoop = True
                    return (len(listOfZs) - matchIndx)

        except Exception as e:
            print(e)
            return 0

    if __name__ == "__solution__":
      solution()

For questions or suggestions, please DM me @sandeep_gopal.

Link to the main topic page: Meet Google Foobar.