Isi urutan yang meningkat dengan angka sebanyak mungkin

29

Daftar angka disebut meningkat secara monoton (atau tidak menurun) adalah setiap elemen lebih besar dari atau sama dengan elemen sebelumnya.

Misalnya, 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14meningkat secara monoton.

Dengan daftar bilangan bulat positif yang meningkat secara monoton yang memiliki jumlah tempat kosong yang dilambangkan secara acak ?, isi tempat kosong dengan bilangan bulat positif sehingga sebanyak mungkin bilangan bulat unik yang ada dalam daftar, namun jumlahnya terus meningkat secara monoton.

Mungkin ada beberapa cara untuk mencapai ini. Apa pun valid.

Keluarkan daftar yang dihasilkan.

Misalnya , jika inputnya adalah

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

dijamin bahwa tanpa tempat kosong daftar akan meningkat secara monoton

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

dan tugas Anda adalah untuk menetapkan bilangan bulat positif untuk masing ?- masing untuk memaksimalkan jumlah bilangan bulat yang berbeda dalam daftar sambil menjaganya agar tidak bertambah.

Satu tugas yang tidak valid adalah

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

karena, meskipun tidak menurun, ia hanya memiliki satu bilangan bulat yang lebih unik daripada input, yaitu 3.

Dalam contoh ini adalah mungkin untuk memasukkan enam bilangan bulat positif unik dan menjaga daftar tidak bertambah.
Beberapa cara yang mungkin adalah:

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

Salah satu dari ini (dan banyak lainnya) akan menjadi output yang valid.

Semua tempat kosong harus diisi.

Tidak ada batas atas pada bilangan bulat yang dapat dimasukkan. Tidak apa-apa jika bilangan bulat yang sangat besar dicetak dalam notasi ilmiah.

Nol bukan bilangan bulat positif dan tidak boleh dimasukkan.

Di tempat ?Anda dapat menggunakan nilai yang konsisten yang bukan bilangan bulat positif, seperti 0, -1, null, False, atau "".

Kode terpendek dalam byte menang.

Lebih banyak contoh

