Fork me on GitHub
#beginners
<
2022-03-15
>
sheluchin18:03:47

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.

jaihindhreddy19:03:43

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.

sheluchin19:03:43

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?

sheluchin19:03:39

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 []]                                     
    (cond                                               
      (= 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]                 

jaihindhreddy19:03:34

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)))
    (count)))

(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)
      ret
      (let [[gap expected] (split-with (complement #{x}) expected)
            n (follow actual expected)]
        (recur
          (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)

sheluchin20:03:30

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

hiredman20:03:45

just build it directly

hiredman20:03:48

((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]
 [])

hiredman20:03:39

vaguely sort of a merge sort

hiredman20:03:27

((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

hiredman20:03:15

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

sheluchin20:03:26

@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.

tschady20:03:49

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

hiredman20:03:13

if you knew what the length was supposed to be

hiredman20:03:34

then (take n (cycle filler))

hiredman21:03:16

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
sheluchin21:03:23

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.

tschady21:03:09

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

sheluchin21:03:46

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

tschady21:03:17

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

sheluchin21:03:32

No problemo. Thank you for your input 🙂

quoll17:03:37

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]
  (reduce
    (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)
    r
    (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 😕

sheluchin19:03:59

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

quoll19:03:00

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

quoll19:03:18

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 😉