Segurança em números

22

Escreva um programa para determinar se uma sequência periódica de números inteiros positivos tem a propriedade de que, para cada número inteiro que nocorre na sequência, nunca há mais do quen outros números inteiros entre duas ocorrências consecutivas de n.

Por exemplo, 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...possui esta propriedade: todo par de ocorrências consecutivas de 2no máximo dois números inteiros entre eles (como 2, 3, 5, 2e 2, 3, 6, 2; todo par de ocorrências consecutivas de 3no máximo três números inteiros entre eles; e o mesmo para5 e 6.

No entanto, 2, 3, 5, 2, 3, 4, 2, 3, 5, 2, 3, 4, ...não possui essa propriedade: duas ocorrências consecutivas de 4, a saber4, 2, 3, 5, 2, 3, 4 , possuem mais de quatro números inteiros entre elas.

Entrada : uma representação razoável de uma sequência periódica de números inteiros positivos. Por exemplo, uma lista finita como {2, 3, 5, 2, 3, 6}pode representar a primeira sequência infinita2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ... acima. (Nesse caso, o problema pode ser indicado para listas finitas que são agrupadas em vez de para listas periódicas infinitas.)

Saída : um valor de verdade / falsidade.

Exemplos de verdade:

{1}
{8, 9}
{2, 3, 4}
{5, 5, 3, 3, 6}
{2, 3, 5, 2, 3, 6}
{6, 7, 3, 5, 3, 7}
{9, 4, 6, 7, 4, 5}
{1, 1, 1, 1, 1, 100, 1}
{1, 9, 1, 8, 1, 7, 1, 11}

Exemplos de falsidade:

{1, 2, 3}
{2, 3, 9, 5}
{3, 5, 4, 4, 6}
{2, 3, 5, 2, 3, 4}
{3, 5, 7, 5, 9, 3, 7}
{5, 6, 7, 8, 9, 10, 11}
{1, 9, 1, 8, 1, 6, 1, 11}

Isso é , então o código mais curto vence. Respostas em todas as línguas são encorajadas.

Greg Martin
fonte
A lista de entrada sempre contém pelo menos um elemento?
N
2
@nimi, caso contrário, não representaria uma sequência periódica infinita.
Martin Ender
1
Se você pegar a sequência thue-morse e adicionar qualquer número inteiro positivo positivo maior que 1 a cada termo, você terá uma sequência infinita aperiódica com essa propriedade.
SuperJedi224

Respostas:

7

Haskell, 60 57 56. 55 bytes

f(a:b)=b==[]||length(fst$span(/=a)b)<=a&&f b
g x=f$x++x

Supõe que a lista de entrada contenha pelo menos um elemento.

Exemplo de uso: g [1]-> True. Experimente online!

Seja ao chefe da lista e ba cauda. O resultado é Truese bestá vazio ou o número de elementos no início bque não são iguais a anão é maior que ae a chamada recursiva de f btambém é True, caso contrário False. Comece com o dobro da lista de entrada.

Edit: @Leo salvou 3 bytes. Obrigado!

Editar 2: @Laikoni salvou 1 byte. Obrigado!

nimi
fonte
Usando takeWhile em vez de span, você pode evitar a correspondência de padrões e salvar uma solução agradável de três bytes ! :)
Leo
@ Leo: Boa captura! Normalmente, usar spané mais curto que usar takeWhile, então eu não olhei para isso.
N
takeWhilesempre pode ser reduzido para fst$spanou fst.span, o que economiza outro byte.
Laikoni
@Laikoni: sim, é claro! Obrigado!
N
Amor Haskell;)
theonlygusti
6

Python , 57 56 bytes

-1 byte graças a Dennis (substitua i+1:i+v+2com i:i-~vcom um ideslocamento de 1 a partir de enumerate)

lambda a:all(v in(a+a)[i:i-~v]for i,v in enumerate(a,1))

Experimente online!

Sem nome função tendo uma lista, ae testando a condição de que cada valor, v, aparece ina fatia relevantes para o seu direito em uma concatenação de acom ele próprio, (a+a)[i:i-~v], onde o índice com base em um de vem a, i, é fornecido pelo enumerate(a,1).

Jonathan Allan
fonte
1
Isso inspirou uma resposta Jelly de 8 bytes. :) Você pode salvar um byte como este .
Dennis
6

JavaScript (ES6), 67 65 55 54 51 49 bytes