[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 *
Hobi Calvin
sumber
Mungkin cara yang lebih baik untuk mengutarakan masalah yang memiliki input ketat, pasangan keluaran untuk verifikasi, adalah "Berapakah jumlah angka berbeda tertinggi dalam urutan". Dengan begitu semua jawaban akan menghasilkan angka yang sama dan membuat evaluasi kasus uji jauh lebih mudah
Cruncher
@StewieGriffin Anda dapat mengasumsikan nilai daftar dan panjangnya di bawah maksimum int seperti biasa. Saya hanya bermaksud bahwa tidak apa-apa untuk memasukkan bilangan bulat yang sangat besar di akhir jika itu cara kerja algoritma Anda.
Calvin Hobi

Jawaban:

11

Haskell , 41 byte

fmengambil daftar dan mengembalikan daftar, dengan 0 mewakili ?s.

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

Pada dasarnya, daftar pemindaian pertama dari kiri, menggantikan 0s dengan satu lebih dari elemen sebelumnya (atau 0 di awal); kemudian pindai dari kanan mengurangi elemen terlalu besar untuk sama dengan yang ada di kanan mereka.

Cobalah online! (dengan pembungkus untuk mengkonversi ?s.)

Ørjan Johansen
sumber
4

Mathematica, 84 byte

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

Fungsi murni mengambil daftar sebagai argumen, di mana titik-titik kosong dilambangkan dengan Null(seperti dalam {1, Null, Null, 2, Null}) atau dihapus sama sekali (seperti dalam {1, , , 2, }), dan mengembalikan daftar yang sesuai (dalam hal ini, {1, 2, 2, 2, 3}).

Ternyata saya menggunakan algoritma yang sama seperti pada jawaban Haskell Ørjan Johansen : pertama ganti setiap Nullsatu lebih dari angka di sebelah kirinya ( //.{a___,b_,,c___}:>{a,b,b+1,c}), kemudian ganti angka yang terlalu besar dengan angka di sebelah kanannya ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Untuk menangani kemungkinan Nulls di awal daftar, kita mulai dengan menambahkan a 0( {0,##}&@@#), melakukan algoritma, lalu menghapus yang awal 0( Rest).

Ya, saya memilih Nullsebagai ganti Xatau sesuatu seperti itu untuk menyimpan secara harfiah satu byte dalam kode (kode yang seharusnya berada di antara koma b_,,c___).

Greg Martin
sumber
Hm, tambahkan 1 kata Anda? Saya menggunakan 0, karena hal-hal seperti ?, 2. Saya menduga Anda kemudian akan menghasilkan 2, 2bukan yang benar 1, 2.
Ørjan Johansen
Poin luar biasa! Untungnya perbaikannya mudah.
Greg Martin
3

C 160

Ini tidak akan pernah menang tetapi:

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

Dibutuhkan daftar dari argumen baris perintah.

Jerry Jeremiah
sumber
137 bytes
ceilingcat
3

05AB1E , 31 23 13 byte

Disimpan 10 byte berkat Grimy

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

Cobalah online!

Penjelasan

ε      ]       # 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
Emigna
sumber
Mengapa ini hanya mencetak sebagian dari output? Dalam contoh TIO Anda 1 yang pertama tidak ada.
Fatalkan
Saya tahu ini sudah lama, dan mungkin bisa bermain golf lagi, tapi -3 byte dengan beberapa golf mudah: Keduanya }}bisa ]menghemat 2 byte; dan õ-)Rdapat )˜Rmenyimpan byte tambahan.
Kevin Cruijssen
2
@KevinCruijssen: Memang bisa :)
Emigna
1
Itu masih bisa! 16 , 15 , 13 .
Grimmy
@ Grimy: Wow, terima kasih! Trik akhiran itu sangat cerdas!
Emigna
2

Pip , 25 23 21 byte

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

Mengambil input sebagai beberapa argumen baris perintah yang dipisahkan oleh spasi. Keluaran daftar hasil satu nomor per baris. Cobalah online! (Saya telah memperdaya banyak argumen baris perintah karena akan merepotkan menambahkan 25 argumen pada TIO, tetapi itu juga berfungsi seperti yang diiklankan.)

Penjelasan

Kami melanjutkan dalam dua operan. Pertama, kami mengganti setiap proses ?s dalam input dengan urutan mulai dari nomor sebelumnya dalam daftar dan bertambah satu setiap kali:

? 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

Kemudian kita mengulanginya lagi; untuk setiap nomor, kami mencetak minimum dan semua nomor di sebelah kanannya. Ini membawa angka terlalu tinggi untuk menjaga monotonitas.

                      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
DLosc
sumber
2

Python 2 dengan NumPy, 163 byte

Disimpan 8 byte berkat @wythagoras

Nol digunakan untuk menandai tempat kosong

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

Lebih mudah dibaca dengan komentar:

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
Possum Mati
sumber
1
Beberapa perbaikan: if l[a]>l[b]:l[a]=l[b]bisa l[a]=min(l[a],l[b])dan kemudian bisa di garis sebelum itu. Juga, ini berarti bahwa seluruh baris dapat diletakkan setelah while. Dan saya pikir l=input()dan l=[1]+lbisa l=[1]+input()(Juga, secara umum: Jika Anda menggunakan dua tingkat lekukan, Anda bisa menggunakan spasi dan tab alih-alih spasi dan dua spasi di Python 2 (lihat codegolf.stackexchange.com/a/58 ) )
wythagoras
1
Selain itu, di samping baris terakhir dapat len(z)-i:f(z[i-1],z[i]);i+=1ketika memulai dengan i = 1.
Wythagoras
@wythagoras Terima kasih, saran yang bagus. Saya telah menambahkan ini ke kode
Dead Possum
Bagus, tetapi hanya 163 byte.
wythagoras
@wythagoras Oh, saya lupa memperbarui jumlah byte
Dead Possum
1

