Google Foobar Challenge level 3 – Find the Access Codes

TL, DR

Google Foobar is a hidden coding challenge by Google, and Find the Access Codes is the challenge I solved using Python in order to complete level 3.

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 sixth task I got for Foobar was to find the access codes for the terrible LAMBCHOP device. The full description of the challenge is the following:

Find the Access Codes
=====================
In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need access to it. But the only door leading to the LAMBCHOP chamber is secured with a unique lock system whose number of passcodes changes daily. Commander Lambda gets a report every day that includes the locks' access codes, but only the Commander knows how to figure out which of several lists contains the access codes. You need to find a way to determine which list contains the access codes once you're ready to go in.
Fortunately, now that you're Commander Lambda's personal assistant, Lambda has confided to you that all the access codes are "lucky triples" in order to make it easier to find them in the lists. A "lucky triple" is a tuple (x, y, z) where x divides y and y divides z, such as (1, 2, 4). With that information, you can figure out which list contains the number of access codes that matches the number of locks on the door when you're ready to go in (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky triple" access codes).
Write a function solution(l) that takes a list of positive integers l and counts the number of "lucky triples" of (li, lj, lk) where the list indices meet the requirement i < j < k. The length of l is between 2 and 2000 inclusive. The elements of l are between 1 and 999999 inclusive. The solution fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0.
For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the solution 3 total.

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, 5, 6])
Output:
3

Input:
solution.solution([1, 1, 1])
Output:
1


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 find and count all triples (x, y, z) where x divides y and y divides z. In our list, x needs to come before y, and y needs to come before z.

It seems quite simple and straightforward, right? We just need to test with the modulo operator % the elements of the possible triples, if we get 0, we add one magic triple to the count.

A simple inefficient solution

Armed with my ingenuity, I thought that iterating throughout the various triples was a good enough solution to pass the challenge, and I tested the function below.

import itertools

def solution(l):
    # Create all possible triples
    all_triples = itertools.combinations(l, 3)
    # Only keep ordered triples
    ordered_triples = [x for x in all_triples if ((x[2]>=x[1]) and (x[1]>=x[0]))]
    # Only keep the ones where the third item is a multiple of the second
    lucky_triples_sel = [x for x in ordered_triples if (x[2]%x[1] == 0)]
    # Only keep the ones where the second item is a multiple of the first
    lucky_triples = [x for x in lucky_triples_sel if (x[1]%x[0] == 0)]
    return len(lucky_triples)

However, this function only passed the first two test cases. All hidden ones were failing. Since I had no clue, I started searching and I found out divisions (and by association the modulo operator) are quite computationally expensive. Maybe also the memory requirements to generate all possible triples were taking a toll on the function’s performances.

Looking out for solutions

Therefore I started searching out on Google what could I have missed, and what could I improve. I found out a very interesting approach in this StackOverflow question, answer by Patrice Gahide.

In order to reduce the computational complexity from O(n³) to O(n²), Patrice suggestion is to calculate the modulo only for couples, and to keep in a separate counter the number of times we found a perfect divisor. This way we only need to iterate in our list twice (rather than three times).

By the way, if you are not familiar with Big O notation for computational complexity you should have a look to this FreeCodeCamp post. That’s the one that clarified it for me.

Getting to the point

A little bit more research led me to this other StackOverflow question. Even if the question was marked for Java, saifeemustafaq solution is a perfect translation in Python of Patrice Gahide pseudo-code in the other thread.

def solution(l):
    c = [0] * len(l)
    count = 0
    for i in range(0,len(l)):
        for j in range(0, i):
            if l[i] % l[j] == 0:
                c[i] = c[i] + 1
                count = count + c[j]
    return count

What to say…it’s elegant, efficient, and – above all – it passes all the test cases! However, it still looks like a mystery object in my eyes. In order to clarify its functioning, I ran it a few times with some added print statement to figure out what was happening.

def solution(l):
    c = [0] * len(l)
    count = 0
    for i in range(0,len(l)):
        for j in range(0, i):
            if l[i] % l[j] == 0:
                print l[i], l[j]  # Add () for Python3
                c[i] = c[i] + 1
                count = count + c[j]
                print count  # Add () for Python3
    return count, c

Looking at the evolution of the counter on a few test cases made it a bit more clear. But most probably I wouldn’t be able to develop that sort of algorithm myself. Good that I can 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 3 – Find the Access Codes!

Now things start to grow more interesting. When you complete level 3 you have the chance to leave your contact details, and link to Github or LinkedIn. In case some Google recruiter will find your profile a fit with their needs, you may get a call for a real interview.

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
• StackOverflow question with pseudo-code on efficient algorithm to find triples of perfect divisors link
• StackOverflow question with Python code implementation of above algorithm link
• FreeCodeCamp post on Big O notation for computational complexity link

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