Solving Google Foobar and hacking it along the way

Introduction

Recently I learned about the existence of what is known as Google Foobar, also known as "Google's secret recruiting program" or "How many bunnies can you rescue before wanting to kill someone." Being the stubborn person that I am, I decided to force my way in and try the challenges.

I didn't expect to be able to get in, but it seems I did, so I guess I'm indebted to do a writeup or something.

Foobar is basically a website containing a unix-like shell based on "jQuery Terminal," which has some standard unix commands -- including some that aren't listed in the help command, namely mount or cat. When you access Foobar they prompt you to use request whenever you're ready, which sends a POST to https://foobar.withgoogle.com/api/v1/commands/request/ and adds a folder into your home directory. That folder always contains 4 files: solution.py, solution.java, constraints.txt, and readme.txt.

Foobar is organized by levels. My session had 1 challenge for level 1, 2 for level 2, 3 for level 3, 2 for level 4, and 1 for level 5 -- all presented below in chronological order.

Solar Doomsday

Level 1 · Easy

This problem is pretty easy (and hopefully so, knowing it is the first one): they ask you to decompose a number into squares, using only the largest squares that fit. Solving it is straightforward -- get the biggest square that doesn't overflow your number, subtract it, and repeat. Nothing really hard there.

View Solution

def get_biggest_square(max_number):
    n = 1
    while(n * n < max_number + 1):
        n = n + 1
    return n - 1

def answer(area):
    if(area > 1000000 or area < 1):
        raise ValueError('Area is outside of bounds')
    array = []
    while(area != 0):
        res = get_biggest_square(area)
        array.append(res * res)
        area -= res * res
    return array

Ion Flux Relabelling

Level 2 · Easy

This one involves binary trees. Given a perfect binary tree labeled in post-order:

   7
 3   6
1 2 4 5

Write a function answer(h, q) where h is the height of the tree and q is a list of node labels. Return the parent of each node, or -1 if there is no parent. For example, answer(3, [1, 4, 7]) returns [3, 6, -1].

The approach: get the root element, then do a recursive check. If the item is less than or equal to the top of the left subtree, search left; otherwise search right. Continue until you find the target as a direct child.

View Solution