PHP, 95 77 71 69 68 byte

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

mengambil input dari argumen baris perintah, mencetak daftar yang dipisahkan spasi. Jalankan dengan -nr.

kerusakan

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

$nbenar untuk string apa pun kecuali string kosong dan "0".
$n>0adalah kebenaran untuk angka positif - dan string yang mengandungnya.

Titus
sumber
1

Perl 6 , 97 byte

{my $p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}

Input adalah daftar nilai, atau string yang dipisahkan spasi, tempat ?digunakan untuk menggantikan nilai yang akan diganti.

Output adalah string yang dipisahkan spasi dengan spasi tambahan.

Cobalah

Diperluas:

{                       # 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
}
Brad Gilbert b2gills
sumber
Saya tidak tahu Perl 6, tetapi dalam Perl 5 Anda dapat menggunakan $"bukannya ' 'mencukur byte. Apakah itu berhasil di sini?
msh210
@ msh210 Hampir semua variabel tersebut hilang, atau memiliki nama yang lebih panjang. Tentang satu-satunya yang masih ada dan memiliki tujuan yang sama adalah $!. ( $/ada tetapi digunakan untuk $1$/[1]dan $<a>$/{ qw< a > })
Brad Gilbert b2gills
1

JavaScript (ES6), 65 byte

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

Karena saya ingin menggunakannya reduceRight. Penjelasan: Yang mapmenggantikan setiap nilai falsy dengan satu lebih dari nilai sebelumnya, lalu reduceRightbekerja kembali dari akhir memastikan bahwa tidak ada nilai yang melebihi nilai berikut.

Neil
sumber
1

Q, 63 byte

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

Pada dasarnya algoritma yang sama dengan jawaban Hasrell Ørjan Johansen .

  • Asumsikan? = 0.
  • Menyisipkan 0 pada awal array jika? di awal.
  • Memindai array yang menggantikan 0 dengan 1 + elemen sebelumnya.
  • Membalikkan array dan memindai lagi, mengganti elemen yang lebih besar dari elemen sebelumnya dengan elemen sebelumnya.
  • Membalik dan memotong elemen pertama (ditambahkan 0 dari awal).

Penggunaan min vs last digunakan untuk menyimpan satu byte, karena dapat mengasumsikan elemen terakhir adalah elemen min yang diberikan semacam array yang menurun.

Daniel Plainview
sumber
Jawaban keren, selamat datang di situs! :)
DJMcMayhem
1

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

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

Sebuah port sederhana dari jawaban Haskell Ørjan Johansen untuk TI-Basic. Menggunakan 0 sebagai nilai nol. Mengambil input dari L 1 .

Penjelasan:

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
pizzapants184
sumber
1

Java 8, 199 164 byte

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

Memodifikasi array input alih-alih mengembalikan yang baru untuk menghemat byte.
Gunakan 0bukan ?.

Cobalah online.

Penjelasan:

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
Kevin Cruijssen
sumber
0

Python 2 , 144 124 119 byte

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

Cobalah online!


Gunakan 0bukan?

ovs
sumber
Tidak b=filter(abs,l[n:])sama dengan b=l[n:] ?
Dead Possum
@DeadPossum filter (abs ... memfilter semua 0's
ovs
Oh, itu menghilangkan nol, saya mengerti
Dead Possum
0

JavaScript (ES6), 59

Suatu fungsi dengan array integer sebagai input. Bintik kosong ditandai dengan0

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

Uji

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

edc65
sumber
0

C # (.NET Core) , 182 byte

Menggunakan strategi yang sama dengan Ørjan Johansen.

Menggunakan 0 pada daftar input untuk menandai var yang tidak dikenal.

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+" ");};

Cobalah online!

Destroigo
sumber
0

Perl 5 -p , 99 byte

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

Cobalah online!

Xcali
sumber