Écrivez un programme pour déterminer si une séquence périodique d'entiers positifs a la propriété que, pour chaque entier n
apparaissant dans la séquence, il n'y a jamais plus que d' n
autres entiers entre deux occurrences consécutives de n
.
Par exemple, 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...
a cette propriété: chaque paire d'occurrences consécutives de 2
a au plus deux entiers entre eux (comme 2, 3, 5, 2
et 2, 3, 6, 2
; chaque paire d'occurrences consécutives de 3
a au plus trois entiers entre eux; et la même chose pour 5
et 6
.
Cependant, 2, 3, 5, 2, 3, 4, 2, 3, 5, 2, 3, 4, ...
n'a pas cette propriété: deux occurrences consécutives de 4
, à savoir 4, 2, 3, 5, 2, 3, 4
, ont plus de quatre entiers entre elles.
Entrée : une représentation raisonnable d'une séquence périodique d'entiers positifs. Par exemple, une liste finie telle que {2, 3, 5, 2, 3, 6}
peut représenter la première séquence infinie 2, 3, 5, 2, 3, 6, 2, 3, 5, 2, 3, 6, ...
ci-dessus. (Pour cette question, le problème pourrait être indiqué pour les listes finies qui s'enroulent plutôt que pour les listes périodiques infinies.)
Sortie : une valeur véridique / fausse.
Exemples véridiques:
{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}
Exemples de fausseté:
{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}
C'est codegolf , donc le code le plus court l'emporte. Les réponses dans toutes les langues sont encouragées.
la source
Réponses:
Haskell,
60575655 octetsSuppose que la liste d'entrée contient au moins un élément.
Exemple d'utilisation:
g [1]
->True
. Essayez-le en ligne!Soit
a
la tête de liste etb
la queue. Le résultat estTrue
ifb
est vide ou le nombre d'éléments au débutb
qui ne sont pas égaux àa
n'est pas supérieur àa
et l'appel récursif def b
est égalementTrue
elseFalse
. Commencez avec deux fois la liste d'entrée.Modifier: @Leo a enregistré 3 octets. Merci!
Edit 2: @Laikoni a enregistré 1 octet. Merci!
la source
span
est plus courte que l'utilisationtakeWhile
, donc je ne l'ai pas regardé du tout.takeWhile
peut presque toujours être raccourci enfst$span
oufst.span
, ce qui économise un autre octet.Python ,
5756 octets-1 octet grâce à Dennis (remplacer
i+1:i+v+2
aveci:i-~v
avec uni
décalage de 1 à partir deenumerate
)Essayez-le en ligne!
Fonction Sans nom prendre une liste,
a
et tester la condition que chaque valeur,v
apparaîtin
la tranche pertinente pour son droit à une concaténation dea
avec lui - même,(a+a)[i:i-~v]
où l'indice de base 1 dev
dansa
,i
est fourni parenumerate(a,1)
.la source
JavaScript (ES6),
67 65 55 54 5149 octets3B enregistrés grâce à @ETHproductions et 2B grâce à @Arnauld
Explication
Cela définit une fonction qui prend un tableau
a
en entrée. Ensuite, la.some
méthode parcourt ce tableau, exécutant une autre fonction pour chaque élément.Cette fonction interne prend deux arguments,
b
etc
, la valeur actuelle et son index. La fonction recherche l'index de la valeur actuelle, à partir de l'indexc + 1
. Il vérifie ensuite si cet indice est supérieur à la valeur actuelle plus l'index actuel (la différence entre deux occurrences de la même valeur est supérieure àb
). Notez que cela renvoie exactement l'opposé de ce que nous voulons.Si l'une de ces valeurs de retour est
true
, la.some
fonction renvoietrue
également. Si aucune des vérifications ne revienttrue
, la.some
fonction retournefalse
. Encore une fois l'opposé de la valeur que nous voulons renvoyer, donc ce résultat est annulé puis renvoyé.Essaye-le
Essayez tous les cas de test ici:
la source
.shift()
pour économiser sur la tranche:a=>!a.some(b=>z.indexOf(z.shift())>b,z=a.concat(a))
a=>!a.some((n,i)=>a.concat(a).indexOf(n,++i)>n+i)
marcherait?Gelée , 11 octets
Essayez-le en ligne!
Comment ça marche
la source
Gelée , 8 octets
Insipred by @ JonathanAllan's Python answer .
Essayez-le en ligne!
Comment ça marche
la source
SWI-Prolog, 83 octets
La liste doit être entrée deux fois:
Si cela n'est pas jugé acceptable, vous pouvez ajouter le prédicat
ce qui ajoute 14 octets supplémentaires.
Essayez-le en ligne
nb: vous pouvez tester simultanément différents faux cas en séparant vos requêtes par ';' (ou) et testez différents cas réels en les séparant par ',' (et)
c'est-à-dire, en utilisant les exemples OP:
et
la source
PHP, 52 octets
prend la séquence des arguments de la ligne de commande; sort avec le code
1
pour la fausse,0
pour la vérité.Courez avec
-nr
.$n
travers arguments:alors ne faites rien, sinon quittez avec le code
1
$$n
( variables variables )0
(implicite)la source
Rétine , 50 octets
Saisie sous forme de liste de nombres unaires séparés par des virgules.
Essayez-le en ligne!
Explication
Dupliquez l'entrée afin que nous puissions vérifier les étapes qui se terminent à la fin.
Faites correspondre et renvoyez chaque section (la plus courte) entre deux valeurs identiques, par exemple
11,111,1,11
.Supprimez à plusieurs reprises un chiffre du premier numéro, ainsi qu'un numéro entier après celui-ci. Si l'écart est suffisamment petit, cela supprimera complètement le premier numéro. Sinon, au moins un chiffre restera.
Comptez la fréquence d'
1,
apparition dans toutes les lignes. S'il apparaît n'importe où, l'une des étapes était trop large.Essayez de faire correspondre un nombre commençant par
0
(c'est-à-dire uniquement0
lui-même). Il s'agit en fait d'une négation logique de la sortie.la source
JavaScript (ES6), 47 octets
Comment ça marche
Nous réutilisons le tableau d'entrée
a
pour stocker la position de la dernière occurrence rencontrée de chaque entier dansa
. Nous utilisons la clé-n
pour stocker cette position afin qu'elle n'interfère pas avec les indices d'origine dea
.Lorsqu'il
a[-n]
existe, le test réel se produit. Lorsqu'ila[-n]
n'existe pas, l'expressiona[-n] - (a[-n] = i)
est égaleundefined - i == NaN
et la comparaison avec~n
est toujours fausse, ce qui est le résultat attendu.Cas de test
Afficher l'extrait de code
la source
Rétine ,
4139 octets2 octets de golf grâce à Martin Ender, qui m'a d'ailleurs initié à l'équilibrage des groupes avec son fantastique guide sur SO
L'entrée est une liste de nombres unaires séparés par des virgules. La sortie est
0
pour false et1
pour vrai.Essayez-le en ligne!(Suite de tests qui convertit automatiquement de la décimale)
J'ai récemment appris à équilibrer les groupes, je voulais donc les essayer. Ils ne sont pas parmi les outils les plus faciles à utiliser, mais ils sont sûrs qu'ils sont puissants.
Explication
Comme beaucoup d'autres soumissions, nous dupliquons la liste pour traiter de l'emballage. Nous ajoutons également une virgule à la fin, donc chaque numéro est suivi d'une virgule (cela rend les choses un peu plus faciles plus tard)
Voici où les choses deviennent intéressantes. Il s'agit d'une étape de remplacement, nous remplaçons tout ce qui correspond à la première ligne par la deuxième ligne, dans ce cas, nous cherchons à supprimer tous les numéros
n
non suivis den+1
autres numéros différents.Pour ce faire, nous faisons d'abord correspondre le nombre, capturant chacun
1
dans un groupe (capturant le groupe numéro 2 dans ce cas). Ensuite, avec une anticipation positive, afin d'avoir une assertion de largeur nulle, nous essayons à plusieurs reprises de faire correspondre dans un groupe d'équilibrage-2
, qui ne réussira pas plus que le nombre de captures effectuées par groupe2
, un nombre suivi d'une virgule. Après cette séquence de nombres, nous sommes satisfaits si nous atteignons à nouveau le premier nombre ou la fin de la ligne.Remarque: cette expression peut correspondre uniquement à la dernière partie d'un numéro, si elle ne parvient pas à trouver une correspondance avec le numéro complet. Ce n'est pas un problème, car alors la première partie du numéro restera dans la chaîne et nous saurons que le remplacement n'a pas complètement réussi.
Enfin, le résultat devrait être véridique si nous avons complètement supprimé tous les numéros de la liste. Nous essayons de faire correspondre la chaîne vide et de renvoyer le nombre de correspondances trouvées.
la source
\b
. Le supprimer entraînera des correspondances errantes mais ils ne supprimeront pas le nombre entier, vous ne vous retrouverez donc pas avec une chaîne vide de toute façon.Gelée , 11 octets
Essayez-le en ligne!
la source
Python 3 , 101 octets
Essayez-le en ligne!
la source
Röda , 50 octets
Essayez-le en ligne!
Finalement! Je suis en attente pour ce défi ...
C'est une fonction qui renvoie une valeur véridique ou fausse. Il faut un argument, le tableau.
Il itère sur un flux d'indices et vérifie pour chaque index
_1
que la distance de l'index actuel et de l'index suivanta[_1]
n'est pas supérieure àa[_1]
.la source
_1
marche exactement ?_
, mais se réfère à la première valeur extraite. Si j'avais utilisé plusieurs_
s, chacun aurait tiré une valeur distincte. Par exemple,[1, 2, 3] | print(_, _, _)
imprime123
, mais[1,2,3] | print(_, _1, _1)
imprime111 222 333
(sur des lignes distinctes).05AB1E , 13 octets
Essayez-le en ligne! ou comme suite de tests
Explication
la source