あなたは8つの同じサイズのボールを持っています(JavaScript手習い)

Twitterを見ていたら次の問題が流れてきました。元ページを探したら消えていたので、下記は又引きです。

16. You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?

http://www.gossiprocks.com/forum/computers-technology/51059-hard-interview-questions-google-sure-you-want-work-there.html

「あなたは8つの同じサイズのボールを持っています。7つは同じ重さで、1つだけが他より少し重いです。秤を2回だけ使って、少しだけ重いボールを見つけるには、どうすればよいでしょうか?」(テキトー訳)

JavaScriptの手習いに解いてみました。もっとJavaScriptっぽいコードが書きたいです! 特にこのあたり。

  • 配列Xを配列a, b, cに分割するイディオムを知りたい
  • 配列a, b, cで、元の配列Xの添え字を保持したい

どうすればいいんでしょう? あと、もっと小さい関数に分割した方がいいのかも。

googleBall.js

var _ = require("./lib/underscore-min.js");

exports.solve = function(balls){
	
	// 3つずつ取り出して比べる
	var right = [];
	var left = [];
	var other = [];
	balls.forEach(function(e, i, a){
		if (i < 3){
			right.push(e);
		} else if (2 < i && i < 6){
			left.push(e);
		} else {
			other.push(e);
		}
	}, this);
	var rsum = _.reduce(right, function(memo, num){ return memo + num; }, 0);
	var lsum = _.reduce(left, function(memo, num){ return memo + num; }, 0);

	var result = -1;
	if(lsum === rsum){
		// 釣り合ったら残り2つで比べる
		result = other[0] < other[1] ? 7 : 6;
	} else if (lsum < rsum) {
		// 右の方が重ければ右から1つずつ取り出して比べる
		if(right[0] === right[1]){
			result = 2;
		} else {
			result = right[0] < right[1] ? 1 : 0;
		}
	} else {
		// 左の方が重ければ左から1つずつ取り出して比べる
		if(left[0] === left[1]){
			result = 5;
		} else {
			result = left[0] < left[1] ? 4 : 3;
		}
	}
	return result;
};

テスト。

var assert = require('assert');
var googleBall = require("./googleBall.js");

describe('8つのボールから1つだけ重いボールのインデックスを返す', function(){
    it('重いボールが先頭にある場合', function(){
    	var answer = googleBall.solve([7, 5, 5, 5, 5, 5, 5, 5]);
        assert(answer === 0);
    })
    it('重いボールが中央付近にある場合', function(){
    	var answer = googleBall.solve([5, 5, 5, 5, 7, 5, 5, 5]);
        assert(answer === 4);
    })
    it('重いボールが末尾にある場合', function(){
    	var answer = googleBall.solve([5, 5, 5, 5, 5, 5, 5, 7]);
        assert(answer === 7);
    })
});

Array.forEachとunderscoreのreduceは、内輪のJavaScript勉強会で知ったので、マネしてみました。

(追記)書き直しました。 http://d.hatena.ne.jp/torazuka/20130626/balls2