8 months, 3 weeks

Google Foobar Challenge

Recently, I was browsing on the internet and searching for some Python related concepts and then my browser split in half, asking me if I was “up for a challenge”. After a little googling, I realized this was some sort of coding challenge by Google with something about saving bunnies. 

Upon starting you are greeted with a unix shell interface. You can interact with the shell using standard unix commands like "ls", "cat" and "cd". You find a journal entry at the very beginning which explains the situation to you. A bunny themed Star Wars fanfic story that you have to code your way through.

The Google Foobar challenge consisted of 5 Levels.
Level 1 consisted of a single question.           [48 hours/question]
Level 2 consisted of two questions.                [72 hours/question]
Level 3 consisted of three questions.             [96 hours/question]
Level 4 consisted of two questions.                [15 days/question]
Level 5 consisted of one question.                 [24 days/question]



Level 1: Re-ID



There's some unrest in the minion ranks: minions with ID numbers like "1", "42", and other "good" numbers have been lording it over the poor minions who are stuck with more boring IDs. To quell the unrest, Commander Lambda has tasked you with reassigning everyone new, random IDs based on her Completely Foolproof Scheme. 

She's concatenated the prime numbers in a single long string: "2357111317192329...". Now every minion must draw a number from a hat. That number is the starting index in that string of primes, and the minion's new ID number will be the next five digits in the string. So if a minion draws "3", their ID number will be "71113". 

Help the Commander assign these IDs by writing a function answer(n) which takes in the starting index n of Lambda's string of all primes, and returns the next five digits in the string. Commander Lambda has a lot of minions, so the value of n will always be between 0 and 10000.

Test cases

I have used this code to complete level 1...


def solution(b):                                                   
    bag = "2"                                                        
    for n in range(0,20500):                                 
        if n > 1:                                                       
            for j in range(2,n):                                  
                if (n % j) == 0:                                    
                elif len(bag) >= 10006:                     
                elif j==n-1:                                        
                    bag += str(n)                                

    return bag[b:b+5]                                                                        


Level 2: Bunny Prisoner Locating


Keeping track of Commander Lambda's many bunny prisoners is starting to get tricky. You've been tasked with writing a program to match bunny prisoner IDs to cell locations.

The LAMBCHOP doomsday device takes up much of the interior of Commander Lambda's space station, and as a result the prison blocks have an unusual layout. They are stacked in a triangular shape, and the bunny prisoners are given numerical IDs starting from the corner, as follows:

| 7
| 4 8
| 2 5 9
| 1 3 6 10

Each cell can be represented as points (x, y), with x being the distance from the vertical wall, and y being the height from the ground. 

For example, the bunny prisoner at (1, 1) has ID 1, the bunny prisoner at (3, 2) has ID 9, and the bunny prisoner at (2,3) has ID 8. This pattern of numbering continues indefinitely (Commander Lambda has been taking a LOT of prisoners). 

Write a function answer(x, y) which returns the prisoner ID of the bunny at location (x, y). Each value of x and y will be at least 1 and no greater than 100,000. Since the prisoner ID can be very large, return your answer as a string representation of the number.



def solution(pegs):                                                                  
    prop_sol = 2*(sum(pegs[1::2]) - sum(pegs[::2])) + pegs[0]

    if len(pegs) % 2 == 0:                                                        
        prop_sol = 2* (prop_sol - pegs[-1])                               
        if prop_sol/3 < 1:                                                                
            return [-1,-1]                                                                
        if prop_sol % 3 == 0:                                                    
            ret_val = [prop_sol/3,1]
            ret_val = [prop_sol,3]                                                
        prop_sol = 2* (prop_sol + pegs[-1])
        if prop_sol < 1:
            return [-1,-1]
            ret_val = [prop_sol, 1]
    last_gear = ret_val[0]/ret_val[1]
    for i in range(len(pegs)-1):
        last_gear = pegs[i+1]-pegs[i] - last_gear
        if last_gear < 1:
            return [-1,-1]
    return ret_val                                                             


Fuel Injection Perfection

Commander Lambda has asked for your help to refine the automatic quantum antimatter fuel injection system for her LAMBCHOP doomsday device. It's a great chance for you to get a closer look at the LAMBCHOP - and maybe sneak in a bit of sabotage while you're at it - so you took the job gladly. 

Quantum antimatter fuel comes in small pellets, which is convenient since the many moving parts of the LAMBCHOP each need to be fed fuel one pellet at a time. However, minions dump pellets in bulk into the fuel intake. You need to figure out the most efficient way to sort and shift the pellets down to a single pellet at a time. 

The fuel control mechanisms have three operations: 

1) Add one fuel pellet
2) Remove one fuel pellet
3) Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)

