Fork me on GitHub

If I expect a vector in a particular sequence, but know that the vector I'm given might have some gaps in it, what's the easiest way to "fill in the blanks"? I'm thinking a combination of cycle, map-indexed, and reduce.


Well, Clojure vectors can't actually have gaps. There can be nils in there, which could be considered gaps, but they are still values. Can you provide a couple of example inputs and expected outputs for this "fill in the blanks" function? It isn't clear to me what you want.


I mean logical gaps:

data [1 2 3 4 5                   
      1   3 4                     
      1 2   4 5]                  
ids  [1 2 3 4 5]                  
exp-count (* 5 3)                 
exp (take exp-count (cycle ids))] 
Does that make sense?


Something like this, but less horrible 🙂

(let [data [1 2 3 4 5                                   
            1   3 4                                     
            1 2   4 5]                                  
      ids  [1 2 3 4 5]                                  
      exp-count (* 5 3)                                 
      exp (take exp-count (cycle ids))]                 
  (loop [data-idx 0                                     
         exp-idx 0                                      
         result []]                                     
      (= exp-idx exp-count) result                      
      (= (nth data data-idx)                            
         (nth exp exp-idx))                             
      (recur (inc data-idx)                             
             (inc exp-idx)                              
             (conj result (nth data data-idx)))         
      :else (recur data-idx                             
                   (inc exp-idx)                        
                   (conj result :x #_(nth exp exp-idx)))
; => [1 2 3 4 5 1 :x 3 4 :x 1 2 :x 4 5]                 


I see. I came-up with something more horrible 😃

(defn- follow
  "returns the common-prefix length of actual and expected"
  [actual expected]
  (->> (map vector actual expected)
    (take-while (fn [[x y]] (= x y)))

(defn fill-gaps
  "fills-in gaps in actual to make it a prefix of expected.
   starts with a gap (empty vector if no gap necessary at the beginning)"
  [actual expected]
  {:post [(->> (apply concat %)
            (map vector expected)
            (every? (fn [[x y]] (= x y))))]}
  (loop [[x :as actual] actual
         expected expected
         ret []]
    (if (empty? actual)
      (let [[gap expected] (split-with (complement #{x}) expected)
            n (follow actual expected)]
          (drop n actual)
          (drop n expected)
          (conj ret (vec gap) (vec (take n actual))))))))
With the example you gave:
(fill-gaps [1 2 3 4 5 1 3 4 1 4 5] (cycle [1 2 3 4 5]))
; => [[] [1 2 3 4 5 1] [2] [3 4] [5] [1] [2 3] [4 5]]
This fn "fills" the gaps using the elements "expected" in said gaps. (I put an invariant in the post-condition)


heh nice 🙂 I feel like someone is going to come in here and solve it with a single function call.


just build it directly


((fn f [the-seq filler-a filler-b]
   (when (seq the-seq)
     (if (seq filler-a)
       (if (= (first the-seq) (first filler-a))
         (lazy-seq (cons (first the-seq)
                         (f (rest the-seq)
                            (rest filler-a)
                            (conj filler-b (first filler-a)))))
         (lazy-seq (cons (first filler-a)
                         (f the-seq
                            (rest filler-a)
                            (conj filler-b (first filler-a))))))
       (recur the-seq filler-b []))))
 [1 2 3 4 5 1 3 4 1 4 5]
 [1 2 3 4 5]


vaguely sort of a merge sort


((fn f [the-seq filler]
   (when (seq the-seq)
     (if (= (first the-seq) (first filler))
       (cons (first the-seq) (f (rest the-seq) (rest filler)))
       (cons (first filler) (f the-seq (rest filler))))))
 [1 2 3 4 5 1 3 4 1 4 5]
 (cycle [1 2 3 4 5]))
not really a sort, a deduping merge


(wrap a lazy-seq call around that function body)


@U0NCTKEV8 thanks, I like that. I'll probably put the cycle inside somewhere I can just pass in the-seq and the-order, but that's approx. what I need.


maybe because of degenerate example, but if you’re always filling in the gaps, then don’t you just know the final answer?


if you knew what the length was supposed to be


then (take n (cycle filler))


but until you look over the input to find gaps, you don't know n, and finding gaps is basically the same procedure as filling them in

💯 1

Yeah, it is a simplified example. In the actual case it's a vector of maps, with each map having an ID and some other set of keys. If there's a gap in the IDs, I need to fill it in with a map that has the right ID and some computed values. The example is just the shortest representation I could think of.


then perhaps: (merge map-of-defaults-over-all-ids map-of-custom-ids-with-unique-values)


Yep, that's definitely a part of it but first the missing maps have to be identified.


sorry, missed that, i’m distracted and not fully reading the problem. homerdisappear


No problemo. Thank you for your input 🙂


I haven't looked in here forever, and this was last week, but I've just looked now, and it's a cute puzzle. My approach was similar to @U0NCTKEV8, though I think I was influenced by @UPWHQK562 with the use of reduce. So I came up with this:

(defn fill-in
  [sparse-seq replace-val cycle-seq]
    (fn [[result [f & r :as c]] x]
      (if-not f
        (reduced result)
        (if (= f x)
          [(conj result x) r]
          [(conj result :x) c])))
    [[] sparse-seq]
    (cycle (cycle-seq)))
(fill-in [1 2 3 4 5 1 3 4 1 4 5] :x (range 1 6))
It's just a merge, but I'm disappointed at how long this is. I feel like there should be something simpler that uses core, and not just a loop:
(defn fill-in
  [sparse-seq replace-val cycle-seq]
  (loop [r []
         [fs & rs :as s] sparse-seq
         [fc & rc] (cycle cycle-seq)]
    (if-not (seq s)
    (if (= fs fc)
      (recur (conj r fs) rs rc)
      (recur (conj r :x) s rc)))))
That's simple, but again, it feels like there is something simpler and more elegant. It's eluding me though 😕


@U051N6TTC thanks for the input 🙂 Looks good, but not the one-liner I was hoping for 😛


Exactly. It feels like there SHOULD be a one-liner, but I haven't had an epiphany on how to do it yet


Incidentally, I DID write it all in one line when I was testing out my ideas (since I wouldn’t post if I hadn't seen it work). I also had to reformat it and turn it into a function before posting 😉