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 *

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

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

Answer 5

Brachylog, 43 27 24 22 bytes

-2 bytes thanks to Unrelated String

Ė|a₀ᶠ⟨{a₁+0}ᶜ+⌉⟩ᵐa₁ᶠ⌋ᵐ

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

Ė|a₀ᶠ⟨{a₁+0}ᶜ+⌉⟩ᵐa₁ᶠ⌋ᵐ

Ė                       If input is empty list, output is empty list
 |                      Otherwise
  a₀ᶠ                   Find all (nonempty) prefixes of input list
                ᵐ       For each prefix:
                         Find how many 0s it ends with:
      {    }ᶜ             Count the number of ways to satisfy this predicate:
       a₁                  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
                 a₁ᶠ    Find all (nonempty) suffixes of the resulting list
                    ⌋ᵐ  Take the minimum of each

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!

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

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
}

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.

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 ?

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!