Попытка новичка в попытке взломать проблему

Question

Я пытаюсь решить следующую проблему на hackerrank:

https://www.hackerrank.com/challenges/counting-valleys

но, к сожалению, мой следующий код clojure истекает во многих тестовых случаях, и я не знаю, что делаетэто так неэффективно.Пожалуйста, будьте снисходительны.У меня всего 2 часа опыта в уловке.

(require '[clojure.string :as str])

; Complete the countingValleys function below.
(defn countingValleys [n s]
    (do 
    (def running 0)
    (defn counter [elem]
    (do
        (cond 
        (= elem "D") (def running (+ running 1))
        (= elem "U")(def running (- running 1))
        )
        running
    )

    )

    (def valley-num 0)

    (defn valley-count [a b]
    (do
        (if (and (= a "U") (= b 0))
        (def valley-num (+ valley-num 1)))
    )
    )

    (def heights (for [elem s] (counter elem)))
    (doseq [[i j] (map vector s heights)]
    (valley-count i j))
    valley-num
    )


)

(def fptr (get (System/getenv) "OUTPUT_PATH"))

(def n (Integer/parseInt (clojure.string/trim (read-line))))

(def s (read-line))

(def result (countingValleys n (str/split s #"")))

(spit fptr (str result "\n") :append true)

Мертвая легкая реализация на python с той же логикой, которая заняла 5 минут и прошла все тестовые случаи:

def countingValleys(n, s):
    list = []
    for i in range(len(s)):
        d = 0
        if s[i] == "D":
            d = 1
        elif s[i] == "U":
            d = -1
        if len(list) == 0:
            list.append(d)
        else:
            list.append(list[-1] + d)
    num = 0
    for i in range(len(s)):
        if s[i] == "U" and list[i] == 0:
            num += 1
    return num

Answer 1

Так что я понял это. Неэффективность была в этой строке:

(doseq [[i j] (map vector s heights)]
    (valley-count i j))

Который можно заменить на:

(doall (map valley-count s heights))

и тогда все тесты проходят.

Answer 2

Медлительность вашего кода - наименьшая из его проблем.Инструменты, которые вы должны использовать:

• чистые функции,
• библиотека последовательностей,
• и, для скорости, перспектива преобразователей.

Мне нравится ваш основной алгоритм: подсчитайте случаи, когда движение up приведет вас к уровню моря.

Мы можем выразить это идиоматически следующим образом:

 (defn countingValleys [n s]
  (let [counter {\D 1, \U -1}
        heights (reductions + (map counter s))
        s-heights (map vector s heights)
        valley-num (count (filter #{[\U 0]} s-heights))]
    valley-num))

... или, используя ->> макрос многопоточности ...

(defn countingValleys [_ s]
  (->> s
       (map {\D 1, \U -1})
       (reductions +)
       (map vector s)
       (filter #{[\U 0]})
       (count))) 

Это яснее ибыстрее чем твой.

---

Кажется, что вы и HackerRank на самом деле используете ClojureScript.Использование "U" в качестве элемента строки не будет работать в самом Clojure: вы должны использовать символ \U.