コマ大数学科の問題をRubyとScalaで解いてみる

Scalaのような関数型言語は、数学的な発想で作られているわけで、
数学の問題を解くのは得意だよね・・・ということで、
勉強ついでに簡単なコードを書いてみました...φ(･ω･｀)

問題

コマ大数学科 2011/2/28放送分より

ある数字にそれを逆に並べた数字を足すという計算を、
回文数（上から読んでも下から読んでも同じ数）になるまで繰り返すとき、
もっとも計算回数を要する二桁の数を答えなさい

例：ab+ba=123の場合、123+321=444で回文数なので、2回となる

これをコードを使って解くならば、10〜99について、
問題の計算を繰り返すのが早いはず

Rubyの場合

まず手慣れたRubyでコーディングし、それをScalaで書き直す、
という予定なので、あえて再帰を使ってます

def reverse_num(num)
  num.to_s.reverse.to_i
end

def reverse_sum(num)
  num + reverse_num(num)
end

def palindrome?(num)
  num == reverse_num(num) ? true : false
end

def execute(ind, num)
  r = reverse_sum(num)
  palindrome?(r) ? ind : execute(ind+1, r)
end

rsl = (10..99).map{|n| [n, execute(1, n)]}
max = rsl.map(&:last).max
rsl.select{|r| r.last == max}.each{|r| puts "num:#{r.first} count:#{r.last}"}

# 実行結果
# num:89 count:24
# num:98 count:24

Scalaの場合

関数型風に書いたRubyのコードをほぼそのまま持ってくればOK
ただ、数値が大きくなるので、IntではなくBigIntにしないと通りません
（Rubyはこの変換を暗黙的にやってくれる）

object Palindrome {
  def reverseNum(num: BigInt): BigInt = BigInt(num.toString.reverse)
  def reverseSum(num: BigInt): BigInt = num + reverseNum(num)
  def isPalindrome(num: BigInt): Boolean = num == reverseNum(num)

  def execute(ind: Int, num: BigInt): Int = {
    val r = reverseSum(num)
    if (isPalindrome(r)) ind else execute(ind + 1, r)
  }

  def main(args: Array[String]): Unit = {
    val rsl = (10 to 99).map(n => (n, execute(1, n)))
    val max = rsl.map(_._2).max
    rsl.filter(_._2 == max).foreach(r => printf("num:%d count:%d\n", r._1, r._2))
  }
}

// 実行結果
// num:89 count:24
// num:98 count:24

やってることはほぼRubyと同一なのですが、
（数学的な意味での）関数の定義はこちらの方が厳格でシンプルに見えます
（改行の有無程度ではありますが・・・）

このように、Rubyの関数型風の記述に慣れておくと、
Scalaで書くのは結構楽です(｀･ω･´) ｂ
逆に、Java屋さんの方が苦労しそうですね・・・

＜おまけ＞
参考までに、正しい（？）解き方(´･ω･)っ

それぞれの桁の数値をa,bとしたとき、
元の数は10a+b、逆にした数は10b+aであることから・・・

 10a+b+10b+a = 11(a+b)

・・・となる
このため、a+b<10だと一度の計算で回文数になってしまう

1<=a<=9、0<=b<=9であるから、10<=a+b<=18となり、
各場合について計算していけばよい

ただし、計算したとき桁が繰り上がるほど回数が多いと推測できるため、
a+b=18 => 17 => 16...の順で計算していくとわかりやすい

すると、a+b=16 or 18の時に6回の計算で回文数になるが、
a+b=17(89 or 98)の時には6回でも回文数にならない
よって89と98が最大となる
（24回の計算が必要になるため、手計算ではほぼ不可能）