Google Foobar Challenge level 5 – Expanding Nebula

TL, DR

Google Foobar is a hidden coding challenge by Google, and Expanding Nebula is the challenge I solved using Python in order to complete level 5.

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 ninth and final task I got for Foobar was to calculate number of possible previous states that could led to a specific gas distribution in the nebula. The full description of the challenge is the following:

Expanding Nebula
================
You've escaped Commander Lambda's exploding space station along with numerous escape pods full of bunnies. But -- oh no! -- one of the escape pods has flown into a nearby nebula, causing you to lose track of it. You start monitoring the nebula, but unfortunately, just a moment too late to find where the pod went. However, you do find that the gas of the steadily expanding nebula follows a simple pattern, meaning that you should be able to determine the previous state of the gas and narrow down where you might find the pod.
From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.
For example, let's say the previous state of the grid (p) was:
.O..
..O.
...O
O...
To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:
.O -> O
..
Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:
O. -> .
.O
Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:
O.O
.O.
O.O
Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.
Write a function solution(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The solution will always be less than one billion (10^9).

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([[True, True, False, True, False, True, False, True, True, False], [True, True, False, False, False, False, True, True, True, False], [True, True, False, False, False, False, False, False, False, True], [False, True, False, False, False, False, True, True, False, False]])
Output:
11567

Input:
solution.solution([[True, False, True], [False, True, False], [True, False, True]])
Output:
4

Input:
solution.solution([[True, False, True, False, False, True, True, True], [True, False, True, False, False, False, True, False], [True, True, True, False, False, False, True, False], [True, False, True, False, False, False, True, False], [True, False, True, False, False, True, True, True]])
Output:
254

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 quickly went over my head. We were requested to calculate the number of possible states that would lead to a specific configuration given the evolutionary algorithm they presented. Therefore, we had to generate all possible scenarios for the t-1 stage.

I’m not afraid to say that this isn’t my usual bread and butter. I consider myself a novice to programing and definitely without a computer science or engineering background. Therefore, I resorted to search the internet to see the work of more qualified people.

Getting to the point

In this Github Gist by lotabout I found an interesting solution using the cellular automata function. The first thing I did was to ask Google what a “cellular automata” is, as the term didn’t ring any bell in my mind.

Luckily a long Wikipedia page and this section of The Nature of Code provided me with some context and additional information. I can’t say I understood them all, but at least I grasped the basic concepts. I report below the code used to solve the challenge:

from collections import defaultdict

def generate(c1,c2,bitlen):
    a = c1 & ~(1<<bitlen)
    b = c2 & ~(1<<bitlen)
    c = c1 >> 1
    d = c2 >> 1
    return (a&~b&~c&~d) | (~a&b&~c&~d) | (~a&~b&c&~d) | (~a&~b&~c&d)

def build_map(n, nums):
    mapping = defaultdict(set)
    nums = set(nums)
    for i in range(1<<(n+1)):
        for j in range(1<<(n+1)):
            generation = generate(i,j,n)
            if generation in nums:
                mapping[(generation, i)].add(j)
    return mapping

def solution(g):
    g = list(zip(*g)) # transpose
    nrows = len(g)
    ncols = len(g[0])

    # turn map into numbers
    nums = [sum([1<<i if col else 0 for i, col in enumerate(row)]) for row in g]
    mapping = build_map(ncols, nums)

    preimage = {i: 1 for i in range(1<<(ncols+1))}
    for row in nums:
        next_row = defaultdict(int)
        for c1 in preimage:
            for c2 in mapping[(row, c1)]:
                next_row[c2] += preimage[c1]
        preimage = next_row
    ret = sum(preimage.values())

    return ret

That was almost too much for me, but I can say I learned something that I may not have seen somewhere else.

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 5 – Expanding Nebula!

That’s the end, but Google has a last bit of puzzle for you. In fact, you will receive a secret message for your eyes only! I immediately googled to fin out about the decryption, and I got plenty of solutions using base64 encoding and XOR with your google username. This is the code you need to use to decrypt in Python 3 (it may work also in Python 2…but I almost exclusively use Python 3):

import base64
from itertools import cycle

message = """YOUR SECRET MESSAGE"""

key = bytes("YOUR GOOGLE USERNAME", "utf8")

print(bytes(a ^ b for a, b in zip(base64.b64decode(message), cycle(key))))

And this is what the message says:

"{'success' : 'great', 'colleague' : 'esteemed', 'efforts' : 'incredible', 'achievement' : 'unlocked', 'rabbits' : 'safe', 'foo' : 'win!'}"

---

It seems everybody got the same message if you search a bit 🙂

This is the final task in my Google Foobar challenge. You can find the post series via the link at the end of this post, have fun!

Related links

• Google Foobar link (it is by invitation only)
• My series of posts on Google Foobar link
• Github gist by lotabout with cellular automata implementation in Python link
• Wikipedia Cellular Automata page
• The Nature of Code section about Cellular Automata link

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