Étant donné une liste de 1s et de -1s, déterminez s'il s'agit ou non d'un code OVSF valide (en émettant une valeur true ou falsey).

Les codes OVSF sont définis comme suit:

• [1] est un code OVSF.

• Si Xest un code OVSF, alors X ++ Xet X ++ -Xsont tous les deux des codes OVSF.

  Voici la ++concaténation de liste et -annule chaque élément de la liste.

• Aucune autre liste n'est un code OVSF valide.

Vous pouvez supposer que la liste d'entrée contient uniquement -1et 1, mais vous devez gérer correctement la liste vide, ainsi que les listes dont la longueur n'est pas une puissance de 2.

Le code le plus court (en octets) gagne.

Cas de test

[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True

Gelée , 18 16 14 11 octets

^2/Eam2µḊ¿Ṭ

Sorties [1](véridiques) pour les codes OVSF, [](fausses) sinon.

Essayez-le en ligne!

Contexte

Comme @ réponse de MATL de LuisMendo et réponse Python @ xnor , cette soumission vérifie le tableau d'entrée de « de l'out à l' intérieur ».

Chaque paire (sans chevauchement) d'éléments d'un code OVSF de longueur deux ou plus est essentiellement une copie de la première paire, soit avec les mêmes signes, soit avec les deux signes échangés. De même, chaque 4-tuple (sans chevauchement) d'éléments d'un code OVSF de longueur quatre ou plus est essentiellement une copie du premier 4-tuple, soit avec les mêmes signes, soit avec les deux signes échangés. Il en va de même pour 8-tuples, 16-tuples, etc., jusqu'à la longueur du code OVFS.

Une façon de vérifier cela consiste à vérifier d'abord toutes les paires pour modulo l'égalité du signe, puis supprimer le deuxième élément de chaque paire (qui est maintenant une information redondante). Si nous répétons ce processus une fois de plus, nous vérifions essentiellement tous les 4-tuples. Dans la prochaine itération, nous comparons 8 tuples, etc.

Enfin, si tous les 2 ^k -uplets requis étaient égaux modulo le signe et le tableau a été réduit à un singleton, il suffit de vérifier si l'élément restant est un 1 .

Comment ça marche

^2/Eam2µḊ¿Ṭ  Main link. Argument: A (array of 1's and -1's)

       µḊ¿   While dequeuing A (removing its first element) yields a non-empty
             array, execute the monadic chain to the left, updating A with the
             return value after each iteration.
^2/            Compute the bitwise XOR of each non-overlapping pair of elements of
               A. Note that 1 ^ 1 = 0 = -1 ^ -1 and 1 ^ -1 = -2 = -1 ^ 1.
               For an array of even length that consists of the same pairs modulo
               the sign, this returns either an array of 0's or an array of -2's.
               If the length is odd, it will also contain the last element, which
               is either a 1 or a -1.
   E           Test the elements of the result for equality. This yields 1 if the
               array consists solely of 0's or solely of -2's, 0 otherwise.
    a          Take the logical AND of the previous result and every element of A.
               This returns A if it passed the previous test, but replaces all of
               its elements with 0's otherwise.
     m2        Modulo 2; select every second element of A, starting with the first.
             At this point, the last return value can be:
               • [  ] if the input was empty
               • [ 1] if the input was a valid OVSF code
               • [-1] if the input was the negative of a valid OVSF code.
               • [ 0] in all other cases.
           Ṭ  Untruth; yield an array with 1's at the specified indices.
              Indexing is 1-based in Jelly, so [1] returns [1], the array with a 1
              at index 1. Since the indices -1 and 0 are non-canonical, the arrays
              [-1] and [0] are mapped to []. The empty array remains empty.

Mathematica, 52 47 45 octets

Le nombre d'octets suppose le codage CP-1252 et $CharacterEncodingdéfini sur WindowsANSI(la valeur par défaut sur les installations Windows).

±___=!(±1=1>0)
a__±b__/;a!==b!||{a}==-{b}:=±a

Ceci définit une fonction variadique PlusMinus, qui prend la liste d'entrée comme une liste plate d'arguments et retourne un booléen, par exemple PlusMinus[1, -1, -1, 1]donne True. Il est théoriquement aussi utilisable comme un opérateur ±, mais que l' opérateur n'est syntaxiquement valide dans des contextes unaires et binaires, de sorte que la convention d'appel obtiendrait bizarre: ±##&[1,-1,-1,1]. Il lancera un tas d'avertissements qui peuvent être ignorés.

Cela lancera également quelques avertissements qui peuvent être ignorés.

Il pourrait y avoir un raccourci pour raccourcir la a!==b!||{a}==-{b}partie quelque peu ennuyeuse , mais je ne trouve rien pour l'instant. Les mots clés aiment SubsetQet MatrixRanksont tout simplement trop longs. : /

Explication

La solution reporte fondamentalement toutes les choses délicates à l'assortiment de motifs de Mathematica et est donc très déclarative dans le style. Mis à part une certaine golfitude sur la première ligne, cela ajoute simplement trois définitions différentes pour l'opérateur ±:

±___=False;
±1=True;
a__±b__/;a!==b!||{a}==-{b}:=±a

Les deux premières lignes ont été raccourcies en imbriquant les définitions et en exprimant Truecomme 1>0.

Nous devrions déconstruire cela davantage pour montrer comment cela définit réellement une fonction variadci PlusMinusen utilisant uniquement la notation d'opérateur unaire et binaire. Le hic, c'est que tous les opérateurs sont simplement du sucre syntaxique pour les expressions complètes. Dans notre cas ±correspond à PlusMinus. Le code suivant est 100% équivalent:

PlusMinus[___]=False;
PlusMinus[1]=True;
PlusMinus[a__,b__]/;a!==b!||{a}==-{b}:=PlusMinus[a]

En utilisant des séquences (un peu comme des splats similaires dans d'autres langages) comme opérandes de, ±nous pouvons couvrir un nombre arbitraire d'arguments PlusMinus, même s'il ±n'est pas utilisable avec plus de deux arguments. La raison fondamentale est que le sucre syntaxique est résolu en premier, avant que l'une de ces séquences ne soit développée.

Passons aux définitions:

La première définition est simplement une solution de repli ( ___correspond à une liste arbitraire d'arguments). Tout ce qui ne correspond pas aux définitions plus spécifiques ci-dessous donnera False.

La deuxième définition est le cas de base pour l'OVSF, la liste ne contenant que 1. Nous définissons cela comme étant True.

Enfin, la troisième définition s'applique uniquement aux listes qui peuvent être décomposées en X ++ Xou X ++ -X, et utilise récursivement le résultat pour X. La définition est limitée à ces listes en garantissant qu'elles peuvent être divisées en sous-séquences aet bavec a__±b__puis en attachant la condition ( /;) qui soit {a}=={b}ou {a}==-{b}. Définir PlusMinuscomme une fonction variadique de cette manière étrange via un opérateur économise un énorme 5 octets sur la définition d'un opérateur unaire ±sur les listes.

Mais attendez, il y a plus. Nous utilisons a!==b!au lieu de {a}=={b}. De toute évidence, nous le faisons parce qu'il est de deux octets plus court, mais la question intéressante est de savoir pourquoi cela fonctionne. Comme je l'ai expliqué ci-dessus, tous les opérateurs ne sont que du sucre syntaxique pour une expression avec une tête. {a}est List[a]. Mais ac'est une séquence (comme je l'ai dit, un peu comme un splat dans d'autres langues) donc si ac'est 1,-1,1alors nous obtenons List[1,-1,1]. Maintenant, le suffixe !est Factorial. Alors ici, nous aurions Factorial[1,-1,1]. Mais Factorialne sait pas quoi faire quand il a un nombre d'arguments différent d'un seul, donc cela reste simplement non évalué. ==ne se soucie pas vraiment si la chose des deux côtés sont des listes, il compare simplement les expressions, et si elles sont égales, cela donneTrue(dans ce cas, il ne donnera pas réellement Falses'ils ne le sont pas, mais les motifs ne correspondent pas si la condition renvoie autre chose que True). Cela signifie donc que le contrôle d'égalité fonctionne toujours s'il y a au moins deux éléments dans les listes. Et s'il n'y en a qu'un? Si ac'est 1alors a!c'est encore 1. Si aest -1alors a!donne ComplexInfinity. Maintenant, la comparaison 1avec elle-même fonctionne bien, bien sûr. Mais ComplexInfinity == ComplexInfinityreste non évalué, et ne donne pas vrai même si a == -1 == b. Heureusement, cela n'a pas d'importance, car la seule situation dans PlusMinus[-1, -1]laquelle cela se produit est de ne pas être un OVSF valide de toute façon! (Si la condition revenait True, l'appel récursif signaleraitFalseaprès tout, il n'a donc pas d'importance que la vérification ne fonctionne pas.) Nous ne pouvons pas utiliser la même astuce pour {a}==-{b}parce que le -fil ne déborderait pas Factorial, il ne ferait que filer List.

Le patcher matcher prendra soin du reste et trouvera simplement la bonne définition à appliquer.

Haskell, 57 octets

q=length
f l=l==until((>=q l).q)(\s->s++map(*l!!q s)s)[1]

Étant donné la liste d'entrée l, développe un code OVSF sen commençant [1]et en concaténant à plusieurs reprises soit sou -s, selon ce qui fait que le premier élément correspond à celui de l. Ensuite, vérifie que le résultat est là la fin. Ceci est vérifié une fois ssa longueur au moins égale à l.

Certaines structures récursives alternatives se sont également avérées donner 57:

(s%i)l|length l<=i=s==l|j<-2*i=(s++map(*l!!i)s)%j$l
[1]%1

q=length
s%l|q s>=q l=s==l|r<-s++map(*l!!q s)s=r%l
([1]%)

q=length
g s l|q s<q l=g(s++map(*l!!q s)s)l|1>0=s==l
g[1]

MATLAB / Octave , 94 octets

function a=f(r);n=nnz(r);m=log2(n);a=0;if fix(m)-m==0;for c=hadamard(n);a=a+all(r==c');end;end

Ceci utilise une nouvelle approche: les codes de longueur OVSF autorisés Napparaissent dans la log2(N)-ème matrice de Walsh , car ils sont essentiellement définis par la même récursivité:

Les matrices de Walsh sont des cas particuliers des matrices de Hadamard de taille N x Nif Nest une puissance de deux. (Il existe également des matrices Hadamard d'autres tailles.) MATLAB et Octave ont une variété de fonctions intégrées qui génèrent des matrices de test pour tester les propriétés des algorithmes numériques, entre autres hadamard(). Heureusement pour les pouvoirs de deux hadamard()usex de MATLAB exactement la construction des matrices galloises.

Donc, cette fonction vérifie d'abord si la longueur des entrées est une puissance de deux, et si c'est le cas, elle vérifie s'il s'agit d'une ligne de la matrice galloise de taille correspondante.

Essayez-le en ligne!

Python, 64 octets

f=lambda l:[]<l[1::2]==[x*l[1]for x in l[::2]]*f(l[::2])or[1]==l

Divise la liste en éléments pairs et en éléments impairs indexés via des tranches. Vérifie si les vecteurs de résultat sont égaux ou négatifs en multipliant un par le signe forcé par son premier élément. Effectue ensuite la même vérification récursive sur les éléments pairs.

Pour le cas de base, si la vérification échoue, rejette sauf si la liste l'est [1]. La liste vide est également spécifiquement rejetée pour éviter une boucle infinie.

Une stratégie différente comme ma réponse Haskell donne 66 octets:

f=lambda l,i=1,s=[1]:l[i:]and f(l,i*2,s+[x*l[i]for x in s])or s==l

Haskell , 106 91 87 86 octets

g n|n<1=[[1]]|m<-g(n-1)=foldl(\a b->[b++map(0-)b,b++b]++a)[]m++m
f l=elem l$g$length l

La fonction ggénère l' nitération des listes (relativement inefficace, carlength $ g n == 3^n , si nous supprimions les doublons, nous l'obtiendrions 2^n), fvérifie si notre liste est dans l'un d'eux. Merci à @Zgrab pour quelques conseils!

Essayez-le en ligne!

JavaScript (ES6), 130 93 87 85 83 octets

f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b))

Démo

f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b)),[[],[1],[-1],[1,1],[1,-1],[1,1,1,1],[1,1,1,1,1],[1,-1,-1,1,-1,1,1,-1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,-1,-1,-1,-1]].map(a=>console.log(`[${a}] -> ${!!f(a)}`))

JavaScript (ES6), 85 61 octets

a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>e==a[j=i&-i]*a[i-j])

Version précédente qui vérifiait les éléments pour s'assurer qu'ils étaient 1ou -1:

a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>i?(j=i&-i)<i?e==a[j]*a[i-j]:e==1|e==-1:e==1)