Salvo 3B graças a @ETHproductions e 2B graças a @Arnauld

a=>!a.some((b,c)=>a.concat(a).indexOf(b,++c)>b+c)

Explicação

Isso define uma função que recebe uma matriz acomo entrada. Então o.some método itera sobre essa matriz, executando outra função para cada elemento.

Essa função interna recebe dois argumentos be c, o valor atual e seu índice. A função localiza o índice do valor atual, iniciando no índice c + 1. Em seguida, verifica se esse índice é maior que o valor atual mais o índice atual (a diferença entre duas ocorrências do mesmo valor é maior queb ). Observe que isso retorna exatamente o oposto do que queremos.

Se um desses valores de retorno for true, a .somefunção retornará truetambém. Se nenhuma das verificações retornar true, a .somefunção retornará false. Mais uma vez, o oposto do valor que queremos retornar, portanto esse resultado é negado e depois retornado.

Teste-o

Experimente todos os casos de teste aqui:

let f=
a=>!a.some((b,c)=>a.concat(a).indexOf(b,++c)>b+c)

let truthy = [[1], [8, 9], [2, 3, 4], [5, 5, 3, 3, 6], [2, 3, 5, 2, 3, 6], [6, 7, 3, 5, 3, 7], [9, 4, 6, 7, 4, 5], [1, 1, 1, 1, 1, 100, 1], [1, 9, 1, 8, 1, 7, 1, 11]];
let falsy  = [[1, 2, 3], [2, 3, 9, 5], [3, 5, 4, 4, 6], [2, 3, 5, 2, 3, 4], [3, 5, 7, 5, 9, 3, 7], [5, 6, 7, 8, 9, 10, 11], [1, 9, 1, 8, 1, 6, 1, 11]];

console.log("Truthy test cases:");
for (let test of truthy) {
    console.log(`${test}: ${f(test)}`);
}

console.log("Falsy test cases:");
for (let test of falsy) {
    console.log(`${test}: ${f(test)}`);
}

Luke
fonte
Muito bom, foi exatamente isso que eu criei :-) Você pode criar o array duplicado uma vez no início e usá-lo .shift()para economizar na fatia:a=>!a.some(b=>z.indexOf(z.shift())>b,z=a.concat(a))
ETHproductions
Hehe, grandes golfistas pensam da mesma forma ;-). Pensei em usar o turno também, mas não o usei, pois acabou sendo mais longo. Criar a matriz dupla uma vez e mudar todas as vezes é realmente inteligente. Obrigado!
25417 Luke
Funcionaria a=>!a.some((n,i)=>a.concat(a).indexOf(n,++i)>n+i)?
Arnauld
Sim. Obrigado!
25417 Luke
4

Gelatina , 11 bytes

ṣZL
;çЀ<‘P

Experimente online!

Como funciona

;çЀ<‘P  Main link. Argument: A (array)

;        Concatenate A with itself.
 çD€     For each n in A, call the helper with left arg. A + A and right arg. n.
     ‘   Increment all integers in A.
    <    Perform element-wise comparison of the results to both sides.
      P  Take the product of the resulting Booleans.


ṣZL      Helper link. Left argument: A. Right argument: n

ṣ        Split A at all occurrences of n.
 Z       Zip to transpose rows and columns.
  L      Length; yield the number of rows, which is equal to the number of columns
         of the input to Z.
Dennis
fonte
3

Gelatina , 8 bytes

ṙJḣ"‘Œpċ

Insipred pela resposta Python de @ JonathanAllan .

Experimente online!

Como funciona

ṙJḣ"‘Œpċ  Main link. Argument: A (array)

 J        Yield the indicies of A, i.e., [1, ..., len(A)].
ṙ         Rotate; yield A, rotated 1, ..., and len(A) units rotated to the left.
    ‘     Increment; add 1 to all elements of A.
  ḣ"      Head zipwith; truncate the n-th rotation to length A[n]+1.
     Œp   Take the Cartesian product of all resulting truncated rotations.
       ċ  Count the number of times A appears in the result.
Dennis
fonte
2

SWI-Prolog, 83 bytes

a(L,[H|R]):-nth0(X,R,H),H>=X,a(L,R);length(R,N),nth0(X,L,H),H>=N+X,a(L,R).
a(_,[]).


A lista deve ser inserida duas vezes:

a([1,2,3],[1,2,3]).

Se isso não for considerado aceitável, você pode adicionar o predicado

a(L):-a(L,L).

