Batasi angka Anda dengan menjalankan Anda

15

Daftar membatasi diri

Pertimbangkan daftar L kosong yang berisi bilangan bulat tidak negatif. Sebuah run di L adalah sublist bersebelahan elemen yang sama, yang tidak bisa dibuat lagi. Misalnya, menjalankan [0,0,1,1,3,3,3,2,1,1] adalah [0,0], [1,1], [3,3,3], [2 ], [1,1] . Daftar L adalah membatasi diri jika untuk setiap bilangan bulat N ≥ 1 , jumlah kejadian N kurang dari atau sama dengan jumlah deret dari N-1 . Daftar di atas tidak membatasi diri, karena ada 4 kemunculan 1 , tetapi hanya satu kali 0 detik.

Berikut adalah contoh daftar self-limiting: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,0,0]] . Memiliki

  • 5 kali 0 dan 5 kejadian 1 ,
  • 4 kali 1 dan 2 kali 2 ,
  • 2 kali 2 dan 1 kemunculan 3 ,
  • 1 run of 3 dan 1 terjadinya 4 ,
  • 1 run of 4 dan tidak ada kejadian 5 ,
  • tidak ada kemunculan bilangan bulat lainnya.

Tugas

Tugas Anda adalah memutuskan apakah suatu daftar membatasi diri. Secara lebih eksplisit, input Anda akan berupa daftar bilangan bulat non-negatif yang tidak kosong. Jika daftar itu membatasi diri, hasil Anda akan benar; jika tidak, itu akan salah. Input dan output dapat dalam format apa pun yang masuk akal.

Hitungan byte terendah dalam setiap bahasa pemrograman adalah pemenangnya. Aturan standar kode-golf berlaku.

Uji kasus

Contoh kebenaran:

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

Contoh palsu:

[2]
[1,1,0]
[0,0,1,1,1,0,0,2]
[0,1,0,1,1,2,2,3,0,0,4,6]
[1,1,2,1,2,0,2,0,3,0,0,2,2,1,2,3,2,0,1,1,1,0,0,3,3,0]
[3,4,1,0,0,0,5,5,0,2,2,0,0,0,0,0,2,0,1,1,0,4,3,5,4,3]
[1,0,0,0,2,5,3,1,1,0,3,3,1,3,5,4,0,4,0,0,2,0,2,1,1,5,0,0,2,4,4,0,2,0,1,4,4,2,3,3,5,3,4,0,2,0,5]
[4,3,1,0,0,4,6,6,1,0,1,2,1,3,0,1,0,2,0,3,4,0,2,1,1,3,0,2,2,2,0,5,5,0,5,2,5,5,0,4,3,2,3,1,1,3,5,1,4,1,6,2,6,2,4,0,4,0,4,5,3,3,0,0,6,1,0,0,0,6,2,1,0,1,2,6,2,4]
[5,1,1,1,0,2,0,6,1,0,2,1,2,2,5,3,1,0,0,0,3,2,3,0,1,1,0,1,0,1,1,2,0,6,4,1,2,1,1,6,4,1,2,2,4,0,1,2,2,1,3,0,1,2,0,0,0,2,0,2,2,0,1,0,0,1,3,0,0,0,6,2,0,1,0,1,2,1,1,1,0,4,0,0,5,2,0,0,0,4,1,2,2,2,2,0,5,3,2,4,5,0,5]
code-golf array-manipulation decision-problem Zgarb
sumber
Bukan untuk menjadi masalah, tapi tolong pertimbangkan untuk menggunakan salah satu pendekatan dari diskusi meta ini alih-alih kebenaran / kepalsuan, karena kebenaran bukanlah properti lebih dari beberapa bahasa yang sering digunakan di sini.
FryAmTheEggman
@ LeakyNun Ya, jika tidak, kondisi gagal untuk N yang N-1 tidak ada.
Zgarb
@ Mr.Xcoder Ada [2]juga, tapi kasus-kasus seperti itu seharusnya palsu, ya.
Erik the Outgolfer
@FryAmTheEggman Saya belum melihat diskusi itu, terima kasih telah menghubungkannya. Saya akan tetap menghadapi tantangan ini, karena saya ingin memproses pendekatan yang dibahas di sana untuk sementara waktu.
Zgarb
Tentu, tetapi saya ingin menyimpan komentar di sana, karena saya merasa seperti banyak orang telah melewatkannya. Sangat penting, setidaknya bagi saya, dalam memposting dalam bahasa seperti Retina.
FryAmTheEggman

Jawaban:

5

Perl 6 , 29 byte

{bag(.grep(?*)X-1)⊆.squish}

Cobalah online!

Tantangan yang sangat bagus untuk Perl 6. Menggunakan operator subset pada Bags (set integer-weighted). Penjelasan:

