What is the level 3 Google Foobar challenge?

Not even to mention finding a solution yet. It’s already difficult to understand the problem. There are 3 challenges at this level. The time is still the same. And I’m starting to get paranoid!

readme.txt:

challenge I - Doomsday Fuel:

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 give n 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.

For example, consider the matrix m:

1
2
3
4
5
6
7
8

[
  [0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal probability
  [4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
  [0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
  [0,0,0,0,0,0],  # s3 is terminal
  [0,0,0,0,0,0],  # s4 is terminal
  [0,0,0,0,0,0],  # s5 is terminal
]

So, we can consider different paths to terminal states, such as:

1
2
3

s0 -> s1 -> s3
s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4
s0 -> s1 -> s0 -> s5

Tracing the probabilities of each, we find that

1
2
3
4

s2 has probability 0
s3 has probability 3/14
s4 has probability 1/7
s5 has probability 9/14

So, putting that together, and making a common denominator, gives an answer in the form of [s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator] which is [0, 3, 2, 9, 14].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

solution.solution(
    [
        [0, 2, 1, 0, 0],
        [0, 0, 0, 3, 4],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0]
    ]
)
[7, 6, 8, 21]

solution.solution(
    [
        [0, 1, 0, 0, 0, 1],
        [4, 0, 0, 3, 2, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0]
    ]
)
[0, 3, 2, 9, 14]

challenge II - The Grandest Staircase Of Them All:

With the LAMBCHOP doomsday device finished, Commander Lambda is preparing to debut on the galactic stage – but in order to make a grand entrance, Lambda needs a grand staircase! As the Commander’s personal assistant, you’ve been tasked with figuring out how to build the best staircase EVER.

Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so they can pick the one with the most options.

Each type of staircase should consist of 2 or more steps. No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step’s height is classified as the total amount of bricks that make up that step.

For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

When N = 4, you still only have 1 staircase choice:

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

Write a function called solution(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda’s not made of money!

1
2
3
4
5

solution.solution(200)
487067745

solution.solution(3)
1

challenge III - Fuel Injection Perfection:

Commander Lambda has asked for your help to refine the automatic quantum antimatter fuel injection system for the 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:

• Add one fuel pellet
• Remove one fuel pellet
• 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

1
2
3
4
5

solution.solution('15')
5

solution.solution('4')
2

How did I solve the level 3 Google Foobar challenge?

challenge I - Doomsday Fuel:

Do you understand the challenge? I’m not 😑

• How would it be in this infinity loop case:

  • s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> .... -> s0 -> s1 ....

  • or we don’t need to list them all? Not being able to list all the possible cases is the purpose of the challenge? I don’t know. 😗

• I know this challenge is related to Markov Chains:

  • Thailand Islands is a Markov Chains math example.
    • 
    • But it’s not similar to our challenge:
      • Thai Islands example has a limit: 3-day trip
      • Our challenge isn’t
      • Maybe I should dig into Markov chains examples

Shit, this challenge is too much math, I’m not a math junkie. I ended this pain by copying from this source instead 🏳️

challenge II - The Grandest Staircase Of Them All:

After going through the pain of the previous challenge, I was like a girl who lost her virginity. Looking for the answer no longer makes me torment myself. So I did it again secretly with Mr. Google Search. Then the submitted code was the result of a sneaky love affair. I renamed the variables to make it appear that the code is my own with Google Foobar. But actually, poor Google Foobar has been cuckolded by me, this result is the biological son of his brother. 😈

challenge III - Fuel Injection Perfection:

Seems to realize that the relationship is about to fall apart. Google Foobar seems gentler to me than he used to be. So I decided to play with him again.

I thought the recursive position would make both of us happy, I tried this pose with Google Foobar, but sadly we don’t get along. Google Foobar wants skill, I only have strength. The fun thus quickly ended with a RecursionError: maximum recursion depth exceeded error. Sad that my needs weren’t met, I returned to Mr. Google Search. He knew his brother very well, then he taught me this trick to make Google Foobar happy.

1
2
3
4
5
6

        if n % 2 == 0:             # bitmask: *0
            n = n // 2
        elif n == 3 or n % 4 == 1: # bitmask: 01
            n = n - 1
        else:                      # bitmask: 11
            n = n + 1

solution.py:

challenge I - Doomsday Fuel:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import numpy as np


# Returns indexes of active & terminal states
def detect_states(matrix):
    active, terminal = [], []
    for rowN, row in enumerate(matrix):
        (active if sum(row) else terminal).append(rowN)
    result = (active,terminal)
    return result


# Convert elements of array in simplest form
def simplest_form(B):
    B = B.round().astype(int).A1                   # np.matrix --> np.array
    gcd = np.gcd.reduce(B)
    B = np.append(B, B.sum())                      # append the common denom
    result = (B / gcd).astype(int)
    return result


# Finds solution by calculating Absorbing probabilities
def solution(m):
    active, terminal = detect_states(m)
    if 0 in terminal:                              # special case when s0 is terminal
        return [1] + [0]*len(terminal[1:]) + [1]
    m = np.matrix(m, dtype=float)[active, :]       # list --> np.matrix (active states only)
    comm_denom = np.prod(m.sum(1))                 # product of sum of all active rows (used later)
    P = m / m.sum(1)                               # divide by sum of row to convert to probability matrix
    Q, R = P[:, active], P[:, terminal]            # separate Q & R
    I = np.identity(len(Q))
    N = (I - Q) ** (-1)                            # calc fundamental matrix
    B = N[0] * R * comm_denom / np.linalg.det(N)   # get absorbing probs & get them close to some integer
    result = simplest_form(B)
    return result

challenge II - The Grandest Staircase Of Them All:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def solution(n):
    room_ids = floor_ids = range(0, n + 1)
    building = [[0 for room_id in room_ids] for floor_id in floor_ids]
    building[0][0] = 1
    for floor_id in floor_ids:
        if floor_id == 0:
            continue
        for room_id in room_ids:
            below_floor_id = floor_id - 1
            below_floor_room = building[below_floor_id][room_id]
            offset_diagonal_room = room_id - floor_id
            if offset_diagonal_room >= 0:
                building[floor_id][room_id] = below_floor_room + building[below_floor_id][offset_diagonal_room]
            else:
                building[floor_id][room_id] = below_floor_room
    return building[n][n] -1

challenge III - Fuel Injection Perfection:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def solution(n):
    num = int(n)
    count = 0
    while num > 1:
        if num % 2 == 0:
            num = num // 2
        elif num == 3 or num % 4 == 1:
            num = num - 1
        else:
            num = num + 1
        count += 1
    return count