Code Chef RAINBOW Palindrome

Question

Problem

Determine whether an array is "Rainbow", i.e. it has the following structure:

• First a₁ elements equal 1.
• Next a₂ elements equal 2.
• Next a₃ elements equal 3.
• Next a₄ elements equal 4.
• Next a₅ elements equal 5.
• Next a₆ elements equal 6.
• Next a₇ elements equal 7.
• Next a₆ elements equal 6.
• Next a₅ elements equal 5.
• Next a₄ elements equal 4.
• Next a₃ elements equal 3.
• Next a₂ elements equal 2.
• Next a₁ elements equal 1.

a_i can be any positive integer. There are no other elements in array.

Solution

(defn palindrome? [items]
  "Efficient algorithm: loops through only (array-size/2)"
  (loop [i 0
         j (-> items count dec)]
    (cond (>= i j)
          true
          (not= (nth items i) 
                (nth items j))
          false
          :else
          (recur (inc i) (dec j)))))

(let [test-cases-count (Integer/parseInt (read-line))
      test-cases       (for [i (range test-cases-count)]
                         (let [nums-count (read-line)
                               nums-temp (-> (read-line) (clojure.string/split #"\s+"))
                               nums (map #(Integer/parseInt %) nums-temp)]
                           nums))]
  (for [t test-cases]
    (if (palindrome? t)
      (println "Yes")
      (println "No"))))

Not able to figure out how to optimize this.

Answer 1

(defn palindrome? [items]
  "Efficient algorithm: loops through only (array-size/2)"
     ...
         (not= (nth items i) 
               (nth items j))

nth is efficient on vectors and other things that support random indexing. On sequences, which you're passing in right now, it's O(n) per lookup since it has to walk the list.

Changing your test cases to use vectors should help (use mapv instead of map):

(let [...
      nums (mapv #(Integer/parseInt %) nums-temp)]

---

(def example (concat (range 1000) (reverse (range 1000))))
(count example)   ; 2000
(def examplev (vec example))
(count examplev)  ; 2000

(dotimes [_ 3] (time (palindrome? example)))
; "Elapsed time: 45.167334 msecs"
; "Elapsed time: 44.568282 msecs"
; "Elapsed time: 45.304136 msecs"

(dotimes [_ 3] (time (palindrome? examplev)))
; "Elapsed time: 0.317649 msecs"
; "Elapsed time: 0.272229 msecs"
; "Elapsed time: 0.30044 msecs"

Answer 2

Explicit trues and falses are usually a code smell in Clojure. Your palindrome? function reads better as

(defn palindrome? [items]
  (loop [i 0, j (-> items count dec)]
    (or (>= i j)
        (and (= (nth items i) (nth items j))
             (recur (inc i) (dec j))))))

... which probably produces identical code.

You could also drop the nth calls, as a vector works as an indexing function. This would trap attempts to supply an ordinary sequence.

Alternatively, We could use sequence functions:

(defn palindrome? [v]
  (let [half-count (-> v count (quot 2))]
    (every? identity (map = (subvec v 0 half-count) (sequence (rseq v))))))

I think this would be slower, though I haven't tested it.