The last Foobar question of level 4 had been unlocked, and it turned out to be all about keys. This was the question:
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],
]
Languages
=========
To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java
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]]
-- Java cases --
Input:
Solution.solution(2, 1)
Output:
[[0], [0]]
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]]
Input:
Solution.solution(4, 4)
Output:
[[0], [1], [2], [3]]
Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
For me the main difficulty with this question was understanding what it was asking for. I just absolutely could not understand the goal. Several things felt contradictory like “The problem is, you don’t know which keys to use at which consoles” but simultaneously “Each lock is numbered starting from 0. The keys are numbered the same as the lock they open“. But if the consoles are numbered, and we know which numbers have been assigned to each keycode, don’t we then know exactly which codes open which locks? And “There are signs by the consoles saying how many minions had some keys for the set of consoles” but simultaneously “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“. If we know which minions knew which keys from these signs, then stealing the keys should have been enough? I was also overcomplicating “Find the lexicographically least such key distribution – that is, the first bunny should have keys sequentially starting from 0“. I wondered why is only the first bunny sequentially ordered, what is it that is determining the order of the remaining bunnies?
I ended up drawing out some fantastically overcomplicated diagrams in an effort to figure out what I was missing. That wasn’t working, so then I tried focusing on their sample answer for (5, 3). I thought if I could figure out a pattern from the answer it might make the question wording click for me. I could tell that there was indeed an interesting pattern to the numbering, but it was a pattern that I found hard to follow and extend from, so it didn’t get me closer to understanding the question.
I eventually searched Google to look for help, and came across a blog posting by ShuXiang Gao detailing his experience with this exact question. It provided the insights I needed. I had misunderstood a lot of the wording and had been vastly overcomplicating the question. Now that I understood it, I visualized the question’s (5, 3) example in terms that made more sense to me, and could finally work towards creating my own solution:
The idea was to start with the first bunny and then recursively add the next. The base case is reaching a depth that matches the number of keys per lock. When we’ve reached that depth we assign the first key before returning. After returning, replace the last bunny with the next, and continue on until reaching the last bunny. That would visit each bunny sequentially while ensuring each set is distinct. And that was all there was to it, that solution passed all the tests:
# Author: Derek Moran, Level 4, Bunny Planet Rescue Service
# With my thanks to Amazon Software Engineer ShuXiang Gao
# While this solution is my own, I gained valuable insights from Gao's blog detailing his own experience with this problem
# Date: 12-DEC-2022
def solution(num_buns, num_required):
# Your code here
return getKeyDistribution( num_buns, num_required )
# Given a total number of bunnies numTotalBunnies ( integer between 1 and 9 inclusive )
# And given total number of locks per room numberOfLocksPerRoom ( integer between 0 and 9 inclusive )
# Then returns a specification for the key distribution such that:
# - any set of bunnies of size ( numberOfLocksPerRoom ) can open the locks ( i.e. all the keys they require must be within their set )
# - any set of bunnies of size ( numberOfLocksPerRoom - 1 ) cannot open the locks ( i.e. their set must lack a key )
# The specification will take the form of a matrix where each row contains the keys held by the bunny whose index matches that row
# Keys will be ordered such that first bunny will have keys sequentially starting from 0
def getKeyDistribution( numTotalBunnies, numberOfLocksPerRoom ):
if not type(numTotalBunnies) is int or numTotalBunnies < 1 or numTotalBunnies > 9:
raise Exception( "numTotalBunnies must be an integer between 1 and 9 inclusive" )
if not type(numberOfLocksPerRoom) is int or numberOfLocksPerRoom < 0 or numberOfLocksPerRoom > 9:
raise Exception( "numberOfLocksPerRoom must be an integer between 0 and 9 inclusive" )
keyDistributionMatrix = [[] for _ in range(numTotalBunnies)]
# If we can already tell that no keys are necessary, then let's bail early to avoid the unnecessary processing
if numberOfLocksPerRoom == 0 or numberOfLocksPerRoom > numTotalBunnies: return keyDistributionMatrix
# Any set of bunnies of size ( numberOfLocksPerRoom - 1 ) should NOT be able to open the set of locks
# This implies that any set of bunnies of size ( numberOfLocksPerRoom - 1 ) is lacking one key
# Yet any set of bunnies of size ( numberOfLocksPerRoom ) SHOULD be able to open the set of locks
# This implies that adding any remaining bunny to our set of bunnies of size ( numberOfLocksPerRoom - 1 ) gives us that missing key
# Therefore each lock must have ( numTotalBunnies - ( numberOfLocksPerRoom - 1 ) ) == ( 1 + numTotalBunnies - numberOfLocksPerRoom ) keys
numberOfKeysPerLock = 1 + numTotalBunnies - numberOfLocksPerRoom
# We know that each lock has numberOfKeysPerLock keys
# So let's visit every possible distinct set of bunnies of size numberOfKeysPerLock
# We'll give the first set of bunnies the full set of keys for the first lock
# -> this implies that the set of remaining bunnies will lack the first key
# Then we'll give the second set of bunnies the full set of keys for the second lock
# -> this implies that the set of remaining bunnies will lack the second key
# Continue this for all the sets we have
# Now given any set of bunnies of size ( numberOfLocksPerRoom - 1 )
# -> the set will always lack one of the keys, and each of the remaining bunnies are the ones that have this key
# -> the other possible sets of bunnies of size ( numberOfLocksPerRoom ) will all have at least one of these bunnies in them,
# and since we've given one of the other keys to each of those sets, our bunnies must already have the remaining keys
# Note that we will visit in ascending order of bunnyId and keyId to ensure the ordering requirement
#
# Example: numTotalBunnies == 5, numberOfLocksPerRoom == 3
# Any 2 bunnies must lack a key, so any of the 3 remaining must always have that missing key -> there must be 3 keys per lock
# So visit every set of 3 bunnies we can make from the 5 and give them a full set of keys:
# [0,1,2] -> Give them all key0 ( [3,4] would then lack key0 )
# [0,1,3] -> Give them all key1 ( [2,4] would then lack key1 )
# [0,1,4] -> Give them all key2 ( [2,3] would then lack key2 )
# [0,2,3] -> Give them all key3 ( [1,4] would then lack key3 )
# [0,2,4] -> Give them all key4 ( [1,3] would then lack key4 )
# [0,3,4] -> Give them all key5 ( [1,2] would then lack key5 )
# [1,2,3] -> Give them all key6 ( [0,4] would then lack key6 )
# [1,2,4] -> Give them all key7 ( [0,3] would then lack key7 )
# [1,3,4] -> Give them all key8 ( [0,2] would then lack key8 )
# [2,3,4] -> Give them all key9 ( [0,1] would then lack key9 )
# Now pick any set of 2 bunnies and it must lack one of the keys; the remaining bunnies are the ones that do have this key
# Any other set of 3 bunnies must have at least one of these 2 bunnies in it, so our 2 must already have all of the other keys
bunniesInSet = []
# Python 2.7.13 does not support assignment to nonlocal int; using this list of size 1 as a workaround to get similar functionality
lockNumber = [0]
def distributeKeys( nextBunnyInSet ):
if len(bunniesInSet) == numberOfKeysPerLock:
for bunny in bunniesInSet:
keyDistributionMatrix[bunny].append( lockNumber[0] )
lockNumber[0] += 1
return
for bunny in range( nextBunnyInSet, numTotalBunnies ):
bunniesInSet.append(bunny)
distributeKeys( nextBunnyInSet = bunny + 1 )
bunniesInSet.pop()
distributeKeys( nextBunnyInSet = 0 )
return keyDistributionMatrix
This solution ended up being, at least for me, much easier to come up with than the prior question. Understanding what I was trying to solve in the first place, that was the most tricky part. There were still days left on the timer for this problem, so I may have eventually clued into what they were asking for. But I can’t be certain of that. So ShuXiang Gao has my gratitude, if it wasn’t for him this question may have brought my Foobar challenge to a premature end.
Leave a Reply