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 weightTo 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.