14
\$\begingroup\$

The xorspace of a set of integers is the set of all integers that can be obtained by combining the starting integers with the usual bitwise xor operator (^). For example, the xorspace of (8, 4) is (0, 4, 8, 12): 0 is 4^4, 12 is 4^8, and no other numbers can be reached. Note that the starting numbers are always included, by this definition (for example, 4 is 4^4^4).

Your goal is to write the shortest program that takes a list of non-negative integers as input, and outputs the number of elements in their xorspace.

  • Standard loopholes are forbidden.
  • Input and output can be in any of the usual formats. Input is guaranteed to be valid, non-empty, and without duplicates.
  • Your code should be able to process all test cases in less than a day.

Test cases

Input: 0
Output: 1

Input: 6
Output: 2

Input: 8 4
Ouput: 4

Input: 0 256
Output: 2

Input: 256 259 3
Output: 4

Input: 60 62 94 101 115
Output: 32

Input: 60 62 94 101 115 40 91
Output: 32

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64

Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768
\$\endgroup\$
0

8 Answers 8

10
\$\begingroup\$

MATL, 11 bytes

t"G!Z~Ghu]n

Try it online!

The last test case doesn't run in the online interpreter because of memory limitations, but runs offline in less than 2 seconds on a modern computer.

Explanation

For input of size n, this does the following:

  1. Initiallize result to input.
  2. Repeat n times:
    1. Apply bitwise XOR to all pair of entries from current result and input.
    2. Attach input values to the result.
    3. Deduplicate.
  3. The output is the number of elements of the final result.

Commented code.

t      % Implicit input: row vector. Duplicate
"      % For each (i.e. do as many times as the input size)
  G!   %   Push input as a column vector
  Z~   %   Bitwise XOR with broadcast, i.e. for all pairs of entries of the
       %   two arguments. The first argument is the accumulated result
       %   from the previous iteration, the second is the input vector
  G    %   Push input again
  h    %   Postpend
  u    %   Unique values. Gives a row vector
]      % End
n      % Number of entries. Implicitly display

Example

The intermediate results (steps 2.1 and 2.3) for input [256 259 3] are:

First iteration: [256 259 3] with [256 259 3]: computing all pairs of bitwise-XOR gives the matrix

  0   3 259
  3   0 256
259 256   0

Attaching [256 259 3] and deduplicating

0 3 259 256

Second iteration: current result [0 3 259 256] with [256 259 3]. After deduplicating this again gives

0 3 259 256

Third iteration: again

0 3 259 256

So the output is 4 (number of entries of result).

\$\endgroup\$
13
  • \$\begingroup\$ Explanation please? You can't use O(2^n). \$\endgroup\$ Jun 5, 2017 at 13:59
  • \$\begingroup\$ I have no idea how it works, but it’s definitely not O(2^n). It actually solves the (1 2 3 … 63) test-case pretty quickly, even though it’s the worst-case for the brute-force method. \$\endgroup\$
    – Grimmy
    Jun 5, 2017 at 14:01
  • 2
    \$\begingroup\$ How is this so quick? I've been trying to do pretty much the same in Jelly, but the first attempt got killed after 19 minutes... (Now trying with more RAM.) \$\endgroup\$
    – Dennis
    Jun 5, 2017 at 14:13
  • 2
    \$\begingroup\$ I believe this is O(2ⁿ) worst case; it's just that in the test that exercises it, n is only 15, so the program still runs fairly quickly. \$\endgroup\$
    – user62131
    Jun 5, 2017 at 14:41
  • 2
    \$\begingroup\$ @ais523 The intermediate numbers obtained from bitwise-XOR can never get greater than the maximum number in the input, call that M. So the size of the vector of intermediate results never exceeds M, and complexity is O(M*M). The OP has said that the exact definition of n doesn't matter, so if I define n as M I can claim this to be O(n*n). \$\endgroup\$
    – Luis Mendo
    Jun 5, 2017 at 14:53
8
\$\begingroup\$

Haskell, 64 bytes

f takes a list of integers and returns an integer.

import Data.Bits
f l|m<-maximum l,m>0=2*f(min<*>xor m<$>l)|0<1=1

Try it online!

This doesn't handle an empty list, for that you can but $0: instead of the space after maximum.

How it works

  • If the maximum m of the list is zero, returns 1.
  • Otherwise, xors every element with the maximum.
    • If the result is smaller than the element, the element is replaced by it.
    • This necessarily zeroes the most significant bit set anywhere in the list.
    • Then recurses on the resulting list, doubling the result of the recursion.
  • This process essentially performs Gaussian elimination (although throwing away the final rows by setting them to 0) modulo 2, on the matrix whose rows are the bit representations of the list of numbers. The set of bit representations of the "xorspace" is the vector space modulo 2 spanned by the rows of this matrix, and whose number of elements is 2 to the power of the matrix's row rank.
  • This algorithm is polynomial time, so should definitely be better than O(2^n).
\$\endgroup\$
1
  • \$\begingroup\$ This is basically the algorithm I was thinking of (for beating the complexity bounds), although this is a particularly elegant way to represent it. It's nice to see it in a properly golfed answer. \$\endgroup\$
    – user62131
    Jun 6, 2017 at 22:40
4
\$\begingroup\$

