30
\$\begingroup\$

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 *
\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – Cruncher
    Mar 16, 2017 at 15:59
  • \$\begingroup\$ @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. \$\endgroup\$ Mar 16, 2017 at 20:24

17 Answers 17

12
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 16, 2017 at 13:15
  • \$\begingroup\$ Excellent point! Luckily the fix is easy. \$\endgroup\$ Mar 16, 2017 at 16:31
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Why does this only print part of the output? In your TIO example the first 1 is missing. \$\endgroup\$
    – Fatalize
    Mar 16, 2017 at 13:21
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 14, 2018 at 10:00
  • 2
    \$\begingroup\$ @KevinCruijssen: Indeed it could :) \$\endgroup\$
    – Emigna
    Dec 14, 2018 at 12:31
  • 2
    \$\begingroup\$ It still can! 16, 15, 13. \$\endgroup\$
    – Grimmy
    May 22, 2019 at 16:46
  • \$\begingroup\$ @Grimy: Wow, thanks! That suffix trick was really smart! \$\endgroup\$
    – Emigna
    May 22, 2019 at 19:49
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ -2 (plus test suite) \$\endgroup\$ Sep 9, 2020 at 13:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – DLosc
    Sep 10, 2020 at 0:29
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Getting rid of the index variable was really well done. \$\endgroup\$ Jun 21, 2020 at 22:03
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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)) \$\endgroup\$
    – wythagoras
    Mar 18, 2017 at 10:29
  • 1
    \$\begingroup\$ Also, next to last line can be while len(z)-i:f(z[i-1],z[i]);i+=1 when starting with i=1. \$\endgroup\$
    – wythagoras
    Mar 18, 2017 at 10:37
  • \$\begingroup\$ @wythagoras Thank you, good advices. I've added this to the code \$\endgroup\$ Mar 20, 2017 at 9:10
  • \$\begingroup\$ Nice, but it is only 163 bytes. \$\endgroup\$
    – wythagoras
    Mar 21, 2017 at 9:15
  • \$\begingroup\$ @wythagoras Oh, I forgot to update byte count \$\endgroup\$ Mar 21, 2017 at 9:17
1
\$\begingroup\$

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
}
\$\endgroup\$
2
  • \$\begingroup\$ I don't know Perl 6, but in Perl 5 you can use $" instead of ' ' to shave a byte. Does that work here? \$\endgroup\$
    – msh210
    Mar 16, 2017 at 22:53
  • \$\begingroup\$ @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 > }) \$\endgroup\$ Mar 16, 2017 at 23:08
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Cool answer, welcome to the site! :) \$\endgroup\$
    – DJMcMayhem
    Mar 17, 2017 at 19:06
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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 ?

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

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.