Puzzles/Fill Zero Gaps
Problem posed by Ladvánszky Károly:
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. NB. bad initial sequences will be made monotone
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
Finally, both your expressions fail for leading zeroes, try:
r4 0 0 10 20
-- John Baker <<DateTime(2005-10-19T14:15:24Z)>>
Thanks, I'll need to think about these "minimize number of files touched", and "leave much space between touched files" issues for a bit. Meanwhile, I'm rather offended by my bug in the above expressions. To fix, change the phrase |.!.0 to |.!._. -- Raul Miller <<DateTime(2005-10-19T17:43:34Z)>>
It seems to me that the left argument to remonotone3, rather than being the total offset, should be the "per-element" offset (which is multiplied by the length of the needed sequence before use). Also, here's an expression which will identify the elements of the right arguments which do not need to change, to achieve a monotonically increasing sequence (eliminating the need for recursion): (= >./\)@(- i.@#). If you want to guarantee some minimum separation x., you can instead use (= >./\)@(] - [ * i.@#@]). If you prefer to push decrease timestamps, rather than increase them, you could instead use the monad (= <./\)&.|.@(- i.@#) or the dyad (= <./\)&.|.@(] - [ * i.@#@]) (but you might want to specifically exclude zeros if you use either of these latter two). -- Raul Miller <<DateTime(2005-10-21T00:56:08Z)>>
Thanks Raul. When I have a few moments I'll give your suggestions a try. -- John Baker <<DateTime(2005-10-21T13:09:34Z)>>