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:

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.