Is it an OVSF code?

Question

Given a list of 1s and -1s, determine whether or not it is a valid OVSF code (by outputting a truthy or falsey value).

OVSF codes are defined as follows:

• [1] is an OVSF code.

• If X is an OVSF code, then X ++ X and X ++ -X are both OVSF codes.

  Here ++ is list concatenation, and - negates every element in the list.

• No other lists are valid OVSF codes.

You may assume the input list contains only -1 and 1, but you must handle the empty list correctly, as well as lists whose length is not a power of 2.

Shortest code (in bytes) wins.

Test cases

[] -> 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

Answer 1

Jelly, 18 16 14 11 bytes

^2/Eam2µḊ¿Ṭ

Outputs [1] (truthy) for OVSF codes, [] (falsy) otherwise.

Try it online!

Background

Like @LuisMendo's MATL answer and @xnor's Python answer, this submission verifies the input array "from the inside out".

Every (non-overlapping) pair of elements of a OVSF code of length two or higher is essentially a copy of the the first pair, either with the same signs or with both signs swapped. Likewise, every (non-overlapping) 4-tuple of elements of a OVSF code of length four or higher is essentially a copy of the the first 4-tuple, either with the same signs or with both signs swapped. The same is true for 8-tuples, 16-tuples, etc., up to the length of the OVFS code.

One way to verify this is to check all pairs for equality modulo the sign first, then remove the second element of each pair (which is now redundant information). If we repeat this process once more, we're essentially checking all 4-tuples. In the next iteration, we're comparing 8-tuples, etc.

Finally, if all the required 2^k-tuples were equal modulo the sign and the array has been reduced to a singleton, it is sufficient to check if the remaining element is a 1.

How it works

^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.

Answer 2

Mathematica, 52 47 45 bytes

Byte count assumes CP-1252 encoding and $CharacterEncoding set to WindowsANSI (the default on Windows installations).

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

This defines a variadic function PlusMinus, which takes the input list as a flat list of arguments and returns a boolean, e.g. PlusMinus[1, -1, -1, 1] gives True. It's theoretically also usable as an operator ±, but that operator is only syntactically valid in unary and binary contexts, so the calling convention would get weird: ±##&[1,-1,-1,1]. It will throw a bunch of warnings that can be ignored.

This will also throw a few warnings which can be ignored.

There might be away to shorten the somewhat annoying a!==b!||{a}==-{b} part, but I'm not finding anything right now. Keywords like SubsetQ and MatrixRank are simply too long. :/

Explanation

The solution basically defers all the tricky things to Mathematica's pattern matcher and is therefore very declarative in style. Apart from some golfitude on the first line, this really just adds three different definitions for the operator ±:

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

The first two rows were shortened by nesting the definitions and expressing True as 1>0.

We should deconstruct this further to show how this actually defines a variadci function PlusMinus by only using unary and binary operator notation. The catch is that all operators are simply syntactic sugar for full expressions. In our case ± corresponds to PlusMinus. The following code is 100% equivalent:

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

By using sequences (sort of like splats in other languages) as the operands to ± we can cover an arbitrary number of arguments to PlusMinus, even though ± isn't usable with more than two arguments. The fundamental reason is that syntactic sugar is resolved first, before any of these sequences are expanded.

On to the definitions:

The first definition is simply a fallback (___ matches an arbitrary list of arguments). Anything that isn't matched by the more specific definitions below will give False.

The second definition is the base case for the OVSF, the list containing only 1. We define this to be True.

Finally, the third definition applies only to lists that can be decomposed into X ++ X or X ++ -X, and recursively uses the result for X. The definition is limited to these lists by ensuring they can be split into subsequences a and b with a__±b__ and then attaching the condition (/;) that either {a}=={b} or {a}==-{b}. Defining PlusMinus as a variadic function in this weird way via an operator saves a whopping 5 bytes over defining a unary operator ± on lists.

But wait, there's more. We're using a!==b! instead of {a}=={b}. Clearly, we're doing this because it's two bytes shorter, but the interesting question is why does it work. As I've explained above, all operators are just syntactic sugar for some expression with a head. {a} is List[a]. But a is a sequence (like I said, sort of like a splat in other languages) so if a is 1,-1,1 then we get List[1,-1,1]. Now postfix ! is Factorial. So here, we'd get Factorial[1,-1,1]. But Factorial doesn't know what to do when it has a different number of arguments than one, so this simply remains unevaluated. == doesn't really care if the thing on both sides are lists, it just compares the expressions, and if they are equal it gives True (in this case, it won't actually give False if they aren't, but patterns don't match if the condition returns anything other than True). So that means, the equality check still works if there are at least two elements in the lists. What if there's only one? If a is 1 then a! is still 1. If a is -1 then a! gives ComplexInfinity. Now, comparing 1 to itself still works fine of course. But ComplexInfinity == ComplexInfinity remains unevaluated, and doesn't give true even though a == -1 == b. Luckily, this doesn't matter, because the only situation this shows up in is PlusMinus[-1, -1] which isn't a valid OVSF anyway! (If the condition did return True, the recursive call would report False after all, so it doesn't matter that the check doesn't work out.) We can't use the same trick for {a}==-{b} because the - wouldn't thread over Factorial, it only threads over List.

The pattern matcher will take care of the rest and simply find the correct definition to apply.

Answer 3

Haskell, 57 bytes

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

Given input list l, grows a OVSF code s by starting from [1] and repeatedly concatenating either s or -s, whichever makes the first element match that of l. Then, checks that the result is l at the end. This is checked once s has length at least that of l.

Some alternatives recursive structures also happened to give 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]

