tsykの日記： なぞなぞ

「１と１と９と９、この４つを適当に四則演算して１０を作れ。」
「１と１と５と８、　　　　　〃　　　　　〃　　　　　　　　」

cyber205氏の日記<http://srad.jp/journal.pl?op=display&uid=4374&id=146330>より引用。
__hage氏のコメント<http://srad.jp/comments.pl?sid=112555&cid=373804>にヒントを得て、
逆ポーランド計算機を使った方式で解いてみた。

頭で考えても全然わからず、とんち問題なのかと思ったが、
rubyが解いた回答を見て、なるほど！ちゃんとした正解があるもんだ。

# nazo.rb
require 'rational'

# 逆ポーランド記法の計算モジュール
module RPN
  def calc(form)
    begin
      stack = []
      form.each {|a|
        puts "stack: #{stack.inspect}" if $DEBUG
        if a.is_a?(Fixnum)
          stack.push(Rational(a))
        elsif a.is_a?(Symbol)
          x = stack.pop
          y = stack.pop
          raise if [x, y].include?(nil)
          puts " calc: #{[y, x, a].inspect}" if $DEBUG
          z = y.send(a, x)
          stack.push(z)
        else
          puts "Illegal formula!"
        end
      }
      stack.pop
    rescue ZeroDivisionError
      puts "Divide by Zero!" if $DEBUG
      nil
    end
  end
  module_function :calc
end

# 順列(permutation)を列挙する関数
# ※「Rubyプログラミング入門」の203ページより拝借
def perm(n, m = n)
  if n < m
    # do nothing
  elsif m <= 0
    yield([])
  else
    perm(n - 1, m - 1) do |x|
      (0...m).each do |i|
        yield(x[0...i] + [n-1] + x[i..-1])
      end
    end
    perm(n - 1, m) do |x|
      yield(x)
    end
  end
end

answer = Rational(10, 1)
num = [1, 1, 9, 9]
#num = [1, 1, 5, 8]
ope = [:+, :-, :*, :/]

# 逆ポーランド記法で４つの数値を四則演算する場合の
# 可能なパターンは以下の５つになる。(true:数値, false:演算子)
# ※これを計算で論理的に求められたらスマートなんだけど…
pattern = [
  [true,  true,  true,  true,  false, false, false],
  [true,  true,  true,  false, true,  false, false],
  [true,  true,  true,  false, false, true,  false],
  [true,  true,  false, true,  false, true,  false],
  [true,  true,  false, true,  true,  false, false] ]

# 数値の順列(4P4)と演算子の順列(4P3)を求め、
# それらをパターンに従って合成して計算式を生成する。
pattern.each {|pat|
  perm(4) do |n|
    a = num.values_at(*n)
    perm(4, 3) do |o|
      b = ope.values_at(*o)
      form = []
      ta = a.dup
      tb = b.dup
      pat.each {|x| form << (x ? ta.shift : tb.shift) }
      p form if $DEBUG
      result = RPN.calc(form)
      p result if $DEBUG
      puts "found! #{form.inspect}" if result == answer
    end
  end
}

※追記(2003.08.08 02:45):
  --- これだと４種類の演算子を各１回ずつしか使えないので不完全。
      実際には同じ演算子を複数回使う場合を考慮する必要がある。
      重複を許すような順列(?)はどうやって求めるのかなぁ…

※追記(2003.08.08 16:50):
  --- 逆ポーランド記法で可能なパターンは４つでなく５つだった。
(((A   x   B)  y   C)  z   D)   --> ABxCyDz
((A   x  (B   y   C)) z   D)   --> ABCyxDz
((A   x   B)  y  (C   z   D))  --> ABxCDzy (これが抜けてた)
  (A   x ((B   y   C)  z   D))  --> ABCyDzx
  (A   x  (B   y  (C   z   D))) --> ABCDzyx