あなたは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