foo.bar: Peculiar balance

In the past few months Google pulled “Matrix” on many Python and Java engineers: if you google terms like “python lambda” you might get pulled into “The Matrix” as well…
To me it happened on a Saturday around midnight, I googled something related to Python and suddenly the search page collapsed and became dark. There was a single sentence that said something like:
“You speak our language”.
and then it invited me to participate in a series of code-challenges.
As a veteran member of CodeEval I gladly stepped into the Matrix and started solving different challenges. All was good until I ran into the following:

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”]

After playing a bit with numbers, I figured out my strategy:
Given a number x I’ll try to find the minimal integer y >=x so that y can be presented as a sum of distinct powers of 3.
I say “distinct” because the coefficients for any power of 3 can be either 0 or 1.
Example:
A good solution: 12 = 0*3^0 + 1*3^1 + 1*3^2
A bad solution: 12 = 3*3^0 + 0*3^1 + 1*3^2
The second solution is bad because one of the coefficients is 3.
So I need to find the smallest y that respects this rule. Once I’ve found such a y, and since I already know how to represent it as a series of distinct powers of 3 – it’s a good candidate for ‘R’.
Now I still need to figure out how to represent the difference y-x as a “series of distinct powers of 3″ and I’m done.
As you might already started suspecting: we cannot find such a representation for any y-x. And indeed, in case we fail, we’ll have to look for the “next y” and on and forth.
The code looked like this:
from itertools import combinations

def answer(x):
    """
    Main logic:
    find the closest number y >= x so such that:
    1. y is a sum of powers of 3
    2. x + z = y where z is sum of numbers, each of which is a power of 3
    3. z will be decomposed to "L" and y will be decomposed to "R" in build_list()
    """
    next = find_next_sum_of_powers(x)        
    left = represent_as_powers(next - x)   
    while list(set(left)) != left: # meaning we have the same item more than once in "left"
        # look for the next "sum of powers" and try to use it instead
        next = find_next_sum_of_powers(next + 1)        
        left = represent_as_powers(next - x)   
    right = represent_as_powers(next)
    return build_list(left, right)


def find_next_sum_of_powers(x):
    """
    Given a number x, find the closest number y
    such that y >= x and y is one of the numbers 
    returned by get_list_of_sums() and there is no number z,
    which is also returned by get_list_of_sums() such that:
    y > z > x
    """
    next = find_next_power(x)
    if x == next:
        return x
    if x <= next // 2:
        sums = []
        for list_of_sums in get_list_of_sums(x):
            for sm in list_of_sums:
                if sm not in sums:                
                    if x == sm:
                        return x                
                    if sm - x in sums:
                        return sm
                    sums.append(sm)
    else:
        return next

def is_power_of_3(x):
    """
    Checks if x is a power of 3
    """
    n = 0
    b = 0
    while n < x:
        n = 3 ** b    
        b += 1
    return n == x


def get_list_of_sums(x):
    """
    Generates a list of sums of powers of 3:
    1, 3, 4, 9, 10, 12, 13...
    4 = 3 + 1; 10 = 9 + 1; 12 = 9 + 3; 13 = 9 + 3 + 1; ...
    """
    workset = []
    for i in gen_next_power():         
        if i > x:
            break        
        workset.append(i) 
    res = []
    for i in range(len(workset)+1):
        for j in combinations(workset, i):
            res.append(j)      
            yield map(sum, res[1:])

def gen_next_power():
    """
    Generator for powers of 3
    each iteration will get the next power
    """
    pow = 0
    while True:
        yield 3 ** pow
        pow += 1


def find_next_power(x):
    """
    Given a number x find the closest 
    power of 3, y such that y > x and there
    is no power of 3, z such that  x < z < y
    """
    if x == 1:
        return x
    t = 3
    while t < x:
        t *= 3
    return t

def represent_as_powers(num):
    res = []
    while num > 0:
        t = find_next_power(num)
        if t > num:
           t /= 3
        res.append(t)
        num -= t
    return res[::-1]

def build_list(left, right):
    stop = right[-1]
    res, i = [],  0
    while 3 ** i <= stop :
        if 3 ** i in left:
            res.append("L")
        elif 3 ** i in right:
            res.append("R")
        else:
            res.append("-")
        i += 1
    return res    
