かわうそのブログ

エントリービルゲイツの面接試験ネタに便乗に便乗の金貨問題で出した問題の2問目は、エントリー金貨問題の解答編で可能であることだけ書いて力技での検証をしませんでした。問題を要約すると

正規品10グラムの金貨が24枚入った6袋中、何袋あるかわからない全て偽造品11グラムの金貨の袋を、1回だけの計量で選別する方法があるか

ちょうど今ものにしようとしているプログラミング言語Rubyの題材として適当そうですので、プログラムを作って本当にそんなことが可能かどうか検証してみます。 (なお組み合わせを生成する部分は書籍Rubyプログラミング入門の「第8章 Rubyスクリプト実例集」のコードを参照しました。yieldの再帰が巧みですね。)

まず以下の2つの関数を作ります。

    
# 各n枚の金貨が入ったm袋からの金貨の取り出しかた全てについて、与えられたブロックを実行する
def combi(n, m)
  if m == 0
    yield([])
  else
    combi(n, m - 1) do |x|
      s = (x.length == 0 ? 1 : x[0] + 1)
      (s..n).each do |i|
        yield([i] + x)
      end
    end
  end
end

# 与えられた金貨の取り出しかたについて、正規品および偽造品の組み合わせ全てで
# 重量が区別できるかどうか調べる
def weight(coins)
  if coins.length == 0
    return [0]
  end
  weight_list = weight(coins[1..-1])
  if !weight_list
    return nil
  end
  new_list = []
  weight_list.each do |x|
    # 正規金貨の場合
    w = coins[0] * 10 + x
    if new_list.index(w)
      # 重量が重複するので不可
      return nil
    end
    new_list.push(w)
    # 偽造金貨の場合
    w = coins[0] * 11 + x
    if new_list.index(w)
      # 重量が重複するので不可
      return nil
    end
    new_list.push(w)
  end
  return new_list
end
    
  

    
combi(24, 6) do |x|
  if weight(x)
    p x
  end
end

[24, 23, 22, 20, 17, 11]
    
  

う〜ん興味深いですね〜。