TSabc 発言

> お題：
>     任意の値の異なる１桁の数値４つが与えられたとき、
>     四則演算(＋、−、×、÷）を使用して計算結果を
>     １０にする。

初の Ruby での投稿です．

1. 和差積 で交換法則や，結合法則で同じになる式は１つだけ含める．
a - b + c = a + c - b, a * (b * c) = a * b * c

2. 和に対する負の符号は展開する
c - (a - b) = c + b - a

1 と 2 の 条件をつけないと () のつけ方でかなり沢山の表現ができてしまいます． 
a + b + c + d = (((a + b) + c) + d) = ... 

3. 積と分数の各因子は評価が正になるように符号を調整する．
(8-2)*(1-4) = -(8-2)*(4-1), (8-2)/(1-4) = -(8-2)/(4-1)

4. 分数と繁分数は各因子の結果を正になるように符号を調整する以外の調整はしない
例えば 2/(8/4) と (2*4)/8, (8/2)/4 と 8/(2*4) は異なる表現とする

数式表現を Object にしたので，多少の汎用性がありますが，
Class 設計で力尽きたので 10 になる数式表現を探すループは
無茶苦茶汚いです．

# 昔，このやり方で
# 多変数多項式の因数分解プログラムを
# つくろうとしたのです．

計算結果です．
デバッグはあまりやっていないので，
過不足があるかもしれません．

==ここから==
4+(8-2)/1
1*(8+4/2)
8+1/(2/4)
2*(8+1-4)
8+4*(1/2)
-2+(8+4)/1
8-2+4/1
(8+4-2)/1
8*1+4/2
8+1*(4-2)
8+4/(2*1)
4-2+8*1
8+(4/1)/2
8+4-2*1
8+1*(4/2)
8-2+4*1
-4+2*(8-1)
-2+1*(8+4)
4+1*(8-2)
(8+4/2)/1
8+(4*1)/2
8+4/(2/1)
8+(4/2)/1
1*(8+4-2)
8+(4-2)/1
4/2+8/1
4-2+8/1
8+4-2/1
==ここまで==

==スクリプト==
#! /usr/bin/ruby
v = [1, 2, 4, 8]
$goal = 10

require 'mathn'

class Expr
  include Comparable

  def sign
    @sign
  end

  def value
    @value
  end

  def neg
    @sign *= -1
    @value *= -1
    self
  end

  def +(x)
    if x.is_a?(Plus)
      x + self
    else
      Plus.new(x, self)
    end
  end

  def -(x)
    self + -x
  end

  def *(x)
    if x.is_a?(Times)
      x * self
    else
      Times.new(x, self)
    end
  end

  def /(x)
    Frac.new(self, x)
  end

  def hash
    to_s.hash
  end

  def eql?(a)
    self == a
  end

end

class Num < Expr

  def initialize(a)
    @num = a.abs
    @sign = a <=> 0
    @value = a
  end

  def num
    @num
  end

  def abs
    Num.new(@num)
  end

  def <=>(a)
    if a.is_a?(Num)
      r = @sign <=> a.sign
      r == 0 ? @num <=> a.num : r
    else
      1
    end
  end

  def to_s
    @sign >= 0 ? @num.to_s : '-' + @num.to_s
  end

  def to_s_in_plus
    (@sign >= 0 ? '+' : '-') + @num.to_s
  end

  def to_s_in_times
    @num.to_s
  end

  def to_s_in_frac
    @num.to_s
  end

  def -@
    Num.new(- value)
  end

end

class Plus < Expr

  def initialize(*a)
    @value = 0
    @sign = 1
    a.each { |x| @value += x.value }
    if @value < 0
      a = a.collect{|x| -x}
      @sign = -1
    end
    @arg = a.sort.reverse
  end

  def arg
    @arg
  end

  def abs
    self
  end

  def <=>(a)
    case a
    when Num
      -1
    when Plus
      @arg <=> a.arg
    else
      1
    end
  end

  def to_s
    @arg[0].to_s + @arg[1..-1].collect{|x| x.to_s_in_plus}.join
  end

  def to_s_in_times
    '(' + to_s + ')'
  end

  def to_s_in_frac
    '(' + to_s + ')'
  end

  def +(x)
    if x.is_a?(Plus)
      Plus.new(*(x.arg + @arg))
    else
      Plus.new(x, *@arg)
    end
  end

  def -@
    Plus.new(*(@arg.collect{|x| -x}))
  end

end

class Times < Expr

  def initialize(*a)
    @arg = a
    @value = 1
    @sign = 1
    @arg.each { |x| @value *= x.value; @sign *= x.sign; x = x.abs }
    @arg = @arg.sort.reverse
  end

  def arg
    @arg
  end

  def abs
    Times.new(*@arg)
  end

  def <=>(a)
    case a
    when Num, Plus
      -1
    when Times
      r = @sign <=> a.sign
      r == 0 ? @arg <=> a.arg : r
    else
      1
    end
  end

  def to_s
    @arg.collect{|x| x.to_s_in_times}.join('*')
  end

  def to_s_in_plus
    (@sign > 0 ? '+' : '-') + to_s
  end

  def to_s_in_frac
    '(' + to_s + ')'
  end

  def -@
    Times.new(*@arg).neg
  end

  def *(x)
    if x.is_a?(Times)
      r = Times.new(*(x.arg + @arg))
    else
      r = Times.new(x, *@arg)
    end
    sign < 0 ? r.neg : r
  end

end

class Frac < Expr

  def initialize(a, b)
    @num = a.abs
    @den = b.abs
    @sign = a.sign * b.sign
    @value = a.value / b.value
  end

  def den
    @den
  end

  def num
    @num
  end

  def abs
    Frac.new(@num, @den)
  end

  def <=>(a)
    if a.is_a?(Frac)
      r = @den <=> a.den
      r == 0 ? @num <=> a.num : r
    else
      -1
    end
  end

  def to_s
    (@sign < 0 ? '-' : '') + @num.to_s_in_frac + '/' + @den.to_s_in_frac
  end

  def to_s_in_plus
    (@sign > 0 ? '+' : '-') + @num.to_s_in_frac + '/' + @den.to_s_in_frac
  end

  def to_s_in_times
    '(' + to_s + ')'
  end

  def to_s_in_frac
    '(' + to_s + ')'
  end

  def -@
    Frac.new(@num, @den).neg
  end

end

v = v.collect {|x| Num.new(x)}

exprs = [v]
$fin = Hash.new(0)
$\ = "\n"

def dojob(exprs)
  ret = []
  exprs.each do |v|
    if (s = v.size) > 1
      for i in 0..s-2
	for j in i+1..s-1
	  u = v.clone
	  y = u.delete_at(j)
	  x = u.delete_at(i)
	  w = u.clone
	  w.push(x + y)
	  ret.push(w)
 	  w = u.clone
	  w.push(x - y)
	  ret.push(w)
	  w = u.clone
	  w.push(y - x)
	  ret.push(w)
	  w = u.clone
	  w.push(x * y)
	  ret.push(w)
	  if y.value != 0
	    w = u.clone
	    w.push(x / y)
	    ret.push(w)
	  end
	  if x.value != 0
	    w = u.clone
	    w.push(y / x)
	    ret.push(w)
	  end
	end
      end
    else
      if v[0].value == $goal
	$fin[v[0]] = 1
      end
    end
  end
  unless ret.empty?
    dojob(ret)
  end
end

dojob(exprs)
$fin.each_key {|x| print x}
exit

==ここまで==
-----------------------------
	廣島 勉
	(tsutomu@...)