Google Foobar Challenge level 4 – Free the Bunny Workers

TL, DR

Google Foobar is a hidden coding challenge by Google, and Free the Bunny Workers is the challenge I solved using Python in order to progress in level 4.

This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.

Getting ready to run

The seventh task I got for Foobar was to divide access keys among fellow bunnies to unlock all rooms where kept prisoner. The full description of the challenge is the following:

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] ]

Tests

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
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Python cases --
Input:
solution.solution(2, 1)
Output:
[[0], [0]]

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

Input:
solution.solution(5, 3)
Output:
[[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]]


Constraints

You also need to keep in mid a few constraints. They are divided between Java and Python ones.

Python
======
Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.
Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.
Input/output operations are not allowed.
Your solution must be under 32000 characters in length including new lines and and other non-printing characters.

There are two important caveats to consider:

• Even if in the Python section there is no mention, execution time is limited. They say so in the Java section, but somehow they do not repeat it in the Python one.
• There are additional blacklisted libraries. For instance, I got a “BLACKLISTED CODE” exception when I tried to import the sys library

Putting a solution together

Spoiler alert: you can find a complete working solution below. However I think that just copy-pasting a solution will not do you any good. But maybe looking at the flow and understanding the thinking behind the code may put you in the right direction to solve the challenge and learn something in the doing!

Coming to our challenge, the task is basically to create groups of bunnies out of our total num_buns in which each group is composed by num_required units.

Therefore, we need to calculate how many groups are needed and how many copies of each key we need to distribute in order to make sure any random group of num_required bunnies can unlock the room.

Getting to the point

Combinatorics calculus is not exactly something I do day-to-day. Therefore, I searched extensively on Google for hints and explanations. On this post by Dalao I found the clearer analysis, and a neat Python code implementation. I report the code below, adding some comments to better explain each passage.

from itertools import combinations

def solution(num_buns, num_required):
    # Initialize the list of keys
    keyrings = [[] for num in range(num_buns)]
    # Calculate how many copies are required
    # per each key
    copies_per_key = num_buns - num_required + 1
    # Append keys in the list initialized above
    for key, bunnies in enumerate(combinations(range(num_buns), copies_per_key)):
        for bunny in bunnies:
            keyrings[bunny].append(key)

    return keyrings

Before this, I tried some implementation by myself…but I was not able to generalize for all test cases. I’m happy that I had the chance to learn from somebody smarter than me!

Once you are ready, you can check your work by typing:

verify solution.py

If you completed your work correctly, a happy green message like this one will greet you:

You can then submit the solution as indicated. And that’s it for Google Foobar Challenge level 4 – Free the Bunny Workers!

I will write about each individual challenge in a dedicated post. You will find the post series via the link at the end of this post, stay tuned for updates!

Related links

• Google Foobar link (it is by invitation only)
• My series of posts on Google Foobar link
• Dalao post with analysis and code link

Do you like our content? Check more of our posts in our blog!