クリスマスパーティーのプレゼント交換プログラムのテストを書く
クリスマスパーティーでプレゼント交換を行う。
- 全員、誰かにプレゼントを一つあげ、誰かからプレゼントを一つもらう。
- 参加者は、自分と同じグループに属している人にはプレゼントをあげない。
- どのグループにも属さない人や、複数のグループに属する人はいない。
この条件を満たすようなプレゼント交換が等確率で出るような、プレゼント交換方法生成プログラムを実装せよ
という問題が面白そうだったのでやってみました。もう締め切りはすぎているのですがテストを書いたという人は見受けられないので曝しておきます。
問題をやる際にまず考えたのが、最近流行のテストをどう書くか？ということでした。特に等確率であることをきっちり検証するにはどうやればいいのだろうということで悩みました。（というより悩み中です）
先にテストを書いたからか実装は素直にやってしまっているのでパーティーの人数が多くなってしまうとすごく時間がかかってしまうと思います。(10人とかでは試してません）
テストデータに一部誤りがあったので訂正します。おそらくもう一つ間違いがあるはず。。。修正しました
require 'set' require 'enumerator' class CristmasParty class RandomFailError < ::Exception; end def initialize groups @groups = groups @members = [] @groups.each_value do |i| @members.concat i end end attr_reader :groups def number_of_members @members.size end def group_of member @groups.each do |key,val| return key if val.include? member end end def same_group? member1, member2 group_of(member1) == group_of(member2) end def expected_exchangers member @members.inject([]) do |arr,item| arr << item unless same_group? member, item Set.new(arr) end end def exchange_list @groups.each do |key,val| return if val.size > @members.size end exchange_list = {} used_exchangers = [] @members.each do |member| expected_exchangers_of_member = expected_exchangers(member).to_a - used_exchangers expected_exchanger = expected_exchangers_of_member.slice(rand(expected_exchangers_of_member.size)) raise CristmasParty::RandomFailError unless expected_exchanger exchange_list[member] = expected_exchanger used_exchangers << expected_exchanger end exchange_list rescue CristmasParty::RandomFailError exchange_list() end end if $PROGRAM_NAME == __FILE__ require 'rubygems' require_gem 'rspec', '>= 0.7' $KCODE = 'u' # カイ二乗検定を行う # \{chi}^2 = \Sigma_{n=1}^k \frac{(f_i - np_i)^2}{np_i} def chi_squared_test? vals, probabirities=Array.new(vals.size, 1/vals.size.to_f) total_count = vals.inject(0) {|i,j| i + j } chi_squared_val = vals.enum_for(:zip, probabirities).map { |item| ((item.first - total_count * item.last) ** 2) / (total_count * item.last) }.inject(0) {|i,j| i + j } degree_of_free = vals.size - 1 chi_squared_val > CHI_SQUARED_TABLE[degree_of_free] end # カイ二乗関数表、有意水準0.05の場合 CHI_SQUARED_TABLE = { 1 => 3.841, 2 => 5.991, 3 => 7.815, 4 => 9.488, 5 => 11.070, 6 => 12.592, 7 => 14.067, 8 => 15.507, 9 => 16.919, 10 => 18.307, 11 => 19.675, 12 => 21.026, 13 => 22.362, 14 => 23.685, 15 => 24.996, 16 => 26.296, 17 => 27.587, 18 => 28.869, 19 => 30.144, 20 => 31.410, 21 => 32.671, 22 => 33.924, 23 => 35.172, 24 => 36.415, 25 => 37.652, 26 => 38.885, 27 => 40.113, 28 => 41.337, 29 => 42.557, 30 => 43.773, } context "すべてのクリスマスパーティーで" do setup do end end context "２つのグループがあって２人のグループが２つある場合" do setup do @party = CristmasParty.new({ "A" => %w(A1 A2), "B" => %w(B1 B2), }) end specify "exchange_listメソッドはいずれかの結果を返しそれがほぼ等確率であること" do chi_squared_test_counter = 0 10.times do |j| case1, case2, case3, case4 = 0, 0, 0, 0 1000.times do |i| result = @party.exchange_list case result when { "A1" => "B1", "A2" => "B2", "B1" => "A1", "B2" => "A2", } case1 += 1 when { "A1" => "B1", "A2" => "B2", "B1" => "A2", "B2" => "A1", } case2 += 1 when { "A1" => "B2", "A2" => "B1", "B1" => "A1", "B2" => "A2", } case3 += 1 when { "A1" => "B2", "A2" => "B1", "B1" => "A2", "B2" => "A1", } case4 += 1 when nil else 0.should.fail_with_message "正しくない解が存在します:\n #{result.inspect}" return end end cases = [ case1, case2, case3, case4 ] chi_squared_test_counter += 1 if chi_squared_test?(cases) end chi_squared_test_counter.should <= 10 end end context "３つのグループがあって２人のグループがひとつで残りは１人のグループののクリスマスパーティーで" do setup do @party = CristmasParty.new({ "鍋谷夫婦" => %w(私 杏子), "穴田さん" => %w(穴田さん), "出部さん" => %w(出部さん), }) end specify "メンバー名からグループ名を得られること" do @party.group_of('私').should == '鍋谷夫婦' @party.group_of('杏子').should == '鍋谷夫婦' @party.group_of('穴田さん').should == '穴田さん' @party.group_of('出部さん').should == '出部さん' end specify "expected_exchangersがmemberと同じグループではないこと" do @party.expected_exchangers("私").should == Set.new(["穴田さん", "出部さん"]) @party.expected_exchangers("杏子").should == Set.new(["穴田さん", "出部さん"]) @party.expected_exchangers("穴田さん").should == Set.new(["私", "杏子", "出部さん"]) @party.expected_exchangers("出部さん").should == Set.new(["私", "杏子", "穴田さん"]) end specify "私と杏子は同じグループであること" do @party.should_be_same_group "私", "杏子" end specify "メンバーは4名であること" do @party.number_of_members.should == 4 end specify "exchange_listメソッドはいずれかの結果を返しそれがほぼ等確率であること" do chi_squared_test_counter = 0 100.times do |j| case1, case2, case3, case4 = 0, 0, 0, 0 1000.times do |i| result = @party.exchange_list case result when { "私" => "穴田さん", "杏子" => "出部さん", "穴田さん" => "私", "出部さん" => "杏子", } case1 += 1 when { "私" => "出部さん", "杏子" => "穴田さん", "穴田さん" => "私", "出部さん" => "杏子", } case2 += 1 when { "私" => "出部さん", "杏子" => "穴田さん", "穴田さん" => "杏子", "出部さん" => "私", } case3 += 1 when { "私" => "穴田さん", "杏子" => "出部さん", "穴田さん" => "杏子", "出部さん" => "私", } case4 += 1 when nil else 0.should.fail_with_message "正しくない解が存在します:\n #{result.inspect}" return end end cases = [ case1, case2, case3, case4 ] chi_squared_test_counter += 1 if chi_squared_test?(cases) end chi_squared_test_counter.should <= 10 end end context "4つのグループがあってその中の一つが二人のグループで残りのグループが一人の場合" do setup do @party = CristmasParty.new({ "A" => %w(A1 A2), "B" => %w(B), "C" => %w(C), "D" => %w(D) }) end specify "正解のリストとその数" do 10000.times do |i| result = @party.exchange_list cases = Array.new(24, 0) case result when { "A1" => "B", "A2" => "C", "B" => "A1", "C" => "D", "D" => "A2", } cases[0] += 1 when { "A1" => "B", "A2" => "C", "B" => "A2", "C" => "D", "D" => "A1", } cases[1] += 1 when { "A1" => "B", "A2" => "C", "B" => "D", "C" => "A1", "D" => "A2", } cases[2] += 1 when { "A1" => "B", "A2" => "C", "B" => "D", "C" => "A2", "D" => "A1", } cases[3] += 1 when { "A1" => "B", "A2" => "D", "B" => "A1", "C" => "A2", "D" => "C", } cases[4] += 1 when { "A1" => "B", "A2" => "D", "B" => "A2", "C" => "A1", "D" => "C", } cases[5] += 1 when { "A1" => "B", "A2" => "D", "B" => "C", "C" => "A1", "D" => "A2", } cases[6] += 1 when { "A1" => "B", "A2" => "D", "B" => "C", "C" => "A2", "D" => "A1", } cases[7] += 1 when { "A1" => "C", "A2" => "B", "B" => "A1", "C" => "D", "D" => "A2", } cases[8] += 1 when { "A1" => "C", "A2" => "B", "B" => "A2", "C" => "D", "D" => "A1", } cases[9] += 1 when { "A1" => "C", "A2" => "B", "B" => "D", "C" => "A1", "D" => "A2", } cases[10] += 1 when { "A1" => "C", "A2" => "B", "B" => "D", "C" => "A2", "D" => "A1", } cases[11] += 1 when { "A1" => "C", "A2" => "D", "B" => "A1", "C" => "A2", "D" => "B", } cases[12] += 1 when { "A1" => "C", "A2" => "D", "B" => "A1", "C" => "B", "D" => "A2", } cases[13] += 1 when { "A1" => "C", "A2" => "D", "B" => "A2", "C" => "A1", "D" => "B", } cases[14] += 1 when { "A1" => "C", "A2" => "D", "B" => "A2", "C" => "B", "D" => "A1", } cases[15] += 1 when { "A1" => "D", "A2" => "B", "B" => "A1", "C" => "A2", "D" => "C", } cases[16] += 1 when { "A1" => "D", "A2" => "B", "B" => "A2", "C" => "A1", "D" => "C", } cases[17] += 1 when { "A1" => "D", "A2" => "B", "B" => "C", "C" => "A1", "D" => "A2", } cases[18] += 1 when { "A1" => "D", "A2" => "B", "B" => "C", "C" => "A2", "D" => "A1", } cases[19] += 1 when { "A1" => "D", "A2" => "C", "B" => "A1", "C" => "A2", "D" => "B", } cases[20] += 1 when { "A1" => "D", "A2" => "C", "B" => "A1", "C" => "B", "D" => "A2", } cases[21] += 1 when { "A1" => "D", "A2" => "C", "B" => "A2", "C" => "A1", "D" => "B", } cases[22] += 1 when { "A1" => "D", "A2" => "C", "B" => "A2", "C" => "B", "D" => "A1", } cases[23] += 1 when nil else 0.should.fail_with_message "正しくない解が存在します:\n #{result.inspect}" return end chi_squared_test?(cases).should == false end end end end
とりあえず統計学のことはかなり忘れてしまっていたのでググって見るとこういったケースではカイ二乗検定を行うのがそれっぽかったのでカイ二乗検定をしてみました。メソッド名はRでカイ二乗検定を行う関数名がchi_squared_testであったのでそれになぞらえておきました。
カイ二乗検定は次のような公式で行います
となります。
１回の検定におけるexchange_listメソッドの試行回数が十分に大きければ何回も検定する必要ないかと思いつつも何回もテストを実行してみると結構失敗するので検定も複数回やってとりあえず10%を超えていたら失敗するようにしてみました。ちなみに５人の場合はさすがに待つのがつらそうなので端折りました。ちなみにこのソースコードはいちおう手元のMacBookで1分30秒前後のようです。
ただこれでも失敗するときがありますがこれは自分の回答が等確率ではないということを意味しているんだろうか…。いちおうテストが通る方が多いので大丈夫かなとは思っているのですが。
本当はもっともう少しコンテキストを書かなければこのプログラムがちゃんと動くとは言えないのだと思われますが、さすがに書くのが疲れたのでこのあたりで。。。
それから今回書いてみて色々とRSpecで書くのはつらいなぁと思えたところとかもありました。（0.should.fail_with_messageとか。case文で分岐したりとか
ランダムなテストの場合may〜みたいなやつが使えるようになると良いなと思いましたが、さすがにRubyの文法ではそういう拡張はできないですねぇ…。ブロックを使えばそういうテストのためのメソッドを作れそうですが、良さそうな名前が思いつかない。
