Listas autolimitadas

Considere una lista no vacía L que contiene enteros no negativos. Una ejecución en L es una sublista contigua de elementos iguales, que no se puede alargar. Por ejemplo, las corridas de [0,0,1,1,3,3,3,2,1,1] son [0,0], [1,1], [3,3,3], [2 ], [1,1] . La lista L es autolimitada si para cada número entero N ≥ 1 , el número de ocurrencias de N es menor o igual que el número de corridas de N-1 . La lista anterior no es autolimitada, porque hay 4 ocurrencias de 1 , pero solo una ejecución de 0 s.

Aquí hay un ejemplo de una lista autolimitada: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . Tiene

• 5 carreras de 0 y 5 ocurrencias de 1 ,
• 4 carreras de 1 y 2 ocurrencias de 2 ,
• 2 carreras de 2 y 1 ocurrencia de 3 ,
• 1 corrida de 3 y 1 ocurrencia de 4 ,
• 1 corrida de 4 y no ocurrencias de 5 ,
• sin ocurrencias de otros enteros.

La tarea

Su tarea es decidir si una lista es autolimitada. Más explícitamente, su entrada será una lista no vacía de enteros no negativos. Si la lista es autolimitada, su salida será verdadera; de lo contrario, será falso. La entrada y salida pueden estar en cualquier formato razonable.

El conteo de bytes más bajo en cada lenguaje de programación es el ganador. Se aplican reglas estándar de código de golf .

Casos de prueba

Ejemplos de verdad:

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

Instancias falsas:

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

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

Pruébalo en línea!

Muy buen desafío para Perl 6. Utiliza el operador de subconjunto en Bolsas (conjuntos ponderados de enteros). Explicación:

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

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

Pruébalo en línea!

¿Cómo?

La matriz c [] se utiliza para almacenar tanto el número de ejecuciones como el número de ocurrencias de enteros. Las ejecuciones se almacenan en índices no negativos y las ocurrencias de enteros se almacenan en índices complementarios de 1 ( c [-1] = número de 0 's, c [-2] = número de 1 ' s, etc.).

Los índices negativos se guardan realmente como propiedades del objeto de matriz subyacente y .some () no itera sobre ellos.

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 bytes

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

Pruébalo en línea!

Jalea , 10 bytes

œ-ŒgḢ€‘ƊS¬

Pruébalo en línea!

Cómo funciona

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

Jalea , 19 bytes

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

Pruébalo en línea!

Jalea , 17 bytes

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

Pruébalo en línea!

Python 3 , 94 bytes

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

Pruébalo en línea!

Japt , 21 bytes

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

¡Pruébalo en línea!

Stax , 13 9 bytes

Dennis encontró un algoritmo mucho mejor . Lo porté descaradamente a Stax.

ä╨²@┬↕OR♣

Ejecútelo y depúrelo en línea

Desempaquetado, sin golf y comentado, así es como se ve.

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

Ejecute este

Vieja respuesta:

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

Ejecutar y depurarlo

Se itera sobre la entrada y verifica las condiciones:

• Es el elemento > 0?
• Es occurrences(element) >= runs(element - 1)?

Si alguna de estas condiciones es verdadera para un elemento, entonces ese elemento es compatible. Si todos los elementos cumplen, el resultado es1 .

Aquí está la representación comentada, desempaquetada, sin golf, del mismo programa.

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

Ejecute este

Haskell, 80 bytes

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

Pruébalo en línea!