回文の発掘 in Clojure

問題と他の方の解答

• 問題
  • 回文の発掘 〜 横へな 2013.11.1 参考問題
• 他の方の解答
  • 第15回オフラインリアルタイムどう書くの参考問題
• 他の方の解答 in Clojure
  • 回文の発掘 in Clojure

私の解答 in Clojure

Scala で動くのを確認してから Clojure で書き直しました．

kaibun.clj

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

(defn solve
  [^String s]
  (letfn [(f [i j]
            (cond (> i j) 0
                  (= i j) 1
                  :else (loop [acc 0 k i]
                          (if (= k j)
                            acc
                            (recur (max acc (g k j)) (inc k))))))
          (g [i j]
            (let [k (.lastIndexOf s (int (nth s i)) (int j))]
              (if (= i k)
                1
                (+ 2 (f (inc i) (dec k))))))]
    (f 0 (dec (count s)))))

(deftest solve-test
  (are [i o] (= (str (solve i)) o)
       "I_believe_you_can_solve" "9"
       "a" "1"
       "aa" "2"
       "aaa" "3"
       "ab" "1"
       "aabb" "2"
       "ABBA" "4"
       "Abba" "2"
       "1234567890" "1"
       "1234567890987654321" "19"
       "abcdcba" "7"
       "0a1b2c3d4c5b6a7" "7"
       "abcdcba0123210" "7"
       "abcdcba_123210" "7"
       "_bcdcba0123210" "7"
       "abcddcba0123210" "8"
       "abcdcba01233210" "8"
       "a0bc1dc2ba3210a" "9"
       "a0bc1ddc2ba3210" "8"
       "3a0bc1ddc2ba3210" "10"
       "11oooo1111o1oo1o111ooooooooooo" "20"
       "11o1111o1111oo11ooo11111ooo1oo" "20"
       "111111oo11o111ooo1o1ooo11ooo1o" "21"
       "11o1o1o11oo11o11oo111o1o1o11oo" "27"
       "oo111o1o11o1oo1ooo11o1o11o1o1o" "27"
       "1o1oo11111o1o1oo1o1o1111oo1o1o" "28"
       "QQooooQooooQQyQoyQQQyyyyQQoyoy" "15"
       "oQoooQooooQyoyQoyoyyyQQyQQQQoQ" "16"
       "yyyyyooyQyyyoyyQyyooyQoQoQQoQy" "17"
       "yyQoyQoyyQyQQoyooooyyQQyQyooQy" "24"
       "oQQooQoQyQQoyoQQoQyQyQyQoQoooo" "24"
       "oQQyQQyyQyQQoooyQQyyyQQQyyQQoy" "25"
       "WAk9iHI4jVDlStyudwTNqE138kwan2" "3"
       "c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7" "3"
       "CAbYcW5VqHjzFdIkH_61PM0TsyRuie" "3"
       "jInQnUvSayrJTsQWujovbbqW0STvoj" "10"
       "iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG" "11"
       "ROgYUOu6er_DA7nB6UGquO1GUHC62R" "11"
       "Oh_be_a_fine_girl_kiss_me" "9"
       "8086_6502_6809_Z80" "11"
       "xcode_visualstudio_eclipse" "11"
       "word_excel_powerpoint_outlook" "9"
       "abcdefghijklmnopqrstuvwxyz0123" "1"))

テスト実行結果

user> #<Namespace kaibun>
kaibun> (time (run-tests))

Testing kaibun

Ran 1 tests containing 43 assertions.
0 failures, 0 errors.
"Elapsed time: 97.209 msecs"
{:type :summary, :fail 0, :error 0, :pass 43, :test 1}

解説

letfn で相互再帰を書いてみたかっただけのコードです．関数 solve について，

• 関数 f
  • 区間 [i, j] で最長の回文の長さを返す関数
• 関数 g
  • 先頭から撤去される文字数が k の回文について最長のものの長さを返す関数

よって，入力文字列を s とすると (f 0 (dec (count s))) が解答となります．

無駄も多く，効率的なコードとは言えませんが，テストケースが比較的小さいのと，Clojure が速いのとで，テストは一瞬で終ります．

再帰でなければ Clojure 関数のメモ化は簡単なのですが，再帰の場合簡単にメモ化できない Clojure というのがありますので．

まとめ

@kohyama の解答のほうが Clojure らしさにあふれると思いますので，
Clojurian はそちらを参考にしたほうがよいです．