13個の玉から重さの違う1つの玉を見つける

http://anond.hatelabo.jp/20160629132908

天秤を3回だけ使って、9つの玉から1つだけ重さの違うものを探すという頭の体操。13個まで行けるというコメントがあったので、試してみた。

やり方を日本語で書くと大変なので、Java でダラダラと記述してみる。

class FindAnomaly {
	/**
	 * 13個の玉（13要素の配列）から、{@code weigh()} を3回だけ使用して
	 * 重さ（数値）の異なる玉（配列要素）を探します。
	 * @return 重さの異なる玉の番号（配列インデックス）
	 */
	public static int findAnomaly13(int[] n) {
		int[] n0123 = { n[0], n[1], n[2], n[3] };
		int[] n4567 = { n[4], n[5], n[6], n[7] };

		int[] n01245 = { n[0], n[1], n[2], n[4], n[5] };
		int[] n89ABC = { n[8], n[9], n[10], n[11], n[12] };
		
		// 0〜3の4個、4〜7の4個、8〜12の5個に分け、4個と4個を比較
		switch(weigh(n0123, n4567)) {
		case LEFT:
			// 0〜3の方が重い
			// 0,1,2,4,5 と、残りの5個（標準の重さ）を比較
			switch(weigh(n01245, n89ABC)) {
			case LEFT:
				// 0,1,2,4,5 が標準より重い。つまり 0,1,2 のいずれかが重い
				// 0 と 1 を比較し、差があれば重い方が正解。同じなら 2 が正解
				switch(weigh(n[0], n[1])) {
				case LEFT:
					return 0;
				case RIGHT:
					return 1;
				default:
					return 2;
				}
			case RIGHT:
				// 0,1,2,4,5 が標準より軽い。つまり 4,5 のどちらかが軽い
				// 4 と 5 を比較し、軽い方が正解
				switch(weigh(n[4], n[5])) {
				case LEFT:
					return 5;
				case RIGHT:
					return 4;
				default:
					// ありえないケース
					throw new IllegalStateException();
				}
			default:
				// 0,1,2,4,5 が標準と同じ、つまり残りの 3 が標準より重いか、6,7 が標準より軽い
				int[] n36 = { n[3], n[6] };
				int[] n89 = { n[8], n[9] };
				// 3,6 と標準の重さの2個を比較
				switch(weigh(n36, n89)) {
				case LEFT:
					// 3,6 が標準より重い。つまり 3 が正解
					return 3;
				case RIGHT:
					// 3,6 が標準より軽い。つまり 6 が正解
					return 6;
				default:
					// 3,6 は標準と同じ。つまり残りの 7 が正解
					return 7;	
				}
			}
		case RIGHT:
			// 0〜3 の方が軽い
			// この中は、0〜3 の方が重いケースの逆で、やり方は同じ
			switch(weigh(n01245, n89ABC)) {
			case LEFT:
				switch(weigh(n[4], n[5])) {
				case LEFT:
					return 4;
				case RIGHT:
					return 5;
				default:
					throw new IllegalStateException();
				}
			case RIGHT:
				switch(weigh(n[0], n[1])) {
				case LEFT:
					return 1;
				case RIGHT:
					return 0;
				default:
					return 2;
				}
			default:
				int[] n36 = { n[3], n[6] };
				int[] n89 = { n[8], n[9] };
				switch(weigh(n36, n89)) {
				case LEFT:
					return 6;
				case RIGHT:
					return 3;
				default:
					return 7;	
				}
			}
		default:
			// 8〜12 のどれかが正解。重いか軽いかはまだわからない
			int[] n012 = { n[0], n[1], n[2] };
			int[] n89A = { n[8], n[9], n[10] };
			// 8,9,10 を標準と比較
			switch(weigh(n012, n89A)) {
			case LEFT:
				// 8,9,10 の方が軽い
				// 8 と 9 を比較し、差があれば軽い方が正解。同じなら 10 が正解。
				switch(weigh(n[8], n[9])) {
				case LEFT:
					return 9;
				case RIGHT:
					return 8;
				default:
					return 10;
				}
			case RIGHT:
				// 8,9,10 の方が重い
				// 8 と 9 を比較し、差があれば重い方が正解。同じなら 10 が正解。
				switch(weigh(n[8], n[9])) {
				case LEFT:
					return 8;
				case RIGHT:
					return 9;
				default:
					return 10;
				}
			default:
				// 8,9,10 は標準と同じ重さ
				// 11 を標準と比較し、差があれば 11 が正解。同じなら残りの 12 が正解。
				switch(weigh(n[0], n[11])) {
				case LEFT:
				case RIGHT:
					return 11;
				default:
					// 重いか軽いかわからない唯一のケース
					return 12;
				}
			}
		}
	}
	
	/**
	 * 重さを比較した結果
	 */
	private enum Balance {
		LEFT,    // 左が重い
		RIGHT,   // 右が重い
		EQUAL;   // 同じ
	}
	
	/**
	 * 重さを比較した結果を返します。
	 * @param left 左の玉（の重さ）
	 * @param right 右の玉（の重さ）
	 * @return 結果
	 */
	private static Balance weigh(int left, int right) {
		if (left > right) {
			return Balance.LEFT;
		} else if (left < right) {
			return Balance.RIGHT;
		} else {
			return Balance.EQUAL;
		}
	}
	
	/**
	 * 重さを比較した結果を返します。
	 * @param left 左の玉（の重さ）の配列
	 * @param right 右の玉（の重さ）の配列
	 * @return 結果
	 */
	private static Balance weigh(int[] left, int[] right) {
		return weigh(sum(left), sum(right));
	}
	
	private static int sum(int[] n) {
		int sum = 0;
		for (int i = 0; i < n.length; i++) {
			sum += n[i];
		}
		return sum;
	}
}

13個全ての玉について、軽い場合と重い場合のどちらでも正しく判定できるか確認。

import java.util.Arrays;
import java.util.function.ToIntFunction;

public class TestMain {
	public static void main(String[] args) {
		int size = 13;
		for (int i = 0; i < size; i++) {
			test(FindAnomaly::findAnomaly13, size, i, true);
			test(FindAnomaly::findAnomaly13, size, i, false);
		}
	}
	
	private static void test(ToIntFunction<int[]> findAnomaly, int size, int anomaly, boolean heavy) {
		int[] balls = new int[size];
		Arrays.fill(balls, 1);
		balls[anomaly] = heavy ? 2 : 0;
		
		System.out.printf("%s : ", Arrays.toString(balls));
		int result = findAnomaly.applyAsInt(balls);
		if (result == anomaly) {
			System.out.printf("result=%d, Success%n", result);
		} else {
			System.out.printf("result=%d, Failure%n", result);
			throw new RuntimeException();
		}
	}
}

OKですね。

[2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=0, Success
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=0, Success
[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=1, Success
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=1, Success
[1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=2, Success
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=2, Success
[1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=3, Success
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] : result=3, Success
[1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1] : result=4, Success
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1] : result=4, Success
[1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1] : result=5, Success
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1] : result=5, Success
[1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1] : result=6, Success
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1] : result=6, Success
[1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1] : result=7, Success
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] : result=7, Success
[1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1] : result=8, Success
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1] : result=8, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1] : result=9, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1] : result=9, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1] : result=10, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1] : result=10, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1] : result=11, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1] : result=11, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] : result=12, Success
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] : result=12, Success