推理判断のプレゼント交換の問題
rsc.hatenablog.comrsc さんのブログから問題を拝借しました。
#
問題:
http://rsc.hatenablog.com/entry/2019/04/07/235903
A~Eの5人がプレゼント交換をした。5人とも自分以外の人から1つずつプレゼントを受け取ったが、プレゼントを渡した相手からプレゼントを受け取った人はいなかったという。さらに次のア~エのことがわかっているとき、確実にいえるのはどれか。
ア.AはBからもDからもプレゼントを受け取らなかった。
イ.BはCかDからプレゼントを受け取った。
ウ.DはEからプレゼントを受け取らなかった。
エ.EはBからもCからもプレゼントを受け取らなかった。
1.AはEにプレゼントを渡した。
2.BはCにプレゼントを渡した。
3.CはAにプレゼントを渡した。
4.DはBにプレゼントを渡した。
5.EはAにプレゼントを渡した。
コードは以下です。Ruby で解いてみました。
solve.rb
Name = "ABCDE" N = Name.size def try(given) person = given.size if person == N #プレゼントを渡した相手からプレゼントを受け取った人はいないかチェック N.times {|i| return if i == given[given[i]]} #どの条件が当て嵌まるかチェック [[0, 4], [1, 2], [2, 0], [3, 1], [4, 0]].each_with_index do |c, i| if given[c.last] == c.first str = given.map.with_index {|p, i| "#{Name[p]}=>#{Name[i]}"}.join(", ") puts "[#{str}]" puts "正解: #{i + 1}" end end else left = [*0...N] - given left.each do |gift| next if gift == person case person when 0 next if gift == 1 || gift == 3 when 1 next unless gift == 2 || gift == 3 when 3 next if gift == 4 when 4 next if gift == 1 || gift == 2 end try(given + [gift]) end end end try([])
Array#permutaion を使ってもよいのですが、敢て再帰を使って解いてみました。配列 given は、位置 i (0~4) の人物が given[i] の人物からプレゼントをもらったことを表わしています。
結果。
$ time ruby solve.rb [E=>A, C=>B, A=>C, B=>D, D=>E] 正解: 5 real 0m0.115s user 0m0.076s sys 0m0.008s