que adiciona 14 bytes extras.

Experimente online


Nota: você pode testar diferentes casos falsos ao mesmo tempo, separando suas consultas com ';' (ou) e teste para diferentes casos verdadeiros, separando com ',' (e)

ou seja, usando os exemplos de OP:

a([1],[1]),
a([8, 9],[8, 9]),
a([2, 3, 4],[2, 3, 4]),
a([5, 5, 3, 3, 6],[5, 5, 3, 3, 6]),
a([2, 3, 5, 2, 3, 6],[2, 3, 5, 2, 3, 6]),
a([6, 7, 3, 5, 3, 7],[6, 7, 3, 5, 3, 7]),
a([9, 4, 6, 7, 4, 5],[9, 4, 6, 7, 4, 5]),
a([1, 1, 1, 1, 1, 100, 1],[1, 1, 1, 1, 1, 100, 1]),
a([1, 9, 1, 8, 1, 7, 1, 11],[1, 9, 1, 8, 1, 7, 1, 11]).

e

a([1, 2, 3],[1, 2, 3]);
a([2, 3, 9, 5],[2, 3, 9, 5]);
a([3, 5, 4, 4, 6],[3, 5, 4, 4, 6]);
a([2, 3, 5, 2, 3, 4],[2, 3, 5, 2, 3, 4]);
a([3, 5, 7, 5, 9, 3, 7],[3, 5, 7, 5, 9, 3, 7]);
a([5, 6, 7, 8, 9, 10, 11],[5, 6, 7, 8, 9, 10, 11]);
a([1, 9, 1, 8, 1, 6, 1, 11],[1, 9, 1, 8, 1, 6, 1, 11]).
Maliafo
fonte
2

PHP, 52 bytes

for(;$n=$argv[++$i];$$n=$i)!$$n|$i-$$n<$n+2?:die(1);

toma sequência dos argumentos da linha de comando; sai com código 1para falsidade, 0para verdade.
Corra com -nr.

  • laço $natravés argumentos:
    • se não houve ocorrência anterior ou foi recente o suficiente
      , não faça nada; saia com o código1
    • lembrar ocorrência anterior em $$n( variáveis ​​variáveis )
  • sair com código 0(implícito)
Titus
fonte
Crazy seus nomes de variáveis ​​são inválidos, mas eu gosto.
Jörg Hülsermann 25/03
2

Retina , 50 bytes

$
,$`
M!&`\b(1+),.*?\b\1\b
+%`(^1*)1,1+
$1
M`1,
^0

Insira como uma lista de números unários separados por vírgula.

Experimente online!

Explicação

$
,$`

Duplique a entrada para que possamos verificar as etapas que envolvem o final.

M!&`\b(1+),.*?\b\1\b

Combine e retorne cada seção (mais curta) entre dois valores idênticos, por exemplo 11,111,1,11.

+%`(^1*)1,1+
$1

Remova repetidamente um dígito do primeiro número, juntamente com um número inteiro depois dele. Se a diferença for pequena o suficiente, isso removerá completamente o primeiro número. Caso contrário, pelo menos um dígito permanecerá.

M`1,

Conte quantas vezes 1,aparece em todas as linhas. Se aparecer em algum lugar, uma das etapas era muito ampla.

^0

Tente combinar um número começando com 0(ou seja, apenas 0ele próprio). Esta é efetivamente uma negação lógica da saída.

Martin Ender
fonte
2

JavaScript (ES6), 47 bytes

a=>![...a,...a].some((n,i)=>a[-n]-(a[-n]=i)<~n)

Como funciona

Reutilizamos a matriz de entrada apara armazenar a posição da última ocorrência encontrada de cada número inteiro em a. Usamos a tecla -npara armazenar esta posição, para que não interfira nos índices originais dea .

Quando a[-n]existe, o teste real ocorre. Quando a[-n]não existe, a expressão a[-n] - (a[-n] = i)é igual undefined - i == NaNe a comparação com~n é sempre falsa, que é o resultado esperado.

Casos de teste

Arnauld
fonte
2

Retina ,  41 39 bytes

2 bytes de golfe graças a Martin Ender, que por sinal me apresentou a grupos de equilíbrio com seu fantástico guia sobre SO