Explication:

• La longueur ne peut pas être nulle
• La longueur doit être une puissance de 2
• Le premier élément doit être 1
• Les éléments dans des positions de puissance 2 doivent être soit 1 soit -1
• Les éléments dans d'autres positions sont le produit de tous les éléments dans les positions correspondant au masque binaire, par exemple a[22] == a[2] * a[4] * a[16]. Comme a[20] == a[4] * a[16]a déjà été vérifié, il suffit a[22] == a[2] * a[20]de le vérifier.
• La vérification ci-dessus donne des résultats dégénérés pour ine pas avoir défini au moins deux bits. Dans le cas d'un jeu de bits zéro, il vérifie que a[0] == a[0] * a[0], ce qui est faux a[0] == -1, tandis que dans le cas d'un jeu de bits, il vérifie cela a[i] == a[0] * a[i].

MATL , 21 20 octets

`2eZ}yy=&=tn1>hh]1X=

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Comment ça marche

Le code divise le tableau en deux morceaux de longueur égale: le premier avec les entrées indexées impaires, le second avec les entrées indexées paires. Les deux pièces sont obligées d'avoir une longueur égale, avec un rembourrage nul dans la seconde si besoin. Ensuite, le code vérifie que

1. Les entrées correspondantes des deux pièces sont toutes égales ou toutes différentes;
2. Aucune entrée dans la deuxième pièce n'est nulle;
3. La longueur des pièces dépasse 1.

Si ces trois conditions sont remplies, le processus est appliqué à nouveau sur la première pièce. Si la boucle est quittée car la longueur était déjà 1, l'entrée est un code OFSV. Sinon, ce n'est pas le cas.

La condition 1 itérée est une version équivalente de la propriété de définition des codes OVSF. Pour un tableau de longueur disons 8, l'approche simple serait de vérifier que les entrées 1, 2, 3, 4 sont toutes égales ou toutes différentes des entrées 5, 6, 7, 8 respectivement (c'est la propriété qui définit). Mais nous pouvons vérifier de manière équivalente que les entrées 1,3,5,7 sont toutes égales ou toutes différentes des entrées 2,4,6,8 respectivement; et cela s'avère utiliser moins d'octets.

La condition 2 garantit que la longueur d'entrée est une puissance de 2: si ce n'est pas le cas, un zéro de remplissage sera introduit à un moment donné.

`        % Do...while loop
  2e     %   Reshape as a two-row matrix, with a padding zero if needed
         %   Row 1 contains the original odd-indexed entries, row 2 the
         %   even-indexed
  Z}     %   Split matrix into two vectors, one corresponding to each row
  yy     %   Duplicate those two vectors
  =      %   Check if corresponding entries are equal or not
  &=     %   Matrix of all pairwise comparisons. This will give a matrix
         %   filled with ones if and only if the previous check gave all
         %   true or all false (condition 1)
  tn1>   %   Duplicate and push true if size exceeds 1, or false otherwise
         %   (condition 3)
  hh     %   Concatenate condition 1, condition 3, and the original copy of
         %   the second piece (condition 2). The resulting vector is truthy
         %   if and only if it doesn't contain any zero
]        % End
1X=      % True if top of the stack is a single 1, false otherwise

