Clojure compress vector

4
votes

I am trying to find a Clojure-idiomatic way to "compress" a vector:

(shift-nils-left [:a :b :c :a nil :d nil])
;=> (true [nil nil :a :b :c :a :d])
(shift-nils-left [nil :a])
;=> (false [nil :a])
(shift-nils-left [:a nil])
;=> (true [nil :a])
(shift-nils-left [:a :b])
;=> (false [:a :b])

In other words, I want to move all of the nil values to the left end of the vector, without changing the length. The boolean indicates whether any shifting occurred. The "outside" structure can be any seq, but the inside result should be a vector.

I suspect that the function will involve filter (on the nil values) and into to add to a vector of nils of the same length as the original, but I'm not sure how to reduce the result back to the original length. I know how to this "long-hand", but I suspect that Clojure will be able to do it in a single line.

I am toying with the idea of writing a Bejeweled player as an exercise to learn Clojure.

Thanks.

4
clojure
If only you allowed to shift the values to the right instead ... – Hamish Grubijan
The data structure I have in mind is a vector or 8 vectors. Each inner vector represents a column of jewels. The apply-move function will replace the jewels that disappear with nil values. I will then use the "compress" function to move the nil values to the top and then refill with jewels (I already have a function to do that). – Ralph

4 Answers

2
votes

I would write it like this:

(ns ...
  (:require [clojure.contrib.seq-utils :as seq-utils]))

(defn compress-vec
  "Returns a list containing a boolean value indicating whether the
  vector was changed, and a vector with all the nils in the given
  vector shifted to the beginning."
  ([v]
     (let [shifted (vec (apply concat (seq-utils/separate nil? v)))]
       (list (not= v shifted)
             shifted))))

Edit: so, the same as what Thomas beat me to posting, but I wouldn't use flatten just in case you end up using some sort of seqable object to represent the jewels.

2
votes

Maybe this way:

(defn shift-nils-left
   "separate nil values" 
    [s] 
    (let [s1 (vec (flatten (clojure.contrib.seq/separate nil? s)))] 
        (list (not (= s s1)) s1)))
2
votes

A little more low-level approach. It traverses the input seq just once as well as the vector of non-nils once. The two more highlevel approaches traverse the input sequence two times (for nil? and (complenent nil?)). The not= traverses the input a third time in the worst-case of no shift.

(defn compress-vec
  [v]
  (let [[shift? nils non-nils]
        (reduce (fn [[shift? nils non-nils] x]
                  (if (nil? x)
                    [(pos? (count non-nils)) (conj nils nil) non-nils]
                    [shift? nils (conj non-nils x)]))
                [false [] []] v)]
    [shift? (into nils non-nils)]))
1
votes
(def v [1 2 nil 4 5 nil 7 8] )

(apply vector (take 8 (concat (filter identity v) (repeat nil))))

This creates a sequence of the non- nil values in the vector using filter and then appends nils to the end of the sequence. This gives the values you want as a sequence and then converts them into a vector. The take 8 ensures that the vector is right size.