Поиск повторяющихся символов в последовательности символов


Следующий код решает эту проблему:

Ниже 3072 символов содержат последовательность из 5 символов, которая повторяется. Однако, есть поворот: одну из последовательностей опечатка. Чтобы быть конкретным, вы ищете две группы по 5 символов, которые поделиться 4 из этих символов. Введите 4 Общая ниже символы продолжить.

Любые предложения о том, как его можно улучшить, используя идиоматические Лисп/язык Clojure?

(ns slurp.slurp)

(defn get-five [in]
  (if (> (.length in) 4)
    (subs in 0 5)
    nil))

(defn how-good [a b position goodness bad-position]
  (if (= position 5)
    (list goodness bad-position)
    (if (= (subs a position (+ 1 position)) (subs b position (+ 1 position)))
          (recur a b (+ 1 position) (+ 1 goodness) bad-position)
          (recur a b (+ 1 position) goodness position))))

(defn matches [a b]
  (let [x (how-good a b 0 0 -1)]
    (list (> (first x) 3) (last x))))

(defn remove-bad-char [in-string bad-index]
  (str (subs in-string 0 bad-index) (subs in-string (+ 1 bad-index))))

(defn sub-parse [left in]
  (let [right (get-five in)]
    (if (not (= right nil))
      (let [match-result (matches left right)]
        (if (first match-result)
          (let [bad-index (last match-result)]
            (println left "is a match. bad-position:" (last match-result) "ans: "(remove-bad-char right bad-index)))
          (recur left (subs in 1)))))))

(defn parse [in]
    (let [left (get-five in)] ;; as soon as we hit the ass end of the input string, get-five returns null and we stop trying to match.
      (if (not (= left nil))
        (do
          (sub-parse left (subs in 1))
          (recur (subs in 1))))))

(parse (slurp "/Users/clojure/challange.txt"))

;; https://www.readyforzero.com/challenge/491f97bc25574346aed237d43e7d0404
;; (answer is i2+r)


Комментарии
2 ответа

Я бы начала снизу вверх на этот один, если вы хотите сделать ее немного более идиоматические / функционального стиля. Также это отличная возможность для получения данных в Clojure последовательности, а не строки, как это делает его немного легче манипулировать.

Вы пытаетесь работать на группах из пяти смежных символов, так что если бы я устанавливал последовательность таких смежных групп:

; define some source data, right answer is "1235"
(def char-seq (seq "dfyfgvbufi12345idvdfhopshbsopgeobvufpdhbugphp123a5ghauoyhewqojbvrbon"))

; now partition into adjacent overlapping groups of five (with a step of 1)
(def char-groups (partition 5 1 char-seq))

; prove it works
(take 3 char-groups)
=> ((\d \f \y \f \g) (\f \y \f \g \v) (\y \f \g \v \b))

Теперь мы хотим определить, что действительное совпадение означает: в данном случае 4 символа должно быть одинаковым в двух группах сравнивали.

; helper function to count the number of true values in a collection / sequence
(defn count-true [coll]
(reduce
#(+ %1 (if %2 1 0))
0
coll))

; function to determine if exactly four characters are equal in two groups
(defn matches? [group1 group2]
(= 4
(count-true (map = group1 group2))))

Наконец, вы просто нужно запустить матчи? функции по всем возможным группам:

(def results
(distinct
(keep identity
(for [group1 char-groups
group2 char-groups]
(if (matches? group1 group2)
(filter identity (map #(if (= %1 %2) %1 nil) group1 group2))
nil)))))

results
=> ((\1 \2 \3 \5))

1
ответ дан 16 июля 2011 в 11:07 Источник Поделиться

Вот моя версия. Работает на любой сл (не только строки) и полностью ленивый.

(def data (slurp "data.txt"))

(defn same-pos
"Return all the elements of xs and ys that match, position-wise. e.g.
(same-pos [\\a \\x \\c] [\\a \\r \\c]) returns [\\a \\c]. Returns nil if xs
and ys have different lengths."
[xs ys]
(when (= (count xs) (count ys))
(filter (complement nil?) (map #(if (= %1 %2) %1) xs ys))))

(def answer
(let [ps (partition 5 1 data)] ; build seq of sliding 5-tuples
(->> (for [x ps y ps] (same-pos x y)) ; n^2 FTW
(filter (comp (partial = 4) count)) ; 4 of 5 positions must match
(first))))

(println (apply str "Answer: " answer)) ; will print "Answer: i2+r"

Обновление: я не читал других ответов заранее (хотел сам разобраться), но, похоже, у меня в принципе то же самое, что mikera. Так что, может, не много, чтобы учиться здесь :)

1
ответ дан 19 июля 2011 в 03:07 Источник Поделиться