Haskell, 66 octets

Oui, des listes infinies!

o=[1]:(o>>= \x->[x++map(0-)x,x++x])
f l=l`elem`take(2*2^length l)o

Versions alternatives:

o=[1]:(o<**>map(>>=flip(++))[map(0-),id])
f=Data.List.Ordered.hasBy(comparing length)o

APL, 46 octets

{0::0⋄⍵≡,1:1⋄⍬≡⍵:0⋄(∇Z↑⍵)∧(∇Y)∨∇-Y←⍵↓⍨Z←.5×⍴⍵}

Assez simple:

• Cas de base:
  • 0::0: si une erreur se produit, retourne 0
  • ⍵≡,1:1: si l'entrée est exactement [1], retourne 1
  • ⍬≡⍵:0: si l'entrée est la liste vide, retourne 0
• Cas récursif:
  • Z←.5×⍴⍵: Zest la moitié de la longueur de l'entrée
  • Y←⍵↓⍨Z: Yest la dernière moitié de l'entrée (cela échoue si elle ⍴⍵est inégale, déclenchant le gestionnaire d'exceptions)
  • (∇Y)∨∇-Y: soit la dernière moitié de la liste, soit la négation de la dernière moitié de la liste, doit être un code OVSF
  • (∇Z↑⍵)∧: et la première moitié de la liste doit être un code OVSF.

