Fill in an increasing sequence with as many numbers as possible

A list of numbers is called monotonically increasing (or nondecreasing) is every element is greater than or equal to the element before it.

For example, 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14 is monotonically increasing.

Given a monotonically increasing list of positive integers that has an arbitrary number of empty spots denoted by ?, fill in the empty spots with positive integers such that as many unique integers as possible are present in the list, yet it remains monotonically increasing.

There may be multiple ways to accomplish this. Any is valid.

Output the resulting list.

For example, if the input is

?, 1, ?, 1, 2, ?, 4, 5, 5, 5, ?, ?, ?, ?, 8, 10, 11, ?, 14, 14, ?, ?


it is guaranteed that without the empty spots the list will be monotonically increasing

1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14


and your task is to assign positive integers to each ? to maximize the number of distinct integers in the list while keeping it nondecreasing.

One assignment that is not valid is

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 8, 10, 11, 14, 14, 14, 14, 14


because, while it is nondecreasing, it only has one more unique integer than the input, namely 3.

In this example it is possible to insert six unique positive integers and keep the list nondecreasing.
A couple possible ways are:

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8, 10, 11, 12, 14, 14, 15, 16

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 10, 11, 13, 14, 14, 20, 200


Either of these (and many others) would be valid output.

All empty spots must be filled in.

There is no upper limit on integers that can be inserted. It's ok if very large integers are printed in scientific notation.

Zero is not a positive integer and should never be inserted.

In place of ? you may use any consistent value that is not a positive integer, such as 0, -1, null, False, or "".

The shortest code in bytes wins.

More Examples

[input]
[one possible output] (a "*" means it is the only possible output)

2, 4, 10
2, 4, 10 *

1, ?, 3
1, 2, 3 *

1, ?, 4
1, 2, 4

{empty list}
{empty list} *

8
8 *

?
42

?, ?, ?
271, 828, 1729

?, 1
1, 1 *

?, 2
1, 2 *

?, 3
1, 3

45, ?
45, 314159265359

1, ?, ?, ?, 1
1, 1, 1, 1, 1 *

3, ?, ?, ?, ?, 30
3, 7, 10, 23, 29, 30

1, ?, 2, ?, 3, ?, 4
1, 1, 2, 3, 3, 3, 4

1, ?, 3, ?, 5, ?, 7
1, 2, 3, 4, 5, 6, 7 *

1, ?, 3, ?, 5, ?, ?, 7
1, 2, 3, 4, 5, 6, 7, 7

1, ?, ?, ?, ?, 2, ?, ?, ?, ?, 4, ?, 4, ?, ?, 6
1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6

98, ?, ?, ?, 102, ?, 104
98, 99, 100, 101, 102, 103, 104 *

• Probably a better way to phrase the problem that has a strict input,output pair for verification, would be "What is the highest possible number of distinct numbers in the sequence". That way all answers will output the same number and makes evaluating test cases much easier – Cruncher Mar 16 '17 at 15:59
• @StewieGriffin You can assume the list values and length are below int maximums as usual. I only meant that it's ok to insert very large integers at the end if that's the way your algorithm works. – Calvin's Hobbies Mar 16 '17 at 20:24

f takes a list and returns a list, with 0 representing ?s.

