18
\$\begingroup\$

A Bit of Background

The exterior algebra is a central object in topology and physics (for the physics concept cf. fermion). The basic rule dictating the behavior of the exterior algebra is that \$yx = -xy\$ (and consequently \$x^2 = -x^2 = 0\$). Applying this rule twice we see that \$yzx = -yxz = xyz\$.

The product of two monomials is 0 if any repeated variable occurs, e.g. \$vxyz * stuv = 0\$ because \$v\$ is repeated. Otherwise, we want to put the variables into some standard order, say alphabetical order, and there is a sign introduced that counts how many variables we passed by each other, so for example \$tvy * suxz = +stuvxyz\$ because it takes a total of six crossings to put \$tvysuxz\$ into alphabetical order (on each line I have highlighted the most recently swapped pair): $$tvy * suxz = +\, tvy\;suxz\\ \phantom{tvy * suxz } {}= -tv\mathbf{\large sy}uxz\\ \phantom{tvy * suxz } {}= +t\mathbf{\large sv}yuxz\\ \phantom{tvy * suxz } {}= -\mathbf{\large st}vyuxz\\ \phantom{tvy * suxz } {}= +stv\mathbf{\large uy}xz\\ \phantom{tvy * suxz } {}= -st\mathbf{\large uv}yxz\\ \phantom{tvy * suxz } {}= +stuv\mathbf{\large xy}z\\ $$ Your task will be to compute this sign.

This is a special case of the Koszul Sign Rule which determines the sign of the terms in many sums in math. If you are familiar with determinants, the sign in the determinant formula is an example.

Task

You will take as input two 32 bit integers \$a\$ and \$b\$, which we will interpret as bitflags. You may assume that \$a\$ and \$b\$ have no common bits set, in other words that \$a\mathrel{\&}b = 0\$. Say a pair of integers \$(i, j)\$ where \$0\leq i,j < 32\$ is an "out of order pair in \$(a,b)\$" when:

  1. \$i < j\$,
  2. bit \$i\$ is set in \$b\$, and
  3. bit \$j\$ is set in \$a\$.

Your goal is to determine whether the number of out of order pairs in \$(a,b)\$ is even or odd. You should output true if the number of out of order pairs is odd, false if it is even.

Input

A pair of 32 bit integers. If you would like your input instead to be a list of 0's and 1's or the list of bits set in each integer, that's fine.

Output

true or any truthy value if the number of out of order pairs is odd, false or any falsey value if it is even. Alternatively, it is fine to output any pair of distinct values for the two cases. It is also fine to output any falsey value when the number of out of order pairs is odd and any truthy value when the number of out of order pairs is even.

Metric

This is code golf so shortest code in bytes wins.

Test cases

    a = 0b000000
    b = 0b101101 
    output = false // If one number is 0, the output is always false.

    a = 0b11
    b = 0b10    
    output = UNDEFINED // a & b != 0 so the behavior is unspecified.

    a = 0b01
    b = 0b10
    output = true // 1 out of order pair (1,2). 1 is odd.

    a = 0b011
    b = 0b100
    output = false // 2 out of order pairs (1,2) and (1,3). 2 is even.

    a = 0b0101
    b = 0b1010
    output = true // 3 out of order pairs (1,2), (1,4), (3,4). 3 is odd.

    a = 0b0101010 // The example from the introduction
    b = 0b1010101 
    output = false // 6 out of order pairs (1,2), (1,4), (1,6), (3,4), (3,6), (5,6).

    a = 33957418
    b = 135299136
    output = false

    a = 2149811776
    b = 1293180930
    output = false

    a = 101843025
    b = 2147562240
    output = false

    a = 1174713364
    b = 2154431232
    output = true

    a = 2289372170
    b = 637559376
    output = false

    a = 2927666276
    b = 17825795
    output = true

    a = 1962983666
    b = 2147814409
    output = true

// Some asymmetric cases:
    a = 2214669314
    b = 1804730945
    output = true

    a = 1804730945
    b = 2214669314
    output = false

    a = 285343744
    b = 68786674
    output = false

    a = 68786674
    b = 285343744
    output = true

    a = 847773792
    b = 139415
    output = false

