Return to Answer

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

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

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

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.

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