読者です 読者をやめる 読者になる 読者になる

クリスマスパーティーのプレゼント交換プログラムのテストを書く

クリスマスパーティーでプレゼント交換を行う。

  • 全員、誰かにプレゼントを一つあげ、誰かからプレゼントを一つもらう。
  • 参加者は、自分と同じグループに属している人にはプレゼントをあげない。
  • どのグループにも属さない人や、複数のグループに属する人はいない。

この条件を満たすようなプレゼント交換が等確率で出るような、プレゼント交換方法生成プログラムを実装せよ

http://d.hatena.ne.jp/Nabetani/20061217#p1

という問題が面白そうだったのでやってみました。もう締め切りはすぎているのですがテストを書いたという人は見受けられないので曝しておきます。

問題をやる際にまず考えたのが、最近流行のテストをどう書くか?ということでした。特に等確率であることをきっちり検証するにはどうやればいいのだろうということで悩みました。(というより悩み中です)

先にテストを書いたからか実装は素直にやってしまっているのでパーティーの人数が多くなってしまうとすごく時間がかかってしまうと思います。(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 "2つのグループがあって2人のグループが2つある場合" 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 "3つのグループがあって2人のグループがひとつで残りは1人のグループののクリスマスパーティーで" 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であったのでそれになぞらえておきました。


カイ二乗検定は次のような公式で行います

 X = \Sigma_{i=0}^n \frac{(actual - expected)^2}{expected}

となります。

1回の検定におけるexchange_listメソッドの試行回数が十分に大きければ何回も検定する必要ないかと思いつつも何回もテストを実行してみると結構失敗するので検定も複数回やってとりあえず10%を超えていたら失敗するようにしてみました。ちなみに5人の場合はさすがに待つのがつらそうなので端折りました。ちなみにこのソースコードはいちおう手元のMacBookで1分30秒前後のようです。

ただこれでも失敗するときがありますがこれは自分の回答が等確率ではないということを意味しているんだろうか…。いちおうテストが通る方が多いので大丈夫かなとは思っているのですが。

本当はもっともう少しコンテキストを書かなければこのプログラムがちゃんと動くとは言えないのだと思われますが、さすがに書くのが疲れたのでこのあたりで。。。

それから今回書いてみて色々とRSpecで書くのはつらいなぁと思えたところとかもありました。(0.should.fail_with_messageとか。case文で分岐したりとか

ランダムなテストの場合may〜みたいなやつが使えるようになると良いなと思いましたが、さすがにRubyの文法ではそういう拡張はできないですねぇ…。ブロックを使えばそういうテストのためのメソッドを作れそうですが、良さそうな名前が思いつかない。