FB4 - Google Foobar - Free the Bunny Workers & Escape Pods

What is the level 4 Google Foobar challenge?

There are 2 challenges at this level. We have 15 days per challenge. I’m starting to get bored with a long-run challenge like this.

readme.txt:

challenge I - 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:

1
2
3
4
5


[
  [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:

1
2
3
4


[
  [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:

1
2
3
4
5


[
  [0, 1],
  [0, 2],
  [1, 2],
]

1
2
3
4
5
6
7
8


solution.solution(2, 1)
[[0], [0]]

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

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

first challenge of level 4 googlefoobar

challenge II - Escape Pods:

You’ve blown up the LAMBCHOP doomsday device and relieved the bunnies of their work duries – 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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.)

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


solution.solution(
  [0],
  [3],
  [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]
)
6

solution.solution(
  [0, 1],
  [4, 5],
  [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
)
16

How did I solve the level 4 Google Foobar challenge?

challenge I - Free the Bunny Workers:

Damn it, the content of this challenge is too long, it’s so tiring to read, I don’t remember what I read after reading it. I tried to understand the solution from the examples instead. Then I can summarize the challenge as follows :

Input:

num_buns: the number of bunnies
- Each bunny can hold many unique keys
  - Key is the number from 0 -> 9
  - Each bunny will hold the same number of keys
num_required: The number of bunnies will be picked to unlock the password

Output:

Find the suitable password for each input(num_buns, num_required)
- Password is the list of unique keys starting from 0->9 lexicographically:
  - Distribute the keys to bunnies to ensure:
    - condition 1: Pick any num_required bunnies from num_buns bunnies will be able to unlock the password(contains password)
    - condition 2: num_required is the minimum number. It means:
      - If we pick any num_required - 1 bunnies from num_buns bunnies. we never can unlock the password(contain the password)

Explain for example: Note: we always have num_required <= len(password).

Don’t believe? just check num_required > len(password) then you will see a missing slot issue

It means: if num_required = 4 then password will be [0, 1, 2, 3, ...]

Example 1:

num_buns = 3, num_required = 1:
- try with password is [0]
  - 1 2 3 4 5
    
    [ [0], [0], [0], ]
  - condition 1: ✅️
    - we can always randomly pick 1/3 bunnies to unlock password. the picked keys will always [0]
  - condition 2: ✅
    - 1 key/bunny
    - num_required == len(password)

Example 2:

num_buns = 2, num_required = 2:
- try with password is [0, 1]
  - 1 2 3 4
    
    [ [0], [1], ]
    - condition 1: ✅️
      - we can always randomly pick 2/2 bunnies to unlock password. the picked keys will always [0, 1]
    - condition 2: ✅
      - 1 key/bunny
      - num_required == len(password)

Example 3:

num_buns = 3, num_required = 2:
- try with password is [0, 1]
  - 1 2 3 4 5
    
    [ [0], [1], [1], ]
    - condition 1: ❌
      - we can not always randomly pick 2/3 bunnies to unlock password.
        
        example: the picked keys [1, 1]
- try with password is [0, 1, 2]
  - 1 2 3 4 5
    
    [ [0], [1], [2], ]
    - condition 1: ❌
      - we can not always randomly pick 2/3 bunnies to unlock password.
        
        example: the picked keys [0, 1]
- try with password is [0, 1, 2] (but increased the number of keys per bunny hold)
  - 1 2 3 4 5
    
    [ [0, 1], [0, 2], [1, 2], ]
    - condition 1: ✅️
      - we can always randomly pick 2/3 bunnies to unlock password. the picked keys will always [0, 1, 2]
    - condition 2: ✅
      - num_required <= len(password):
        
        we need to test with num_required - 1:
        
        condition 1:
        
        we can not always randomly pick 1/3 bunnies to unlock password.
        
        So, with num_required - 1 will not work

Example 4:

num_buns = 2, num_required = 1:
- try with password is [0]
  - 1 2 3 4
    
    [ [0], [0], ]
    - condition 1: ✅️
      - we can always randomly pick 1/2 bunnies to unlock password. the picked keys will always [0]
    - condition 2: ✅
      - 1 key/bunny
      - num_required == len(password)

Example 5:

num_buns = 4, num_required = 4:
- try with password is [0, 1, 2, 3]
  - 1 2 3 4 5 6
    
    [ [0], [1], [2], [3], ]
    - condition 1: ✅️
      - we can always randomly pick 4/4 bunnies to unlock password. the picked keys will always [0, 1, 2, 3]
    - condition 2: ✅
      - 1 key/bunny
      - num_required == len(password)

Example 6:

num_buns = 5, num_required = 3:
- try with password is [0, 1, 2]
  - 1 2 3 4 5 6 7
    
    [ [0], [1], [2], [2], [2], ]
    - condition 1: ❌
      - we can not always randomly pick 2/3 bunnies to unlock password.
        
        example: 0, 2, 2
- try with password is [0, 1, 2]
  - 1 2 3 4 5 6 7
    
    [ [0, 1], [0, 2], [1, 2], [1, 2], [0, 1], ]
    - condition 1: ✅️
      - we can always randomly pick 3/5 bunnies to unlock password. the picked keys will always [0, 1, 2]
    - condition 2: ❌
      - num_required == len(password) but 2 keys/bunny
        
        we need to test with num_required - 1:
        
        condition 1:
        
        we can randomly pick 2/5 bunnies to unlock password.
        
        example: 2 first bunnies: the picked keys [0, 1, 2]
        
        So, with num_required - 1 will work
- try with password is [0, 1, 2, 3] … ❌
- try with password is [0, 1, 2, 3, 4] … ❌
- try with password is [0, 1, 2, 3, 4, 5] … ❌
- …
- try with password is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  - 1 2 3 4 5 6 7
    
    [ [0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9], ]
    - condition 1: ✅️
      - we can always randomly pick 3/5 bunnies to unlock password. the picked keys will always [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    - condition 2: ✅
      - num_required <= len(password):
        
        we need to test with num_required - 1:
        
        condition 1:
        
        we never can randomly pick 2/3 bunnies to unlock password.
        
        So, with num_required - 1 will not work
Are you dizzy yet? that’s just the way I understand the challenge after spending hours on it, you don’t need to understand it. I found a math nerd resolved this in a simple way

challenge II - Escape Pods:

I don’t tell anything in this challenge, guys. Solution was copied from this one cry on lever 4 googlefoobar

solution.py:

challenge I - Free the Bunny Workers:

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


from itertools import combinations


def solution(num_buns, num_required):
    keys_grouped_by_bunnies = [[] for _ in range(num_buns)]
    num_keys = num_buns - (num_required - 1)
    bunnies_ids = range(num_buns)
    bunnies_grouped_by_key = list(combinations(bunnies_ids, num_keys))
    key_and_group_bunny_by_key = enumerate(bunnies_grouped_by_key)
    for key, group_bunny_by_key in key_and_group_bunny_by_key:
        for bunny in group_bunny_by_key:
            keys_grouped_by_bunnies[bunny].append(key)
    return keys_grouped_by_bunnies

challenge II - Escape Pods:

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


def solution(entrances, exits, path):
    le = len(entrances)
    lp = len(path)
    lx = len(exits)
    bunn_count = 0
    inter_paths = path[le:(lp-lx)]                # To find all intermediate rooms
    for i in range(lp - le - lx):                 # Loop through range of length of intermediate rooms
        sum_range = sum(inter_paths[i])           # Sum of an intermediate room's possible number of bunnies allowed
        sum_enter = 0                             # Sum of bunnies that enter that room
        for j in entrances:
            sum_enter += path[j][le + i]          # Get all bunnies that enter a room
        bunn_count += min(sum_enter, sum_range)
    return bunn_count