Haskell, 69 68 octets

g x=any(elem x)$scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]]x

Exemple d'utilisation: g [-1,1]-> False.

Encore plus inefficace que la réponse de @ flawr . Cela prend trop de temps et de mémoire pour 4 listes d'éléments. Pour voir que la liste des codes OVSF (avec beaucoup de doublons) est réellement créée, essayez:

take 10 $ c $ scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]] [1..4]

qui revient

[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]]

c'est-à-dire que la liste commence avec les 16 listes d'éléments (4 fois concaténées, à cause de [1..4]), continue avec les 8 listes d'éléments et ainsi de suite jusqu'à ce qu'elle se termine par [1].

Modifier: @xnor a enregistré un octet. Merci!

Python 2 , 78 75 octets

def f(x):l=len(x)/2;return[n*x[l]*f(x[:l])for n in x[l:]]==x[:l]>[]or[1]==x

Essayez-le en ligne!

JavaScript (ES6), 80

f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

Construit récursivement et vérifie chaque liste jusqu'à la longueur de la liste d'entrée, en commençant par [1].

La valeur de retour est JS véridique ou falsey, spécifiquement 1ou truesi valide, 0ou falseou undefinedsi non valide.

Tester

f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

test=`[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True`
.split('\n')

test.forEach(r=>{
  input = r.match(/-?1/g)||[]
  check = r.slice(-4) == 'True'
  result = f(input)
  console.log(result, check, '['+input+']')
})

Clojure, 118 octets

(defn f[C](or(=(count C)1)(let[l(/(count C)2)[a b](split-at l C)](and(> l 0)(=(count b)l)(apply =(map * a b))(f a)))))

Divise l'entrée cen deux moitiés aetb vérifie si leurs produits par élément sont tous identiques. Si c'est le cas, vérifie que la première moitié est une séquence valide.

Celui-ci fait 142 octets mais je l'ai trouvé plus intéressant:

#((set(nth(iterate(fn[I](mapcat(fn[i][(concat i i)(concat i(map - i))])I))[[1][-1]])(loop[l(count %)i 0](if(< l 2)i(recur(/ l 2)(inc i))))))%)

loopcalcule log_2la longueur de l'entrée, iterategénère des séquences de ce nombre d'itérations en fonction de la définition. Cela renvoie l'argument d'entrée s'il s'agit d'une séquence valide et nilsinon.