Clojure: find locations "1" in line and print them in spacing format
I am trying to solve a problem like this:
For a line consisting of "1" and "0", find all locations "1" and print them in spacing format.
For example:
"00101110101110" => 3, 5-7, 9, 11-13
My (ugly) solution:
(defn bar [x]
(letfn [(foo [mystr]
(->>
(map-indexed vector mystr)
(filter #(= (second %) \1))
(map (comp inc first))
(partition-all 2 1)
(filter #(= 2 (count %)))))]
(let [y (map #(if (> (- (second %) (first %)) 1) (print (first %) ", " (second %) "-")) (foo x))]
(print (ffirst y) "-" y (last (last (foo x)))))))
Explanation:
First, I find the location "1" on the given line:
(->>
(map-indexed vector mystr)
(filter #(= (second %) \1))
(map (comp inc first)))
"00101110101110" => (3 5 6 7 9 11 12 13)
Then I split the list of positions into a sequence of 2-element tuples. If there is a 1-element tuple at the end of this sequence, leave it:
(->>
(map-indexed vector mystr)
(filter #(= (second %) \1))
(map (comp inc first))
(partition-all 2 1)
(filter #(= 2 (count %))))
"00101110101110" => ((3 5) (5 6) (6 7) (7 9) (9 11) (11 12) (12 13))
Finally, I print the first position in the first tuple and the second in the last tuple, using
(map #(if (> (- (second %) (first %)) 1) (print (first %) ", " (second %) "-")) (foo x))
to get the middle part.
Entrance:
(bar "00101110101110")
Final result:
3 , 5 -nil - (nil nil 7 , 9 -nil 9 , 11 -nil nil nil nil) 13
My questions:
- How to remove
nil
in the end result? - How can I solve this problem in a more concise manner?
source to share
To understand how to remove nil
from the final result, make it clear how they get there in the first place. The value associated with the name y
in the last form let
is actually a sequence of all values nil
. The function itself bar
also returns nil
. This is because it print
always returns nil
and if
returns nil
when the condition is false and the "else" form is missing. Effectively, each value in the sequence returned foo
is converted to nil
. Output non-nil values are values printed as a side effect. nil
and non-nil values are mixed because it map
is lazy and the display function is only applied when the latterprint
implements lazy sequence y
. Needless to say, using it map
for side effects is a bad idea.
So the easiest way to remove nil
from output is to avoid values altogether nil
.
(->> "00101110101110"
(map-indexed vector) ;; ([0 \0] [1 \0] [2 \1]...
(partition-by second) ;; (([0 \0] [1 \0]) ([2 \1]) ([3 \0]) ([4 \1] [5 \1] [6 \1]) ...
(filter #(= \1 (-> % first second))) ;; (([2 \1]) ([4 \1] [5 \1] [6 \1])...
(map #(map (comp inc first) %)) ;; ((3) (5 6 7) (9) (11 12 13))
(map #(if (next %) [(first %) (last %)] %)) ;; ((3) [5 7] (9) [11 13])
(map #(clojure.string/join "-" %)) ;; ("3" "5-7" "9" "11-13")
(clojure.string/join ", "))
;; => "3, 5-7, 9, 11-13"
source to share
I found this problem interesting, so I tried to attack it using the approach from this conversation : Higher parallelism by mapping data into a more convenient space and then combining sub-solutions in parallel. To this end, I focused on creating spacing in parallel; using transducers to complete all intermediate steps, then using eduction
and fold
. This kind of organization does a few helper functions and such, so maybe not that good at the tip, but hopefully interesting anyway.
I view the intermediate representation as nested vectors: [accepted boundary]
where the spacing represented by the 2-vector boundary
grows until the gap appears, in which case it is added to the end accepted
.
(defn indices "Transducer finding indices of an element occuring in a sequence"
[element]
(keep-indexed #(when (= element %2) %1)))
(defn combine "Combine two series of intervals"
([] [[] nil])
([[acc-a bnd-a] [acc-b bnd-b]]
(let[ [[a b] [c d]] [bnd-a (first acc-b)] ]
(if (<= b c (inc b))
[(into acc-a (concat [[a d]] (pop acc-b) )) bnd-b]
[(into acc-a (concat [bnd-a] acc-b)) bnd-b]))))
(defn plus "Add an interval to the series"
([] [[] nil])
([[accepted boundary] to-add]
(if (nil? boundary)
[accepted to-add]
(let[[[a b] [c d]] [boundary to-add]]
(if (<= b c (inc b))
[accepted [a d]]
[(conj accepted boundary) to-add])))))
(defn printable-indices [element the-seq]
(let[glommed (clojure.core.reducers/fold combine plus (eduction (comp (indices \1) (map #(vector % %))) the-seq))
fixed-up (conj (first glommed) (last glommed))] ;;Because the reduction is done, the last boundary is now accepted.
(clojure.string/join ", " (map (fn [[a b]](if (= a b) (str a) (str a \- b)))) fixed-up)))
source to share