Urutan yang bisa ditumpuk

29

Anda menangani kartu berlabel 0 hingga 9 dari tumpukan kartu sekaligus, membentuk tumpukan yang dimulai dari 0 dan dihitung dengan 1.

  • Saat Anda memberikan 0, Anda meletakkannya di atas meja untuk memulai tumpukan baru.
  • Ketika Anda memberikan kartu lain, Anda menumpuknya di atas kartu yang nilainya persis lebih rendah, dan menutupinya. Jika tidak ada kartu seperti itu, dek tidak dapat ditumpuk.

Diberi geladak, tentukan apakah bisa ditumpuk ketika dibagikan sesuai urutan. Dengan cara yang sama, diberikan daftar digit, putuskan apakah ia dapat dipartisi menjadi disjoint selanjutnya dari masing-masing bentuk0,1,..,k

Contoh

Ambil dek 0012312425. Dua kartu pertama adalah 0, jadi mereka naik ke atas meja:

Stacks: 00

  Deck: 12312425

Selanjutnya, kita berurusan dengan 1, yang berlangsung 0, tidak masalah yang:

        1
Stacks: 00

  Deck: 2312425

Kami kemudian menangani 2di atas yang baru saja ditempatkan 1, dan 3di atasnya.

        3
        2
        1
Stacks: 00

  Deck: 12425

Selanjutnya, 1, 2dan ditempatkan di atas tumpukan pertama dan 4atas yang kedua. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Sekarang, kita perlu menempatkan 2, tetapi tidak ada 1di atas tumpukan. Jadi, dek ini tidak bisa ditumpuk.

Input: Daftar angka 0-9 yang tidak kosong, atau stringnya. Anda tidak dapat berasumsi bahwa 0 akan selalu ada di input.

Keluaran : Salah satu dari dua nilai konsisten yang berbeda, satu untuk urutan yang dapat ditumpuk dan satu untuk yang tidak dapat ditumpuk

Kasus uji:

Stackable:

0
01
01234
00011122234567890
012031
0120304511627328390

Tidak bisa ditumpuk:

1
021
0001111
0012312425
012301210
000112223

Untuk kenyamanan, sebagai daftar:

[0]
[0, 1]
[0, 1, 2, 3, 4]
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]

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

Dikelompokkan:

[[0], [0, 1], [0, 1, 2, 3, 4], [0, 0, 0, 1, 1, 1, 2, 2, 2, 3], [0, 1, 2, 0, 3, 1], [0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]]
[[1], [0, 2, 1], [0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 2, 3, 1, 2, 4, 2, 5]]

Papan peringkat:

Tampilkan cuplikan kode

code-golf sequence decision-problem subsequence Tidak
sumber
Bisakah kita mengasumsikan batas pada panjang daftar?
orlp
@ orlp Tidak ada batasan eksplisit.
xnor
@ xnor dia mungkin meminta pembenaran untuk menulis int a[99]di C
Leaky Nun
@LuisMendo Anda mungkin, saya katakan "tidak kosong".
xnor
@xnor Ah, maaf, saya tidak melihat itu. Bisakah array berbasis 1? Artinya, angka dari 1ke10
Luis Mendo

Jawaban:

6

Haskell , 55 byte

Fungsi anonim mengambil daftar bilangan bulat dan mengembalikan a Bool.

Penggunaan: (all(<1).foldr(?)[]) [0,1,2,3,4].

all(<1).foldr(?)[]
m?l|(p,r)<-span(/=m+1)l=m:p++drop 1r

Cobalah online!

Bagaimana itu bekerja

  • foldr(?)[]melipat argumen daftar dari menggunakan kanan ke kiri ?, dimulai dengan daftar kosong. Hasilnya adalah daftar angka dalam daftar yang tidak cocok di atas angka sebelumnya.
  • all(<1) menguji apakah satu-satunya angka yang tidak pas di atas angka sebelumnya adalah nol.
  • m?lmenambahkan nomor mke daftar lnomor yang tidak sesuai. Jika m+1sudah ada dalam daftar, sekarang dapat dihapus karena cocok di atas m.
    • (p,r)<-span(/=m+1)lmembagi daftar lmenjadi dua bagian pdan rpada contoh pertama nomor tersebut m+1. Jika tidak ada, bagian kanan rakan kosong.
    • m:p++drop 1r prepends m pada bagian yang dibagi. Jika rbukan kosong, maka itu harus dimulai dengan m+1, yang dihapus oleh drop 1.
