Repair the ranges

Question

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 code-golf, 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

Answer 1

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`

Answer 2

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

Answer 3

Haskell, 68 61 58 bytes

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!

Answer 4

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} *)

Answer 5

Perl, 47 45 44 39 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

Answer 6

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.
        ¥    Create a dyadic chain:
      Ṫ        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.

Answer 7

Retina, 39 34 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.

Answer 8

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.

Answer 9

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

Answer 10

Jelly, 8 bytes

ḟ0rƝṖ€Fo

Try it online!

Answer 11

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.

Answer 12

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:]

Answer 13

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.

Answer 14

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^["sy0dd`a@f ^["bc0yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@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"tyiWdd`b@t ^["zd0dd`bAe^[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"ty2ldd`b@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 ^["sy0dd`a@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"tyiWdd`b@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-"ayhdd`a@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^["sy0dd`a@f ^["bc0 :Write to @b and reset line

yiwo^V^V^V^X^V^R"^V^[0l@sa^V^V^V^A-^V^[0f-"ayhdd`a@i ^["dc0 :Write to @d and reset line

mbyiwo^V^R"Exe@b^V^[0fel"ty2ldd`b@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"tyiWdd`b@t ^["zd0 :Write to @z and reset line

dd`b :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

Answer 15

05AB1E, 3 bytes

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]

Try it online! or Verify all test cases!

Answer 16

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]

Answer 17

Perl 6, 54 bytes

{$_=$^a;1 while s/:s(\d+) 0 + (\d+)/{+~$0...+~$1}/;$_}

Answer 18

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 ~=.

Answer 19

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.

Answer 20

Husk, 3 bytes

…fI

Try it online!