La sécurité en chiffres

22

Écrivez un programme pour déterminer si une séquence périodique d'entiers positifs a la propriété que, pour chaque entier napparaissant dans la séquence, il n'y a jamais plus que d' nautres 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 2a au plus deux entiers entre eux (comme 2, 3, 5, 2et 2, 3, 6, 2; chaque paire d'occurrences consécutives de 3a au plus trois entiers entre eux; et la même chose pour 5et 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 , donc le code le plus court l'emporte. Les réponses dans toutes les langues sont encouragées.

Greg Martin
la source
La liste d'entrée contient-elle toujours au moins un élément?
nimi
2
@nimi sinon il ne représenterait pas une séquence périodique infinie.
Martin Ender
1
Si vous prenez la séquence thue-morse et ajoutez un entier positif fixe supérieur à 1 à chaque terme, vous aurez une séquence infinie apériodique avec cette propriété.
SuperJedi224

Réponses:

7

Haskell, 60 57 56 55 octets

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

Suppose que la liste d'entrée contient au moins un élément.

Exemple d'utilisation: g [1]-> True. Essayez-le en ligne!

Soit ala tête de liste et bla queue. Le résultat est Trueif best vide ou le nombre d'éléments au début bqui ne sont pas égaux à an'est pas supérieur à aet l'appel récursif de f best également Trueelse False. Commencez avec deux fois la liste d'entrée.

Modifier: @Leo a enregistré 3 octets. Merci!

Edit 2: @Laikoni a enregistré 1 octet. Merci!

nimi
la source
En utilisant takeWhile au lieu de span, vous pouvez éviter la correspondance de motifs et économiser trois octets Une belle solution, au fait! :)
Leo
@Leo: Belle prise! Habituellement, l'utilisation spanest plus courte que l'utilisation takeWhile, donc je ne l'ai pas regardé du tout.
nimi
takeWhilepeut presque toujours être raccourci en fst$spanou fst.span, ce qui économise un autre octet.
Laikoni
@Laikoni: oui bien sûr! Merci!
nimi
Love haskell;)
theonlygusti
6

Python , 57 56 octets

-1 octet grâce à Dennis (remplacer i+1:i+v+2avec i:i-~vavec un idécalage de 1 à partir de enumerate)

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

Essayez-le en ligne!

Fonction Sans nom prendre une liste, aet tester la condition que chaque valeur, vapparaît inla tranche pertinente pour son droit à une concaténation de aavec lui - même, (a+a)[i:i-~v]où l'indice de base 1 de vdans a, iest fourni par enumerate(a,1).

Jonathan Allan
la source
1
Cela a inspiré une réponse Jelly de 8 octets. :) Vous pouvez enregistrer un octet comme celui-ci .
Dennis
6

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

3B enregistrés grâce à @ETHproductions et 2B grâce à @Arnauld

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

Explication

Cela définit une fonction qui prend un tableau aen entrée. Ensuite, la .someméthode parcourt ce tableau, exécutant une autre fonction pour chaque élément.

Cette fonction interne prend deux arguments, bet c, la valeur actuelle et son index. La fonction recherche l'index de la valeur actuelle, à partir de l'index c + 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 .somefonction renvoie trueégalement. Si aucune des vérifications ne revient true, la .somefonction retourne false. 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:

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

Luc
la source
Très bien, c'est exactement ce que j'ai trouvé :-) Vous pouvez créer le tableau doublé une fois au début et l'utiliser .shift()pour économiser sur la tranche:a=>!a.some(b=>z.indexOf(z.shift())>b,z=a.concat(a))
ETHproductions
Hehe, les grands golfeurs pensent de la même façon ;-). J'ai aussi pensé à utiliser shift, mais je ne l'ai pas utilisé, car il s'est avéré plus long. Créer le double tableau une fois et le déplacer à chaque fois est vraiment intelligent. Merci!
Luke
Ça a=>!a.some((n,i)=>a.concat(a).indexOf(n,++i)>n+i)marcherait?
Arnauld
Oui. Merci!
Luke
4

Gelée , 11 octets

ṣZL
;çЀ<‘P

Essayez-le en ligne!

Comment ça marche

;çЀ<‘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
la source
3

Gelée , 8 octets

ṙJḣ"‘Œpċ

Insipred by @ JonathanAllan's Python answer .

Essayez-le en ligne!

Comment ça marche

ṙ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
la source
2

SWI-Prolog, 83 octets

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(_,[]).


La liste doit être entrée deux fois:

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

Si cela n'est pas jugé acceptable, vous pouvez ajouter le prédicat

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

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:

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]).

et

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

PHP, 52 octets

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

prend la séquence des arguments de la ligne de commande; sort avec le code 1pour la fausse, 0pour la vérité.
Courez avec -nr.

  • boucle à $ntravers arguments:
    • s'il n'y a pas eu d'occurrence précédente ou si c'était assez récent
      alors ne faites rien, sinon quittez avec le code1
    • se souvenir de l'occurrence précédente dans $$n( variables variables )
  • quitter avec du code 0(implicite)
Titus
la source
Fou vos noms de variables ne sont pas valides mais j'aime ça.
Jörg Hülsermann
2

Rétine , 50 octets

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

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.

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

Faites correspondre et renvoyez chaque section (la plus courte) entre deux valeurs identiques, par exemple 11,111,1,11.

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

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.

M`1,

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.

^0

Essayez de faire correspondre un nombre commençant par 0(c'est-à-dire uniquement 0lui-même). Il s'agit en fait d'une négation logique de la sortie.

Martin Ender
la source
2

JavaScript (ES6), 47 octets

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

Comment ça marche

Nous réutilisons le tableau d'entrée apour stocker la position de la dernière occurrence rencontrée de chaque entier dans a. Nous utilisons la clé -npour stocker cette position afin qu'elle n'interfère pas avec les indices d'origine de a.

Lorsqu'il a[-n]existe, le test réel se produit. Lorsqu'il a[-n]n'existe pas, l'expression a[-n] - (a[-n] = i)est égale undefined - i == NaNet la comparaison avec ~nest toujours fausse, ce qui est le résultat attendu.

Cas de test

Arnauld
la source
2

Rétine ,  41 39 octets

2 octets de golf grâce à Martin Ender, qui m'a d'ailleurs initié à l'équilibrage des groupes avec son fantastique guide sur SO

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

^$

L'entrée est une liste de nombres unaires séparés par des virgules. La sortie est 0pour 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)

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

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érosn non suivis den+1 autres numéros différents.

Pour ce faire, nous faisons d'abord correspondre le nombre, capturant chacun 1dans 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.

Leo
la source
1
Bon travail! :) Il n'y a pas besoin de \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.
Martin Ender
@MartinEnder Vous avez bien sûr raison, merci :)
Leo
1

Gelée , 11 octets

ẋ2ĠṢI_2<"QȦ

Essayez-le en ligne!

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

Python 3 , 101 octets

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))

Essayez-le en ligne!

ovs
la source
1

Röda , 50 octets

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

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 _1que la distance de l'index actuel et de l'index suivant a[_1]n'est pas supérieure à a[_1].

fergusq
la source
Comment ça _1marche exactement ?
Kritixi Lithos
@KritixiLithos C'est comme _, 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(_, _, _)imprime 123, mais [1,2,3] | print(_, _1, _1)imprime 111 222 333(sur des lignes distinctes).
fergusq
0

05AB1E , 13 octets

Dì©v®¦©yky›_P

Essayez-le en ligne! ou comme suite de tests

Explication

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