Skip to main content
3 of 9
added 1139 characters in body
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975

Mathematica, 52 50 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 unary operator ± which takes a list as input and returns a boolean. It will throw a bunch of warnings that 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.

The first definition is simply a fallback (_ matches an arbitrary argument). 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}. There's one super weird golfing trick here. We're using !a==!b instead of {a}=={b}. Obviously, we're doing this because it's too bytes shorter but the more interesting question is why does it work. {a}=={b} is really List[a]==List[b]. But then a and b are sequences which are similar to splats in other languages so if a is 1,-1,1, say we'd get List[1,-1,1]. The trick is to find a unary operator (so we can save a byte), which doesn't actually evaluate to anything. If we used +a that would result in Plus[1,-1,1] which is really just 1+(-1)+1 and that would immediately be evaluated as 1. However, the Not function (operator !) doesn't actually know what to do with non-boolean arguments (or any number of arguments other than 1). So !a is Not[1,-1,1] and that's completely meaningless. So it remains unevaluated (and throws a warning). However, this is just an expression which can be compared for equality with ==. Whether the head is List or Not doesn't matter for ==. We can't use the same trick for {a}==-{b} because - only threads over Lists, not arbitrary heads.

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

Martin Ender
  • 197.2k
  • 67
  • 447
  • 975