{
    bag(           # Create bag of
        .grep(?*)  # non-zero elements,
        X- 1       # decremented by one.
    )
    ⊆              # Subset test.
    .squish        # "squish" removes repeated elements in each run.
                   # The result is implicitly converted to a bag
                   # counting the number of runs.
}
nwellnhof
sumber
1
Cantik. Saya melihat pendekatan Bag + subset tetapi terjebak pada hal untuk dibandingkan.
Phil H
3

JavaScript (ES6), 92 89 byte

a=>a.map(n=>g(~n,n!=p&&g(p=n)),c=[j=0],p=g=n=>c[n]=-~c[n])&&!c.some((n,i)=>i-j++|n<c[~j])

Cobalah online!

Bagaimana?

Array c [] digunakan untuk menyimpan jumlah proses dan jumlah kejadian bilangan bulat. Run disimpan pada indeks non-negatif dan kejadian integer disimpan pada indeks komplemen 1's ( c [-1] = jumlah 0 's, c [-2] = jumlah 1 ' s, dll.).

Indeks negatif sebenarnya disimpan sebagai properti dari objek array yang mendasarinya dan .some () tidak mengulanginya.

a =>                        // given the input array a[]
  a.map(n =>                // for each value n in a[]:
    g(                      //   update c[]:
      ~n,                   //     increment c[~n] (# of integer occurrences)
      n != p && g(p = n)    //     if n != p, set p to n and increment c[n] (# of runs)
    ),                      //   end of c[] update
    c = [j = 0],            //   start with c = [0] and j = 0 (used later)
    p =                     //   initialize p to a non-numeric value
    g = n => c[n] = -~c[n]  //   g = helper function to increment c[n]
  )                         // end of map()
  && !c.some((n, i) =>      // for each value n at position i in c[]:
    i - j++ |               //   make sure that i == j++
    n < c[~j]               //   and n is greater than or equal to c[~j]
  )                         // end of some()
Arnauld
sumber
3

Jelly , 10 byte

œ-ŒgḢ€‘ƊS¬

Cobalah online!

Bagaimana itu bekerja

œ-ŒgḢ€‘ƊS¬  Main link. Argument: A (array)

       Ɗ    Drei; group the three links to the left into a monadic chain.
  Œg          Group consecutive, identical elements of A into subarrays.
    Ḣ€        Head each; pop the first element of each run.
      ‘       Increment the extracted integers.
            The resulting array contains n repeated once for each run of (n-1)'s.
œ-          Perform multiset subtraction, removing one occurrence of n for each
            run of (n-1)'s.
       S    Take the sum. If only 0's remain, the sum will be 0.
        ¬   Take the logical NOT, mapping 0 to 1 and positive integers to 0.
Dennis
sumber
2

Jelly , 17 byte

ŒgḢ€ċ’}<ċ
çЀx⁸ẸṆ

Cobalah online!

Erik the Outgolfer
sumber
2

Python 3 , 94 byte

lambda a:all(sum(1for x,y in zip(a,a[1:]+[-1])if x==j!=y)>=a.count(j+1)for j in range(max(a)))

Cobalah online!

HyperNeutrino
sumber
1
sum(1for ... if x==j!=y)=> sum(x==j!=y for ...).
Tn. Xcoder
@ Mr.Xcoder oh ofc. Terima kasih!
HyperNeutrino
2

Stax , 13 9 byte

Dennis menemukan algoritma yang jauh lebih baik . Saya tanpa malu-malu porting ke stax.

ä╨²@┬↕OR♣

Jalankan dan debug secara online

Dibongkar, tidak diserang, dan berkomentar, seperti inilah bentuknya.

c   copy input
:g  get run elements
{^m increment each
|-  multiset-subtract from original input
|M! get maximum from result, and apply logical not

Jalankan yang ini

Jawaban lama:

║Ä|╤#╫∩▼cëózü

Jalankan dan debug itu

Itu beralih pada input dan memeriksa kondisi:

  • Apakah unsurnya > 0?
  • Benarkah occurrences(element) >= runs(element - 1)?

Jika salah satu dari kondisi ini berlaku untuk suatu elemen, maka elemen tersebut sesuai. Jika semua elemen sesuai, hasilnya adalah1 .

Inilah representasi yang tidak dibungkus, tidak disunat, dan komentar dari program yang sama.

O           push 1 under the input
F           iterate over the input using the rest of program
  |c        skip this iteration of the value is 0
  x#        number of occurrences of this value in input (a)
  x:g _v#   number of runs of (current-1) in input (b)
  >!        not (a > b); this will be truthy iff this element is compliant
  *         multiply with running result

Jalankan yang ini

rekursif
sumber
1

Haskell, 80 byte

import Data.List
o#l=[1|x<-l,x==o]
f x=and[(i-1)#(head<$>group x)>=i#x|i<-x,i>0]

Cobalah online!

nimi
sumber