f=scanr1 min.tail.scanl(#)0
m#0=m+1
_#n=n


Basically, first scan list from left, replacing 0s by one more than the previous element (or 0 at the start); then scan from right reducing too large elements to equal the one on their right.

Try it online! (with wrapper to convert ?s.)

Mathematica, 84 bytes

Rest[{0,##}&@@#//.{a___,b_,,c___}:>{a,b,b+1,c}//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}]&


Pure function taking a list as argument, where the empty spots are denoted by Null (as in {1, Null, Null, 2, Null}) or deleted altogether (as in {1, , , 2, }), and returning a suitable list (in this case, {1, 2, 2, 2, 3}).

Turns out I'm using the same algorithm as in Ørjan Johansen's Haskell answer: first replace every Null by one more than the number on its left (//.{a___,b_,,c___}:>{a,b,b+1,c}), then replace any too-large number by the number on its right (//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). To deal with possible Nulls at the beginning of the list, we start by prepending a 0 ({0,##}&@@#), doing the algorithm, then deleting the initial 0 (Rest).

Yes, I chose Null instead of X or something like that to save literally one byte in the code (the one that would otherwise be between the commas of b_,,c___).

• Hm, prepending 1 you say? I used a 0, because of things like ?, 2. I suspect you would then produce 2, 2 instead of the correct 1, 2. – Ørjan Johansen Mar 16 '17 at 13:15
• Excellent point! Luckily the fix is easy. – Greg Martin Mar 16 '17 at 16:31

C 160

This will never win but:

#define p(x)printf("%d ",x);
i=1,l=0,m=0,n;main(c,v)char**v;{for(;i<c;i++)if(*v[i]==63)m++;else{for(n=atoi(v[i]);m>0;m--)p(l<n?++l:n)p(l=n)}for(;m>0;m--)p(++l)}


It takes the list from the command line arguments.

Pip, 2523 21 bytes

Y{Y+a|y+1}MgW PMNyPOy


Takes input as multiple space-separated command-line arguments. Outputs the result list one number per line. Try it online! (I've fudged the multiple command-line args thing because it would be a pain to add 25 arguments on TIO, but it does work as advertised too.)

Explanation

We proceed in two passes. First, we replace every run of ?s in the input with a sequence starting from the previous number in the list and increasing by one each time:

? 1 ? 1 2 ? 4 5 5 5 ? ? ? ? 8 10 11 ?  14 14 ?  ?
1 1 2 1 2 3 4 5 5 5 6 7 8 9 8 10 11 12 14 14 15 16


Then we loop through again; for each number, we print the minimum of it and all numbers to its right. This brings the too-high numbers down to keep monotonicity.

                      y is initially "", which is 0 in numeric contexts
Stage 1:
{       }Mg           Map this function to list of cmdline args g:
+a                  Convert item to number: 0 (falsey) if ?, else nonzero (truthy)
|                 Logical OR
y+1              Previous number +1
Y                    Yank that value into y (it is also returned for the map operation)
Y                      After the map operation, yank the whole result list into y
Stage 2:
W          While loop, with the condition:
MNy      min(y)
P         printed (when y is empty, MN returns nil, which produces no output)
POy  Inside the loop, pop the leftmost item from y


Python 2 with NumPy, 163 bytes

Saved 8 bytes thanks to @wythagoras

Zeros used to mark empty spots

import numpy
l=[1]+input()
z=numpy.nonzero(l)[0]
def f(a,b):
while b-a-1:a+=1;l[a]=l[a-1]+1;l[a]=min(l[a],l[b])
i=1
while len(z)-i:f(z[i-1],z[i]);i+=1
print l[1:]


import numpy
l=[1]+input()           # add 1 to the begining of list to handle leading zeros
z=numpy.nonzero(l)[0]   # get indices of all non-zero values
def f(a,b):             # function to fill gap, between indices a and b
while b-a-1:
a+=1
l[a]=l[a-1]+1   # set each element value 1 larger than previous element
l[a]=min(l[a],l[b])   # caps it by value at index b
i=1
while len(z)-i:
f(z[i-1],z[i])      # call function for every gap
i+=1
print l[1:]             # print result, excluding first element, added at the begining

• A few improvements: if l[a]>l[b]:l[a]=l[b] can be l[a]=min(l[a],l[b]) and then it can be at the line before that. Also, this means that that whole line can be put after the while. And I think l=input() and l=[1]+l can be l=[1]+input() (Also, in general: If you use two levels of indentation, you can use a space and a tab instead of a space and two spaces in Python 2 (see codegolf.stackexchange.com/a/58)) – wythagoras Mar 18 '17 at 10:29
• Also, next to last line can be while len(z)-i:f(z[i-1],z[i]);i+=1 when starting with i=1. – wythagoras Mar 18 '17 at 10:37
• @wythagoras Thank you, good advices. I've added this to the code – Dead Possum Mar 20 '17 at 9:10
• Nice, but it is only 163 bytes. – wythagoras Mar 21 '17 at 9:15
• @wythagoras Oh, I forgot to update byte count – Dead Possum Mar 21 '17 at 9:17

05AB1E, 31 23 bytes

Îvy_iD>ëy])¦¤URεX‚WDU}R


Try it online!

Explanation

Î                        # initialize stack with a zero
v                       # for each element y in the input list
y_i                    # if it is zero
D>                  # push top_of_the_stack + 1
ëy                # else push y
])              # end loop and wrap in a list
¦             # remove the extra zero in the beginning
¤U           # store the last (largest) element in X)
R          # reverse the list
ε     }   # apply to each item in the list
X‚W      # take the minimum of it and X
DU    # store a copy of this value in X
R  # reverse the list