Mathematica, 52 bytes

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&
\$\endgroup\$
3
  • \$\begingroup\$ Why did you delete your Pari/GP answer? It seemed to be working fine. EDIT: nevermind, it failed some test-cases actually. \$\endgroup\$
    – Grimmy
    Jun 5, 2017 at 14:22
  • \$\begingroup\$ @Grimy Why did you accept my answer? This is a code-golf, the shortest code wins. \$\endgroup\$
    – alephalpha
    Jun 12, 2017 at 10:16
  • \$\begingroup\$ Sorry, I changed the accepted answer to the 7 bytes packed Pyth one. \$\endgroup\$
    – Grimmy
    Jun 12, 2017 at 12:13
3
\$\begingroup\$

05AB1E, 8 bytes

vDy^ìÙ}g

Try it online!

All test-cases finish in under 1 minute on TIO.

\$\endgroup\$
6
  • \$\begingroup\$ This fails the last criterion: « Your code should be able to process all test cases in less than a day (no O(2**n) stuff). » \$\endgroup\$
    – Grimmy
    Jun 5, 2017 at 13:24
  • \$\begingroup\$ @Grimy: Didn't read the 2^n part :/ \$\endgroup\$
    – Emigna
    Jun 5, 2017 at 13:25
  • \$\begingroup\$ @Grimy: Now updated to finish allt test-cases in under 1 minute (and with fewer bytes used) \$\endgroup\$
    – Emigna
    Jun 5, 2017 at 15:11
  • \$\begingroup\$ Was thinking âü^Ùg until I saw you can xor more than once, nice solution. \$\endgroup\$ Jun 5, 2017 at 15:27
  • \$\begingroup\$ @carusocomputing: That saves a byte, but I'm not sure about the complexity. \$\endgroup\$
    – Emigna
    Jun 5, 2017 at 15:37
3
\$\begingroup\$

Python 2, 55 bytes

r={0}
for n in input():r|={x^n for x in r}
print len(r)

Try it online!

Beats out functions:

f=lambda l,r={0}:l and f(l[1:],r|{x^l[0]for x in r})or len(r)
f=lambda l:len(reduce(lambda r,n:r|{x^n for x in r},l,{0}))

Ørjan Johansen's beautiful row elimination method is one byte shorter.

Python 2, 54 bytes

f=lambda l:1-any(l)or 2*f([min(x,x^max(l))for x in l])

Try it online!

\$\endgroup\$
0
2
\$\begingroup\$

Pyth, 8 bytes

lu{+xM*Q

Test suite

Explanation:

To generate the xorspace, we find the fixpoint of taking the xor of every pair of numbers, adding in every number, and deduplicating. Then, we take the length of the result. This runs in 20 seconds (offline only) on the final test case.

lu{+xM*Q
lu{+xM*QGGQ    Implicit variable introduction
 u        Q    Find the fixed point of the following, starting with the input,
               where the current value is G.
      *QG      Form the Cartesian product of Q (input) and G (current)
    xM         Take the xor of every pair
   +           Add the current values
  {            Deduplicate
l              Output the length of the result.

Packed Pyth, 7 bytes

Hexdump:

0000000: d9d7 dabf 1355 51                        .....UQ

The same as the above, with a 7-bit ASCII encoding.

Put the above in a file with xxd -r, and run it as follows:

py packed-pyth.py xorspace.ppyth '[256, 259, 3]'
\$\endgroup\$
2
  • \$\begingroup\$ I think you can do l{mxFdy. \$\endgroup\$
    – xnor
    Jun 6, 2017 at 2:28
  • \$\begingroup\$ @xnor y applied to the 1 through 63 test case is much too slow. I don't have 2^63 memory. \$\endgroup\$
    – isaacg
    Jun 6, 2017 at 2:51
2
\$\begingroup\$

Jelly, 9 8 bytes

0œ|⁺^¥/L

Finishes all test cases in under 8 seconds on TIO, with negligible memory requirements.

Try it online!

How it works

0œ|⁺^¥/L  Main link. Argument: A (array)

0œ|       Perform multiset union with 0, prepending 0 if A doesn't contain it.
      /   Reduce A by the link to the left.
     ¥      Combine the previous two links into a dyadic chain.
            Left argument: V (array). Right argument: n (integer)
    ^           Bitwise XOR each element in V with n.
   ⁺            This quick refers to the previous link, making it a shorthand for
                the link 'œ|'. Thus, it performs multiset union on V and the array
                of bitwise XORs.
       L  Compute the length of the result.
\$\endgroup\$
1
\$\begingroup\$

Python, 113 bytes

def f(x):
 u,s=[0],{0}
 while u:
	a=u.pop()
	for b in x:
	 c=a^b
	 if c not in s:u+=[c]
	 s.add(c)
 return len(s)
\$\endgroup\$
6
  • \$\begingroup\$ It works, but I’m counting 113 bytes; did I miss something? \$\endgroup\$
    – Grimmy
    Jun 5, 2017 at 13:53
  • \$\begingroup\$ @totallyhuman that’s probably because you’re counting tabulations as 8 bytes, rather than a single byte. \$\endgroup\$
    – Grimmy
    Jun 5, 2017 at 13:59
  • \$\begingroup\$ If the first indentation is a space, next one is a tab, and the last one a tab + a space (or 2 tabs), then it's 113 bytes \$\endgroup\$
    – daniero
    Jun 5, 2017 at 14:00
  • \$\begingroup\$ @Grimy Actually each tab is 4 spaces not 8. \$\endgroup\$ Jun 5, 2017 at 14:00
  • \$\begingroup\$ A full program would be shorter, as it saves a handful of indentation. Also, the for loop can be condensed into a single line, as u+=[c][c in s:] is equivalent to your if statement. \$\endgroup\$
    – Dennis
    Jun 5, 2017 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.