4clojure Problem 150の回文数パズルが解決策を投稿したときにタイムアウトになる理由がわかりません。私のローカル REPL では、すべてがかなり高速です。このソリューションを見つけて動作しますが、パフォーマンスは私のソリューションと同様です。コードが多いことはわかっていますが、問題は簡単ではありません。コメントがアイデアを得るのに役立つことを願っています。
(defn palindrome [n]
(let [ ;; given a number return a string
digits (fn [^String x] (String/valueOf x))
;; given a string return the length
digits-count (fn [^String x] ( .length x) )
;; given an input sequence of digits, return a number. e.g. (seqstr (seq "1234")) => 1234
seqstr #(Long/parseLong (apply str %))
;; true when the given string has an even number of digits:
even-digits? #(even? (digits-count %))
;; return the left middle of a string. For even-digit strings returns the 'real' left part, for odd-digit strings returns one digit more.
;; e.g. (left-middle "12345678") => "1234"
;; e.g. (left-middle "1234567") => "1234"
left-middle #(if (even-digits? %)
(subs % 0 (quot (digits-count % ) 2) )
(subs % 0 (inc (quot (digits-count % ) 2))))
;; mirror a given number.
;; (mirror [1234 :even] ) => 12344321
;; (mirror [1234 :odd] ) => 1234321
mirror (fn [[num dig]]
(let [ d (seq (digits num))]
(if (= :even dig) (seqstr (concat d (reverse d)))
(seqstr (concat d (drop 1 (reverse d)))))))
;; initialize loop given a string. Returns a vector given a starting point.
;; (init "12345678") => [1234 :even 10000]
;; (init "1234567" ) => [1234 :odd 10000]
;; the first item in the vector contains the number we start the iteration with.
;; the flag indicates whether we should mirror it to an even or odd-digit number
;; the goal (power of 10) indicates when the next switch between odd/even-digit numbers will occur
init #(let [s (left-middle %)]
(vector (Long/parseLong s)
(if (even-digits? %) :even :odd)
(long (Math/pow 10 (digits-count s)))))
;; given a vector (see structure above), determine the next step
;;(next [999 :even 1000] ) => [1000 :odd 10000] . When finished mirroring even-digit numbers of length 3, continue with mirroring 4-digit odd-digit numbers
;;(next [9999 :odd 10000] ) => [1000 :even 10000]. When finished mirroring odd-digit numbers of length 4, continue with mirroring 4-digit even-digit numbers
;;(next [123 :odd 1000]) => [124 :odd 1000]. The normal case.
next (fn [[num even goal]]
(let [m (inc num)]
(if (= m goal)
(if (= even :even)
[goal :odd (* 10 goal)]
[(/ goal 10) :even goal])
[m even goal] )))
i (init (digits n))
palindromes (iterate next i) ]
(filter (partial <= n ) (map mirror palindromes))))
上記のコードを REPL に貼り付けると、次の単体テストを評価できます。
(= (take 26 (palindrome 0))
[0 1 2 3 4 5 6 7 8 9
11 22 33 44 55 66 77 88 99
101 111 121 131 141 151 161])
(= (take 16 (palindrome 162))
[171 181 191 202
212 222 232 242
252 262 272 282
292 303 313 323])
(= (take 6 (palindrome 1234550000))
[1234554321 1234664321 1234774321
1234884321 1234994321 1235005321])
(= (first (palindrome (* 111111111 111111111)))
(* 111111111 111111111))
(= (set (take 199 (palindrome 0)))
(set (map #(first (palindrome %)) (range 0 10000))))
(= true
(apply < (take 6666 (palindrome 9999999))))
(= (nth (palindrome 0) 10101)
9102019)
「最も遅い」テスト (番号 5) では、次のパフォーマンスが得られます。
user=> (time (= (set (take 199 (palindrome 0)))
(set (map #(first (palindrome %)) (range 0 10000)))))
"Elapsed time: 66.509472 msecs"
4clojure のホームページにある「タイムアウト」の基準がよくわかりません。私の意見では、1秒未満のものはすべて機能するはずです。JRE 7 では Clojure 1.5.1 を、JRE 6 では Clojure 1.2.1 を使用しました。
このパズルを解くのは私の 4 回目の試みであり、私の解決策のほとんどはテスト 5 に苦労していますが、遅いと言う意味がはっきりとわかりません。RAM の使用量が多すぎますか? 再帰？私はこの言語に慣れていないので、クールなヒントをいただければ幸いです。
私の最初の解決策は少し遅いですが、私のマシンでは約 600ms で終了します。
(defn palindrome [n]
(let [
digits #(seq (str %)) ;; given a number return a seq of its digits
digits-count #(count (digits %)) ;; given a number return how many digits it has
seqstr #(Long/parseLong (apply str %)) ;; seq to number
start (seqstr (take (/ (digits-count n) 2) (digits n)))
digits-range #(map long (range (max (Math/pow 10 (dec %)) start) (Math/pow 10 %))) ;; return all numbers of given digits length
mirror #(let [d (digits %1)]
(if (true? %2) (seqstr (concat d (reverse d))) ;; mirror 1234 true => 12344321 even number of digits
(seqstr (concat d (drop 1 (reverse d)))))) ;; mirror 1234 false => 1234321 odd number of digits
digits-seq #(drop (/ (digits-count %) 2) (range)) ;; e.g. when input number has 10 digits, result is a seq: 5, 6, 7, 8, ....
;; when input number has 9 digits, result is a seq: 5, 6, 7, 8, ....
input-even (even? (digits-count n))
]
(filter #(<= n %) (cons 0 (mapcat #(concat (map (fn [x] (mirror x false)) (if (and input-even (* 2 %)) [] (digits-range %)))
(map (fn [x] (mirror x true )) (digits-range %)) ) (digits-seq n) )))))