回文基数 in Clojure

問題と他の方の解答

問題: 回文基数 〜 横へな 2014.1.10 参考問題
他の方の解答: 第17回オフラインリアルタイムどう書くの参考問題

私の解答 in Clojure

(ns ord17ref
  (:require [clojure.test :refer (deftest are run-tests)]))

(defn- columns [b]
  (fn f [i]
    (if (zero? i) '()
      (cons (mod i b) (f (quot i b))))))

(defn solve [s]
  (let [i (read-string s)
        bs (for [b (range 2 i)
                 :let [cs ((columns b) i)]
                 :when (= cs (reverse cs))]
               b)]
    (if (empty? bs) "-" (apply str (interpose "," bs)))))

(deftest solve-test
  (are [i o] (= (solve i) o)
    "17301" "5,38,100,218,236,5766,17300"    
    "2" "-"    
    "1" "-"    
    "3" "2"    
    "4" "3"    
    "5" "2,4"    
    "6" "5"    
    "10" "3,4,9"    
    "101" "10,100"    
    "1001" "10,25,76,90,142,1000"    
    "10001" "10,24,30,42,80,100,136,10000"    
    "1212" "22,100,201,302,403,605,1211"    
    "123412" "62,100,205,215,30852,61705,123411"    
    "5179" "5178"    
    "4919" "4918"    
    "5791" "5790"    
    "5498" "2748,5497"    
    "453" "150,452"    
    "134" "66,133"    
    "8489" "27,652,8488"    
    "1234" "22,616,1233"    
    "5497" "41,238,5496"    
    "4763" "19,35,432,4762"    
    "3974" "17,27,1986,3973"    
    "3521" "44,55,502,3520"    
    "5513" "20,38,53,148,5512"    
    "8042" "23,29,60,4020,8041"    
    "7442" "37,60,121,3720,7441"    
    "4857" "25,1618,4856"    
    "22843" "49,69,91,141,430,22842"    
    "194823" "84,121,21646,64940,194822"    
    "435697" "160,169,235,626,1822,435696"    
    "142" "3,7,70,141"    
    "886" "5,14,442,885"    
    "3102" "7,65,93,140,281,516,1033,1550,3101"    
    "17326" "11,28,99,105,8662,17325"    
    "32982" "13,72,238,477,716,1433,5496,10993,16490,32981"    
    "36" "5,8,11,17,35"    
    "37" "6,36"    
    "251" "8,250"    
    "252" "5,10,17,20,27,35,41,62,83,125,251"    
    "253" "12,14,22,252"    
    "6643" "2,3,9,81,90,510,948,6642"    
    "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"    
    "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"))

テスト実行結果

Clojure 1.6.0
user=> (ns ord17ref)
nil
ord17ref=> (require 'ord17ref :reload-all)
nil
ord17ref=> (run-tests)

Testing ord17ref

Ran 1 tests containing 45 assertions.
0 failures, 0 errors.
{:type :summary, :fail 0, :error 0, :pass 45, :test 1}

解説

(defn- columns [b]
  (fn f [i]
    (if (zero? i) '()
      (cons (mod i b) (f (quot i b))))))

columns は, 基数 b を与えると「整数 i を与えると, i を基数 b で表した場合の, 各桁の数値をシーケンスで返す関数」を返します.

関数 f は, 数値 i を与えると「i を b で割った商を, 自身 f に与えて得られるシーケンス」の先頭に「i を b で割った余り」を付加します. i が 0 の時は空リストを返します.
これで基数 b の場合の各桁を下位から並べたシーケンスが得られます.

利用例です.

ord17ref=> ((columns 2) 10)
(0 1 0 1)
ord17ref=> ((columns 3) 10)
(1 0 1)
ord17ref=> ((columns 4) 10)
(2 2)
ord17ref=> ((columns 5) 10)
(0 2)

---

(defn solve [s]
  (let [i (read-string s)
        bs (for [b (range 2 i)
                 :let [cs ((columns b) i)]
                 :when (= cs (reverse cs))]
               b)]
    (if (empty? bs) "-" (apply str (interpose "," bs)))))

文字列で与えられた数字列 s を (read-string ...) で数値にし, i とします.
基数 b を 2 から i - 1 の範囲で変化させ, その場合の i の各桁を下位から並べたシーケンスを cs とします.
cs と (reverse cs) が一致する場合は, 基数 b を抽出します.
抽出した基数のシーケンスを bs とします.
bs が空なら "-" を返し, そうでなければ, (interpose "," ...) で "," を間に挟んで,
(apply str ...) で文字列化します.

各部分は以下の例のように機能します.

ord17ref=> (read-string "17301")
17301

ord17ref=> (for [b (range 2 17301) :let [cs ((columns b) 17301)] :when (= cs (reverse cs))] b)
(5 38 100 218 236 5766 17300)

ord17ref=> (interpose "," '(5 38 100 218 236 5766 17300))
(5 "," 38 "," 100 "," 218 "," 236 "," 5766 "," 17300)

ord17ref=> (apply str '(5 "," 38 "," 100 "," 218 "," 236 "," 5766 "," 17300))
"5,38,100,218,236,5766,17300"