Write a function called solution(n) which takes a positive integer as a string and returns the minimum number of operations needed to transform the number of pellets to 1. The fuel intake control panel can only display a number up to 309 digits long, so there won't ever be more pellets than you can express in that many digits.

For example:
solution(4) returns 2: 4 -> 2 -> 1
solution(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1


def solution(n):                                        
    n = int(n)                                             
    i = 0                                                 
    while n > 1:                                         
        if (n&1) == 0:                                     
            n >>= 1                                   
        elif (n&3) == 1 or n == 3:                   
            n -= 1                      
            n += 1                                
        i += 1                                
    return i                                  


Level 3: Doomsday Fuel (absorbing Markov Chain problem)
Making fuel for the LAMBCHOP’s reactor core is a tricky process because of the exotic matter involved. It starts as raw ore, then during processing, begins randomly changing between forms, eventually reaching a stable form. There may be multiple stable forms that a sample could ultimately reach, not all of which are useful as fuel.

Commander Lambda has tasked you to help the scientists increase fuel creation efficiency by predicting the end state of a given ore sample. You have carefully studied the different structures that the ore can take and which transitions it undergoes. It appears that, while random, the probability of each structure transforming is fixed. That is, each time the ore is in 1 state, it has the same probabilities of entering the next state (which might be the same state). You have recorded the observed transitions in a matrix. The others in the lab have hypothesized more exotic forms that the ore can become, but you haven’t seen all of them.

Write a function solution(m) that takes an array of array of nonnegative ints representing how many times that state has gone to the next state and return an array of ints for each terminal state giving the exact probabilities of each terminal state, represented as the numerator for each state, then the denominator for all of them at the end and in simplest form. The matrix is at most 10 by 10. It is guaranteed that no matter which state the ore is in, there is a path from that state to a terminal state. That is, the processing will always eventually end in a stable state. The ore starts in state 0. The denominator will fit within a signed 32-bit integer during the calculation, as long as the fraction is simplified regularly.


from fractions import Fraction                              
import numpy as np                                             

def solution(m):
    if len(m) < 2:
        return [1,1]
    r_subm, q_subm = split_martix(m)
    f_subm = calc_f(q_subm)
    fr_subm = np.dot(f_subm, r_subm)
    return dec_to_frac_with_lcm(fr_subm[0])

def split_martix(m):
    absorbing = set()
    for row_i in range(len(m)):
        if sum(n[row_i]) == 0:
    r_subm = []
    q_subm = []
    for row_i in range(len(m)):
        if row_i not in absorbing:
            row_total = float(sum(m[row_i]))
            r_temp = []
            q_temp = []
            for col_i in range(len(m[row_i])):
                if col_i in absorbing:
    return r_subm, q_subm

def calc_f(q_subm):
    return np.linalg.inv(np.subtract(np.identity(len(q_subm)), q_subm))

def dec_to_frac_with_lcm(l):
    ret_arr = []
    denoms = []
    for num in l:
        frac = Fraction(num).limit_denominator()
    lcd = 1
    for denom in denoms:
        lcd = lcm(lcd,denom)
    for num_i in range(len(ret_arr)):
        ret_arr[num_i] *= int(lcd/denoms[num_i])
    return ret_arr                                                                          


 ‘Hey! I already did that.’
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:

Start with a random minion ID n, which is a nonnegative integer of length k in base b
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
Define z = x - y. Add leading zeros to z to maintain length k if necessary
Assign n = z to get the next minion ID, and go back to step 2
For 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.
def dTob(d, b):
    digits = []
    while d > 0:
        digits.insert(0, str(d % b))
        d  = d / b
    return ''.join(digits)
def bTod(b, c):
  n = 0
  for d in str(b):
    n = c * n + int(d)
  return n
def negative(x, y, b):
  if b==10:
    return int(x) - int(y)
  return dTob(dz, b)
def solution(n, b):
    while True:
        i = "".join(sorted(str(n), reverse=True))
        j = "".join(sorted(str(n)))
        k = negative(i,j,b)
        k2 = len(str(k))
        i2 = len(str(i))
        if (k2) != i2:
            k = k * pow(10 ,(i2-k2))
        for index, item in enumerate(arr):
          if item == k:
            return index + 1
        arr = [k] + arr
        n = k

Find the Access Codes
Write a function answer(l) that takes a list of positive integers l and counts the number of “lucky triples” of (lst[i], lst[j], lst[k]) where i < j < k. The length of l is between 2 and 2000 inclusive. The elements of l are between 1 and 999999 inclusive. The answer fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0.

For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the answer 3 total.
def solution(l):
    trips = 0
    doubs = [0]*len(l)

    for i in range(1, len(l)):
        for j in range(i):
            if l[i] % l[j] == 0:
                doubs[i] += 1
                trips += doubs[j]
    return trips

And with that, I  finished with Level 3. At this point, a dialogue appears to send your information to a Google recruiter. 

Level 4: Free the Bunny Workers
You need to free the bunny workers before Commander Lambda's space station explodes! Unfortunately, the Commander was very careful with the highest-value workers -- they all work in separate, maximum-security work rooms. The rooms are opened by putting keys into each console, then pressing the open button on each console simultaneously. When the open button is pressed, each key opens its corresponding lock on the work room. So, the union of the keys in all of the consoles must be all of the keys. The scheme may require multiple copies of one key given to different minions.
The consoles are far enough apart that a separate minion is needed for each one. Fortunately, you have already relieved some bunnies to aid you - and even better, you were able to steal the keys while you were working as Commander Lambda's assistant. The problem is, you don't know which keys to use at which consoles. The consoles are programmed to know which keys each minion had, to prevent someone from just stealing all of the keys and using them blindly. There are signs by the consoles saying how many minions had some keys for the set of consoles. You suspect that Commander Lambda has a systematic way to decide which keys to give to each minion such that they could use the consoles.
You need to figure out the scheme that Commander Lambda used to distribute the keys. You know how many minions had keys, and how many consoles are by each work room. You know that Command Lambda wouldn't issue more keys than necessary (beyond what the key distribution scheme requires), and that you need as many bunnies with keys as there are consoles to open the work room.
Given the number of bunnies available and the number of locks required to open a work room, write a function solution(num_buns, num_required) which returns a specification of how to distribute the keys such that any num_required bunnies can open the locks, but no group of (num_required - 1) bunnies can.
Each lock is numbered starting from 0. The keys are numbered the same as the lock they open (so for a duplicate key, the number will repeat, since it opens the same lock). For a given bunny, the keys they get is represented as a sorted list of the numbers for the keys. To cover all of the bunnies, the final solution is represented by a sorted list of each individual bunny's list of keys. Find the lexicographically least such key distribution - that is, the first bunny should have keys sequentially starting from 0.
num_buns will always be between 1 and 9, and num_required will always be between 0 and 9 (both inclusive). For example, if you had 3 bunnies and required only 1 of them to open the cell, you would give each bunny the same key such that any of the 3 of them would be able to open it, like so:
[ [0], [0], [0] ]
If you had 2 bunnies and required both of them to open the cell, they would receive different keys (otherwise they wouldn't both actually be required), and your solution would be as follows:
[ [0], [1] ]
Finally, if you had 3 bunnies and required 2 of them to open the cell, then any 2 of the 3 bunnies should have all of the keys necessary to open the cell, but no single bunny would be able to do it. Thus, the solution would be:
[ [0, 1], [0, 2], [1, 2] ]

The challenge also list a couple of test cases you will need to pass. However, it also indicates that there will be additional hidden tests that you need to pass. But you may not know what those test are about. Nice, uh?

Test cases
from itertools import combinations

def solution(num_buns, num_required):
    c = list(combinations(range(num_buns), num_buns - (num_required - 1)))
    return [[key for key, bunnies in enumerate(c) if bunny in bunnies] for bunny in xrange(num_buns)]


Escape Pods
You've blown up the LAMBCHOP doomsday device and broken the bunnies out of Lambda's prison,
  and now you need to escape from the space station as quickly and as orderly as possible!
  The bunnies have all gathered in various locations throughout the station,
  and need to make their way towards the seemingly endless amount of escape pods positioned
  in other parts of the station.
  You need to get the numerous bunnies through the various rooms to the escape pods.
  Unfortunately, the corridors between the rooms can only fit so many bunnies at a time.
  What's more, many of the corridors were resized to accommodate the LAMBCHOP,
  so they vary in how many bunnies can move through them at a time.
  Given the starting room numbers of the groups of bunnies,
  the room numbers of the escape pods,
  and how many bunnies can fit through at a time in each direction of every corridor in between,
  figure out how many bunnies can safely make it to the escape pods at a time at peak.
  Write a function solution(entrances, exits, path) that takes
  an array of integers denoting where the groups of gathered bunnies are,
  an array of integers denoting where the escape pods are located,
  and an array of an array of integers of the corridors,
  returning the total number of bunnies that can get through at each time step as an int.
  The entrances and exits are disjoint and thus will never overlap.
  The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step.
  There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.
  For example, if you have:
  entrances = [0, 1]
  exits = [4, 5]
  path = [
  [0, 0, 4, 6, 0, 0],  # Room 0: Bunnies
  [0, 0, 5, 2, 0, 0],  # Room 1: Bunnies
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate room
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate room
  [0, 0, 0, 0, 0, 0],  # Room 4: Escape pods
  [0, 0, 0, 0, 0, 0],  # Room 5: Escape pods
  Then in each time step, the following might happen:
  0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
  1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
  2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
  3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5
  So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step.
  (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5,
  such as 2/6 and 6/6, but the final solution remains the same.)

from collections import deque 

def solution(map):
    m, n = len(map), len(map[0])
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    def bfs(i, j):
        matrix = [[None] * n for _ in range(m)]
        matrix[i][j] = 1
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                new_x, new_y = x + dx, y + dy
                if 0 <= new_x < m and 0 <= new_y < n:
                    if matrix[new_x][new_y] is None:
                        matrix[new_x][new_y] = matrix[x][y] + 1
                        if map[new_x][new_y] == 1: continue
                        queue.append((new_x, new_y))
        return matrix
    start = bfs(0, 0)
    end = bfs(m - 1, n - 1)
    res = float('inf')
    for i in range(m):
        for j in range(n):
            if start[i][j] and end[i][j]:
                res = min(res, start[i][j] + end[i][j] - 1)
    return res

Level 5: Disorderly Escape

Oh no! You've managed to free the bunny prisoners and escape Commander Lambdas exploding space station,
but her team of elite starfighters has flanked your ship. If you dont jump to hyperspace, and fast,
youll be shot out of the sky!

Problem is, to avoid detection by galactic law enforcement, Commander Lambda planted her space station in the middle of a quasar quantum flux field. In order to make the jump to hyperspace, you need to know the configuration of celestial bodies in the quadrant you plan to jump through. In order to do that, you need to figure out how many configurations each quadrant could possibly have, so that you can pick the optimal quadrant through which youll make your jump.

There's something important to note about quasar quantum flux fields' configurations: when drawn on a star grid, configurations are considered equivalent by grouping rather than by order. That is, for a given set of configurations, if you exchange the position of any two columns or any two rows some number of times, youll find that all of those configurations are equivalent in that way - in grouping, rather than order.

Write a function solution(w, h, s) that takes 3 integers and returns the number of unique, non-equivalent configurations that can be found on a star grid w blocks wide and h blocks tall where each celestial body has s possible states. Equivalency is defined as above: any two star grids with each celestial body in the same state where the actual order of the rows and columns do not matter (and can thus be freely swapped around). Star grid standardization means that the width and height of the grid will always be between 1 and 12, inclusive. And while there are a variety of celestial bodies in each grid, the number of states of those bodies is between 2 and 20, inclusive. The solution can be over 20 digits long, so return it as a decimal string. The intermediate values can also be large, so you will likely need to use at least 64-bit integers.

For example, consider w=2, h=2, s=2.
We have a 2x2 grid where each celestial body is either in state 0
(for instance, silent) or state 1 (for instance, noisy). We can examine which grids are equivalent by swapping rows and columns.

In the above configuration, all celestial bodies are "silent" - that is, they have a state of 0 - so any swap of row or column would keep it in the same state.

  00 00 01 10
  01 10 00 00

1 celestial body is emitting noise - that is, has a state of 1 - so swapping rows and columns can put it in any of the 4 positions. All four of the above configurations are equivalent.

  00 11
  11 00

2 celestial bodies are emitting noise side-by-side. Swapping columns leaves them unchanged, and swapping rows simply moves them between the top and bottom. In both, the groupings are the same: one row with two bodies in state 0, one row with two bodies in state 1, and two columns with one of each state.

  01 10
  01 10

2 noisy celestial bodies adjacent vertically. This is symmetric to the side-by-side case, but it is different because there's no way to transpose the grid.

  01 10
  10 01

2 noisy celestial bodies diagonally. Both have 2 rows and 2 columns that have one of each state, so they are equivalent to each other.

  01 10 11 11
  11 11 01 10

3 noisy celestial bodies, similar to the case where only one of four is noisy.


4 noisy celestial bodies.

There are 7 distinct, non-equivalent grids in total, so solution(2, 2, 2) would return 7.

from math import factorial
from collections import Counter
from fractions import gcd

def solution(w, h, s):
    for cpw in cycle_partitions(w):
        for cph in cycle_partitions(h):            
            m=cycle_count(cpw, w)*cycle_count(cph, h)
            grid+=m*(s**sum([sum([gcd(i, j) for i in cpw]) for j in cph]))
    return str(grid//(factorial(w)*factorial(h)))

def cycle_count(c, n):                                                               
    for a, b in Counter(c).items():                                      
    return cc                                                                             

def cycle_partitions(n, i=1):                                                     
    yield [n]                                                                                 
    for i in range(i, n//2 + 1):                                                        
        for p in cycle_partitions(n-i, i):                                      
            yield [i] + p