Hacking Spot Vol.1 Issue 3: Weights and Balance about algohacks

[airekans]

Given a thing weighting x gram, we first convert it to 3-based representation, e.g. 55 in decimal to 2001 in 3. Check each digit of the representation, if the digit is 1, it means that the weight corresponding to this digit is put on the other side of the balance. If the digit is 2, we add 1 to this digit, and it means the weight corresponding to this digit it put on the same side of the thing. Continue till the last digit, and we get the answer.

The following Python program is the example code:

#! /usr/bin/env python

# num is a integer >= 0
# return a list containing the digits in base
# the digits are ordered from lower bits to higher bits
def convert_to_based_num(num, base):
    digits = []
    while num > 0:
        quotient, remainder = num / base, num % base
        digits.append(remainder)
        num = quotient

    return digits

def add_3_based_digits(digits, index, num):
    while digits[index] + num >= 3:
        digits[index] = (digits[index] + num) % 3
        num = 1
        index += 1
        if index >= len(digits):
            digits.append(0)

    digits[index] += num

def balance(digits):
    left = []
    for i, d in enumerate(digits):
        if d == 2:
            add_3_based_digits(digits, i, 1)
            left.append(1)
        else:
            left.append(0)

    return left, digits

def print_balance(num, left, right):
    print "Output:", num,
    for i, d in enumerate(left):
        if d != 0:
            print "+ 3^%d" % i,
    print "= 3^" + " + 3^".join([str(i) for i, d in enumerate(right) if d != 0])

if __name__ == '__main__':
    w = int(raw_input("Input: "))
    left, right = balance(convert_to_based_num(w, 3))
    print_balance(w, left, right)

[kmalloc]

55 = 2_(3^3)+3^0
-->
55+3^3 = 3_(3^3)+3^0
-->
55+3^3 = 3^4+3^0

[airekans]

@kmalloc What do you mean?

[kmalloc]

solution to the problem.

[airekans]

@kmalloc Yeah, the point is to transform a given number to 3 based representation.