Nuestros mejores desarrolladores agotaron sus reservas de café, por su búsqueda todo el tiempo por la resolución, hasta que Amanda encontró la respuesta en Gitea así que hoy la comparte contigo.
Solución:
Mathematica, 5247 45 bytes
El recuento de bytes asume la codificación CP-1252 y $CharacterEncoding ajustado a WindowsANSI (el valor predeterminado en las instalaciones de Windows).
±___=!(±1=1>0)
a__±b__/;a!==b!||a==-b:=±a
Esto define una función variádica PlusMinus, que toma la lista de entrada como una lista plana de argumentos y devuelve un valor booleano, p. ej. PlusMinus[1, -1, -1, 1] da True. En teoría, también se puede utilizar como operador. ±, pero ese operador solo es sintácticamente válido en contextos unarios y binarios, por lo que la convención de llamada se volvería extraña: ±##&[1,-1,-1,1]. Lanzará un montón de advertencias que pueden ignorarse.
Esto también arrojará algunas advertencias que pueden ignorarse.
Allí podría estar lejos para acortar el algo molesto a!==b!||a==-b parte, pero no encuentro nada en este momento. Palabras clave como SubsetQ y MatrixRank son simplemente demasiado largas. : /
Explicación
La solución básicamente difiere todas las cosas complicadas al comparador de patrones de Mathematica y, por lo tanto, tiene un estilo muy declarativo. Aparte de algo de golfitud en la primera línea, esto realmente solo agrega tres definiciones diferentes para el operador ±:
±___=False;
±1=True;
a__±b__/;a!==b!||a==-b:=±a
Las dos primeras filas se acortaron anidando las definiciones y expresando True como 1>0.
Deberíamos deconstruir esto más a fondo para mostrar cómo esto realmente define una función variadci PlusMinus utilizando únicamente la notación de operador unario y binario. El problema es que todos los operadores son simplemente azúcar sintáctico para expresiones completas. En nuestro caso ± corresponde a PlusMinus. El siguiente código es 100% equivalente:
PlusMinus[___]=False;
PlusMinus[1]=True;
PlusMinus[a__,b__]/;a!==b!||a==-b:=PlusMinus[a]
Mediante el uso de secuencias (algo así como símbolos en otros lenguajes) como operandos para ± podemos cubrir un número arbitrario de argumentos para PlusMinus, aunque ± no se puede utilizar con más de dos argumentos. La razón fundamental es que el azúcar sintáctico se resuelve primero, antes de que se expanda cualquiera de estas secuencias.
Pasando a las definiciones:
La primera definición es simplemente una alternativa (___ coincide con una lista arbitraria de argumentos). Cualquier cosa que no coincida con las definiciones más específicas a continuación dará False.
La segunda definición es el caso base para el OVSF, la lista que contiene solo 1. Definimos esto como True.
Finalmente, se aplica la tercera definición solamente a listas que se pueden descomponer en X ++ X o X ++ -Xy utiliza de forma recursiva el resultado para X. La definición se limita a estas listas asegurándose de que se puedan dividir en subsecuencias a y b con a__±b__ y luego adjuntando la condición (/;) Eso tampoco a==b o a==-b. Definiendo PlusMinus como una función variada de esta extraña manera a través de un operador ahorra una enorme 5 bytes sobre la definición de un operador unario ± en listas.
Pero espera hay mas. Estamos usando a!==b! en lugar de a==b. Claramente, estamos haciendo esto porque es dos bytes más corto, pero la pregunta interesante es por qué funciona. Como expliqué anteriormente, todos los operadores son simplemente azúcar sintáctico para alguna expresión con cabeza. a es List[a]. Pero a es un secuencia (como dije, una especie de símbolo en otros idiomas) así que si a es 1,-1,1 entonces tenemos List[1,-1,1]. Ahora postfix ! es Factorial. Entonces aquí, obtendríamos Factorial[1,-1,1]. Pero Factorial no sabe qué hacer cuando tiene un número diferente de argumentos que uno, por lo que esto simplemente permanece sin evaluar. == realmente no le importa si las cosas en ambos lados son listas, solo compara las expresiones, y si son iguales, da True (en este caso, en realidad no dará False si no lo son, pero los patrones no coinciden si la condición devuelve algo diferente a True). Eso significa que la verificación de igualdad aún funciona si hay al menos dos elementos en las listas. ¿Y si solo hay uno? Si a es 1 luego a! es todavía 1. Si a es -1 luego a! da ComplexInfinity. Ahora, comparando 1 a sí mismo todavía funciona bien, por supuesto. Pero ComplexInfinity == ComplexInfinity permanece sin evaluar, y no dar true aunque a == -1 == b. Afortunadamente, esto no importa, porque la única situación en la que esto aparece es PlusMinus[-1, -1] que no es un OVSF válido de todos modos. (Si la condición regresó True, la llamada recursiva informaría False después de todo, por lo que no importa que la verificación no funcione). No podemos usar el mismo truco para a==-b porque el - no se enhebraría Factorial, solo se enhebra List.
El comparador de patrones se encargará del resto y simplemente encontrará la definición correcta para aplicar.
Haskell, 57 bytes
q=length
f l=l==until((>=q l).q)(s->s++map(*l!!q s)s)[1]
Lista de entrada dada l, crece un código OVSF s comenzando desde [1] y concatenando repetidamente s o -s, lo que haga que el primer elemento coincida con el de l. Luego, verifica que el resultado sea l al final. Esto se verifica una vez s tiene una longitud al menos la de l.
Algunas estructuras recursivas alternativas también dieron 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 s0=s==l
g[1]
Gelatina, 18dieciséis14 11 bytes
^2/Eam2µḊ¿Ṭ
Salidas [1] (veraz) para códigos OVSF, [] (falso) de lo contrario.
¡Pruébelo en línea!
Fondo
Al igual que la respuesta MATL de @ LuisMendo y la respuesta de Python de @ xnor, esta presentación verifica la entrada array “de adentro hacia afuera”.
Cada par (no superpuesto) de elementos de un código OVSF de longitud dos o superior es esencialmente una copia del primer par, ya sea con los mismos signos o con ambos signos intercambiados. Asimismo, cada 4-tupla (no superpuesta) de elementos de un código OVSF de longitud cuatro o superior es esencialmente una copia de la primera 4-tupla, ya sea con los mismos signos o con ambos signos intercambiados. Lo mismo es true para 8 tuplas, 16 tuplas, etc., hasta la longitud del código OVFS.
Una forma de verificar esto es verificar la igualdad de todos los pares en el módulo del signo primero, luego eliminar el segundo elemento de cada par (que ahora es información redundante). Si repetimos este proceso una vez más, esencialmente estamos comprobando las 4 tuplas. En la siguiente iteración, comparamos 8 tuplas, etc.
Finalmente, si todos los 2 requeridosk-tuplas eran iguales módulo el signo y el array se ha reducido a un singleton, basta con comprobar si el elemento restante es un 1.
Cómo funciona
^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.