Google Foobar: An Example Problem

I recently wrote a post about how I fell into the world of Google Foobar. In this post I will provide my answer to one of the problems. This is designed to give an insight into the nature of the problems posed rather than providing an exemplar answer for others solving the same problem.

The Problem:

Peculiar balance
Can we save them? Beta Rabbit is trying to break into a lab that contains the only known zombie cure – but there’s an obstacle. The door will only open if a challenge is solved correctly. The future of the zombified rabbit population is at stake, so Beta reads the challenge: There is a scale with an object on the left-hand side, whose mass is given in some number of units. Predictably, the task is to balance the two sides. But there is a catch: You only have this peculiar weight set, having masses 1, 3, 9, 27, … units. That is, one for each power of 3. Being a brilliant mathematician, Beta Rabbit quickly discovers that any number of units of mass can be balanced exactly using this set.
To help Beta get into the room, write a method called answer(x), which outputs a list of strings representing where the weights should be placed, in order for the two sides to be balanced, assuming that weight on the left has mass x units.
The first element of the output list should correspond to the 1-unit weight, the second element to the 3-unit weight, and so on. Each string is one of:

“L” : put weight on left-hand side
“R” : put weight on right-hand side
“-” : do not use weight

To ensure that the output is the smallest possible, the last element of the list must not be “-“.
x will always be a positive integer, no larger than 1000000000.

Test cases

Inputs:
(int) x = 2
Output:
(string list) [“L”, “R”]
Inputs:
(int) x = 8
Output:
(string list) [“L”, “-“, “R”]

Some Thoughts:

This problem initially made me feel somewhat intimidated: the premise that any mass on a scale could be balanced by using weights with only powers of three ( and limited to one weight per power of three) didn’t seem particularly intuitive to me.

With a bit of digging, I found that this problem related to balanced ternary, a centuries-old mathematical concept. Ternary is a base-3 numeral system that operates similarly to binary. There is a way to represent ternary in a balanced form, through which every digit is represented by either a “+”, “0”, or “-” (or similar).

I found Rosetta Code to be a particularly useful resource for understanding the concept of balanced ternary and developing an algorithm.

Solution:

This is by no means the most efficient solution, but understanding and exploring  the established algorithm for converting decimals to ternary, I landed upon the following:

def answer(x):
    if x == 0:
        return []
    elif (x%3) == 0:
        return ["-"] + answer(x // 3)
    elif (x%3) == 1:
        return ["R"] + answer(x // 3)
    elif (x%3) == 2:
        return ["L"] + answer((x+1) // 3)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s