「回文基数」をErlangとRubyで(横へな17参考)

「[回文基数](http://nabetani.sakura.ne.jp/hena/ord17scheherazade/)」をErlangとRubyでやってみました。他の皆様による実装は [第17回オフラインリアルタイムどう書くの参考問題](http://qiita.com/Nabetani/items/dabe8ec57e0313229552) から辿れます。

コンパクトに書けたので、アルゴリズムの説明用にRubyで書いたものを先に載せます。

```rb:sheh.rb
def solve(data)
  x = data.to_i
  x < 3 ? "-" : (2...x).select { |b| x == rev(x, b, 0) } * ","
end

def rev(x, base, acc)
  x == 0 ? acc : rev(x.div(base), base, acc * base + (x % base))
end
```

```erlang:sheh.erl
-module(sheh).
-compile(export_all).

solve(Data) -> bases(list_to_integer(Data)).

bases(1) -> "-";
bases(X) -> to_s(lists:filter(fun(Base) ->
  X =:= rev(X, Base, 0) end, lists:seq(2, X - 1))).

to_s([]) -> "-";
to_s(Bs) -> string:join([integer_to_list(X) || X <- Bs], ",").

rev(0, _, Acc) -> Acc;
rev(X, Base, Acc) -> rev(X div Base, Base, Acc * Base + (X rem Base)).

test(Data, Expected) -> test(Data, solve(Data), Expected).
test(Data, Result, Expected) -> io:fwrite("~s: ~s -> ~s~n",
  [case Result =:= Expected of true -> ok; false -> ng end, Data, Result]).

tests() ->
  test("17301", "5,38,100,218,236,5766,17300"), %0
  test("2", "-"), %1
  test("1", "-"), %2
  test("3", "2"), %3
  test("4", "3"), %4
  test("5", "2,4"), %5
  test("6", "5"), %6
  test("10", "3,4,9"), %7
  test("101", "10,100"), %8
  test("1001", "10,25,76,90,142,1000"), %9
  test("10001", "10,24,30,42,80,100,136,10000"), %10
  test("1212", "22,100,201,302,403,605,1211"), %11
  test("123412", "62,100,205,215,30852,61705,123411"), %12
  test("5179", "5178"), %13
  test("4919", "4918"), %14
  test("5791", "5790"), %15
  test("5498", "2748,5497"), %16
  test("453", "150,452"), %17
  test("134", "66,133"), %18
  test("8489", "27,652,8488"), %19
  test("1234", "22,616,1233"), %20
  test("5497", "41,238,5496"), %21
  test("4763", "19,35,432,4762"), %22
  test("3974", "17,27,1986,3973"), %23
  test("3521", "44,55,502,3520"), %24
  test("5513", "20,38,53,148,5512"), %25
  test("8042", "23,29,60,4020,8041"), %26
  test("7442", "37,60,121,3720,7441"), %27
  test("4857", "25,1618,4856"), %28
  test("22843", "49,69,91,141,430,22842"), %29
  test("194823", "84,121,21646,64940,194822"), %30
  test("435697", "160,169,235,626,1822,435696"), %31
  test("142", "3,7,70,141"), %32
  test("886", "5,14,442,885"), %33
  test("3102", "7,65,93,140,281,516,1033,1550,3101"), %34
  test("17326", "11,28,99,105,8662,17325"), %35
  test("32982", "13,72,238,477,716,1433,5496,10993,16490,32981"), %36
  test("36", "5,8,11,17,35"), %37
  test("37", "6,36"), %38
  test("251", "8,250"), %39
  test("252", "5,10,17,20,27,35,41,62,83,125,251"), %40
  test("253", "12,14,22,252"), %41
  test("6643", "2,3,9,81,90,510,948,6642"), %42
  test("5040", "71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039"), %43
  test("9240", "23,38,62,104,109,119,131,139,153,164,167,209,219,230,263,279,307,329,384,419,439,461,615,659,769,839,923,1154,1319,1539,1847,2309,3079,4619,9239"). %44
```

Rubyの方はテストケースを割愛しています。速度については考慮していません。

rev関数はbase進数にした時の桁を逆転した値を返します。3進数で112になる数なら211 (を10進数に戻した数) を返します。solve関数の中で元の値とrevしたものを比較し、同じなら「base進表記で回文になっている」と判定しています。

普段からErlangで書きすぎているので、ついRubyでも再帰で書いてしまいます (^^;)