• Why does this only print part of the output? In your TIO example the first 1 is missing. – Fatalize Mar 16 '17 at 13:21
• I know it's been a while, and it can probably be golfed some more, but -3 bytes with some easy golfs: Both }} can be ] to save 2 bytes; and õ-)R can be )˜R to save an additional byte. – Kevin Cruijssen Dec 14 '18 at 10:00
• @KevinCruijssen: Indeed it could :) – Emigna Dec 14 '18 at 12:31

PHP, 95777169 68 bytes

for($p=1;$n=$argv[++$i];)echo$p=$n>0?$n:++$p-in_array($p,$argv)," ";


takes input from command line arguments, prints space separated list. Run with -nr.

breakdown

for($p=1;$n=$argv[++$i];)   # loop through arguments
echo$p= # print and copy to$p:
$n>0 # if positive number ?$n                             # then argument
:++$p # else$p+1 ...
-in_array($p,$argv)         # ... -1 if $p+1 is in input values ," "; # print space  $n is truthy for any string but the empty string and "0".
$n>0 is truthy for positive numbers - and strings containing them. Perl 6, 97 bytes {my$p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}


Input is either a list of values, or a space separated string, where ? is used to stand in for the values to be replaced.

Output is a space separated string with a trailing space.

Try it

Expanded:

{                       # bare block lambda with implicit parameter ｢$_｣ my$p;              # holds the previous value of ｢$2｣ in cases where # a number is sandwiched between two replacements ~ # stringify (may not be necessary) S # replace :global / ( \d+ ' ' )? # a number followed by a space optionally ($0)

<(              # start of replacement

( '?' )+      # a list of question marks
%%            # separated by (with optional trailing)
' '           # a space

)>              # end of replacement

(\d*)           # an optional number ($2) /{ # replace with the result of: flat( +($0 || $p ) # previous value or 0 ^.. # a range that excludes the first value ( +$2 || * ), # the next value, or a Whatever star

(
+$2 xx *, # the next value repeated endlessly ($p = $2 ) # store the next value in ｢$p｣
)

)[ ^ +@1 ]      # get as many values as there are replacement chars
} /                 # add a space afterwards
}

• I don't know Perl 6, but in Perl 5 you can use $" instead of ' ' to shave a byte. Does that work here? – msh210 Mar 16 '17 at 22:53 • @msh210 Almost all of those variables are either gone, or have longer names. About the only one that still exists and has the same purpose is $!. ($/ exists but is used for $1$/[1] and $<a>\$/{ qw< a > }) – Brad Gilbert b2gills Mar 16 '17 at 23:08

JavaScript (ES6), 65 bytes

a=>a.map(e=>a=e||-~a).reduceRight((r,l)=>[r[0]<l?r[0]:l,...r],[])


Because I wanted to use reduceRight. Explanation: The map replaces each falsy value with one more than the previous value, then the reduceRight works back from the end ensuring that no value exceeds the following value.

Q, 63 bytes

