TL, DR
Google Foobar is a hidden coding challenge by Google, and Numbers Station Coded Messages is the challenge I solved using Python in order to progress in level 2.
This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.
Getting updates from your bunnies
The second task I got for Foobar was to decode hidden messages my bunny friends were secretly sending me. The full description of the challenge is the following:
Numbers Station Coded Messages
==============================When you went undercover in Commander Lambda's organization, you set up a coded messaging system with Bunny Headquarters to allow them to send you important mission updates. Now that you're here and promoted to Henchman, you need to make sure you can receive those messages -- but since you need to sneak them past Commander Lambda's spies, it won't be easy!Bunny HQ has secretly taken control of two of the galaxy's more obscure numbers stations, and will use them to broadcast lists of numbers. They've given you a numerical key, and their messages will be encrypted within the first sequence of numbers that adds up to that key within any given list of numbers.
Given a non-empty list of positive integers l and a target positive integer t, write a function solution(l, t) which verifies if there is at least one consecutive sequence of positive integers within the list l (i.e. a contiguous sub-list) that can be summed up to the given target positive integer t (the key) and returns the lexicographically smallest list containing the smallest start and end indexes where this sequence can be found, or returns the array [-1, -1] in the case that there is no such sequence (to throw off Lambda's spies, not all number broadcasts will contain a coded message).
For example, given the broadcast list l as [4, 3, 5, 7, 8] and the key t as 12, the function solution(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function solution(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15.
To help you identify the coded broadcasts, Bunny HQ has agreed to the following standards:
- Each list l will contain at least 1 element but never more than 100.
- Each element of l will be between 1 and 100.
- t will be a positive integer, not exceeding 250.
- The first element of the list l has index 0.
- For the list returned by solution(l, t), the start index must be equal or smaller than the end index.
Remember, to throw off Lambda's spies, Bunny HQ might include more than one contiguous sublist of a number broadcast that can be summed up to the key. You know that the message will always be hidden in the first sublist that sums up to the key, so solution(l, t) should only return that sublist.
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([1, 2, 3, 4], 15)
Output:
-1,-1
Input:
solution.solution([4, 3, 10, 2, 8], 12)
Output:
2,3
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
syslibrary
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, we basically need to sum consecutive elements in our list until one of the following conditions is reached:
- The sum is equal to our target value, in which case we stop and return the index for starting and ending position in the list.
- The sum is more than our target value, in which case we move on to the next item in the list and start summing again.
If we reach the end of the list without finding a sum which is equal to our target value, we then return the prescribed -1, -1.
The challenge is quite straightforward, all you need to do is to get the breaking conditions right. In fact, if you forget to break you may risk testing sums way more than needed, and incur in the execution timeout.
Getting to the point
A very simple function that does all the above is the following:
def solution(l, t):
# Setup each list element as
# potential starting point
for i in l:
# Initialize the sum at 0 every time
tot = 0
# Setup each following element to
# be added
for j in range(i, len(l)):
# Increase the total
tot += l[j]
# If total is equal to target
if tot == t:
# Return start and end index
return i, j
# If total is above target
if tot > t:
# Break the loop and move to
# next item
break
# If we did not find a sequence that
# adds up to the target, return -1,-1
return -1, -1The breaking conditions are clearly indicated in the code above. You shouldn’t add numbers more than needed.
Once you are ready, you can get tested for your work by typing:
verify solution.pyIf 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 that’s it for Google Foobar Challenge level 2 – Numbers Station Coded Messages!
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
Do you like our content? Check more of our posts in our blog!