\$\endgroup\$
9
  • \$\begingroup\$ @ovs I think it's right as is, I'm looking for pairs that are in the "wrong" order. \$\endgroup\$
    – Hood
    Apr 25, 2020 at 14:03
  • \$\begingroup\$ Except for the trivial 1, 2 test case, all of the other test cases seem to give the same result with the inputs swapped. Can you make more test cases which give different results when you swap the inputs? \$\endgroup\$
    – Neil
    Apr 25, 2020 at 15:44
  • 1
    \$\begingroup\$ Is the idea of an antisymmetric tensor at all relevant? \$\endgroup\$
    – golf69
    Apr 26, 2020 at 2:13
  • 1
    \$\begingroup\$ @golf69, yes, it is very relevant. This is exactly the rule you use when doing calculations with differential forms, which are totally antisymmetric tensor fields. (Also I have ever heard people refer to this property by the word antisymmetry, never by anything like "Koszul sign rule".) (And it works for determinants because, well, they're totally antisymmetric in all rows & columns.) \$\endgroup\$
    – Ramillies
    Apr 26, 2020 at 8:54
  • 1
    \$\begingroup\$ @Ramillies Calling this the "Koszul sign rule" seems to be a pretty strong cultural marker. As a sign of its rarity, this is now the 3rd google hit and second duckduckgo hit for that term. Usually I would use "Koszul sign rule" more generally for rules like d(xy) = d(x)y + (-1)^{|x|}xd(y) and (a otimes b)(c otimes d) = (-1)^{|b||c|} (ac otimes bd). This is really just multiplication in an exterior algebra. \$\endgroup\$
    – Hood
    Apr 26, 2020 at 14:56

9 Answers 9

7
\$\begingroup\$

COW, 363 285 bytes

moOoommoOmoOmoOoomMOOmoOmOoMOOMOomOoMoOmoOMMMMOOMMMMOomOoMOomoOmoOMoOmOoMMMOOOmooMMMmoomoOMMMOOOmOoMMMmOoMOOmOoMMMmoOmoOmoOMMMMOOMOomoOMMMMOOMMMMOoMOoMMMOOOmooMMMMoOmOomoomOomOoOOOmoomOomOoMOOMOomoOMoOmOoMMMMOOMMMMOomoOMOomOomOoMoOmoOMMMOOOmooMMMmoomOoMMMOOOmoOMMMmoOmoOmoOmoomoOmoOOOM

Try it online!

A major change! (It's faster but still test cases exceed the 60 seconds timeout on TIO)
Now I like it better, it's cleaner, symmetric and I've brute forced the memory cells disposition for least number of movements.

The idea is to directly operate in terms of parity. Information in both LSB will be used in each iteration and then a and b will be halved, until b=0.

  • Every a%2 is calculated (during repeated subtraction) alternating +1 and -1 in one memory cell, so that their partial sum p is available.
  • When a '1' is found in b, the parity (the answer) is toggled p many times.

Detailed Explanation:

moo ]    mOo <    MOo -    OOO *    OOM i
MOO [    moO >    MoO +    MMM =    oom o


[0]: a/2     [1]: a     [2]: Sum(a%2)     [3]: b%2     [4]: b     [5]: b/2     [6]: parity


>i>>>i                        ;  Read a in [1] and b in [5]
[                             ;  Loop while [5] is non-zero
    ><                        ;     Just 2 instructions for free cause COW doesn't handle consecutive parethesis :D
    [                         ;     Loop while [5] is non-zero
        -<+>=[=-<->>+<=*]=    ;         SECTION B
    ]                         ;     [5] is 0, [3] is b%2, [5] is b/2
    >=*<=                     ;     Copy [5] in [4], delete [5]
    <                         ;     Point to [3]
    [                         ;     Loop if [3] is non-zero. '1' it's been found in b, parity gets updated
        <=>>>=                ;         Copy [2] in [5]
        [                     ;         Loop while [5] is non zero
            -                 ;             Decrement [5]
            >=[=--=*]=+<      ;             TOGGLE [6]
        ]                     ;  
        <<*                   ;         Delete [3] (to exit the loop)
    ]                         ;     
    <<                        ;     Point to [1]
    [                         ;     Loop while [1] is non-zero
        ->+<=[=->-<<+>=*]=    ;         SECTION A
    ]                         ;     [1] is 0, a%2 is added in [2], [0] is a/2
    <=*>=                     ;     Copy [0] in [1], delete [0]
    >>>                       ;     Point to [5]
]                             ;     a's and b's LSB have been treated. Now a=a/2 and b=b/2
>>o                           ;  Print [6]

SECTION ASECTION B is repeated subtraction that divide \$n\$ (a or b, resp.) by \$2\$.
This can't be done in one single step (i.e. --), because \$0\$ can't be surpassed in order to stop (so it'd be -[- =*]=). These sections contextually produce \$n\bmod 2\$ (LSB).

TOGGLE is a toggling method:
When target is 0 it fails the condition and simply +1 is done.
When target is 1 it passes the condition and it's set to -1 so that +1 on exit makes it 0.

Copy, delete, and paste in the same memory cell is a tecnique to treat a while loop like an if loop, also the seemgly useless copy-paste at the beginning of these (=[=) serves to balance the ending one (=*]=) in case if condition fails.

\$\endgroup\$
6
\$\begingroup\$

05AB1E, 11 9 bytes

Port of my Python answer. Takes a and b in reverse order, output is 1 for a odd number of out-of-order pairs, 0 for an even number.

-2 bytes thanks to @CommandMaster !

тÝo÷&bSOÉ

Try it online!

Explanation

Code        Comment                       (Example) Stack

            # implicit input              a, b
т           # push 100                    a, b, 100
 Ý          # inclusive range             a, b, [0,1,...,100]
  o         # 2**x                        a, b, [1,2,...,2**100]
   ÷        # integer divide              a, [b//1,b//2,...,b//2**100]
    &       # bitwise and                 [a&b//1, a&b//2, ..., a&b//2**100]
     b      # convert to binary           [000100, ... , 00101001001, ..., 0]
      S     # convert to a list of chars  ["0", "0", "0", "1", ..., "0"]
       O    # sum (as integers)           4 (number of "out of order pairs")
        É   # is this odd?                0
            # implicit output
\$\endgroup\$
3
  • \$\begingroup\$ 10 bytes: žwÝo÷&bSOÉ \$\endgroup\$ Apr 25, 2020 at 16:34
  • \$\begingroup\$ 9 bytes: тÝo÷&bSOÉ (replaces the 32 with the one char 100 constant) \$\endgroup\$ Apr 25, 2020 at 16:39
  • \$\begingroup\$ @CommandMaster thanks a lot \$\endgroup\$
    – ovs
    Apr 25, 2020 at 16:50
5
\$\begingroup\$

J, 13 bytes

2|[:+/@,>/&I.

Try it online!

Take our input as lists of ones and zeros.

  • &I. Convert both a and b to a lists of the indexes of the ones.
  • >/ Create a function table of all pairs of those indexes, where a cell will be 1 when the a index is greater than the b index.
  • [:+/@, Flatten the table and sum all the ones.
  • 2| Remainder when you divide 2 into that sum. Will be 1 (true) exactly when the sum is odd.
\$\endgroup\$
4
\$\begingroup\$

Jelly, 8 bytes

:Ƭ2&BSSḂ

A dyadic Link accepting an integer, \$b\$, on the left and an integer, \$a\$, on the right which yields 0 (even) or 1 (odd).

Try it online! Or see the test-suite.

How?

:Ƭ2&BSSḂ - Link: integer b, integer a
  2      - literal two
 Ƭ       - starting with b, collect up while results are distinct, applying:
:        -   integer division
   &     - bitwise AND (vectorises) with a
    B    - convert to binary (vectorises)
     S   - sum
      S  - sum
       Ḃ - least significant bit (i.e. mod 2)
\$\endgroup\$
4
\$\begingroup\$

Python 2, 49 46 bytes

-3 bytes thanks to Arnauld (and Noodle9)!

f=lambda a,b:b and~int(bin(a&b),13)&1^f(a,b/2)

Try it online!

\$\endgroup\$
1
3
\$\begingroup\$

JavaScript (ES6),  42  39 bytes

Takes input as (a)(b).

Almost identical to ovs' answer.

a=>g=(b,n=a&b)=>n?!g(b,n&n-1):b&&g(b/2)

Try it online!

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

Charcoal, 19 bytes

NθNη﹪Σ⭆φ⍘&×θX²ι粦²

Try it online! Link is to verbose version of code. Outputs - for true, nothing for false. Port of @ovs's Python answer. Works for somewhat more than 32 bits. Explanation:

Nθ                  Input `a` as a number
  Nη                Input `b` as a number
      ⭆φ            Loop from 0 to 999 and join
          ×θX²ι     Left shift `a` that many times
         &     η    Bitwise And with `b`
        ⍘       ²   Convert to base 2 as a string
     Σ              Count total number of bits
    ﹪             ² Reduce modulo 2
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 52 bytes

+`.(.*)¶.(.*)$
$&¶¶$1¶$2
(.+¶0|¶1).*¶¶

M`1
[13579]$

Try it online! Takes input in padded binary. Explanation:

+`.(.*)¶.(.*)$
$&¶¶$1¶$2

Generate all of the pairs of suffixes of the inputs.

(.+¶0|¶1).*¶¶

Delete the pairs of suffixes if the suffix of b starts with 0, otherwise just delete the suffixes of b.

M`1

Count the total number of bits of suffixes of a remaining.

[13579]$

Check whether the total is odd.

\$\endgroup\$
1
\$\begingroup\$

Io, 88 bytes

Port of the 05AB1E answer.

method(a,b,Range 0 to(100)map(x,((a/2**x)floor&b)asBinary)join removeSeq("0")size isOdd)

Try it online!

\$\endgroup\$

Your Answer

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

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