{1_(|){if[y>min x;y-:1];x,y}/[(|){if[y=0;y:1+-1#x];x,y}/[0,x]]}

• Assumes ? = 0.
• Inserts a 0 at the start of the array in case of ? at start.
• Scans the array replacing 0 with 1+previous element.
• Reverses the array and scans again, replacing elements greater than previous element with previous element.
• Reverses and cuts the first element out (the added 0 from the beginning).

Use of min vs last was used to save one byte, since can assume the last element will be the min element given the descending sort of the array.

• Cool answer, welcome to the site! :) – DJMcMayhem Mar 17 '17 at 19:06

TI-Basic (TI-84 Plus CE), 81 bytes

not(L1(1))+L1(1→L1(1
For(X,2,dim(L1
If not(L1(X
1+L1(X-1→L1(X
End
For(X,dim(L1)-1,1,-1
If L1(X)>L1(X+1
L1(X+1→L1(X
End
L1

A simple port of Ørjan Johansen's Haskell answer to TI-Basic. Uses 0 as null value. Takes input from L1.

Explanation:

not(L1(1))+L1(1→L1(1 # if it starts with 0, change it to a 1
For(X,2,dim(L1     # starting at element 2:
If not(L1(X              # if the element is zero
1+L1(X-1→L1(X            # change the element to one plus the previous element
End
For(X,dim(L1)-1,1,-1 # starting at the second-last element and working backwards
If L1(X)>L1(X+1           # if the element is greater than the next
L1(X+1→L1(X               # set it equal to the next
End
L1                   # implicitly return

Java 8, 199 164 bytes

a->{for(int l=a.length,n,j,x,i=0;i<l;)if(a[i++]<1){for(n=j=i;j<l;j++)if(a[j]>0){n=j;j=l;}for(j=i-3;++j<n-1;)if(j<l)a[j+1]=j<0?1:a[j]+(l==n||a[n]>a[j]|a[n]<1?1:0);}}


Modifies the input-array instead of returning a new one to save bytes.
Uses 0 instead of ?.

Try it online.

Explanation:

a->{                      // Method with integer-array parameter and no return-type
for(int l=a.length,     //  Length of the input-array
n,j,x,              //  Temp integers
i=0;i<l;)           //  Loop i over the input-array, in the range [0, length):
if(a[i++]<1){         //   If the i'th number of the array is 0:
//   (And increase i to the next cell with i++)
for(n=j=i;          //    Set both n and j to (the new) i
j<l;j++)        //    Loop j in the range [i, length):
if(a[j]>0){       //     If the j'th number of the array is not 0:
n=j;            //      Set n to j
j=l;}           //      And set j to the length to stop the loop
//    (n is now set to the index of the first non-0 number
//     after the i-1'th number 0)
for(j=i-3;++j<n-1;) //    Loop j in the range (i-3, n-1):
if(j<l)           //     If j is still within bounds (smaller than the length)
a[j+1]=         //      Set the j+1'th position to:
j<0?          //       If j is a 'position' before the first number
1            //        Set the first cell of the array to 1
:             //       Else:
a[j]+        //        Set it to the j'th number, plus:
(l==n       //        If n is out of bounds bounds (length or larger)
||a[n]>a[j]//        Or the n'th number is larger than the j'th number
|a[n]<1?   //        Or the n'th number is a 0
:          //        Else:
0);}}     //         Leave it unchanged by adding 0


Python 2, 144124 119 bytes

l=input()
for n in range(len(l)):a=max(l[:n]+[0]);b=filter(abs,l[n:]);b=len(b)and b[0]or-~a;l[n]=l[n]or a+(b>a)
print l


Try it online!

Uses 0 instead of ?

• Doesn't b=filter(abs,l[n:]) equals to b=l[n:] ? – Dead Possum Mar 20 '17 at 12:15
• @DeadPossum filter(abs... filters out all 0's – ovs Mar 20 '17 at 12:27
• Oh, that removes zeros, I get it – Dead Possum Mar 20 '17 at 12:31

JavaScript (ES6), 59

A function with an integer array as input. The empty spots are marked with 0

a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)


Test

var F=
a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

;[[2, 4, 10]
,[1, 0, 3]
,[1, 0, 4]
,[]
,[8]
,[0]
,[0, 0, 0]
,[0, 1]
,[0, 2]
,[0, 3]
,[45, 0]
,[1, 0, 0, 0, 1]
,[3, 0, 0, 0, 0, 30]
,[1, 0, 2, 0, 3, 0, 4]
,[1, 0, 3, 0, 5, 0, 7]
,[1, 0, 3, 0, 5, 0, 0, 7]
,[1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 4, 0, 0, 6]
,[98, 0, 0, 0, 102, 0, 104]]
.forEach(a=>{
console.log(a+'\n'+F(a))
})

C# (.NET Core), 182 bytes

Using the same strategy as Ørjan Johansen.

Uses 0 in the input list to mark the unknown var.

l=>{if(l[0]<1)l[0]=1;int j;for(j=0;j<l.Length;j++)l[j]=l[j]==0?l[j-1]+1:l[j];for(j=l.Length-2;j>=0;j--)l[j]=l[j]>l[j+1]?l[j+1]:l[j];foreach(var m in l) System.Console.Write(m+" ");};


Try it online!