正規表現でアッカーマン関数

速度とかどうでもいいから，とにかくアッカーマン関数が展開される様子をただなんとなく見たくなったのです。

ackermann_function.rb

# usage: ruby ackermann_function Ack(3,1)
ack = ARGV[0].dup
begin
  puts ack
end while ack.sub!(/Ack\((\d+),(\d+)\)/) do
  m, n = $1.to_i, $2.to_i
  if m == 0
    "#{n + 1}"
  elsif n == 0
    "Ack(#{m - 1},1)"
  else
    "Ack(#{m - 1},Ack(#{m},#{n - 1}))"
  end
end

ruby ackermann_function.rb Ack(3,1)

Ack(3,1)
Ack(2,Ack(3,0))
Ack(2,Ack(2,1))
Ack(2,Ack(1,Ack(2,0)))
Ack(2,Ack(1,Ack(1,1)))
Ack(2,Ack(1,Ack(0,Ack(1,0))))
Ack(2,Ack(1,Ack(0,Ack(0,1))))
Ack(2,Ack(1,Ack(0,2)))
Ack(2,Ack(1,3))
Ack(2,Ack(0,Ack(1,2)))
Ack(2,Ack(0,Ack(0,Ack(1,1))))
Ack(2,Ack(0,Ack(0,Ack(0,Ack(1,0)))))
Ack(2,Ack(0,Ack(0,Ack(0,Ack(0,1)))))
Ack(2,Ack(0,Ack(0,Ack(0,2))))
Ack(2,Ack(0,Ack(0,3)))
Ack(2,Ack(0,4))
Ack(2,5)
Ack(1,Ack(2,4))
Ack(1,Ack(1,Ack(2,3)))
Ack(1,Ack(1,Ack(1,Ack(2,2))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(2,1)))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,Ack(2,0))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,1))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(1,0)))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,1)))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,2))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(1,3)))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(1,2))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(1,1)))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(1,0))))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,1))))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,2)))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,3))))))
Ack(1,Ack(1,Ack(1,Ack(1,Ack(0,4)))))
Ack(1,Ack(1,Ack(1,Ack(1,5))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(1,4)))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(1,3))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(1,2)))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,1))))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,0)))))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,1)))))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,2))))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,3)))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,4))))))
Ack(1,Ack(1,Ack(1,Ack(0,Ack(0,5)))))
Ack(1,Ack(1,Ack(1,Ack(0,6))))
Ack(1,Ack(1,Ack(1,7)))
Ack(1,Ack(1,Ack(0,Ack(1,6))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(1,5)))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(1,4))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,3)))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,2))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,1)))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,0))))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,1))))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,2)))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,3))))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,4)))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,5))))))
Ack(1,Ack(1,Ack(0,Ack(0,Ack(0,6)))))
Ack(1,Ack(1,Ack(0,Ack(0,7))))
Ack(1,Ack(1,Ack(0,8)))
Ack(1,Ack(1,9))
Ack(1,Ack(0,Ack(1,8)))
Ack(1,Ack(0,Ack(0,Ack(1,7))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(1,6)))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,5))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,4)))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,3))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,2)))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,1))))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,0)))))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,1)))))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,2))))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,3)))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,4))))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,5)))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,6))))))
Ack(1,Ack(0,Ack(0,Ack(0,Ack(0,7)))))
Ack(1,Ack(0,Ack(0,Ack(0,8))))
Ack(1,Ack(0,Ack(0,9)))
Ack(1,Ack(0,10))
Ack(1,11)
Ack(0,Ack(1,10))
Ack(0,Ack(0,Ack(1,9)))
Ack(0,Ack(0,Ack(0,Ack(1,8))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,7)))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,6))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,5)))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,4))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,3)))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,2))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,1)))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(1,0))))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,1))))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,2)))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,3))))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,4)))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,5))))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,6)))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,7))))))
Ack(0,Ack(0,Ack(0,Ack(0,Ack(0,8)))))
Ack(0,Ack(0,Ack(0,Ack(0,9))))
Ack(0,Ack(0,Ack(0,10)))
Ack(0,Ack(0,11))
Ack(0,12)
13

間違っても，

ruby ackermann_function.rb Ack(10,10) > output.txt

とかしないようにしましょう。