Google Foobar Challenge level 1 – Re-ID

TL, DR

Google Foobar is a hidden coding challenge by Google, and Re-ID is the challenge I solved using Python in order to complete level 1.

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

Give a better ID to minions

All right, so the first task I got for Foobar was to give some better ID to Commander Delta’s minions. The full description of the challenge is the following:

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 a Completely Foolproof Scheme.
Commander Lambda has 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 solution(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.

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(0)
Output:
23571

Input:
solution.solution(3)
Output:
71113

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

I will not give you a solution directly – you may look on Google for that, there are plenty. However I think that just copy-pasting a solution will not do you any good. But maybe a little bit of advice and a couple of code snippets may put you in the right direction to solve the challenge and learn something in the doing!

Coming to our challenge, the first step is to create the string with a lot prime numbers concatenated. The string needs to be at least 10.004 characters long, because we know from the text that n can be up to 10.000. In case one test calls our function with 10.000 as argument, we need to give back an answer with the 10.000th character and the following four to complete the 5 digit ID.

The point is to generate a lot of consecutive prime numbers in a memory efficient way. Divisions are computationally expensive, and if we just tests millions of numbers for their predecessors (or up until their square root) we may quickly pass the execution timeout.

Actually, you could also search for this extra-long sequence of number somewhere, and just paste it in your code. You will still be under the 32.000 characters limit. However, it wouldn’t be that fun or smart.

Ancient Greeks wisdom

Luckily, a guy named Eratosthenes of Cyrene solved this issue about two thousand years ago. The solution is called the sieve of Eratosthenes, and it still works quite well.

The sieve progressively crosses out multiples of numbers you encounter, eliminating the need to test them with divisions. You can find many implementations on Python, like this one.

Once you put together a function that implements the sieve, let’s call it sieve_of_eratosthenes(n) , and puts prime numbers in a list you are already in good shape to complete the Re-ID challenge for Google Foobar and clear level 1!

Getting to the point

Then you will have to convert those numbers into strings and join them together like this:

prime_list = sieve_of_eratosthenes(n)
long_string = "".join([str(x) for x in prime_list])

You may also convert the number into strings while you append them to the list, and get your function to return directly the long string. Another point to consider is how big n needs to be to generate our 10.004 characters string. By trial and error, I saw that a n of 22.000 generates more than enough primes to satisfy our requirements while staying within the limited execution time.

Finally, in your solution(n) function you need to implement list slicing on the n-th character of our long_string, returning that one and the following 4 to give the new ID to our minions.

Once you are ready, you can get tested for your work by typing:

verify solution.py

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

You can then submit the solution as indicated, and you will see a dancing bunny celebrating your success.

And that’s it for Google Foobar Challenge level 1 – Re-ID!

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

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