Ørjan Johansen
sumber
Ide bagus melakukan penumpukan secara terbalik! Saya mencoba memperluas ?secara rekursif, tetapi mendapatkan panjang yang sama .
xnor
54 byte denganData.List.delete
H.PWiz
5

Sekam , 9 byte

Λ¬ḞS:o-→ø

Cobalah online!

Kembali 1 untuk deck yang dapat ditumpuk dan 0untuk deck yang tidak dapat ditumpuk.

Sepertinya Ørjan Johansen di jawaban Haskell-nya sudah muncul dengan algoritma yang sama, tetapi dalam Husk ini jelas jauh lebih ringkas.

Penjelasan

Kami mengambil masalah dari sisi lain: membalik geladak dan membuat tumpukan menurun. Jika setelah melewati semua dek semua tumpukan memiliki 0 di atas, dek tersebut dapat ditumpuk.

Λ¬ḞS:(-→)ø
         ø    Starting with the empty list (each element of this list will be the top card
              of a stack)
  ḞS          Traverse the input from right to left. For each card:
      -→        Remove the successor of this card from our list (if present)
    :           Add this card to our list
Λ¬            At the end, check if all the cards in our list are zeroes (falsy)
Leo
sumber
4

Jelly , 15 11 byte

‘Ṭ€+\I>0FS¬

Cobalah online!

Biarawati Bocor
sumber
Oh bagus sekali. Akan ‘Ṭ€+\I>0FṀbekerja selalu?
Jonathan Allan
@ JonathanAllan Yah, mengingat aturan 2 nilai yang konsisten seharusnya.
Erik the Outgolfer
4

C (gcc), 74 73 byte

f(int*l){int s[10]={},r=1;for(;~*l;s[*l++]++)r*=!*l||s[*l-1]--;return r;}

Membutuhkan array input untuk menandai akhir dengan -1. Contoh penggunaan:

int main(int argc, char** argv) {
    int a[] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1};
    printf("%d\n",  f(a));
    return 0;
}
orlp
sumber
Apa yang salah dengan polos return r?
Leaky Nun
4

Retina , 42 byte

O$#`(.)(?<=(\1.*?)*)
$#2
.
$*1,
^(,|1\1)+$

Cobalah online!

Penjelasan

O$#`(.)(?<=(\1.*?)*)
$#2

Ini mengurutkan digit, secara stabil, dengan seberapa sering digit yang sama telah terjadi sebelumnya. Akibatnya, ini merangkum berbagai calon kandidat bersama-sama. String yang dihasilkan pertama-tama akan memiliki kemunculan pertama dari setiap digit, dan kemudian kemunculan kedua dari setiap digit dan seterusnya. Dalam input yang dapat ditumpuk, hasilnya akan terlihat seperti 0123...0123...0123..., di mana masing-masing substring ini dapat berakhir pada titik mana pun.

Paling mudah untuk menentukan apakah input memiliki pola seperti ini di unary.

.
$*1,

Kami mengganti setiap digit n dengan n 1 s, diikuti oleh koma untuk memisahkan masing-masing digit.

^(,|1\1)+$

Akhirnya kami menggunakan referensi maju untuk mencocokkan berturut-turut peningkatan angka. Kami mencoba mencocokkan seluruh string baik dengan mencocokkan satu koma (mewakili 0 , yang memulai proses baru) atau dengan mencocokkan hal sebelumnya yang didahului oleh tambahan 1, yang hanya berfungsi jika digit saat ini adalah penerus dari yang sebelumnya.

Martin Ender
sumber
3

TI-Basic (83 series), 25 byte (49 karakter)

