#!/usr/local/bin/ruby
=begin
ticket.rb
  いわゆる切符問題をときます。
  「1, 3, 4, 6 の 4 つの数字（順序は入れ替えてよい）と四則演算をもちいて
    24 をつくれ」
  だったら、
  ./ticket.rb 24 1 3 4 6
  になります。
=end

require 'rational'

=begin
== each_tree_permutaion(array) {|a| ... }
  配列をうけとって、構文木の候補を生成します。
  たとえば、[a, b, c] からは
     [[a, b], c], [[b, a], c], [c, [a, b]], ...
  が次々に生成されブロックに渡されます。
=end
def each_tree_permutation(ary)
  pr = Proc.new

  if ary.size > 2
    0.upto(ary.size - 1) do |i0|
      a = ary.dup
      x = a.delete_at(i0)

      0.upto(a.size - 1) do |i1|
        b = a.dup
        y = b.delete_at(i1)

        0.upto(b.size) do |j|
          each_tree_permutation(b.dup.insert(j, [x, y]), &pr)
        end
      end
    end
  else
    pr.call(ary)
  end
end

=begin
== each_operations(ary){|a| ... }
  each_tree_permutation で生成された木の各ノード [x, y] に
  可能な四則演算をはめこんでブロックに渡します。
  [x, y] は、['+', x, y], ['-', x, y], ['*', x, y], ['/', x, y]
  になります。y が 0 でないか等の検査はしない。
  (eval まかせ)
=end
OPS=['+', '-', '*', '/']

def each_operations(ary)
  x,y, = ary

  def unexpanded?(a)
    a.class == Array and a.size != 3
  end

  if unexpanded? x
    each_operations(x) do |a|
      if unexpanded? y
        each_operations(y) do |b|
          OPS.each do |op|
            yield([op, a, b])
          end
        end
      else
          OPS.each do |op|
            yield([op, a, y])
          end
      end
    end
  else
      if unexpanded? y
        each_operations(y) do |b|
          OPS.each do |op|
            yield([op, x, b])
          end
        end
      else
          OPS.each do |op|
            yield([op, x, y])
          end
      end
  end
end

=begin
== eval(expr) => [value, string]
  each_operation が返す形式を受け取って、
  値を評価します。
  評価値と式の表現（文字列）の組を返します。
=end
def eval(expr)
  op, x, y, = expr

  def v_and_s(a)
    if a.class == Array
      eval(a)
    else
      [a, a.to_s]
    end
  end

  x_val, x_str = v_and_s(x)
  y_val, y_str = v_and_s(y)

  ret_val = nil
  if x_val and y_val
    case(op)
    when '+'
      ret_val = x_val + y_val
    when '-'
      ret_val = x_val - y_val
    when '*'
      ret_val = x_val * y_val
    when '/'
      if y_val != 0
        ret_val = x_val / y_val
      else
        ret_val = nil
      end
    end
  end

  ret_str = "(#{x_str} #{op} #{y_str})"

  [ret_val, ret_str]
end

# ======== main ========

target = ARGV.shift.to_i

n = []
ARGV.each do |a|
  n << Rational(a.to_i, 1)
end

hash = {}

each_tree_permutation(n) do |tree|
  each_operations(tree) do |expr|
    v,s = eval(expr)
    if v == target
      puts s unless hash[s]
      hash[s] = true
    end
  end
end

書いてみて: