O algoritmo de contagem de retorno

14

As crianças que estão aprendendo a contar costumam saber séries de números, mas parecem não conseguir montar essas séries adequadamente.

Por exemplo, eles podem dizer:

1,2,3,4,7,8,9,10

Às vezes, as crianças percebem que pularam alguns números e voltam:

1,2,3,4,7,8,5,6,7,8,9,10

Este é claramente o padrão superior. Precisamos identificá-los.

Para identificar essas listas:

  1. Identificamos o mínimo Me o máximo Nda lista

  2. Percorremos a lista. Se o número atual for maior ou igual a qualquer membro da lista à direita, removeremos o número atual.

  3. Se a lista restante contém todos os números de Maté N, retornamos um valor verdadeiro.

Você pode assumir que sua lista de entrada conterá pelo menos 1 elemento. Você pode assumir que todos os números inteiros serão não negativos.

Casos de teste:

Verdade:

0
10
0 0 0 
1 0 1
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 0 1 2 3
0 1 2 3 4 5 5
0 1 1 2 2 3
0 3 6 1 4 7 2 5 8 3 4 5 6 7 8
1 3 5 7 2 3 4 5 6 7
5 6 0 1 2 3 6 7 4 5 6 7
5 6 7 8
5 5 6 7 8
4 6 7 8 3 4 5 6 7 8

Falsy:

1 0
4 3 2 1
1 2 3 7 8 9
0 1 2 3 1 3
0 1 2 3 1 3 4
0 1 2 3 1 3 2 4
0 1 2 3 1 3 2 4 3
1 3 5 7 2 4 6 8
0 1 2 1 3 4 5 6
4 5 6 3 4 5

Isso é , então faça suas respostas o mais curto possível!

Nathan Merrill
fonte
Não é muito claro: [0,1,2,3,4,5,4,3,2,1] deve ser considerado verdadeiro ou falso?
GB
1
@GB False. Quando você estiver no segundo elemento, remova-o na etapa 2 (porque há outro 1mais adiante). Você também removeria todos os outros elementos (exceto o último 1), para acabar com o 0 1que não é0 1 2 3 4 5
Nathan Merrill

Respostas:

6

05AB1E , 5 bytes

Não tenho 100% de certeza de que isso funcione, mas ele passa em todos os casos de teste e não consegui encontrar nenhuma situação em que falhe.

Ú¥1QP

Experimente online!

Ú¥1QP   Main link. Argument a
Ú       Reverse uniquify a, keeps only last occurence of each element
 ¥      Get all deltas - all 1 if ascending list
  1Q    Compare all deltas to 1
    P   Product of all results
kalsowerus
fonte
7 bytes, na verdade
val diz Reinstate Monica
2
@val No, 05AB1E usa uma codificação personalizada, 05AB1E.
Erik the Outgolfer
2

Geléia , 10 9 bytes

ṀrṂɓṚ«\Q⁼

Experimente online!

Como funciona

ṀrṂɓṚ«\Q⁼  Main link. Argument: A (array)