$
,$`,
((1)+,)(?=(?<-2>1+,)*(\1|$))

^$

Entrada é uma lista separada por vírgula de números unários. A saída é 0para false e 1true.

Experimente online!(Conjunto de testes que converte automaticamente de decimal)

Recentemente, aprendi sobre o equilíbrio de grupos, então queria experimentá-los. Eles não estão entre as ferramentas mais fáceis de usar, mas com certeza são poderosos.

Explicação

$
,$`,

Como muitos outros envios, duplicamos a lista para lidar com o agrupamento. Também adicionamos uma vírgula no final, para que cada número seja seguido por uma vírgula (isso facilita as coisas um pouco mais tarde)

((1)+,)(?=(?<-2>1+,)*(\1|$))

Aqui é onde as coisas ficam interessantes. Esta é uma etapa de substituição. Substituímos tudo o que corresponde à primeira linha pela segunda. Nesse caso, procuramos remover todos os números nnão seguidos porn+1 outros números diferentes.

Para fazer isso, primeiro correspondemos ao número, capturando cada 1um em um grupo (capturando o número do grupo 2 nesse caso). Então, com uma aparência positiva, para ter uma afirmação de largura zero, tentamos repetidamente corresponder em um grupo de equilíbrio -2, que terá sucesso não mais do que o número de capturas feitas pelo grupo2 , um número seguido por uma vírgula. Após essa sequência de números, ficaremos satisfeitos se alcançarmos o primeiro número novamente ou o final da linha.

Nota: esta expressão pode corresponder apenas à parte final de um número, se não conseguir encontrar uma correspondência com o número completo. Isso não é um problema, porque a primeira parte do número permanecerá na sequência e saberemos que a substituição não foi completamente bem-sucedida.

^$

Finalmente, o resultado deve ser verdadeiro se removermos completamente todos os números da lista. Tentamos combinar a sequência vazia e retornar o número de correspondências encontradas.

Leo
fonte
1
Bom trabalho! :) Não há necessidade de \b. Removê-lo causará correspondências dispersas, mas elas não conseguirão remover o número inteiro, portanto, você não acabará com uma sequência vazia.
Martin Ender
@MartinEnder Você está certo, é claro, obrigado :) #
Leo #
1

Gelatina , 11 bytes

ẋ2ĠṢI_2<"QȦ

Experimente online!

ẋ2ĠṢI_2<"QȦ  Main link. Argument: A (array)

ẋ2           Repeat A twice to account for wrap-around.
  Ġ          Group all indices of A + A by their respective values, sorting the
             index groups by the associated values.
   Ṣ         Sort the groups lexicographically, i.e., by first appearance in A.
    I        Increments; compute the forward differences of adjacent indices in
             each of the groups.
     _2      Subtract 2 from the differences.
         Q   Unique; yield A, deduplicated.
       <"    Compare all differences in the index group corresponding to the n-th
             unique value in A with the n-th unqiue value in A.
          Ȧ  All; yield 1 if and only if none of the comparisons returned 0.
Dennis
fonte
1

Python 3 , 101 bytes

lambda l:all(v>=(l[i+1:].index(v)if v in l[i+1:]else len(l[i+1:])+l.index(v))for i,v in enumerate(l))

Experimente online!

ovs
fonte
1

Röda , 50 bytes

f a{seq 0,#a-1|[indexOf(a[_],a[_1+1:]..a)<=a[_1]]}

Experimente online!

Finalmente! Eu estava esperando por esse desafio ...

É uma função que retorna um valor verdadeiro ou falso. É preciso um argumento, a matriz.

Ele itera sobre um fluxo de índices e verifica para cada índice _1que a distância do índice atual e do próximo índice a[_1]não é maior que a[_1].

fergusq
fonte
Como exatamente _1funciona?
Kritixi Lithos 25/03
@KritixiLithos É como _, mas se refere ao primeiro valor obtido. Se eu tivesse usado vários _s, cada um teria puxado um valor separado. Por exemplo, [1, 2, 3] | print(_, _, _)imprime 123, mas [1,2,3] | print(_, _1, _1)imprime 111 222 333(em linhas separadas).
fergusq
0

05AB1E , 13 bytes

Dì©v®¦©yky›_P

Experimente online! ou como um conjunto de testes

Explicação

Dì             # duplicate input and prepend the copy to the original
  ©            # store a copy in the register
   v           # for each element in the list
    ®          # push the list from register
     ¦©        # remove the first element and store a copy in the register
       yk      # get the index of the current element in the list
         y›_   # check if it's less than or equal to the current element
            P  # product of stack
Emigna
fonte