回文の発掘 in Clojure

問題と他の方の解答

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

私の解答 in Clojure

ord15ref.clj

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

(defn solve [s]
  (apply max 0
    (map
      (fn [[h & r]]
        (let [rs (drop-while (partial not= h) (reverse r))]
          (if (empty? rs) 1 (+ 2 (solve (rest rs))))))
      (take-while seq (iterate rest 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"))

テスト実行結果

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

Testing ord15ref

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

解説

(defn solve [s]
  (apply max 0
    (map
      (fn [[h & r]]
        (let [rs (drop-while (partial not= h) (reverse r))]
          (if (empty? rs) 1 (+ 2 (solve (rest rs))))))
      (take-while seq (iterate rest s)))))

(iterate rest s) で, 文字列 s から, 「元の文字列 s, 先頭一文字を削った文字のシーケンス (rest s), 先頭二文字を削った文字のシーケンス (rest (rest s)), ...」というシーケンスを作ります.
この時点では, 末尾に空のリストが無限に続きます.
(take-while seq ...) で, 1つ以上の要素を持つシーケンスのみ取り出します.

user=> (take-while seq (iterate rest "believer"))
("believer" (\e \l \i \e \v \e \r) (\l \i \e \v \e \r) (\i \e \v \e \r) (\e \v \e \r) (\v \e \r) (\e \r) (\r))

これら全てについて下記を考慮します.

(fn [[h & r]] ...) で, シーケンスを最初の要素 h と最初の要素を除いたシーケンス r に分けて受け取ります.

user=> ((fn [[h & r]] [h r]) "iever")
[\i (\e \v \e \r)]

(drop-while (partial not= h) (reverse r)) で, 最初の要素を除いたシーケンス r を後ろから見て, 最初の要素 h と同じ文字が現れるところまで要素を除きます.

user=> (drop-while (partial not= \i) (reverse "ever"))
()
user=> (drop-while (partial not= \e) (reverse "ver"))
(\e \v)

(let [rs ...] ...): これを rs とします.

(if (empty? rs) 1 ...): シーケンス rs が空の場合, 先頭はこのままで, この文字列の末尾からいくつか要素を削除して作成することのできる回文の長さは, 先頭の要素だけを残した場合の 1 です.

そうでない場合,
(+ 2 (solve (rest rs))): 先頭の要素と一致した文字を削除した残りの文字列についての最長の回文の長さ (測定するために再度 rs を reverse する必要はありません) に 2 を足したものが, 先頭からは文字を削除しなかった場合についての最長の回文の長さです.

(map 上記の測定 先頭から何文字か削除した全ての場合の文字列): で, 先頭から何文字か削除した全ての場合の, 最長の回文の長さがリストで得られます.

(apply max 0 ...) 再帰的に呼ばれた場合に, 文字列が空でも機能するよう, 番兵として 0 を設定した上で, 全ての場合の最大値を求めます.