第17回オフラインリアルタイムどう書くの参考問題 with ruby

遅くなりましたが、第17回オフラインリアルタイムどう書くの参考問題「回文基数」
http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
の実装例。

rubyで。

他の言語などの解答例は
http://qiita.com/Nabetani/items/dabe8ec57e0313229552
から辿れます。

現在は第18回
http://atnd.org/events/47025
の参加者募集中。2月1日、横浜です。

で。

# tested with ruby 2.1.0

# 二桁の場合
def solve2(n)
  # 表示する数で回す
  (1..((n-1)**0.5).floor).select{ |d|
    b = (n-d)/d
    n==(b+1)*d && d<b
  }.map{ |d|
    (n-d)/d
  }
end

def to_digits( n, b )
  n<b ? [n] : to_digits( n/b, b )+[n%b]
end

# 3桁以上の場合
def solve_many(n)
  # 基数で回す
  (2..(n**0.5).floor).select{ |b|
    dig=to_digits( n, b )
    dig==dig.reverse
  }
end

def solve(s)
  r=solve2(s.to_i)+solve_many(s.to_i)
  r.empty? ? "-" : r.sort.join(",")
end

$stdout.sync=true

DATA.each do |line|
  num, src, expected = line.split( /\s+/ )
  actual = solve( src )
  ok = actual==expected;
  puts "%s %s->%s ( %s )" % [ ok ? "ok" : "***NG***", src, actual, expected ]
end

__END__
0 17301 5,38,100,218,236,5766,17300
1 2 -
2 1 -
3 3 2
4 4 3
5 5 2,4
6 6 5

いつも通り、テストデータの大半は省略。

で。

例えば 10000 の場合。
三桁以上になる場合は 基数が 1〜100。その基数で回文数になるかどうか調べる。
二桁の場合、逆に、回文数になった後の表現形式は「1・1」〜「99・99」の約百通りのどれかなので、これらを調べて、そのような回文数になるような基数があるかどうか調べる。
そうすると、計算量のオーダーが O(n**0.5) ぐらいになる。

計算量を気にしなければ、もう少し短く書ける。