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

*distinct*powers of 3.

**3***3^0 + 0*3^1 + 1*3^2

*y-x*as a “series of distinct powers of 3″ and I’m done.

*any*. And indeed, in case we fail, we’ll have to look for the “next y” and on and forth.

**y-x**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

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

**1***3^1

**-1***3^0 =

**1-1**

**1***3^1 +

**0***3^0 =

**10**

**1***3^1 +

**1***3^0 =

**11**

**=**

**1***3^2

**–**

**1***3^1

**–**

**1***3^0 = 9 – 3 – 1 =

**1-1-1**

**sum of distinct powers of 3!**

**1***3^2

**–**

**1***3^1

**–**

**1***3^0 = 9 – 3 – 1 =

**1-1-1**

**–**

**1***3^0

**–**

**1***3^1 +

**1***3^2

**[-1, -1, 1]**

**[L, L, R]**

**L**nor

**R**should add the respective power of 3, so we can simply replace any zero with “-” (dash).

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