:min(seq(min(cumSum(Ans=I)≤cumSum(Ans=I-1)),I,1,9

Bagaimana itu bekerja

Mengambil input sebagai daftar di Ans. Output 1untuk input stackable,0 jika tidak.

Untuk masing-masing I, cumSum(Ans=I)hitung daftar berapa kali Itelah terjadi di setiap segmen awal, jadi min(cumSum(Ans=I)≤cumSum(Ans=I-1))hanya 1 jika, di setiap posisi, kami telah melihat I-1setidaknya sebanyak kali I. Ekspresi keseluruhan adalah 1setiap kali ini berlaku untuk masing-masing I.

Misha Lavrov
sumber
3

JavaScript (ES6), 61 45 40 byte

Mengambil input sebagai daftar.

a=>a.every(k=>a[~k]=!k|a[-k]--&&-~a[~k])

Uji kasus

Tampilkan cuplikan kode

Bagaimana?

Untuk setiap nilai 0 ... 9 , kami melacak jumlah tumpukan yang tersedia dengan kartu sebelumnya di atas. Penghitung ini disimpan dalam [-9] ke [0] , di mana a [] adalah array input asli. Satu-satunya penghitung yang bertabrakan dengan data input adalah [0] , tetapi kami tidak terlalu peduli dengan yang ini karena 1) kartu berlabel 0 selalu diizinkan dan tetap harus diproses secara terpisah dan 2) nilai input a [0 ] diproses sebelum memiliki kesempatan untuk diperbarui.

a => a.every(k =>  // given the input array a, for each card k in a:
  a[~k] =          // the card is valid if:
    !k |           //   - it's a 0 or
    a[-k]-- &&     //   - there's at least one stack with the card k-1 atop
    -~a[~k]        // in which case we allow a new card k+1 and go on with the next card
)                  // otherwise, every() fails immediately
Arnauld
sumber
Anda lebih cepat dari saya: o
Leaky Nun
@ LeakyNun Anda harus pergi selama 20 menit ...;)
Arnauld
2

MATL , 16 byte

0*GQ"@yQy=f1)(]a

Input adalah array angka.

Kode output 1dalam STDOUT jika input dapat ditumpuk, atau keluar dengan kesalahan dan output kosong dalam STDOUT jika input tidak dapat ditumpuk.

Cobalah online!

Luis Mendo
sumber
2

Retina , 110 byte

