Repair the ranges

Given an input of a list of positive integers with some replaced with 0, output the list with the missing numbers that were changed to 0 replaced.

Characteristics of the input list:

• The list will always have a length of at least 2.

• Let us define the input list as a and the "original list" (that is, the list before numbers were replaced with 0s) as b. For any n, a[n] is either b[n] or 0.

• For any n, b[n] is either b[n-1] + 1 or b[n-1] - 1. That is, the numbers in b will always change by 1 at each index from its previous. The first element is, of course, exempt from this rule.

• For every run of zeroes in a (that is, consecutive elements replaced with 0), with x representing the index of the start of the run and y representing the end, a[x-1] to a[y+1] will always be either solely increasing or solely decreasing. Therefore, there will only be one possible way to fill in the zeroes.

• This also means that neither the first nor the last element of the array can be zeroes.

In simpler terms, to fill in a run of zeroes, simply replace it with a range from the number before to the number following it. For example, an input of

1 2 0 0 0 6 7


must output

1 2 3 4 5 6 7


Since this is , the shortest code in bytes will win.

Test cases:

In                      Out
-----------------------------------------------------
1 0 0 0 5 6 0 4 0 0 1 | 1 2 3 4 5 6 5 4 3 2 1
7 6 0 0 3 0 0 0 7 0 5 | 7 6 5 4 3 4 5 6 7 6 5
1 0 3 0 5 0 3 0 5 0 7 | 1 2 3 4 5 4 3 4 5 6 7
14 0 0 0 0 0 0 0 0 23 | 14 15 16 17 18 19 20 21 22 23

• Instead of 0 can our program take another value such as null? Feb 20, 2016 at 0:43
• @Downgoat No, missing numbers must be given as 0. Feb 20, 2016 at 0:44

JavaScript (ES6), 72 66 64 54 53 bytes

Saved 12 bytes thanks to @Neil!

Saved 1 byte thanks to @IsmaelMiguel

a=>a.map((l,i)=>l?b=l:b+=a.find((q,r)=>r>i&&q)>b||-1)


Pretty good for JavaScript.

Try it online (all browsers work)

Explanation

a=>  // Function with arg a
a.map((l,i)=>  // Loop through input
l?             // If nonzero
b=l          // Set b to current number
:a.find((q,r)=>r>i&q) // Otherwise look for the next nonzero number
>b?           // If it's increased since nonzero last number
++b:--b)    // Increasing? increase b (the previous nonzero number)
// otherwise decrease b

• I think that a.find((q,r)=>r>i&&q)>b?++b:--b is the same as b+=a.find((q,r)=>r>i&&q)>b||-1 Feb 21, 2016 at 0:24
• @IsmaelMiguel that's smart, thanks! Feb 21, 2016 at 6:24
• You're welcome. I'm glad it worked out for you. Feb 21, 2016 at 18:03
• I think you can replace && with just & (Just noticed you have one & in the explanation and two in the answer) Feb 26, 2016 at 19:28

MATL, 11 12 bytes

fGXzGn:3$Yn  Works with current release (13.0.0) of the language/compiler. Try it online! f % implicitly input array. Indices of nonzero elements (*) GXz % push input and get its nonzero elements (**) Gn: % vector [1,2,...,n], where n is input length (***) 3$Yn     % interpolate at positions (***) from data (**) defined at positions (*)


g(a:b:r)=[a..b-1]++[a,a-1..b+1]++g(b:r)
g x=x
g.filter(>0)


Usage example: g.filter(>0) $[7,6,0,0,3,0,0,0,7,0,5]-> [7,6,5,4,3,4,5,6,7,6,5]. How it works: remove zeros from the input, then call g. Let a be the first and b then second element of the remaining list. Concatenate the lists from a upwards to b-1 and from a downwards to b+1 (one of them will be empty) and a recursive call with a dropped. Edit: @Zgarb saved 3 bytes. Thanks! Mathematica, 59 bytes #//.{a___,x_,0..,y_,b___}:>{a,##&@@Range[x,y,Sign[y-x]],b}&  Test case %[{1,0,3,0,5,0,3,0,5,0,7}] (* {1,2,3,4,5,4,3,4,5,6,7} *)  Perl, 47454439 37 bytes Includes +1 for -p s%\S+%$p+=/\G(0 )+/?$'<=>$p:$&-$p%eg