Ṁ          Yield the maximum of A.
  Ṃ        Yield the minimum of A.
 r         Yield R := [max(A), ... min(A).
   ɓ       Begin a new chain. Left argument: A. Right argument: R
    Ṛ      Reverse A.
     «\    Take the cumulative minimum.
       Q   Unique; deduplicate the results.
        ⁼  Compare the result with R.
Dennis
fonte
Interessante, é ɓum recurso relativamente novo?
ETHproductions
Sim, é de uma solicitação de recebimento de Jonathan Allan.
Dennis
Ah, há 13 dias. No entanto, ainda não o tinha visto (talvez você ou Jonathan tenham visto e eu apenas perdi).
ETHproductions
A parte realmente interessante aqui é, «\na minha opinião.
Erik the Outgolfer
1

Python 2 , 81 bytes

x=input();r=m=[]
for n in x[::-1]:r=[n][:n<m]+r;m=r[0]
print r==range(m,max(x)+1)

Experimente online!

Dennis
fonte
1

PHP , 148 130 bytes

-18 bytes, obrigado @Christoph

$a=explode(' ',$argn);$b=range(min($a),max($a));foreach($a as$i=>&$k)for(;++$i<count($a);)$k<$a[$i]?:$k=-1;echo!array_diff($b,$a);

Experimente online!

MIM
fonte
Ok, muito para comentar aqui: $argné sempre uma string foreachque não funciona nela. Você pode usar $argvpara obter uma matriz como entrada, mas tome cuidado para que ela sempre contenha o nome do arquivo como primeiro elemento. Você usa $me $napenas uma vez para que você pode salvar um monte de bytes criando $banteriormente: $b=range(min($a),max($a));. O elenco (bool)é completamente desnecessário. if($k>=$a[$s])$a[$i]=null;para $k<$a[$s]?:$a[$i]=-1;. Usando referência, podemos fazer isso: foreach($a as$i=>&$k)(+1 byte) e $a[$i]to $k(-4 byte). Além disso, isso nos deixa cair $s=$iporque podemos iterar $idiretamente agora.
Christoph
O resultado é semelhante a este $a=$argn;$b=range(min($a),max($a));foreach($a as$i=>&$k)for(;++$i<count($a);)$k<$a[$i]?:$k=-1;echo!array_diff($b,$a);(117 bytes). Mas ainda usa $argnda maneira errada. $a=explode(' ',$argn);corrigiria isso por 13 bytes adicionais.
Christoph
1
Sem problemas ! Sempre bom encontrar um novo jogador de golfe em PHP. Espero ver mais de vocês :) ou Titus, Jörg ou eu estamos sempre lá para ajudar!
Christoph
1
@Christoph Por que não usar $_GETcomo array de entrada? Neste caso, não há necessidade de usar explodeadditonal -6 Bytes para usar e não a $bvariável
Jörg Hülsermann
1
@Christoph Okay Neste caso, precisamos de uma versão abaixo da 7.1 e usamos ´a & `em vez de ~ Experimente online!
Jörg Hülsermann
1

Java 8, 264 262 bytes

import java.util.*;l->{int m=Collections.max(l),n=Collections.min(l),i=0,q;for(;i<(q=l.size());i++)if(l.subList(i+1,q).size()>0&&l.get(i)>=Collections.min(l.subList(i+1,q)))l.remove(i--);for(i=0;n<=m;)if(i<l.size()&&l.get(i++)==n)n++;else return 0>1;return 1>0;}

Explicação:

Experimente aqui.

import java.util.*;                 // Import for Collections

l->{                                // Method with integer-ArrayList parameter and boolean return-type
  int m=Collections.max(l),         //  Max of the list
      n=Collections.min(l),         //  Min of the list
      i=0,q;                        //  Two temp integers
  for(;i<(q=l.size());i++)          //  Loop (1) over the list
    if(l.subList(i+1,q).size()>0    //   If the sublist right of the current item is not empty
    &&l.get(i)>=Collections.min(l.subList(i+1,q))) 
                                    //   and if the current item is larger or equal to the lowest value of this sublist
      l.remove(i--);                //    Remove the current item from the main list
                                    //  End of loop (1) (implicit / single-line body)
  for(i=0;n<=m;)                    //  Loop (2) from min to max
    if(i<l.size()                   //   If the current item doesn't exceed the list's size
    &&l.get(i++)==n)                //   and the items are in order so far
      n++;                          //    Go to the next item
    else                            //   Else:
      return 0>1;//false            //    Return false
                                    //  End of loop (2) (implicit / single-line body)
  return 1>0;//true                 //  Return true
}                                   // End of method
Kevin Cruijssen
fonte
1

R, 88 85 bytes

y=NULL;for(i in x<-scan())if(all(i<x[-(1:(F<-F+1))]))y=c(y,i);all(min(x):max(x)%in%y)

Provavelmente isso pode ser ainda mais diminuído. Loops sobre os elementos de x, verifica se todos os valores futuros são maiores e, somente então, mantém esse elemento. Após o loop, ele cria uma sequência de min(x)para max(x)e verifica %in%se todos os valores estão incluídos na versão removida de x.

JAD
fonte
Ao portar a resposta de Dennis, podemos chegar a 53 bytes. function(n)all(unique(cummin(rev(n)))==max(n):min(n))
Giuseppe
1

JavaScript (ES6), 60 bytes

s=>(o={},s.reverse().every((n,i)=>!i|o[n+1]|o[n]&&(o[n]=1)))

Ungolfed:

s=>(
  o={},
  s.reverse().every((n,i)=>
    !i|o[n+1]|o[n]&&(o[n]=1)
  )
)

Este é um algoritmo mais simples:

Itere a matriz no sentido inverso e verifique se cada número (exceto o primeiro) é um menor ou igual a um número já visto.

Snippet:

Rick Hitchcock
fonte
1

Haskell, 62 bytes

g(a:b)=[a|all(a<)b]++g b
g a=a
f x=g x==[minimum x..maximum x]

Experimente online!

Uma implementação direta da definição em que gremove os elementos se eles forem> = do que os elementos à sua direita.

nimi
fonte
1

C #, 69 bytes

s=>s.Where((e,i)=>s.Skip(i+1).All(r=>e<r)).Count()==s.Max()-s.Min()+1

Resumindo:
s = a equação de entrada (s) é tirada
do elemento s, onde todos os itens após este (pular (I) ndex + 1 itens), o valor atual é maior,
conte-os e veja se o valor restante é igual ao valor esperado ((max) valor imum menos (min) imum) quantidade de números

Experimente online!

Barodus
fonte
@MDXF Você quer recebê-lo?
Stan Strum
@StanStrum eu entendi mal as regras? meu inglês está muito bagunçado? postagem i -am- pela primeira vez ...
Barodus
Não não! É um privilégio para acolher um recém-chegado ao PPCG, e eu estava perguntando-lhe se ele queria dizer oi para você
Stan Strum
Parece que o privilégio é para vocês dois. Obrigado, gente ^^
Barodus
Esta é uma ótima primeira resposta, espero que você se divirta no seu futuro do PPCG!
Stan Strum
0

JavaScript (ES6), 82 73 72 70 bytes

Retorna um booleano.

a=>a.filter((x,i)=>k-=a.every(y=>~i--<0|y>x,m=x>m?x:m),m=k=0)[0]+~m==k

Quão?

Iteramos em cada elemento x de entrada do painel uma , mantendo um registo do valor máximo encontrado m e o número k de valores que não são maiores do que ou igual a qualquer membro a sua direita. Por definição, os valores válidos aparecem em ordem estritamente crescente.

Usamos, em filter()vez de map(), para que todos os elementos sejam filtrados até que k fique negativo. Isso nos permite isolar o primeiro elemento válido, que também é garantido como o valor mínimo da matriz.

Por fim, testamos se minimum - (maximum + 1) == -number_of_valid_elements:

a.filter(...)[0] + ~m == k

Casos de teste

Arnauld
fonte