+`0((.*?)1((.*?)2((.*?)3((.*?)4((.*?)5((.*?)6((.*?)7((.*?)8((.*?)9)?)?)?)?)?)?)?)?)?
$2$4$6$8$10$12$14$16$+
^$

Cobalah online! Tautan termasuk kasus uji. Saya tidak sering menggunakan $16...

Neil
sumber
2

Mathematica, 80 byte

Catch[Fold[#~Join~{-1}/.{{p___,#2-1,q___}:>{p,#2,q},-1:>Throw[1<0]}&,{},#];1>0]&
JungHwan Min
sumber
2

Python 2 , 69 61 55 47 46 byte

s=[]
for c in input():s+=-1,;s[s.index(c-1)]=c

Cobalah online!

Output adalah error/ no error.

TFeld
sumber
46 byte
ov
2

R , 88 byte

function(d){s={}
for(e in d)if(!e)s=c(s,0)else{k=match(e,s+1)
if(is.na(k))T=F
s[k]=e}
T}

Cobalah online!

Fungsi yang mengambil vektor R; kembali TRUEuntuk stackable danFALSE unstackable.

Penjelasan:

function(d){
 s <- {}              # initialize the stacks as empty
 for(e in d){         # iterate over the deck
  if(!e)              # if e is zero
   s <- c(s,0)        # start a new stack
  else {              # otherwise
   k <- match(e,s+1)  # find where e should go in s, NA if not there
   if(is.na(k))       # if no match (unstackable)
    T <- F            # set T to F (False)
   s[k] <- e          # set s[k] to e
  }
 T                    # return the value of T, which is TRUE by default and only gets changed in the loop to F.
}
Giuseppe
sumber
2

Nim, 133 byte

proc s(d:seq[int]):int=
 var
  t= @[0]
  r=1
 for c in d:(t.add(0);var f=0;for i,s in t.pairs:(if s==c:(t[i]=c+1;f=1;break));r*=f)
 r

1 jika itu bekerja; 0jika tidak.

Harus menarik beberapa bisnis yang funky untuk menghadapi perubahan variabel dalam for-loop, oh well.

Quelklef
sumber
1

Haskell , 77 75 byte

import Data.List
g[]=1<3
g(x:r)|s<-r\\[x-1]=g r&&(x<1||s/=r&&g s)
g.reverse

Cobalah online! Penggunaan: g.reverse $ [0,1,2]. Kembali Trueuntuk input yang bisa ditumpuk dan Falsesebaliknya.

Ini adalah solusi rekursif yang melintasi daftar yang diberikan dari belakang ke depan. Ini mengimplementasikan pengamatan itu

  • daftar kosong dapat ditumpuk.
  • daftar yang tidak kosong dengan awalan rdan elemen terakhir xdapat ditumpuk jika rdapat ditumpuk dan apakah xnol atau keduanya x-1muncul di rdan rdengan x-1dihapus juga dapat ditumpuk.
Laikoni
sumber
1

Java 8, 168 150 142 byte

a->{int x[]=new int[a.length],s=0,i;a:for(int n:a){if(n<1){s++;continue;}for(i=0;i<s;i++)if(x[i]==n-1){x[i]=n;continue a;}return 0;}return 1;}

Pengembalian 0/ 1apakah itu dapat ditumpuk dengan benar atau tidak.

Penjelasan:

Coba di sini.

a->{                         // Method with integer-array parameter and integer return-type
  int x[]=new int[a.length], //  Array for the stacks, (max) size equal to input-size
      s=0,                   //  Amount of stacks, starting at 0
      i;                     //  Index integer
  a:for(int n:a){            //  Loop (1) over the input
    if(n<1){                 //   If the current item is a zero:
      s++;                   //    Increase amount of stacks `s` by 1
      continue;}             //    And go to the next iteration
    for(i=0;i<s;i++)         //   Inner loop (2) over the stacks
      if(x[i]==n-1){         //    If a top item of a stack equals the current item - 1:
        x[i]=n;              //     Set this item in the stacks-array
        continue a;}         //     And go to the next iteration of loop (1)
    return 0;                //   If we haven't encountered a `continue`, return 0
  }                          //  End of loop (1)
  return 1;                  //  Return 1 if we were able to correctly stack everything
}                            // End of method
Kevin Cruijssen
sumber
1

C, 248 byte

Catatan: Untuk mencetak status pengembalian, ketik "echo $ status" ke terminal

Status pengembalian 0: Tidak bisa ditumpuk

Status pengembalian 1: Stackable

Penjelasan: Menambahkan elemen array dengan indeks yang setara dengan digit saat ini di tumpukan. Kemudian, program memeriksa apakah elemen array yang baru saja bertambah ini lebih besar dari elemen sebelumnya. Jika demikian, kembalikan 0. Lain jika program berhasil sampai akhir array mengembalikan 1.

 main(int argc, char ** argv)
{
    static int stack[10];

    while ( *++argv != 0x0 )
    {
        stack[**argv - 0x30]++;

        if ( **argv - 0x30 > 0 )
        {
            if ( stack[**argv - 0x30] > stack[**argv - 0x30 - 1] )
            {
                return 0;
            }

        }

    }   

    return 1;
}
T. Salim
sumber
3
Selamat datang di Golf Code! Kode Anda dan bytecount Anda harus cocok, jadi pastikan untuk memberikan versi kode yang sepenuhnya golf. Versi ungolfed adalah yang opsional.
Stephen
0

Jelly , 15 byte

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ

Tautan monadik mengambil daftar bilangan bulat non-negatif dan kembali 0jika dapat ditumpuk atau1 jika tidak dapat ditumpuk.

Cobalah online!

Bagaimana?

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ - Link: list
             ¿  - while loop:
      µ     µ   - ...condition chain:
       0        -      literal zero
         Ṁ      -      maximum of current list
        r       -      inclusive range = [0,1,2,...,max(list)]
           Q    -      de-duplicate list (unique values in order of appearance)
          ⁼     -      equal?
                - ...do:
   ŒQ           -      distinct sieve (1s at first occurrences 0s elsewhere)
  @             -      use swapped arguments:
œp              -        partition (the list) at truthy values (of the distinct sieve)
     Ẏ          -      tighten (makes the list flat again ready for the next loop)
              Ẹ - any truthy? 1 if the resulting list has any non-zero integers remaining
                -           - effectively isNotEmpty for our purposes since a list of only
                -             zeros gets reduced to an empty list via the loop.
Jonathan Allan
sumber
Langkah Anda: P: P
Leaky Nun
Heh, baik saya ragu saya akan mengalahkan 11 (atau 10 ?!) dan harus tidur: D
Jonathan Allan
0

Japt , 16 byte

£=k_¥T©°T}T=0ÃUd

Uji secara online! Output falseuntuk stackable,true untuk non-stackable.

Penjelasan

 £   = k_  ¥ T© ° T}T=0Ã Ud
UmX{U=UkZ{Z==T&&++T}T=0} Ud    Ungolfed
                               Implicit: U = input array
UmX{                   }       For each item X in the array:
                    T=0          Set T to 0.
      UkZ{         }             Remove the items Z where
          Z==T&&++T              Z == T (and if so, increment T).
                                 This has the effect of removing the largest stack.
    U=                           Reset U to the result.
                               This process is repeated U.length times, which is
                               evidently enough to handle any U.
                         Ud    Return whether there are any truthy items in U.
                               Any items not part of a stack are non-zero/truthy,
                               so this works for every possible case.
Produksi ETH
sumber
0

05AB1E , 25 byte

ηε[DõQ#ZƒDNåiNõ.;Dëˆ#]¯OĀ

Tantangannya tidak terlihat terlalu sulit, tapi cukup sulit di 05AB1E (setidaknya untuk saya ..)

Output 0jika stackable, dan 1jika tidak stackable.

Cobalah online atau verifikasi semua kasus uji .

Penjelasan:

η             # Prefixes of the (implicit) input
              #  i.e. '012031' → ['0','01','012','0120','01203','012031']
              #  i.e. `021` → ['0','02','021']
 ε            # Map each to:
  [           # Start an infinite inner loop
   D          # Duplicate the current value
    õQ#       # If it's an empty String, stop the infinite loop
   Z          # Get the maximum (without popping)
              #  i.e. '01203' → 3
              #  i.e. '02' → 2
    ƒ         # Inner loop `N` in the range [0,max]
     D        # Duplicate the current value
      Nåi     # If it contains the current digit `N`
              #  i.e. '01203' and 1 → 1 (truthy)
              #  i.e. '02' and 1 → 0 (falsey)
         Nõ.; # Remove the first one (by replacing the first `N` with an empty string)
              #  i.e. '1203' and 1 → '203'
         D    # And duplicate it again for the next iteration of the inner loop
      ë       # Else (does not contain the digit `N`):
       ˆ      # Push `N` to the global stack
        #     # And break the infinite loop
 ]            # Close the if-else, inner loop, infinite loop, and mapping (short for `}}}}`)
  ¯           # Push the global stack
   O          # Take the sum
              #  i.e. [] → 0
              #  i.e. ['2'] → 2
    Ā         # And get the trutified value of that (which we implicitly output as result)
              #  i.e. 0 → 0
              #  i.e. 2 → 1
Kevin Cruijssen
sumber
0

Java 8, 87 byte

Alih-alih membangun tumpukan saya hanya menghitung jika elemen tidak bisa ditumpuk pada elemen sebelumnya, dan mengembalikan 0 ketika elemen unstackable ditemukan. Jika saya mencapai akhir, seluruh string dapat ditumpuk dan 1 dikembalikan:

s->{int l[]=new int[10];for(int n:s)if(n!=0&&l[n]>=l[n-1]||l[n]++<0)return 0;return 1;}

Cobalah online!

Penjelasan:

s->{
  int l[]=new int[10];                # initialise the counts of each digit encountered prefix of element, all initialised to 0
  for(int n:s)                        # Iterate over all entries in input
    if(n!=0&&l[n]>=l[n-1]||++l[n]<0)  # Check if the element is stackable on the previous elements. Last check is always evaluated and false, but the sideeffect is to add the element to the handled, prefixed element og the next element.  
      return 0;                       # Unstackable
  return 1;                           # No unstackable elements, so the result is stackable
}
tfantonsen
sumber