非決定計算

Ruby 30分プログラム

30分プログラム、その43。id:Gemmaさん出題によるラグランジェの4平方定理。id:zyxwv:20070531に対抗してみる。

ある自然数nが与えられた場合、
n = a^2 + b^2 + c^2+d^2
という等式を満す非負の整数a,b,c,dをすべて求める問題。(微妙にオリジナルと変えました)

まず、callccで非決定計算を行なえるようにしてから、その上で問題を解いている。

class Amb
  def initialize
    @paths = []
  end
 
  def choice(*choices)
    if choices.empty?
      self.fail
    else
      callcc do|cc|
        @paths.push(*choices.map do|choice| 
          lambda{ cc.call choice }
        end)
        self.fail
      end
    end
  end
 
  def fail
    if @paths.empty? then
      throw :last
    else
      cc = @paths.pop
      cc.call
    end
  end
end
 
def lagrange(amb,n)
  seed = (0..Math.sqrt(n).floor).map{|x| x*x}
  a = amb.choice(*seed)
  b = amb.choice(*seed.select{|x| x <= a})
  c = amb.choice(*seed.select{|x| x <= b})
  d = amb.choice(*seed.select{|x| x <= c})
  if a + b + c + d == n then
    [a,b,c,d]
  else
    amb.fail
  end
end
 
def all_lagrange(x)
  amb = Amb.new
  result = []
  catch(:last){
    result.push lagrange(amb,x)
    loop {
      amb.fail
    }
  }
  result
end