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

リクルートコミュニケーションズの採用情報のところにあった問題

ruby

http://rikunabi-next.yahoo.co.jp/company/cmi0089954001/nx1_rq0008861224/

「相手の思考を推理する」過程をプログラムで表現する問題です。
開発言語は問いませんので、慣れ親しんだ開発環境をご用意ください。

A, B, C の3人が 1〜5の5枚のカードを使ってインディアンポーカーをします。
3人は、ランダムに1枚のカードを引いて額にかざします。
相手のカードは見えますが、自分のカードは見えません。

この状態で、A->B->Cの順番に、
■自分が1番大きい(MAX)
■自分は2番目に大きい(MID)
■自分が1番小さい(MIN)
■わからない(?)
を答えます。

一人でも答えがわかった場合、そこで終了となります。
「わからない」と答えた場合、回答権が次の人に移ります。
Cもわからない場合、再度Aに回答権が移ります。
3人ともウソを言ったり、適当に答えてはいけません。

例1「A=1 B=4 C=5」だった場合、
「A => MIN」で終了します。

例2「A=1 B=2 C=4」だった場合、
「A => ?, B => MID」で終了します。

Bは「Aがわからないなら、自分は5ではない」と考えるからです。

以上を踏まえて、
引数で「A=1 B=4 C=5」で実行すると「A => MIN」を出力
引数で「A=1 B=2 C=4」で実行すると「A => ?, B => MID」を出力
するようなコマンドラインのプログラムを作成してください。

なお、人数やカードの枚数がパラメーター化されていて、
さまざまなケースがシミュレーションできるコードが望ましいです。

※ヒント: 今回のケースでは、
「全員がわからない(無限ループ)」という結果にはなりません。 

三連休の最終日、ちょっと面白そうだったので暇つぶしに挑戦してみた。ちなみに書いたコードは公開してOKと許可頂き済み。

class Resolver
  def initialize(num_of_members, num_of_cards)
    @num_of_cards = num_of_cards
    @members = 'A'.upto('Z').to_a[0, num_of_members]
    @all_card_nums = 1.upto(num_of_cards).to_a
  end

  def resolve(cards, members_hist = [])
    @members.each do |member|
      if member_and_result = trackback_members_hist(cards, members_hist + [member])
        return members_hist.map{|m| {m => nil}} + [member_and_result]
      end
      members_hist << member
    end

    if members_hist.size > @members.size * 3
      nil
    else
      resolve(cards, members_hist)
    end
  end

  def get_visible_cards(cards, member)   
    visible_cards = cards.clone
    visible_cards.delete(member)
    visible_cards
  end

  def trackback_members_hist(cards, members_hist)
    # puts "#{'-' * 40} cards:#{cards}, members:#{members_hist} #{'-' * 40}"

    members_hist = members_hist.clone
    member = members_hist.pop
    visible_cards = get_visible_cards(cards, member)
    result = answer(visible_cards.values)
    return {member => result} if result  

    return nil if members_hist.empty?

    undecidable_nums = []
    visible_nums = @all_card_nums - visible_cards.values
    visible_nums.each do |visible_num|   
      assumed_cards = visible_cards.clone
      assumed_cards[member] = visible_num

      member_and_result = trackback_members_hist(assumed_cards, members_hist)
      undecidable_nums << visible_num unless member_and_result
    end

    visible_cards_min = visible_cards.values.min
    visible_cards_max = visible_cards.values.max

    result =
      case
      when undecidable_nums.all?{|x| x < visible_cards_min}
        :min
      when undecidable_nums.all?{|x| x > visible_cards_max}
        :max
      when undecidable_nums.all?{|x| visible_cards_min < x && x < visible_cards_max}
        :mid
      else
        return
      end

    return {member => result}
  end

  def answer(other_nums)
    min_start = nil
    min_end = nil
    mid_start = nil
    mid_end = nil
    max_start = nil
    max_end = nil

    1.upto(@num_of_cards).each do |i|
      if max_start
        max_end = i - 1 unless other_nums.include? i
      elsif mid_start
        if other_nums.include? i
          mid_end = i - 1
          max_start = i
        end
      elsif min_start
        unless other_nums.include? i
          min_end = i - 1
          mid_start = i
        end
      else
        min_start = i if other_nums.include? i
      end
    end

    min_end = @num_of_cards if min_start && min_end.nil?
    mid_end = @num_of_cards if mid_start && mid_end.nil?
    max_end = @num_of_cards if max_start && max_end.nil?

    case
    when min_start == 1 && max_end == @num_of_cards
      :mid
    when min_start == 1 && mid_end == @num_of_cards
      :max
    when min_end == @num_of_cards
      :min
    else
      nil
    end
  end
end

if __FILE__ == $0
  resolver = Resolver.new(4, 6)
  raise unless resolver.answer([1, 2, 3]) == :max
  raise unless resolver.answer([4, 5, 6]) == :min
  raise unless resolver.answer([1, 2, 6]) == :mid
  raise unless resolver.answer([1, 5, 6]) == :mid
  raise unless resolver.answer([3, 4, 5]).nil?
  raise unless resolver.answer([1, 3, 6]).nil?
  raise unless resolver.answer([1, 4, 6]).nil?
  raise unless resolver.answer([1, 4, 5]).nil?
  raise unless resolver.answer([2, 3, 6]).nil?
  raise unless resolver.resolve('A' => 1, 'B' => 2, 'C' => 5, 'D' => 6) == [{'A' => nil}, {'B' => :mid}]
  # p resolver.resolve('A' => 3, 'B' => 4, 'C' => 5, 'D' => 2)

  resolver = Resolver.new(3, 5)
  raise unless resolver.resolve('A' => 1, 'B' => 4, 'C' => 5) == [{'A' => :min}]
  raise unless resolver.resolve('A' => 1, 'B' => 2, 'C' => 4) == [{'A' => nil}, {'B' => :mid}]
  raise unless resolver.resolve('A' => 2, 'B' => 3, 'C' => 4) == [{'A' => nil}, {'B' => nil}, {'C' => :max}]

  exit if ARGV.size < 2

  print_result = proc do |x|
    case x
    when :min then 'MIN'
    when :max then 'MAX'
    when :mid then 'MID'
    when nil then '?'
    end
  end

  num_of_members = Integer(ARGV.shift)
  num_of_cards = Integer(ARGV.shift)
  cards = ARGV.inject({}){|a, kv| kvs = kv.split('='); a[kvs[0]] = Integer(kvs[1]); a}

  resolver = Resolver.new(num_of_members, num_of_cards)
  answer = resolver.resolve(cards)
  puts answer.map{|kv| k = kv.keys.first; "#{k} => #{print_result.call(kv[k])}"}.join(', ')
end

ちなみに今現在、会社の飲み会から帰宅して酔っ払ってるのでコピペミスがあるかも。