pecular-balance-google-foobar.js

// 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 1,000,000,000.

// Test cases
// ==========
// Inputs:
// (int) x = 2
// Output:
// (string list) [“L”, “R”]
// Inputs:
// (int) x = 8
// Output:
// (string list) [“L”, “-“, “R”]


// The idea here is that balanced ternary representation represents a number
// as the sum of 3^(place) numbers:
// for example, 23 in ter is 212 (2*3^0 + 1*3^1 + 2*3^2)
// and in the balanced form is +0--. Conversion is achieved by, starting from
// the lowest place, converting 2 to +- and carrying over. therefore:
// 212 = +-00 + 00+0 + 00+- = +0--.
// This balance represents the scale, with + being a weight added 
// to the right and a - being a weight on the left. 0s are left out.

// http://www.rezaparang.com/entries/6-foobar-with-google-peculiar-balance was
// exceedingly helpful in figuring this out.

// More notes at the bottom.

var dec2ter = function(int) {
  if (int === 0) {
    return [0];
  }
  var digits = [];
  while (int) {
    digits.unshift(int % 3);
    int = Math.floor(int/3);
  }
  return digits;
}

var answer = function(ter) {
  // start at the smallest place
  var bal = ter.reverse();
  var result = Array(); 
  var carry = 0;
  for (i = 0; i < bal.length; i++) {
    switch(bal[i] + carry){
      case 0:
        // even, no carry
        result.push("-");
        carry = 0;
        break;
      case 1:
        // negative, no carry
        result.push('R');
        carry = 0;
        break;
      case 2:
        // positive, convert and carry
        result.push('L');
        carry = 1;
        break;
      case 3:
        // this is + and -, which works out to 0 and a carry
        result.push('-');
        carry = 1;
        break;
    }
  }
  // catch the remainder
  if (carry === 1) {
    result.push("R");
  }
  return result;
}

console.log(answer(dec2ter(2)));    // [ 'L', 'R' ]
console.log(answer(dec2ter(8)));    // [ 'L', '-', 'R' ]
console.log(answer(dec2ter(23)));   // [ 'L', 'L', '-', 'R' ]
console.log(answer(dec2ter(2300))); // [ 'L', 'L', 'R', 'R', 'R', '-', '-', 'R' ]

// I began trying to work out if it was possible to translate this problem to an
// anbitrary base system -- say, for example, a set of weights based on 5^n -- 
// but quickly realized that for that to work you'd have to be given n-1 of each
// weight (for example, try balancing 15 with a set of base 4 weights and you 
// find you need three 1s and three 4s, the upshot being they can all be stacked
// on the right side of the scale). The only real interesting part of this 
// problem, then, is the assertion that you only have *one* of each weight, 
// because otherwise you can just build your balances using as many of the b^0
// form as you need.