Listy samoograniczające

Rozważ niepustą listę L zawierającą nieujemne liczby całkowite. Prowadzony w L oznacza ciągłą podlistę jednakowych elementów, które nie mogą być dłuższe. Na przykład przebiegi [0,0,1,1,3,3,3,3,2,1,1] wynoszą [0,0], [1,1], [3,3,3], [2 ], [1,1] . Lista L jest samoograniczająca, jeśli dla każdej liczby całkowitej N ≥ 1 liczba wystąpień N jest mniejsza lub równa liczbie przebiegów N-1 . Powyższa lista nie jest samoograniczająca, ponieważ występują 4 wystąpienia 1 , ale tylko jeden ciąg 0 s.

Oto przykład listy samoograniczającej się: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . To ma

• 5 serii 0 i 5 wystąpień 1 ,
• 4 serie po 1 i 2 wystąpieniach po 2 ,
• 2 serie 2 i 1 wystąpienie 3 ,
• 1 seria 3 i 1 wystąpienie 4 ,
• 1 seria 4 i brak wystąpień 5 ,
• brak wystąpień innych liczb całkowitych.

Zadanie

Twoim zadaniem jest zdecydować, czy lista jest samoograniczająca. Mówiąc ściślej, twój wkład będzie niepustą listą nieujemnych liczb całkowitych. Jeśli lista jest samoograniczająca, twoje wyniki będą zgodne z prawdą; w przeciwnym razie będzie to fałsz. Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie.

Najniższa liczba bajtów w każdym języku programowania jest zwycięzcą. Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

Prawdziwe przypadki:

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

Instancje Falsy:

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

Perl 6 , 29 bajtów

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

Wypróbuj online!

Bardzo miłe wyzwanie dla Perla 6. Używa operatora podzbioru w Torby (zestawy ważone liczbą całkowitą). Wyjaśnienie:

{
    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.
}

JavaScript (ES6), 92 89 bajtów

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

Wypróbuj online!

W jaki sposób?

Tablica c [] służy do przechowywania zarówno liczby uruchomień, jak i liczby wystąpień liczb całkowitych. Trasy są zapisywane w nieujemna liczbę całkowitą, a wskaźników zdarzenia są przechowywane w 1's-dopełniacza indeksach ( C [1] = liczba 0 's, C [-2] = liczba 1 jest, etc.).

Indeksy ujemne są w rzeczywistości zapisywane jako właściwości bazowego obiektu tablicowego, a .some () nie iteruje nad nimi.

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

Perl 5 -p , 49 48 44 bajtów

#!/usr/bin/perl -p
$z[$_+1]+=!/^$o$/;$z[$o=$_]--}{$_="@z"!~/.-/

Wypróbuj online!

Galaretka , 10 bajtów

œ-ŒgḢ€‘ƊS¬

Wypróbuj online!

Jak to działa

œ-Œ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.

Galaretka , 19 bajtów

ŒgḢ€ċЀṀḶ$<ċЀṀR$$Ẹ

Wypróbuj online!

Galaretka , 17 bajtów

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

Wypróbuj online!

Python 3 , 94 bajty

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

Wypróbuj online!

Japt , 21 bajtów

x o e@ó¥ mÌè¥X ¨Uè¥XÄ

Przetestuj online!

Stax , 13 9 bajtów

Dennis znalazł znacznie lepszy algorytm . Bezwstydnie przeniosłem go na stax.

ä╨²@┬↕OR♣

Uruchom i debuguj online

Rozpakowane, nieprzygotowane i skomentowane, tak to wygląda.

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

Uruchom ten

Stara odpowiedź:

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

Uruchom i debuguj

Powtarza dane wejściowe i sprawdza warunki:

• Czy ten element > 0?
• Jest occurrences(element) >= runs(element - 1)?

Jeśli którykolwiek z tych warunków jest spełniony dla elementu, ten element jest zgodny. Iff wszystkie elementy są zgodne, wynik jest 1.

Oto rozpakowana, nieposortowana, skomentowana reprezentacja tego samego programu.

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

Uruchom ten

Haskell, 80 bajtów

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

Wypróbuj online!