Listes auto-limitatives

Considérons une liste non vide L contenant des entiers non négatifs. Un run en L est une sous-liste contiguë d'éléments égaux, qui ne peut pas être allongée. Par exemple, les séries de [0,0,1,1,3,3,3,2,1,1] sont [0,0], [1,1], [3,3,3], [2 ], [1,1] . La liste L est auto-limitative si pour chaque entier N ≥ 1 , le nombre d'occurrences de N est inférieur ou égal au nombre de passages de N-1 . La liste ci-dessus n'est pas limitative, car il y a 4 occurrences de 1 , mais une seule série de 0 s.

Voici un exemple de liste auto-limitative: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . Il a

• 5 séries de 0 et 5 occurrences de 1 ,
• 4 séries de 1 et 2 occurrences de 2 ,
• 2 séries de 2 et 1 occurrence de 3 ,
• 1 série de 3 et 1 occurrence de 4 ,
• 1 série de 4 et aucune occurrence de 5 ,
• aucune occurrence d'autres entiers.

La tâche

Votre tâche consiste à décider si une liste se limite d'elle-même. Plus explicitement, votre entrée doit être une liste non vide d'entiers non négatifs. Si la liste se limite d'elle-même, votre sortie doit être véridique; sinon, ce sera faux. L'entrée et la sortie peuvent être dans n'importe quel format raisonnable.

Le nombre d'octets le plus bas dans chaque langage de programmation est le gagnant. Les règles de code-golf standard s'appliquent.

Cas de test

Instances véridiques:

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

Instances de fausseté:

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

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

Essayez-le en ligne!

Très beau défi pour Perl 6. Utilise l'opérateur de sous-ensemble sur les sacs (ensembles à pondération entière). Explication:

{
    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 octets

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

Essayez-le en ligne!

Comment?

Le tableau c [] est utilisé pour stocker à la fois le nombre d'exécutions et le nombre d'occurrences entières. Les exécutions sont stockées à des indices non négatifs et les occurrences entières sont stockées à des indices de complément à 1 ( c [-1] = nombre de 0 , c [-2] = nombre de 1 , etc.).

Les indices négatifs sont en fait enregistrés en tant que propriétés de l'objet tableau sous-jacent et .some () ne les réitère pas.

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 octets

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

Essayez-le en ligne!

Gelée , 10 octets

œ-ŒgḢ€‘ƊS¬

Essayez-le en ligne!

Comment ça fonctionne

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

Gelée , 19 octets

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

Essayez-le en ligne!

Gelée , 17 octets

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

Essayez-le en ligne!

Python 3 , 94 octets

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

Essayez-le en ligne!

Japt , 21 octets

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

Testez-le en ligne!

Stax , 13 9 octets

Dennis a trouvé un bien meilleur algorithme . Je l'ai porté sans vergogne sur Stax.

ä╨²@┬↕OR♣

Exécutez-le et déboguez-le en ligne

Déballé, non golfé et commenté, voici à quoi il ressemble.

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

Exécutez celui-ci

Ancienne réponse:

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

Exécuter et déboguer

Il itère sur l'entrée et vérifie les conditions:

• Est l'élément > 0?
• Est-ce occurrences(element) >= runs(element - 1)?

Si l'une ou l'autre de ces conditions est vraie pour un élément, alors cet élément est conforme. Si tous les éléments sont conformes, le résultat est 1.

Voici la représentation commentée non emballée, non golfée du même programme.

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

Exécutez celui-ci

Haskell, 80 octets

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

Essayez-le en ligne!