回文の発掘 in Clojure
問題と他の方の解答
- 問題
- 他の方の解答
- 他の方の解答 in Clojure
私の解答 in Clojure
Scala で動くのを確認してから Clojure で書き直しました.
(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 はそちらを参考にしたほうがよいです.
Author And Source
この問題について(回文の発掘 in Clojure), 我々は、より多くの情報をここで見つけました https://qiita.com/tnoda_/items/3cc74cbb77312e8a143f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .