3
\$\begingroup\$

Problem

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

  • First a1 elements equal 1.
  • Next a2 elements equal 2.
  • Next a3 elements equal 3.
  • Next a4 elements equal 4.
  • Next a5 elements equal 5.
  • Next a6 elements equal 6.
  • Next a7 elements equal 7.
  • Next a6 elements equal 6.
  • Next a5 elements equal 5.
  • Next a4 elements equal 4.
  • Next a3 elements equal 3.
  • Next a2 elements equal 2.
  • Next a1 elements equal 1.

ai 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.

\$\endgroup\$
  • \$\begingroup\$ You didn't solve the stated problem. Consider this vector: 9 8 9. Yes, it is a palindrome. No, it's not a Rainbow. You don't range check for 1..7. You don't enforce monotonically increasing (until middle). You don't require starting with 1 and ending (in middle) with 7. \$\endgroup\$ – J_H Sep 13 '17 at 18:19
3
\$\begingroup\$
(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"
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.