Answer 4

MATLAB/Octave, 94 bytes

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

This is using a new approach: The allowed OVSF codes of length N appear in the log2(N)-th Walsh-matrix, as they are basically defined by the same recursion:

Walsh matrices are special cases of the Hadamard-matrices of size N x N if N is a power of two. (There are also Hadamard matrices of other sizes.) MATLAB and Octave have a variety of built in functions that generate test matrices to test properties of numerical algorithms, among them is hadamard(). Fortunately for powers of two MATLAB's hadamard() usex exactly the construction of the Welsh-matrices.

So this function first checks whether the inputs length is a power of two, and if it is, it checks whether it is a row of the corresponding size Welsh-matrix.

Try it online!

Answer 5

Python, 64 bytes

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

Splits the list into even-indexed elements and odd-indexed elements via slices. Checks if the result vectors are either equals or negatives by multiplying one by the sign forced by its first element. Then, does the same recursive check on the even-indexed elements.

For the base case, if the check fails, rejects unless the list is [1]. The empty list is also specifically rejected to avoid an infinite loop.

A different strategy like my Haskell answer gives 66 bytes:

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

Answer 6

Haskell, 106 91 87 86 bytes

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

The function g generates the n iteration of lists (relatively inefficiently, since length $ g n == 3^n, however if we'd delete the duplicates, we'd get 2^n), f checks if our list is in any one of them. Thanks to @Zgrab for a few hints!

Try it online!

Answer 7

JavaScript (ES6), 130 93 87 85 83 bytes

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

Demo

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

Answer 8

JavaScript (ES6), 85 61 bytes

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

Previous version which checked elements to ensure that they were 1 or -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)

Explanation:

• The length cannot be zero
• The length must be a power of 2
• The first element must be 1
• Elements in positions that are a power of 2 must be either 1 or -1
• Elements in other positions are the product of all the elements in the positions corresponding to the bitmask, e.g. a[22] == a[2] * a[4] * a[16]. Since a[20] == a[4] * a[16] has already been checked, only a[22] == a[2] * a[20] needs to be checked.
• The above check gives degenerate results for i not having at least two bits set. In the case of zero bits set, it checks that a[0] == a[0] * a[0], which is false for a[0] == -1, while in the case of one bit set, it checks that a[i] == a[0] * a[i].

Answer 9

MATL, 21 20 bytes

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

Try it online! Or verify all test cases.

How it works

The code splits the array into two equal-length pieces: the first with the odd-indexed entries, the second with the even-indexed entries. The two pieces are forced to have equal length, with a padding zero in the second if needed. Then the code checks that

1. The corresponding entries of the two pieces are either all equal or all different;
2. No entry in the second piece is zero;
3. The length of the pieces exceeds 1.

If these three conditions are met, the process is applied again on the first piece. If the loop is exited because the length was already 1, the input is an OFSV code. Else it is not.

Condition 1 iterated is an equivalent version of the defining property of OVSF codes. For an array of say length 8, the straightforward approach would be to check that entries 1,2,3,4 are all equal or all different to entries 5,6,7,8 respectively (this is the defining property). But we can equivalently check that entries 1,3,5,7 are all equal or all different to entries 2,4,6,8 respectively; and this turns out to use fewer bytes.

Condition 2 makes sure that the input length is a power of 2: if it's not, a padding zero will be introduced at some stage.

`        % 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

Answer 10

Haskell, 66 bytes

Yay, infinite lists!

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

Alternative versions:

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

Answer 11

Haskell, 69 68 bytes

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

Usage example: g [-1,1] -> False.

Even more inefficient than @flawr's answer. It takes too much time and memory for 4 element lists. To see that the list of OVSF codes (with a lot of duplicates) is actually created, try:

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

which returns

[[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]]

i.e. the list starts with all 16 element lists (4 times concatenated, because of [1..4]), continues with all 8 element lists and so on until it ends with [1].

Edit: @xnor saved a byte. Thanks!

Answer 12

APL, 46 bytes

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

Fairly straightforward:

• Base cases:
  • 0::0: if an error occurs, return 0
  • ⍵≡,1:1: if the input is exactly [1], return 1
  • ⍬≡⍵:0: if the input is the empty list, return 0
• Recursive case:
  • Z←.5×⍴⍵: Z is half the length of the input
  • Y←⍵↓⍨Z: Y is the last half of the input (this fails if ⍴⍵ is uneven, triggering the exception handler)
  • (∇Y)∨∇-Y: either the last half of the list, or the negation of the last half of the list, must be an OVSF code
  • (∇Z↑⍵)∧: and the first half of the list must be an OVSF code.

Answer 13

Python 2, 78 75 bytes

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

Try it online!

Answer 14

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

Recursively builds and check each list up to the length of the input list, starting with [1].

Return value is JS truthy or falsey, specifically 1 or true if valid, 0 or false or undefined if not valid.

Test

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+']')
})

Answer 15

Clojure, 118 bytes

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

Splits input c into two halves a and b and checks if their element-wise products are all identical. If so, checks that the first half is valid sequence.

This one is 142 bytes but I found it more interesting:

#((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))))))%)

loop calculates log_2 of input's length, iterate generates sequences of that many iterations based on the definition. This returns the input argument if it is a valid sequence and nil otherwise.