Reconnaître les plis mods

18

Tâche

Définissez un pli mod en fonction de la forme f (x) = x% a 1  % a 2  %…% a k , où les a i sont des entiers positifs et k ≥ 0 . (Ici, % est l'opérateur modulo associatif gauche.)

Etant donné une liste de n entiers y 0 ,…, y n − 1 , déterminer s'il existe un mod-fold f de sorte que chaque y i  = f (i) .

Vous pouvez choisir et fixer deux sorties Y et N pour votre fonction / programme. S'il existe un tel f , vous devez toujours retourner / imprimer exactement Y ; sinon, vous devez toujours retourner / imprimer exactement N . (Il peut s'agir de true/ false, ou 1/ 0, false/ / true, etc.) Mentionnez-les dans votre réponse.

La soumission la plus courte en octets l'emporte.

Exemple

Définissez f (x) = x% 7% 3 . Ses valeurs commencent:

|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...

Ainsi, étant donné 0 1 2 0 1 2 0 0 1 2en entrée de notre solution, nous imprimerions Y , comme ce f génère cette séquence. Cependant, étant donné 0 1 0 1 2en entrée, nous imprimerions N , car aucun f ne génère cette séquence.

Cas de test

Les formules données lorsque la sortie est Y sont juste pour référence; vous ne devez à aucun moment les imprimer.

0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)
Lynn
la source
Y a-t-il des limites de temps ou de mémoire?
Dennis
2
Puis-je plutôt produire des valeurs véridiques et des valeurs Falsey?
Leaky Nun
2
@Leaky, je préfère que tu ne le fasses pas. Je ne suis pas un grand fan de vérité-falsey; J'essaie explicitement cela comme une alternative plus objective qui vous donne toujours la liberté.
Lynn
@Lynn est-ce juste moi ou vous ne l'avez toujours pas corrigé?
Leaky Nun
En ce qui concerne les contraintes de mémoire / temps: je ne pense pas que j'ajouterai le défi lui-même, mais je pourrais exécuter une prime pour la réponse la plus courte en octets qui puisse répondre à chacun de mes cas de test dans une durée raisonnable.
Lynn

Réponses:

7

Pyth, 14 octets

}Qm%M+RdUQy_Sl

Retours True/False. Essayez-le en ligne: démonstration ou suite de tests

Explication:

}Qm%M+RdUQy_SlQ   implicit Q (=input) at the end
             lQ   length of input list
            S     create the list [1, 2, ..., len]
           _      reverse => [len, ..., 2, 1]
          y       generate all subsets (these are all possible mod-folds)
  m               map each subset d to:
        UQ           take the range [0, 1, ..., len-1]
     +Rd             transform each number into a list by prepending it to d
                     e.g. if mod-fold = [7,3], than it creates:
                        [[0,7,3], [1,7,3], [2,7,3], [3,7,3], ...]
   %M                fold each list by the modulo operator
                  this gives all possible truthy sequences of length len
}Q                so checking if Q appears in the list returns True or False

Pyth, 11 octets

q%M.e+k_tx0

Basé sur l'idée de @ ferrsum . En fait, j'ai pensé à utiliser les indices zéro pour la génération du sous-ensemble, mais je ne me suis pas rendu compte que tous les indices zéro doivent déjà être la solution.

Jakube
la source
4

Python 3, 239 218 octets

from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]

Une fonction anonyme qui prend l'entrée d'une liste zet retourne Trueou Falsepour YetN .

Celui - ci utilise une méthode similaire à l » @Jakube réponse , et bien qu'il soit essentiellement une force brute, fonctionne très rapidement.

from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False

Essayez-le sur Ideone

TheBikingViking
la source
4

Python 2, 69 octets

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)

Utilise True/ False.

La réponse à ce qui caractérise une série mod-pliable s'avère moins intéressante qu'il n'y paraît au premier abord. C'est une série de la forme 0, 1, ..., M - 1, 0, 1, ... x 1 , 0, 1, ..., x 2 , ... telle que pour tout i, 0 <= x i <M. Une telle séquence peut être produite par la chaîne mod de tous les indices (basés sur 0) des zéros du tableau, à l'exception du premier.

feersum
la source
3

Gelée , 19 15 14 octets

LṗLUZ’1¦%/sLe@

Renvoie 1 pour la vérité, 0 pour la fausse. Essayez-le en ligne!

L'algorithme est O (n n ) , où n est la longueur de la liste, ce qui la rend trop lente et gourmande en mémoire pour la plupart des cas de test.

Une version modifiée - qui remplace la seconde Lpar un 5- peut être utilisée pour vérifier tous les cas de test . Notez que cette version modifiée ne fonctionnera pas pour les listes arbitrairement longues.

Comment ça fonctionne

LṗLUZ’1¦%/sLe@  Main link. Argument: A (array of integers)

L L             Yield the length l of A.
 ṗ              Take the l-th Cartesian power of [1, ..., l], i.e., construct
                all arrays of length l that consist of elements of [1, ..., l].
   U            Upend/reverse each array. This way, the first l arrays start
                with [1, ..., l], as do the next l arrays, etc.
    Z           Zip/transpose the array of arrays.
     ’1¦        Decrement the first array to map [1, ..., l] to [0, ..., l - 1].
        %/      Reduce the array's columns by modulus/residue.
          sL    Split the result into chunks of length l.
            e@  Verify if A belongs to the resulting array.
Dennis
la source
Pouvez-vous ajouter une explication? En tant que personne qui n'a pas encore utilisé Jelly, je ne sais pas comment cela fonctionne.
Steven H.
J'en ajouterai un dès que j'aurai fini de jouer au golf. Il y a encore quelques choses que je veux essayer en premier.
Dennis
J'ai (abandonné et) ajouté une explication.
Dennis
3

JavaScript (ES6), 98 octets

a=>a.every((n,i)=>n?n<(l+=p==i)&&n==p++:p=1,l=p=1)

Sauvegardé 48 octets en passant à la découverte de @ Feersum. Toute valeur donnée ndans le tableau est soit zéro, auquel cas la prochaine prédiction pest 1, soit égale à la prochaine prédiction, auquel cas elle pest incrémentée. Nous mesurons également la longueur lde la séquence initiale en comparant pà i, car elle ndoit toujours être inférieure là tout le temps.

Neil
la source
2

Python 2, 103 99 octets

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))

Imprime 1 pour la vérité et 0 pour la fausse. Testez-le sur Ideone .

Dennis
la source