Expects the list on stdin. Example: echo 1 0 3 0 1 | perl -p file.pl

• I see some copy pasting here.. ;-) Nicely done btw. Feb 20, 2016 at 19:47

Jelly, 12 11 bytes

ḢWW;ḟ0Ṫr¥\F


Try it online!

Alternative version, 8 bytes (non-competing)

Unfortunately, Jelly's pop did not cast to iterable, in the latest version that predates this challenge. This has been fixed, and the following works in the current version.

ḟ0Ṫr¥\FḊ


Try it online!

How it works

ḢWW;ḟ0Ṫr¥\F  Main link. Input: A (list)

Ḣ            Pop the first element of A. Let's call it a.
WW          Yield [[a]].
;         Concatenate with the popped A.
This wraps the first element of A in an array.
ḟ0       Filter; remove all zeroes.
Ṫ        Pop the last element of the left argument.
r       Call range on the popped element and the right argument.
\   Reduce the modified A by this chain.
F  Flatten the resulting list of ranges.


In the alternate version, ḢWW; becomes unnecessary. However, since the first element is cast to iterable before popping, it is not actually modified. The final Ḋ removes the duplicate of the first element.

Retina, 3934 31 bytes

3 bytes saved thanks to @Martin.

+1(1*) (?= +((1)\1)?)
$0$1$3$3


Takes input and gives output in unary.

The code iteratively fills every empty place (0's) with previous_number - 1 + 2 * if_next_nonzero_number_bigger. previous_number - 1 is $1 and if_next_nonzero_number_bigger is $3.

With decimal I/O the code is 51 bytes long as you can see in the online interpreter with all the test cases.

• You can save another byte by omitting the first 1 in the lookahead. Feb 21, 2016 at 12:53
• @MartinBüttner Right, edited. Feb 21, 2016 at 17:28

GNU Sed (with exec extension using bash), 61

Score includes +1 for -r option to sed.

:
s/( 0)+ /../
s/\w+..\w+/{&}/
s/.*/bash -c 'echo &'/e
/ 0/b

• Find runs of 0s and replace them ..
• Put braces around the endpoint numbers to create a bash brace expansion like {1..4} for the local endpoints. The beauty of bash brace expansions here is that the generated sequence will always run in the right direction, regardless of whether the start or end is larger.
• Use the e option to the s command to call out to bash to evaluate this brace expansion
• If any more 0s are found, jump back to the start.

Ideone.

Python 2, 195 111 bytes (thanks Alex!)

t=input()
z=0
for i,e in enumerate(t):
if e:
while z:t[i-z]=e+z if l>e else e-z;z-=1
l=e
else:z+=1
print t


Input: must be a [list] of ints
Output: [list] of ints

• Sorry about that! Fixed. Thanks for the heads up. Feb 20, 2016 at 18:28
• No worries. Nice solution. :) You can get it down to 112 bytes using this, which is your same approach, just golfed a bit more. We also have a collection of tips for golfing in Python here. Feb 20, 2016 at 18:38

Jelly, 8 bytes

ḟ0rƝṖ€Fo


Try it online!

Perl, 85 82 bytes

includes +1 for -p

s/(\d+)(( 0)+) (\d+)/$s=$1;$e=$4;$_=$2;$c=$s;s!0!$c+=$e<=>$s!eg;"$s$_$e"/e&&redo


Expects the list on stdin. Example: echo 1 0 3 0 1 | perl -p file.pl.

This uses a nested regexp. Somewhat readable:

