A few weeks ago I was browsing some threads discussing reddit’s april fool’s day /r/place experiment. I was interested in seeing some of the overlay scripts people whipped up on short notice and found myself in a script discussion thread.  In this thread I came across a redditor giving others a heads up that if you are ever searching for python programming terms and google asks you if you are up for a challenge, say yes, because it is a job interview. I thought that was really interesting so I did some research and came across a few older hacker news threads discussing this practice and this article that confirmed this thing existed.

As I am just venturing down the road of learning python (I started learning less than a month ago), I find myself googling almost everything related to the code I am writing. If this thing is real I am probably going to see it eventually…

Fast forward to today and I am working on writing an AWS lambda/boto function in python and needed a reminder on list comprehension syntax. I went to google and searched python list comprehension. As I snapped my cursor to click the first link, I saw the page morph. I was instantly reminded of the foobar challenge and knew I had just been invited. Unfortunately I had clicked too fast and left the search results page. I went back and refreshed and re-searched but the invite was gone!

I went to lunch and pondered over what a fun learning opportunity I missed. When I got back to my desk, I went back to google to retrace my steps, hopeful the invites were google account linked and perhaps I would get another invite. I never technically “declined” my invite I just missed it. Sure enough, one google search later, I had my invite. This is what it looked like.

After accepting the invite I was taken to google’s foobar challenge site. It was a web app with a very minimalist feel. I was greeted with what looked like a linux command prompt so I typed “ls”. It listed a bunch of files, one called journal.txt and another called start_here.txt. Using “cat” on these files start_here.txt gave me instructions on how to request a challenge and journal.txt set the stage for challenges plot line.

LEVEL 1
=======

Success! You’ve managed to infiltrate Commander Lambda’s evil organization, and finally earned yourself an entry-level position as a Minion on her space station. From here, you just might be able to subvert her plans to use the LAMBCHOP doomsday device to destroy Bunny Planet. Problem is, Minions are the lowest of the low in the Lambda hierarchy. Better buck up and get working, or you’ll never make it to the top…

Next time Bunny HQ needs someone to infiltrate a space station to rescue prisoners, youre going to tell them to make sure stay up for 48 hours straight scrubbing toilets is part of the job description. Its only fair to warn people, after all.

I followed the instructions and requested a challenge. I was given “the cake is not a lie!” challenge as my level 1 challenge. A timer appeared on the lower left hand side of the screen, indicating I had 48 hours to solve this challenge. A new directory was created in my home directory of this virtual terminal. Here is what the challenge looked like.

The cake is not a lie!
======================

Commander Lambda has had an incredibly successful week: she completed the first test run of her LAMBCHOP doomsday device, she captured six key members of the Bunny Rebellion, and she beat her personal high score in Tetris. To celebrate, she’s ordered cake for everyone – even the lowliest of minions! But competition among minions is fierce, and if you don’t cut exactly equal slices of cake for everyone, you’ll get in big trouble.

The cake is round, and decorated with M&Ms in a circle around the edge. But while the rest of the cake is uniform, the M&Ms are not: there are multiple colors, and every minion must get exactly the same sequence of M&Ms. Commander Lambda hates waste and will not tolerate any leftovers, so you also want to make sure you can serve the entire cake.

To help you best cut the cake, you have turned the sequence of colors of the M&Ms on the cake into a string: each possible letter (between a and z) corresponds to a unique color, and the sequence of M&Ms is given clockwise (the decorations form a circle around the outer edge of the cake).

Write a function called answer(s) that, given a non-empty string less than 200 characters in length describing the sequence of M&Ms, returns the maximum number of equal parts that can be cut from the cake without leaving any leftovers.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases
==========

Inputs:
(string) s = “abccbaabccba”
Output:
(int) 2

Inputs:
(string) s = “abcabcabcabc”
Output:
(int) 4

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

I read over this challenge and knew this was no task for work. This was going to be a brain twister for a python novice such as myself and I’m not being paid to play python games afterall. My immediate schedule is quite busy and I didn’t have a ton of time to spend on this, so I decided to think on this challenge on my commute home.

I thought about the intricacies of this problem while dealing with my daily dose of New Jersey’s rush hour. The function would need to return 0 if the cake could not be cut without leftovers or if the string was empty. I needed to identify possible M&M patterns from the input string. The pattern surely could not be longer than half the length of the string. I needed to check to see if there were remainders  (probably with a modulus) when chopping the string with the possible patterns and discard those results. I had to wrap the string somehow because the function needed to iterate over all possible starting points of the string to find valid solutions. There would be edge cases / test cases on that part I was sure due to the way it was stated on the description that the M&Ms were laid out clockwise. As such a python beginner, who had to google list comprehension syntax to get here, I knew I wasn’t solving this in the few hours of free time I had in the next two days.

So I did what anyone in IT does when they don’t know a solution off the top of their head, I went to the search engines to discover some discussions on this problem. A quick search later and I found this stackoverflow question with a valid java answer by Jawad Le Wywadi. Further searches for a python solution turned up blank. In the end, this blog post may very well change that.

Here is the example code from the stack overflow question written in java:

Well, with a possible answer in hand, I still wanted to at least have somewhat of a challenge so I decided to see if I could turn this solution into a valid python solution to the problem. There was a text file with constraints listed, so I would need to take those into consideration. Notably for me was the fact that this needed to run on python 2.7.6

Java
====

Your code will be compiled using standard Java 7. It must implement the answer() method in the solution stub.

Execution time is limited. Some classes are restricted (e.g. java.lang.ClassLoader). You will see a notice if you use a restricted class when you verify your solution.

Third-party libraries, input/output operations, spawning threads or processes and changes to the execution environment are not allowed.

Python
======

Your code will run inside a Python 2.7.6 sandbox.

Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.

After a few more searches and some quick print debugging, I was getting closer. While I know I had zero chance of coming up with this solution on my own with my current time constraints, I was still able to learn a bit of python syntax from this challenge when converting the java code into a python solution. The python code was solving all the inputs I threw at it despite being overly verbose and unoptimized. Here is that code

I used the foobar editor to put my code into solution.py and ran the verify command to see if I had a solution.

Well look at that, All test cases passed! I had indeed googled my solution to google’s challenge.

After verifying my solution, I submitted it to move on to level 2, and was greeted by a jumping ASCII bunny on the terminal. Who doesn’t love ASCII art?

For this next challenge level, I am going to wait until I have a free weekend and proper time to possibly come up with my own solution.