Now, this works. Only problem is – this approach of trying different y’s could get really expensive.
In fact, if I limited the number “retries” to a small number – I could get almost all the test-cases to pass – all but one…
But I wasn’t ready to give up 🙂
So I started googling and found this post which provided a good direction but to be honest – I didn’t understand:
1. how balanced ternary representation helps to solve our problem
2. how to translate from ternary representation to balanced ternary
These questions are coupled, and it took me some extra-reading to figure it out and what I’d like to do now – is save you the time that I spent, by trying to explain it a little better than that post, wikipedia and other resources I ran into during my investigation.
Let’s start with the second question which is pure technical, by comparing numbers in different bases, we’ll represent “balanced” with 1,0,-1:
decimal      1    2      3     4      5
ternary      1    2      10    11     12
balanced     1    1-1    10    11     1-1-1
Trying to follow up on the “balanced” gave me a headache… but after playing with it for a bit, and reading some search results like this answer (which explains how to add numbers in balanced-ternary form), made things much clearer:
in “balanced” we’re still using ternary-base, and the numbers 1/0/-1 are simply the coefficients of the respective power of 3. Lets demonstrate:
2 = 1*3^1 -1*3^0 = 1-1
3 = 1*3^1 + 0*3^0 = 10
4 = 1*3^1 + 1*3^0 = 11
5 = 1*3^2 1*3^1 1*3^0 = 9 – 3 – 1 = 1-1-1
etc
Once you realize the answer to #2 it’s only another small step to understand the connection to the code challenge:
Given that number x, once we find its balanced-ternary representation we can express it as a… sum of distinct powers of 3!
Now we have only a small obstacle: this sum has positive and negative elements – how do we handle it?
The challenge was to balance weights, which means that instead of “subtracting” the left side we can “add” the weight to the right side – like balancing equations!
The meaning of this is that the balanced-ternary form is actually the answer we’re looking for, lets take the number 5 from the previous example:
5 = 1*3^2 1*3^1 1*3^0 = 9 – 3 – 1 = 1-1-1
in the form of our answer – we’re looking at the result from right to left, which means that
1-1-1 = [-1, -1, 1] = 1*3^0 1*3^1 + 1*3^2
and the way it helps us solving the problem is by using ‘R’ as 1*3^2 and balancing it with ‘L’ by adding to ‘L’ 1*3^0 + 1*3^1 which ends up as simply replacing letters in the reversed version of the balanced-ternary form
from: [-1, -1, 1]
to:   [L,  L,  R]
 
Further, if we have a zero in the balanced-ternary form it means that neither L nor R should add the respective power of 3, so we can simply replace any zero with “-” (dash).
We’re now ready to look at the code:
def answer(x):
    return to_balanced(to_ternary(x))

def to_ternary(x):
    """
    convert decimal into ternary
    """
    res = ""
    while x > 0:
        res = str(x % 3) + res
        x /= 3
    return int(res) 

def to_balanced(t):
    """
    convert ternary number into balanced-ternary
    and then to L/-/R representation
    """
    res = map(int, str(t))[::-1] # iterating the digit from right --> left
    for i in range(0, len(res)):
        # zeros will remain zeros and ones remain ones
        # the only thing we need to convert is 2 into +- (== +1-1)
        if res[i] == 2:
            res[i] = -1
            res = inc(res, i + 1)

    # convert from (1,0,-1) representation to (R,-,L)
    return ['-' if x == 0 else ('R' if x == 1 else 'L') for x in res]


def inc(arr, ind):
    """
    calculate the carryover
    """
    if len(arr) == ind:
        arr += [1] # prepend the last carryover
    elif arr[ind] == -1:
        arr[ind] = 0
    elif arr[ind] == 0:   
        arr[ind] = 1
    elif arr[ind] == 1: 
        arr[ind] = -1
        arr = inc(arr, ind + 1)
    else: # arr[ind] == 2
        arr[ind] = 0
        arr = inc(arr, ind + 1)
    return arr

Needless to say that this solution worked perfectly.
Advertisements
foo.bar: Peculiar balance

2 thoughts on “foo.bar: Peculiar balance

  1. I recently got this challenge. Initially, I figured this was relatively easy, as it is pretty simple to do in your head (for small numbers anyway). The path I took was to break down the what I was doing in my head in a fraction of a second into individual steps in my head. Easier said than done. What I ended up with was to go with the power of 3 that was closest to the difference between the total weight of the right and left sides. Unfortunately, this only ended up working about 70% of the time. I could not come up with a hard and fast rule to go higher or lower than my target.

    So in the end I used simple probability and brute force to solve it. I simply use a random number, 0 or 1, to decide on higher or lower, looping until I get it right. Given the maximum x value of 1,000,000,000, that’s somewhere around 1 million combinations. In my testing it only took a few thousand tries, though. But I get the correct answer, every time.

    Upon verifying my answer in Google’s environment, however, I realized that Python’s random library is not supported, even though they don’t say so. I even tried os.urandom, but that wasn’t supported either.

    I was trying really hard to not search for information on this specific problem as I wanted to do it on my own. Unfortunately I no longer have time left to fully understand this ternary concept and roll my own. Oh well, maybe next time.

    Thank you for posting this. It’s eye opening. Will certainly be playing with the concept in the future.

    Like

  2. Jonny says:

    Thanks a lot for this! I’m far from perfect at maths and was not having a good time with this question. Your explanation really helped a lot!

    Like

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