Listas autolimitadas
Considere uma lista não vazia L contendo números inteiros não negativos. Uma execução em L é uma sub-lista contígua de elementos iguais, que não podem ser prolongados. Por exemplo, as execuções de [0,0,1,1,3,3,3,2,1,1] são [0,0], [1,1], [3,3,3], [2 ], [1,1] . A lista L é autolimitada se, para cada número inteiro N ≥ 1 , o número de ocorrências de N for menor ou igual ao número de execuções de N-1 . A lista acima não é autolimitada, porque existem 4 ocorrências de 1 , mas apenas uma execução de 0 s.
Aqui está um exemplo de uma lista autolimitada: [0,0,3,4,1,0,2,1,1,0,2,1,0,0,0,1,0] . Tem
- 5 execuções de 0 e 5 ocorrências de 1 ,
- 4 execuções de 1 e 2 ocorrências de 2 ,
- 2 execuções de 2 e 1 ocorrência de 3 ,
- 1 corrida de 3 e 1 ocorrência de 4 ,
- 1 execução de 4 e nenhuma ocorrência de 5 ,
- sem ocorrências de outros números inteiros.
A tarefa
Sua tarefa é decidir se uma lista é autolimitada. Mais explicitamente, sua entrada deve ser uma lista não vazia de números inteiros não negativos. Se a lista for autolimitada, sua saída será verdadeira; caso contrário, será falso. A entrada e a saída podem estar em qualquer formato razoável.
A menor contagem de bytes em cada linguagem de programação é a vencedora. Aplicam-se as regras de código-golfe padrão .
Casos de teste
Instâncias verdadeiras:
[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]
Instâncias de falsidade:
[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]
[2]
também, mas esses casos devem ser falsos, sim.Respostas:
Perl 6 , 29 bytes
Experimente online!
Desafio muito bom para o Perl 6. Usa o operador de subconjunto em Bags (conjuntos com pesos inteiros). Explicação:
fonte
JavaScript (ES6),
9289 bytesExperimente online!
Quão?
A matriz c [] é usada para armazenar o número de execuções e o número de ocorrências inteiras. As execuções são armazenadas em índices não negativos e as ocorrências inteiras são armazenadas em índices complementares de 1 ( c [-1] = número de 0 's, c [-2] = número de 1 ' s, etc.).
Os índices negativos são realmente salvos como propriedades do objeto de matriz subjacente e .some () não itera sobre eles.
fonte
Perl 5
-p
,494844 bytesExperimente online!
fonte
Gelatina , 10 bytes
Experimente online!
Como funciona
fonte
Geléia , 19 bytes
Experimente online!
fonte
Gelatina , 17 bytes
Experimente online!
fonte
Python 3 , 94 bytes
Experimente online!
fonte
sum(1for ... if x==j!=y)
=>sum(x==j!=y for ...)
.Japonês , 21 bytes
Teste online!
fonte
Stax ,
139 bytesDennis encontrou um algoritmo muito melhor . Eu descaradamente portado para stax.
Execute e depure on-line
Descompactado, não jogado e comentado, é assim que parece.
Execute este
Resposta antiga:
Execute e depure
Ele itera sobre a entrada e verifica as condições:
> 0
?occurrences(element) >= runs(element - 1)
?Se qualquer uma dessas condições for verdadeira para um elemento, esse elemento será compatível. Se todos os elementos são compatíveis, o resultado é
1
.Aqui está a representação descompactada, não destruída e comentada do mesmo programa.
Execute este
fonte
Haskell, 80 bytes
Experimente online!
fonte