def find_item(item, cur, dif):
    right_node = cur - 1
    left_node = right_node - dif // 2

    if(right_node == item or left_node == item):
        return cur
    else:
        if(item <= left_node):
            return find_item(item, left_node, dif // 2)
        else:
            return find_item(item, right_node, dif // 2)

def answer(h, q):
    if(h > 30 or h < 1):
        raise ValueError('Height is outside of bounds')
    if(len(q) > 10000 or len(q) < 1):
        raise ValueError('Flux converters list is outside of bounds')

    items = (2 ** h) - 1
    array = []
    for i in range(len(q)):
        if (q[i] < items and q[i] > 0):
            array.append(find_item(q[i], items, items - 1))
        else:
            array.append(-1)
    return array

En Route Salute

Level 2 · Easy

Given a string containing <, >, or -, figure out the number of arrows that cross, knowing they all move one step at a time. Save the position of each arrow and figure out their distance: if a right-facing arrow is to the left of a left-facing arrow, they'll obviously cross.

View Solution

def answer(s):
    if(len(s) > 100 or len(s) < 1):
        raise ValueError('Height is outside of bounds')

    s = list(s.replace("-", ""))
    left = []
    right = []
    res = 0

    for i in range(0, len(s)):
        if s[i] == '<':
            left.append(i)
        if s[i] == '>':
            right.append(i)

    for i in right:
        for y in left:
            if i < y:
                res += 1
    for i in left:
        for y in right:
            if y < i:
                res += 1

    return res

Fuel Injection Perfection

Level 3 · Medium

This is where Foobar becomes tricky and focuses on math. Given a number and three operations (add 1, subtract 1, or divide by 2 if even), find the fewest steps to reduce it to 1.

If you can divide by 2, you always should. The tricky part is deciding whether to add or subtract when the number is odd. The answer lies in binary: maximize trailing zeros. When you see ...111 in binary, adding 1 pushes to ...000, making future divisions faster.

View Solution

def answer(n):
    n = int(n)
    res = 0

    while(n != 1):
        if(n % 2 == 0):
            n = n / 2
        elif((n == 3) or ((n + 1) & n) > ((n - 1) & (n - 2))):
            n -= 1
        else:
            n += 1
        res += 1
    return res

Queue To Do

Level 3 · Medium

This problem is about XOR reduction. Given a grid of sequential numbers:

0 1 2 /
3 4 / 5
6 / 7 8

XOR all numbers to the left of the slash (0^1^2^3^4^6). The naive loop is too slow for huge grids, so you exploit the fact that XOR of consecutive numbers repeats in a 4-element cycle, reducing each row's XOR to O(1).

View Solution

def xor(a, b):
    if(a % 2 == 0):
        xor_rotation = [b, 1, b + 1, 0]
    else:
        xor_rotation = [a, a ^ b, a - 1, (a - 1) ^ b]
    return xor_rotation[(b - a) % 4]

def answer(start, length):
    res = 0
    for i in range(0, length):
        res ^= xor(start + (length * i), start + (length * i) + (length - i) - 1)
    return res

Find the Access Code

Level 3 · Medium

The goal is to find "lucky triples" in a list -- ordered triplets (a, b, c) where a divides b and b divides c. Check if pairs of numbers divide each other, then extend those pairs into triples. For each element, count how many earlier elements divide it (pairs), then for each later element that it divides, add the pair count to the triple count.

View Solution

def answer(l):
    triples = 0
    pairs = [0] * len(l)

    for i in range(1, len(l) - 1):
        for j in range(i):
            if(l[i] % l[j] == 0):
                pairs[i] += 1
    for i in range(2, len(l)):
        for j in range(1, i):
            if(l[i] % l[j] == 0):
                triples += pairs[j]
    return triples

Distract the Guards

Level 4 · Hard

Level 4 is where challenges get interesting. Guards pair up in banana-based thumb wrestling: the one with fewer bananas always bets that amount and always wins. When both have equal bananas, they stop. We need to maximize the number of pairs stuck in infinite loops.

The math: if (a+b), divided by gcd(a,b), is a power of two, the game terminates. Otherwise it loops forever. The second part is a greedy matching: pair guards with the fewest loop-partners first, matching them to the next-fewest partner.

View Solution

from fractions import gcd

def loops(x, y):
    res = (x + y) / gcd(x, y)
    return bool(res & (res - 1))

def remove(guards, ref):
    for i in range(len(guards)):
        j = 0
        while j < len(guards[i]):
            if(guards[i][j] == ref):
                guards[i].pop(j)
            j += 1
    guards[ref] = [-1]

def answer(banana_list):
    guards = [[] for i in range(len(banana_list))]
    bad = 0

    for i in range(len(guards)):
        for j in range(len(guards)):
            if(loops(banana_list[i], banana_list[j])):
                guards[i].append(j)

    to_process = len(banana_list)
    while(to_process > 0):
        min_num = 0
        for i in range(len(guards)):
            if(i != 0 and (len(guards[i]) < len(guards[min_num]) or guards[min_num]
                == [-1]) and guards[i] != [-1]):
                min_num = i

        if((len(guards[min_num])) == 0 or (len(guards[min_num]) == 1 and
                guards[min_num][0] == guards[min_num]) and guards[min_num] !=
                [-1]):
            remove(guards, min_num)
            to_process -= 1
            bad += 1
        else:
            min_node = guards[min_num][0]
            for i in range(len(guards[min_num])):
                if(i != 0 and guards[min_num][i] != min_num and len(guards[guards[min_num][i]]) < len(guards[min_node])):
                    min_node = guards[min_num][i]
            if(guards[min_node] != [-1]):
                remove(guards, min_num)
                remove(guards, min_node)
                to_process -= 2

    return bad

Bringing a Gun to a Guard Fight

Level 4 · Hard

Easily the hardest challenge for me. You're in a room of given dimensions and can shoot a laser beam that reflects off walls. Figure out exactly which directions you can shoot so the beam reaches your enemy, given a max distance and your position.

The key insight: instead of calculating reflections, mirror the room. By tiling mirrored copies of the room, every reflected path becomes a straight line to a mirrored copy of the target. The room mirrors in a predictable pattern, so you build an atlas of mirrored positions up to the max distance, then check angles and ensure the guard's reflection is closer than your own.

              ----- -----
              |*~~| |~~*|
              |xxx| |xxx|
              ----- -----
By mirroring the room, reflections become straight lines
to mirrored copies of the target.

View Solution

def mirror_atlas(node, dimensions, distance):
    node_mirrored = []
    for i in range(len(node)):
        points = []
        for j in range(-(distance // dimensions[i]) - 1, (distance // dimensions[i] + 2)):
            points.append(get_mirror(j, node[i], dimensions[i]))
        node_mirrored.append(points)
    return node_mirrored

def get_mirror(mirror, coordinates, dimensions):
    res = coordinates
    mirror_rotation = [2 * coordinates, 2 * (dimensions - coordinates)]
    if(mirror < 0):
        for i in range(mirror, 0):
            res -= mirror_rotation[(i + 1) % 2]
    else:
        for i in range(mirror, 0, -1):
            res += mirror_rotation[i % 2]
    return res

def answer(dimensions, your_position, guard_position, distance):
    mirrored = [mirror_atlas(your_position, dimensions,
        distance), mirror_atlas(guard_position, dimensions, distance)]
    res = set()
    angles_dist = {}
    for i in range(0, len(mirrored)):
        for j in mirrored[i][0]:
            for k in mirrored[i][1]:
                beam = atan2((your_position[1] - k), (your_position[0] - j))
                l = sqrt((your_position[0] - j) ** 2 + (your_position[1] - k) ** 2)
                if [j, k] != your_position and distance >= l:
                    if((beam in angles_dist and angles_dist[beam] > l) or beam not in angles_dist):
                        if i == 0:
                            angles_dist[beam] = l
                        else:
                            angles_dist[beam] = l
                            res.add(beam)
    return len(res)

Expanding Nebula

Level 5 · Hard

The second hardest problem. Given a 2D grid of booleans, find the number of possible predecessor grids, knowing that a cell is true if and only if exactly one of its four predecessors (itself, right, bottom, bottom-right) was true.

The challenge is beating the time limit. Use memoization: index each cell's state by its coordinates and recent move history to avoid redundant recursion. Not complicated in concept, but much harder to figure out than it looks.

View Solution

def answer(state, a=0, b=0, past=0, solutions=0, history=0):
    if(past == 0):
        past = [[True] * (len(state[0]) + 1) for i in range(len(state) + 1)]
        solutions = {}
        history = []

    if(b == len(state[0]) + 1):
        return True

    res = 0
    index = ((a, b), tuple(history[-(len(state) + 2):]))
    if index in solutions:
        return solutions[index]

    for cell in [True, False]:
        if (not a or not b) or len(set([((past[a][b - 1] + past[a - 1][b]
            + past[a - 1][b - 1] + cell) == 1), state[a - 1][b - 1]])) == 1:
                history.append(cell)
                past[a][b] = cell
                res += answer(state, a=(a + 1) % (len(state) + 1),
                        b=b + (a + 1) // (len(state) + 1), past=past,
                        solutions=solutions, history=history)
                history.pop()

    solutions[index] = res
    return res

End & Hack Stuff

After finishing all challenges, there's a recruitme command and a nice cipher to end the game. The ending message was encrypted with a rolling XOR pad using my Foobar username as the key -- notoriously weak encryption that was easy to spot since the base64 string started with "HEYGA" (my username being "gauvain").

View Decryption Script

import base64
encrypted = "HEYGAwIKCxQSUlZbSUkAExAXFU5CR0YWGQ0FCwYGABNGSVRHRhAFFQwLCgQRUU1JSQIHExkTHR1AQU9WRgAABBMQEggLAgJGWVZGCA0PCBAABAQLCRVSVltJSRIPGRkCAgsDRllWRhsPBQMcAhJOTl1BUgUADwtATVVRBwYBQEFPVkYeBwlAUgs="
my_eyes = str.encode("gauvain")
decoded = base64.b64decode(encrypted)
decrypted = ""
for i in range(0, len(decoded)):
    decrypted += chr((my_eyes[i % len(my_eyes)] ^ decoded[i]))
print(decrypted)

$ python end.py
{'success' : 'great', 'colleague' : 'esteemed', 'efforts' : 'incredible',
 'achievement' : 'unlocked', 'rabbits' : 'safe', 'foo' : 'win!'}

Hacking the Test VM

When using asserts in my solutions, I noticed that misindented asserts running in global scope leaked error text -- revealing read access to the VM. After painfully editing dumping scripts around the 1MB memory limit and file-open restrictions, I managed a full dump.

$ file ~/foobar/hack/dump/export/pypy/bin/pypy
ELF 64-bit LSB shared object, x86-64, version 1 (SYSV),
dynamically linked, for GNU/Linux 2.6.26, stripped

The VM contained /tmp, /pypy, and /main.py which reads source code from file descriptor 3, locates the answer function, runs test cases, and writes results back to fd 3. The VM was locked down by nsjail -- no network, time-limited, read-only. While I achieved code execution, a full sandbox escape from nsjail remained elusive.

Conclusion

All 9 challenges done. Levels 1-2 were "just code and think later." Level 3 was "how good can you Google." Levels 4 and 5 required pen-and-paper math and genuinely creative thinking.

One neat observation: I finished all 9 challenges in under 200 lines of Python. Foobar was a fun challenge, albeit a bit overhyped -- ultimately a glorified month-spanning interview for Google. No new Cicada 3301 hiding under the lines.

The full code is available at code.govanify.com/govanify/foobar.