s/(\d+)(( 0)+) (\d+)                  # match number, sequence of 0, number
/
$s=$1;                            # start number
$e=$4;                            # end number
$_=$2;                            # sequence of ' 0'
$c=$s;                            # initialize counter with start number
s!0! $c +=$s <=> $e !eg # replace all 0 with (in|de)cremented counter "$s$_$e"                         # return replacement
/e
&& redo                               # repeat until no more changes.


Python 2, 92 88 bytes

(Removed intermediate variable)

t=filter(bool,input())
print sum([range(o,p,cmp(p,o))for o,p in zip(t,t[1:])],[])+t[-1:]


Pyth, 17 bytes

u+G+treGHHfTtQ[hQ


The way it works:

u                 reduce
[hQ     seed: the first element of input, in a list
iterable:
tQ              all except the first element of input
fT                remove if 0
lambda: G is the list to be returned, H is the current item
+G                       append to return list
reGH                  a range from the last element of the return list and the current item
+                      concatenated with
H                 the last item (this step forms a bidirectional inclusive list)


In other words: all zeroes are removed from input, then an exclusive range is inserted between every element. This range is zero length on elements only one apart.

05AB1E, 3 bytes (non-competing)

This was a feature added after the challenge. Code:

0KŸ


Explanation:

0K   # Remove all zeroes from the input list
Ÿ  # Rangify, [1, 4, 1] would result into [1, 2, 3, 4, 3, 2, 1]


Vim: 231 Key Commands

Note that any ^ preceding a character means you should hold control while typing that character

mbomayiwo^V^R"^V^V^V^X ^V^["sy0dda@f ^["bc0yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdda@i ^["dc0mbyiwo^V^R"Exe@b^V^[0fel"ty2lddb@t ^["ec0wmbyiwo@f @d^V^[@z ^["fc0"xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWddb@t ^["zd0ddbAe^[0@e


Steps so you can run this too!

1. Copy the line into Vim
2. Type :s/\^V/<Ctrl-V><Ctrl-V>/g and press enter (the two s should give you a blue ^V)
3. Type :s/\^R/<Ctrl-V><Ctrl-R>/g and press enter (you should see blue ^Rs now)
4. Type :s/\^X/<Ctrl-V><Ctrl-X>/g and press enter (you should see blue ^Xs now)
5. Type :s/\^O/<Ctrl-V><Ctrl-O>/g and press enter
6. Type :s/\^A/<Ctrl-V><Ctrl-A>/g and press enter
7. Type :s/\^\[/<Ctrl-V><Ctrl-[>/g and press enter (this command is slightly different because I needed to escape the [)
8. Type 0"yy$. The command is now stored in the y register 9. Set up input on a line, and run with @y If someone knows a better way to share the command, please let me know. I know this is lengthy, but it's the best I could come up with. Input/Output The input string should be alone on any line in the file. 1 0 0 4 3 0 0 0 7 The output will simply overwrite the input string 1 2 3 4 3 4 5 6 7 Explanation Algorithm 1. Start at a non-zero number, make sure it's not the last number 2. Find the next non-zero number 3. Take their difference. If the answer is negative, you should decrement to repair the range, otherwise, increment to repair the range. 4. Go back to the first character and replace each zero by incrementing/decrementing the previous number. 5. Repeat until you get to the last character Macros Used @e - Check for end. The last number will have an e appended to it. If the number under the cursor has an e at the end, delete the e and stop execution. Otherwise, start an interpolation cycle with @b. mbyiwo^R"Exe@b^[0fel"ty2lddb@t  @b - Begin interpolation cycle. Save the number under the cursor for a subtraction operation (@s) and then find the next non-zero term (@f) mayiwo^R"^V^X ^["sy0dda@f  @s - Stores the subtraction command to use in @d. It is simply (val)^X where (val) is the number at the start of the interpolation step. This is set by the @b command. @f - Find the next non-zero term. Write the current value to the unnamed register, then write @f @d on the next line, and then run @z. This will repeat this command if the number is a zero, and execute @d if it isn't. wmbyiwo@f @d^[@z  @z - Conditional execute if unnamed register is 0. This command expects two commands on a new line in the format command1 command2. If the unnamed register is 0, command1 is executed, otherwise command2 is executed. Note that neither command can have any spaces in it.  IB0 B^R" ^OWB0 ^OA B0^[0*w"tyiWddb@t  @t - Temporary command register. Stores various commands for a short time before executing them. Used primarily in if statements. @d - Determine interpolation direction. Subtracts the first number in the sequence from the number under the cursor (using @s). If the result is negative, the interpolation must decrement so ^X is saved to @a. Otherwise, we should increment so ^A is saved to @a. Once this is saved, move back to the beginning of this interpolate cycle and run @i to actually interpolate yiwo^V^X^R"^[0l@sa^V^A-^[0f-"ayhdda@i  @a - Stores either ^A or ^X to increment or decrement during the interpolation step. This is set by the @d command. @i - Interpolate. Copy the number at the current location to @x and move to the next number. If that number is zero, replace it with @x and run @a to properly modify it up or down, then repeat this command. If the number isn't a zero, we have reached the end of this interpolation cycle. A new one should be started with this number as the beginning, so run @e to check for the end and run again. "xyiwwmbyiwocw^V^Rx^V^[@a@i @e^[@z  @x - Temporary storage register. Used in the interpolate command (@i) Breaking Down the keystrokes mbo :Set b mark to current position and open a new line below to write macros mayiwo^V^R"^V^V^V^X ^V^["sy0dda@f ^["bc0 :Write to @b and reset line yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdda@i ^["dc0 :Write to @d and reset line mbyiwo^V^R"Exe@b^V^[0fel"ty2lddb@t ^["ec0 :Write to @e and reset line wmbyiwo@f @d^V^[@z ^["fc0 :Write to @f and reset line "xyiwwmbyiwocw^V^V^V^Rx^V^V^V^[@a@i @e^V^[@z ^["ic0 :Write to @i and reset line IB0 B^V^R" ^V^OWB0 ^V^OA B0^V^[0*w"tyiWddb@t ^["zd0 :Write to @z and reset line ddb :Delete this line and move cursor back to original line Ae^[ :Append an e to the last number 0@e :Move to the beginning of the line and run  Python 3.5, 159 bytes a recursive solution def f(s): h=s[0] g=lambda s,h,v:h*(h[-1]==s[0])if len(s)==1else(g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v))*(s[0]==0 or h[-1]==s[0]) return g(s,[h],1)  Ungolfed def f(s): h=s[0] def g(s,h,v): if len(s)==1: if h[-1]!=s[0]: r=[] else: r=h else: if s[0]==0: r=g(s[1:],h+[h[-1]+v],v) elif h[-1]!=s[0]: r=[] else: r=g(s[1:],h+[h[-1]-v],-v)+g(s[1:],h+[h[-1]+v],+v) return r return g(s,[h],1)  In the golfed solution, I replace conditions by using the fact that h*True=h and h*False=[] Result >>> f([7, 6, 0, 0, 3, 0, 0, 0, 7, 0, 5]) [7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5]  Perl 6, 54 bytes {$_=$^a;1 while s/:s(\d+) 0 + (\d+)/{+~$0...+~$1}/;$_}


MATLAB, 39 38 37 bytes

@(a)interp1(find(a),a(a>0),find(a/0))


Anonymous function that linearly interpolates between the points in a. find(a) is an array of indices of non-zero elements in a and a(a>0) are the positive values. Saved 1 byte thanks to a friend's suggestion of > rather than ~=.

J, 32 bytes

{:,~[:;2<@({.+(i.@|**)@-~/)\-.&0


Try it online!

• -.&0 Remove zeroes.
• 2...\ For each infix of size 2...
• @-~/ Subtract the left from the right and...
• (i.@|**) Create integers 0..<size of difference>, multiplied by * the sign of the difference *.
• <@ And box (technical necessity for ragged arrays in J).
• [:; Raise the result to remove the boxes.
• {:,~ And append the last element of the original array.

Husk, 3 bytes

…fI


Try it online!