Fill in an increasing sequence with as many numbers as possible

Question

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 *

• Cruncher: 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
• Calvin's Hobbies: @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.

Answer 1

Haskell, 41 bytes

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.)

Answer 2

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___).

• Ørjan Johansen: 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.
• Greg Martin: Excellent point! Luckily the fix is easy.

Answer 3

Pip, (削除) 25 (削除ここまで) (削除) 23 (削除ここまで) 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

Answer 4

05AB1E, (削除) 31 (削除ここまで) (削除) 23 (削除ここまで) 13 bytes

Saved 10 bytes thanks to Grimy

ε®X:D>U].sR€ß

Try it online!

Explanation

ε ] # apply to each number in input
 ®X: # replace -1 with X (initially 1)
 D>U # store current_number+1 in X
 .s # get a list of suffixes
 R # reverse
 ۧ # take the minimum of each

• Fatalize: Why does this only print part of the output? In your TIO example the first 1 is missing.
• Kevin Cruijssen: 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.
• Emigna: @KevinCruijssen: Indeed it could :)
• Grimmy: It still can! 16, 15, 13.
• Emigna: @Grimy: Wow, thanks! That suffix trick was really smart!

Answer 5

Brachylog, (削除) 43 (削除ここまで) (削除) 27 (削除ここまで) (削除) 24 (削除ここまで) 22 bytes

-2 bytes thanks to Unrelated String

Ė|a0f⟨{a1+0}c+⌉⟩ma1f⌋m

Uses 0 as the blank value. Try it online!

How?

Lots of prefixes and suffixes.

We want to perform a two-step process that goes like this:

[0, 1, 0, 0, 0, 3, 0, 0]
[1, 1, 2, 3, 4, 3, 4, 5]
[1, 1, 2, 3, 3, 3, 4, 5]

For the first step, we look at each prefix of the list:

[0]
[0, 1]
[0, 1, 0]
...
[0, 1, 0, 0, 0, 3, 0, 0]

We're going to map each prefix to what its last number would be if we had already completed step 1:

[1] -> 1
[1, 1] -> 1
[1, 1, 2] -> 2
...
[1, 1, 2, 3, 4, 3, 4, 5] -> 5

Observe that nonzero final numbers stay the same, while final zeros are replaced with the result of counting up from the last previous nonzero number (or from 1, if there is no previous nonzero number). Since the list is nondecreasing, the last previous nonzero number is simply the max of the prefix, so our calculation boils down to (max value) + (number of trailing 0s). We collect all the results in a list, and step 1 is completed.

For step 2, we simply take each suffix of the step 1 result and replace it with its minimum.

Code with explanation

Ė|a0f⟨{a1+0}c+⌉⟩ma1f⌋m
Ė If input is empty list, output is empty list
 | Otherwise
 a0f Find all (nonempty) prefixes of input list
 m For each prefix:
 Find how many 0s it ends with:
 { }c Count the number of ways to satisfy this predicate:
 a1 Get a suffix
 + whose sum
 0 is 0
 The numbers are nonnegative, so this means they are all 0
 ⌉ Get the maximum number in the prefix
 ⟨ + ⟩ Add that to the number of trailing 0s
 a1f Find all (nonempty) suffixes of the resulting list
 ⌋m Take the minimum of each

• Unrelated String: -2 (plus test suite)
• DLosc: @UnrelatedString Ah, very nice! I usually forget the Variables and Constants page is there, but of course there would be a 1-byte builtin for empty list.

Answer 6

C 127

Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter

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

Try it online!

• Jerry Jeremiah: @ceilingcat Getting rid of the index variable was really well done.

Answer 7

PHP, (削除) 95 (削除ここまで) (削除) 77 (削除ここまで) (削除) 71 (削除ここまで) (削除) 69 (削除ここまで) 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.

Answer 8

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

More readable with comments:

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

• wythagoras: 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: Also, next to last line can be while len(z)-i:f(z[i-1],z[i]);i+=1 when starting with i=1.
• Dead Possum: @wythagoras Thank you, good advices. I've added this to the code
• wythagoras: Nice, but it is only 163 bytes.
• Dead Possum: @wythagoras Oh, I forgot to update byte count

Answer 9

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
}

• msh210: I don't know Perl 6, but in Perl 5 you can use $" instead of ' ' to shave a byte. Does that work here?
• Brad Gilbert b2gills: @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 > })

Answer 10

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.

Answer 11

Q, 63 bytes

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

Essentially the same algorithm as Ørjan Johansen's Haskell answer.

• 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.

• DJMcMayhem: Cool answer, welcome to the site! :)

Answer 12

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 L₁.

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

Answer 13

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
 1 // Add 1
 : // Else:
 0);}} // Leave it unchanged by adding 0

Answer 14

Python 2, (削除) 144 (削除ここまで) (削除) 124 (削除ここまで) 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 ?

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

Answer 15

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

Answer 16

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!

Answer 17

Perl 5 -p, 99 bytes

s,(\d+ )?\K((\? )+)(?=(\d+)),$d=1ドル;$l=4ドル;2ドル=~s/\?/$d<$l?++$d:$l/rge,ge;($d)=/.*( \d+)/;s/\?/++$d/ge

Try it online!