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.