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 `nil`s 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.

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 😉