「回文基数」をErlangとRubyでやってみました。他の皆様による実装は 第17回オフラインリアルタイムどう書くの参考問題 から辿れます。
コンパクトに書けたので、アルゴリズムの説明用にRubyで書いたものを先に載せます。
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
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でも再帰で書いてしまいます (^^;)