L'algorithme de comptage de reprise

14

Les enfants qui apprennent à compter connaissent souvent des séries de chiffres, mais ne semblent pas pouvoir les assembler correctement.

Par exemple, ils pourraient dire:

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

Parfois, les enfants se rendent compte qu'ils ont sauté certains chiffres et reviennent:

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

C'est clairement le modèle supérieur. Nous devons les identifier.

Pour identifier ces listes:

  1. Nous identifions le minimum Met le maximum Nde la liste

  2. Nous parcourons la liste. Si le nombre actuel est supérieur ou égal à un membre de la liste à sa droite, nous supprimons le nombre actuel.

  3. Si la liste restante contient tous les nombres de Mà N, alors nous retournons une valeur véridique.

Vous pouvez supposer que votre liste d'entrées contiendra au moins 1 élément. Vous pouvez supposer que tous les entiers seront non négatifs.

Cas de test:

Vérité:

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

Il s'agit de , alors faites vos réponses aussi courtes que possible!

Nathan Merrill
la source
Pas très clair: [0,1,2,3,4,5,4,3,2,1] doit-il être considéré comme vrai ou faux?
GB
1
@GB False. Lorsque vous êtes sur le deuxième élément, vous le supprimeriez à l'étape 2 (car il y en a un autre 1plus tard). Vous supprimeriez également tous les autres éléments (sauf le dernier), vous vous retrouveriez donc avec 0 1, ce qui n'est pas le cas0 1 2 3 4 5
Nathan Merrill

Réponses:

6

05AB1E , 5 octets

Je ne suis pas sûr à 100% que cela fonctionne, mais il passe tous les cas de test et je n'ai trouvé aucune situation où il échoue.

Ú¥1QP

Essayez-le en ligne!

Ú¥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
la source
7 octets, en fait
val dit Reinstate Monica
2
@val Non, 05AB1E utilise un encodage personnalisé, 05AB1E.
Erik the Outgolfer
2

Gelée , 10 9 octets

ṀrṂɓṚ«\Q⁼

Essayez-le en ligne!

Comment ça fonctionne

Ṁ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
la source
Intéressant, est-ce ɓune fonctionnalité relativement nouvelle?
ETHproductions
Oui, c'est à partir d'une demande de pull par Jonathan Allan.
Dennis
Aha, il y a 13 jours. Je ne l'avais pas encore vu utilisé (peut-être que vous ou Jonathan l'avez fait et je l'ai juste raté).
ETHproductions
La vraie partie intéressante ici est «\à mon avis cependant.
Erik the Outgolfer
1

Python 2 , 81 octets

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

Essayez-le en ligne!

Dennis
la source
1

PHP , 148 130 octets

-18 octets, merci @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);

Essayez-le en ligne!

MOI
la source
Ok beaucoup de commentaires ici: $argnest toujours une chaîne foreachne fonctionne pas dessus. Vous pouvez utiliser $argvpour obtenir un tableau en entrée, mais attention, il contient toujours le nom de fichier comme premier élément. Vous utilisez $met une $nseule fois pour que vous pouvez économiser beaucoup d'octets créant $bplus tôt: $b=range(min($a),max($a));. Le casting (bool)est complètement inutile. if($k>=$a[$s])$a[$i]=null;à $k<$a[$s]?:$a[$i]=-1;. En utilisant la référence, nous pouvons le faire: foreach($a as$i=>&$k)(+1 octet) et $a[$i]à $k(-4 octets). De plus, cela nous laisse tomber $s=$iparce que nous pouvons itérer $idirectement maintenant.
Christoph
Le résultat ressemble à ceci $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 octets). Mais il utilise toujours $argndans le mauvais sens. $a=explode(' ',$argn);corrigerait cela pour 13 octets supplémentaires.
Christoph
1
Aucun problème ! Toujours sympa de trouver un nouveau golfeur PHP J'espère en voir plus :) :) Titus, Jörg ou moi sommes toujours là pour vous aider!
Christoph
1
@Christoph Pourquoi ne pas utiliser $_GETcomme tableau d'entrée? Dans ce cas, il n'est pas nécessaire d'utiliser des explodeoctets supplémentaires -6 pour utiliser non la $bvariable
Jörg Hülsermann
1
@Christoph Okay Dans ce cas, nous avons besoin d'une version sous 7.1 et nous utilisons ´a & `au lieu de l' ~ essayer en ligne!
Jörg Hülsermann
1

Java 8, 264 262 octets

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;}

Explication:

Essayez-le ici.

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
la source
1

R, 88 85 octets

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)

Cela peut probablement être approfondi. Boucle sur les éléments de x, vérifie si toutes les valeurs à venir sont plus grandes et ne conserve que cet élément. Après la boucle, il crée une séquence de min(x)à max(x)et vérifie %in%si toutes les valeurs sont incluses dans la version élaguée de x.

JAD
la source
En portant la réponse de Dennis, nous pourrions descendre à 53 octets. function(n)all(unique(cummin(rev(n)))==max(n):min(n))
Giuseppe
1

JavaScript (ES6), 60 octets

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

Non golfé:

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

Ceci est un algorithme plus simple:

Répétez le tableau en sens inverse et assurez-vous que chaque nombre (sauf le premier) est inférieur ou égal à un nombre déjà vu.

Fragment:

Rick Hitchcock
la source
1

Haskell, 62 octets

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

Essayez-le en ligne!

Une implémentation directe de la définition où gsupprime les éléments s'ils sont> = que les éléments à sa droite.

nimi
la source
1

C #, 69 octets

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

En bref:
s = entrée (s) équation
prise de l'élément s où tous les éléments après celui-ci (sauter (I) ndex + 1 éléments), la valeur actuelle est plus élevée
comptez-les et voyez si le montant restant est égal au montant attendu ((max) valeur imum moins (min) imum) quantité de nombres

Essayez-le en ligne!

Barodus
la source
@MDXF Voulez-vous lui souhaiter la bienvenue?
Stan Strum
@StanStrum ai-je mal compris les règles? mon anglais est-il trop salissant? i -am- poste pour la première fois ...
Barodus
Non non! C'est un privilège d'accueillir un nouveau venu au PPCG, et je lui demandais s'il avait voulu vous dire bonjour
Stan Strum
On dirait que le privilège est pour vous deux. Merci, les gens ^^
Barodus
Ceci est une excellente première réponse, j'espère que vous vous amuserez dans votre avenir de PPCG!
Stan Strum,
0

JavaScript (ES6), 82 73 72 70 octets

Renvoie un booléen.

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

Comment?

Nous itérons sur chaque élément x du tableau d'entrée a , en gardant une trace de la valeur maximale rencontrée m et du nombre -k de valeurs qui ne sont ni supérieures ni égales à aucun membre à leur droite. Par définition, les valeurs valides apparaissent dans un ordre strictement croissant.

Nous utilisons filter()plutôt que map(), afin que tous les éléments soient filtrés jusqu'à ce que k devienne négatif. Cela nous permet d'isoler le premier élément valide, qui est également garanti comme étant la valeur minimale du tableau.

Enfin, nous testons si minimum - (maximum + 1) == -number_of_valid_elements:

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

Cas de test

Arnauld
la source