# Puzzles/Fill Zero Gaps

Given a list of numbers, fill the zero gaps between the non-zero items so that these intervals each form a linear series. For example:

```1 0 0 4 2  =>  1 2 3 4 2
0 0 1 0 0  =>  0 0.5 1 0.5 0
```

There is a 21-line solution in Python, applying 3 loops.

Solution:

```fill=: 3 : 0 ^: (*@#)
b=. 1 (0 _1)} 0~:y
x=. b#y
n=. 2 -~/\ I. b
({:x) ,~ (n#}:x) + ; (i.&.>n) *&.> n %~ 2 -~/\ x
)
```

The ^:(*@#) is to handle empty lists.

It is possible to squeeze this down to one line but there'd be little point to that.

This puzzle is related to a problem I recently dealt with. I wanted a verb that would take an integer list with 0's and fill the 0's so that the resulting sequence was strictly monotone increasing, for example:

```0 0 1 0 2 3 4 5 0 6 7 8 0 9 10 => _10 _5 _2 _1 0 1 2 3 4 5 6 7 8 9 10
```

One more requirement was to change as few nonzero list elements as possible. This fill verb is close. Using it I was able to simplify remonotone2 to this version.

```remonotone3=:4 : 0

NB.*remonotone3 v-- converts  integer lists  with 0s to  strictly
NB. monotone increasing integer sequences.
NB.
NB. Version of remonotone using (fill).
NB.
NB. verbatim:  (see J Wiki at url)
NB.
NB.   http://202.67.223.49/jwiki/Puzzles/Fill_Zero_Gaps
NB.
NB. dyad:  ilMonotone =. iGap remonotone3 il
NB.
NB.    ism=: [: *./ 2: </\ ]  NB. is strictly increasing
NB.    ism 3 remonotone3 i.0
NB.    ism 5 remonotone3 8
NB.    ism 5 remonotone3 0 7
NB.    ism 3 remonotone3 0 0 0 0
NB.    ism 3 remonotone3 0 0 0 2 0 0
NB.    ism 2 remonotone3 0 0 1 0 2 3 4 5 0 6 7 8 0 9 10
NB.    ism 180 remonotone3 1 0 3 0 5 0 7 0 9
NB.
NB.    ism 2 remonotone3 5 6 0 0 3 4 0 12
NB.    ism 3 remonotone3 ((?5)#14?14){0 0,i.12
NB.
NB.    NB. worst case - minimum gaps
NB.    x0=. 1 2 0 0 3 4 5 6 0 7 8 9 10 0 0
NB.    ism y0=. 2 remonotone3 x0
NB.
NB.    NB. best case - wide gaps
NB.    x1=. 8 12 0 55 66 0 87 112 152 166 0 191 0 219 229 266 0 300 0 342 353
NB.    ism y1=. 5 remonotone3 x1
NB.
NB.    (0~:x1)#x1=y1  NB. 1's are unchanged old times
NB.
NB.    NB. 0 free not strictly increasing - assertion failure
NB.    5 remonotone3 8 9 2 3

if.  0 = #y.       do. y. return.
NB. insure lists without 0s are strictly increasing
elseif. -. 0 e. y. do.    assert. *./ 2 </\ y.
y. return.
end.

s=. y.
g=. |x.

NB. replace any leading or trailing 0s with gap width
if. 0={. s do. s=. ((<./s) - g) , }. s end.
if. 0={: s do. s=. (}: s) , g + >./s end.

if. *./ 2 </\ s=. <. fill s do. s  NB. 0s can occur in s
else.
NB. list is not strictly increasing - adjust borders and recurse
s=. x. remonotone3 s * (0~:s) *. 1 ,~ 2 </\ s
end.
)
```

Any further simplifications would be welcome -- John Baker <<DateTime(2005-10-18T17:02:09Z)>>

I'd like to understand all of what remonotone3 does that's different from (+ [: ; [: <@i.@#;.1 ] ~: _1: |.!.0 ])@:(>./\)^:_ or, perhaps (+ [: ; [: <@(i. - <.@-:)@#;.1 ] ~: _1: |.!.0 ])@:(>./\)^:_ (and why these differences are important)? -- Raul Miller <<DateTime(2005-10-18T18:10:59Z)>>

Raul, to answer your questions: remonotone came up during a file time stamp maintenance problem. Basically I had a directory of files that were ordered by time. I wanted to insert new files in this directory subject to a fixed order that I could not change. This required touching some files and resetting dates. I wanted to minimize the number of touched files and leave as much "time" as possible to insert more files in the future. remonotone3 does a few things that your expressions do not.

It divides zero gaps evenly (Roger's fill does this as well):

```  NB. your first expression
r4=: (+ [: ; [: <@i.@#;.1 ] ~: _1: |.!.0 ])@:(>./\)^:_

NB. (v) is seconds between file times
v=. 5 0 0 0 100

r4 v
5 6 7 8 100

1 remonotone3 v
5 28 52 76 100
```

The x. argument defines a time gap:

```  v0=. 10 23 0 0 0
200 remonotone3 v0
10 23 89 156 223

v1=. 0 0 20 0 0 40 0
50 remonotone3 v1
_50 _15 20 26 33 40 90
```

```  r4 0 0 10 20