3
\$\begingroup\$

The basis vectors for geometric algebra are

$$(e_0=1), e_1, e_2,\dots,e_n$$

They all square to 1 (we do not consider vectors which square to -1 or zero)

$$e_i \cdot e_i = 1$$

They are associative and anticommutative (except \$e_0=1\$ which is associative and commutative)

$$e_i \cdot e_j =-e_j \cdot e_i \: \; (i\neq j); \;and\; i,j > 0$$

For example, this product is simplified to

$$e_1 \cdot e_3 \cdot e_3 \cdot e_5\cdot e_4 \cdot e_5 \\ = e_1 \cdot (e_3 \cdot e_3) \cdot (e_5\cdot e_4) \cdot e_5 \\ = e_1 \cdot (1) \cdot (-e_4\cdot e_5) \cdot e_5 \\ = e_1 \cdot (-e_4) \cdot (e_5 \cdot e_5) \\ = e_1 \cdot (-e_4) \cdot (1) \\ = - e_1 \cdot e_4$$

(note that the simplified product is sorted by the index of \$e\$)

Challenge

If a product of basis vectors is represented by a signed integer where each bit is 1 if the vector is present, or 0 if the vector is not present

$$\begin{align} 0101011 & = e_0 \cdot e_1 \cdot e_3 \cdot e_5 \\ & = e_0^1 \cdot e_1^1 \cdot e_2^0 \cdot e_3^1 \cdot e_4^0 \cdot e_5^1 \cdot e_6^0 \\ -0101011 & = -e_0 \cdot e_1 \cdot e_3 \cdot e_5 \end{align}$$

Given two signed integers \$a\$, \$b\$ (you can choose the numeric encoding for negative values), output the product \$c= a \:. b\$

The input is only 2 signed integers. There are many ways to encode signed integers. You can pick anyone, but the input is only 2 variables.

Note that \$| c |= |a|\; XOR \; |b|\$ , but the tricky part is to find the sign.

If the language doesn't allow its integer type to encode signed zeros (\$-00000\$), the code should return \$-00001\$ (because \$-e_0^0=-e_0^1=-1\$)

Because \$x=e_0 \cdot x=x \cdot e_0\$, then \$x=x \;OR\; 1\$, so is equally valid to return 0 or 1 for \$e_0\$

You should at least calculate for 4 basis vectors \$e_0=1, e_1, e_2, e_3\$

Here is a multiplication table generator (to check the right answers), which also offers code in C++, C#, Python and Rust (the webpage requires to manually specify how many vectors square to 1,-1 and 0. You can set 3 (or more) positive, 0 negative, and 0 Zero)

Here is Rosetta code in many languages for geometric algebra

Example:

given a, b: $$a=e_1 \cdot e_2=00110$$

$$b=e_2 \cdot e_3=01100$$

possible products are:

$$c=a.b=e_1 \cdot e_3=01010$$

$$c=b.a=-e_1 \cdot e_3=-01010$$

note that $$b.b=-e_0^0=-1 =-00000$$

So, the sign has to be calculated even if the number is 00000, because \$+00000 \neq -00000\$

Example: \$a=-e_2=-00100\\ b=-e_1 \cdot e_2=-00110\\ c=a.b=(-1 \cdot e_2)(-1 \cdot e_1 \cdot e_2)\\ =(-1) \cdot (e_2)(-1) \cdot (e_1 \cdot e_2)\\ = (e_2 \cdot e_1)\cdot e_2\\ =(-e_1 \cdot e_2)\cdot e_2\\ =(-e_1) \cdot (e_2\cdot e_2)\\ =-e_1=-00010\$

but \$b.a=00010\$

\$e_0=1\$ and -1 are scalars and commute with any basis vector (do not anticommute), so negative signs on the input can be treated as in standard multiplication of integers: \$-*-=+\\ +*-=-*+=-\$

Example: \$a=e_1\cdot e_2 \cdot e_3=01110\\ b=-e_1 \cdot e_2=-00110\\ c=a.b=(e_1e_2e_3)(-e_1e_2)\ =-(e_1e_2e_3)(e_1e_2)\\ =-(-e_1e_2e_1e_3e_2)\\ =-(e_1e_1e_2e_3e_2)\\ =-(e_1e_1)(-e_2e_2e_3)\\ =e_3=01000\\ \\ b.a=e_3=01000\$

Note that on this case, \$b.a=a.b\$, so the basis vectors \$e_i\$ anticommute, but it doesn't means that always \$b.a=-a.b\$


This is not part of the challenge, but I would appreciate suggestions on how should be encoded vectors which square to -1 or 0

This Pyhton code generates the right answers

Python 3, 11427 bytes



"""3D Projective Geometric Algebra.

Written by a generator written by enki.
"""

__author__ = 'Enki'

import math

class R300:
    def __init__(self, value=0, index=0):
        """Initiate a new R300.
         
        Optional, the component index can be set with value.
        """
        self.mvec = [0] * 8
        self._base = ["1", "e1", "e2", "e3", "e12", "e13", "e23", "e123"]
        #self._base = ["0001", "0010", "0100", "1000", "0110", "1010", "1100", "1110"]
        if (value != 0):
            self.mvec[index] = value
            
    @classmethod
    def fromarray(cls, array):
        """Initiate a new R300 from an array-like object.

        The first axis of the array is assumed to correspond to the elements
        of the algebra, and needs to have the same length. Any other dimensions
        are left unchanged, and should have simple operations such as addition 
        and multiplication defined. NumPy arrays are therefore a perfect 
        candidate. 

        :param array: array-like object whose length is the dimension of the algebra.
        :return: new instance of R300.
        """
        self = cls()
        if len(array) != len(self):
            raise TypeError('length of array must be identical to the dimension '
                            'of the algebra.')
        self.mvec = array
        return self
        
    def __str__(self):
        if isinstance(self.mvec, list):
            res = ' + '.join(filter(None, [("%.7f" % x).rstrip("0").rstrip(".") + (["",self._base[i]][i > 0]) if abs(x) > 0.000001 else None for i,x in enumerate(self)]))
            #res = ' + '.join([x for i,x in enumerate(self)])
        else:  # Assume array-like, redirect str conversion
            res = str(self.mvec)
        if (res == ''):
            return "0"
        return res

    def __getitem__(self, key):
        return self.mvec[key]

    def __setitem__(self, key, value):
        self.mvec[key] = value
        
    def __len__(self):
        return len(self.mvec)

    def __invert__(a):
        """R300.Reverse
        
        Reverse the order of the basis blades.
        """
        res = a.mvec.copy()
        res[0] = a[0]
        res[1] = a[1]
        res[2] = a[2]
        res[3] = a[3]
        res[4] = -a[4]
        res[5] = -a[5]
        res[6] = -a[6]
        res[7] = -a[7]
        return R300.fromarray(res)

    def Dual(a):
        """R300.Dual
        
        Poincare duality operator.
        """
        res = a.mvec.copy()
        res[0] = -a[7]
        res[1] = -a[6]
        res[2] = a[5]
        res[3] = -a[4]
        res[4] = a[3]
        res[5] = -a[2]
        res[6] = a[1]
        res[7] = a[0]
        return R300.fromarray(res)

    def Conjugate(a):
        """R300.Conjugate
        
        Clifford Conjugation
        """
        res = a.mvec.copy()
        res[0] = a[0]
        res[1] = -a[1]
        res[2] = -a[2]
        res[3] = -a[3]
        res[4] = -a[4]
        res[5] = -a[5]
        res[6] = -a[6]
        res[7] = a[7]
        return R300.fromarray(res)

    def Involute(a):
        """R300.Involute
        
        Main involution
        """
        res = a.mvec.copy()
        res[0] = a[0]
        res[1] = -a[1]
        res[2] = -a[2]
        res[3] = -a[3]
        res[4] = a[4]
        res[5] = a[5]
        res[6] = a[6]
        res[7] = -a[7]
        return R300.fromarray(res)

    def __mul__(a,b):
        """R300.Mul
        
        The geometric product.
        """
        if type(b) in (int, float):
            return a.muls(b)
        res = a.mvec.copy()
        res[0] = b[0] * a[0] + b[1] * a[1] + b[2] * a[2] + b[3] * a[3] - b[4] * a[4] - b[5] * a[5] - b[6] * a[6] - b[7] * a[7]
        res[1] = b[1] * a[0] + b[0] * a[1] - b[4] * a[2] - b[5] * a[3] + b[2] * a[4] + b[3] * a[5] - b[7] * a[6] - b[6] * a[7]
        res[2] = b[2] * a[0] + b[4] * a[1] + b[0] * a[2] - b[6] * a[3] - b[1] * a[4] + b[7] * a[5] + b[3] * a[6] + b[5] * a[7]
        res[3] = b[3] * a[0] + b[5] * a[1] + b[6] * a[2] + b[0] * a[3] - b[7] * a[4] - b[1] * a[5] - b[2] * a[6] - b[4] * a[7]
        res[4] = b[4] * a[0] + b[2] * a[1] - b[1] * a[2] + b[7] * a[3] + b[0] * a[4] - b[6] * a[5] + b[5] * a[6] + b[3] * a[7]
        res[5] = b[5] * a[0] + b[3] * a[1] - b[7] * a[2] - b[1] * a[3] + b[6] * a[4] + b[0] * a[5] - b[4] * a[6] - b[2] * a[7]
        res[6] = b[6] * a[0] + b[7] * a[1] + b[3] * a[2] - b[2] * a[3] - b[5] * a[4] + b[4] * a[5] + b[0] * a[6] + b[1] * a[7]
        res[7] = b[7] * a[0] + b[6] * a[1] - b[5] * a[2] + b[4] * a[3] + b[3] * a[4] - b[2] * a[5] + b[1] * a[6] + b[0] * a[7]
        return R300.fromarray(res)
    __rmul__ = __mul__

    def __xor__(a,b):
        res = a.mvec.copy()
        res[0] = b[0] * a[0]
        res[1] = b[1] * a[0] + b[0] * a[1]
        res[2] = b[2] * a[0] + b[0] * a[2]
        res[3] = b[3] * a[0] + b[0] * a[3]
        res[4] = b[4] * a[0] + b[2] * a[1] - b[1] * a[2] + b[0] * a[4]
        res[5] = b[5] * a[0] + b[3] * a[1] - b[1] * a[3] + b[0] * a[5]
        res[6] = b[6] * a[0] + b[3] * a[2] - b[2] * a[3] + b[0] * a[6]
        res[7] = b[7] * a[0] + b[6] * a[1] - b[5] * a[2] + b[4] * a[3] + b[3] * a[4] - b[2] * a[5] + b[1] * a[6] + b[0] * a[7]
        return R300.fromarray(res)


    def __and__(a,b):
        res = a.mvec.copy()
        res[7] = 1 * (a[7] * b[7])
        res[6] = 1 * (a[6] * b[7] + a[7] * b[6])
        res[5] = -1 * (a[5] * -1 * b[7] + a[7] * b[5] * -1)
        res[4] = 1 * (a[4] * b[7] + a[7] * b[4])
        res[3] = 1 * (a[3] * b[7] + a[5] * -1 * b[6] - a[6] * b[5] * -1 + a[7] * b[3])
        res[2] = -1 * (a[2] * -1 * b[7] + a[4] * b[6] - a[6] * b[4] + a[7] * b[2] * -1)
        res[1] = 1 * (a[1] * b[7] + a[4] * b[5] * -1 - a[5] * -1 * b[4] + a[7] * b[1])
        res[0] = 1 * (a[0] * b[7] + a[1] * b[6] - a[2] * -1 * b[5] * -1 + a[3] * b[4] + a[4] * b[3] - a[5] * -1 * b[2] * -1 + a[6] * b[1] + a[7] * b[0])
        return R300.fromarray(res)


    def __or__(a,b):
        res = a.mvec.copy()
        res[0] = b[0] * a[0] + b[1] * a[1] + b[2] * a[2] + b[3] * a[3] - b[4] * a[4] - b[5] * a[5] - b[6] * a[6] - b[7] * a[7]
        res[1] = b[1] * a[0] + b[0] * a[1] - b[4] * a[2] - b[5] * a[3] + b[2] * a[4] + b[3] * a[5] - b[7] * a[6] - b[6] * a[7]
        res[2] = b[2] * a[0] + b[4] * a[1] + b[0] * a[2] - b[6] * a[3] - b[1] * a[4] + b[7] * a[5] + b[3] * a[6] + b[5] * a[7]
        res[3] = b[3] * a[0] + b[5] * a[1] + b[6] * a[2] + b[0] * a[3] - b[7] * a[4] - b[1] * a[5] - b[2] * a[6] - b[4] * a[7]
        res[4] = b[4] * a[0] + b[7] * a[3] + b[0] * a[4] + b[3] * a[7]
        res[5] = b[5] * a[0] - b[7] * a[2] + b[0] * a[5] - b[2] * a[7]
        res[6] = b[6] * a[0] + b[7] * a[1] + b[0] * a[6] + b[1] * a[7]
        res[7] = b[7] * a[0] + b[0] * a[7]
        return R300.fromarray(res)


    def __add__(a,b):
        """R300.Add
        
        Multivector addition
        """
        if type(b) in (int, float):
            return a.adds(b)
        res = a.mvec.copy()
        res[0] = a[0] + b[0]
        res[1] = a[1] + b[1]
        res[2] = a[2] + b[2]
        res[3] = a[3] + b[3]
        res[4] = a[4] + b[4]
        res[5] = a[5] + b[5]
        res[6] = a[6] + b[6]
        res[7] = a[7] + b[7]
        return R300.fromarray(res)
    __radd__ = __add__

    def __sub__(a,b):
        """R300.Sub
        
        Multivector subtraction
        """
        if type(b) in (int, float):
            return a.subs(b)
        res = a.mvec.copy()
        res[0] = a[0] - b[0]
        res[1] = a[1] - b[1]
        res[2] = a[2] - b[2]
        res[3] = a[3] - b[3]
        res[4] = a[4] - b[4]
        res[5] = a[5] - b[5]
        res[6] = a[6] - b[6]
        res[7] = a[7] - b[7]
        return R300.fromarray(res)

    def __rsub__(a,b):
        """R300.Sub
                
        Multivector subtraction
        """
        return b + -1 * a


    def smul(a,b):
        res = a.mvec.copy()
        res[0] = a * b[0]
        res[1] = a * b[1]
        res[2] = a * b[2]
        res[3] = a * b[3]
        res[4] = a * b[4]
        res[5] = a * b[5]
        res[6] = a * b[6]
        res[7] = a * b[7]
        return R300.fromarray(res)


    def muls(a,b):
        res = a.mvec.copy()
        res[0] = a[0] * b
        res[1] = a[1] * b
        res[2] = a[2] * b
        res[3] = a[3] * b
        res[4] = a[4] * b
        res[5] = a[5] * b
        res[6] = a[6] * b
        res[7] = a[7] * b
        return R300.fromarray(res)


    def sadd(a,b):
        res = a.mvec.copy()
        res[0] = a + b[0]
        res[1] = b[1]
        res[2] = b[2]
        res[3] = b[3]
        res[4] = b[4]
        res[5] = b[5]
        res[6] = b[6]
        res[7] = b[7]
        return R300.fromarray(res)


    def adds(a,b):
        res = a.mvec.copy()
        res[0] = a[0] + b
        res[1] = a[1]
        res[2] = a[2]
        res[3] = a[3]
        res[4] = a[4]
        res[5] = a[5]
        res[6] = a[6]
        res[7] = a[7]
        return R300.fromarray(res)


    def ssub(a,b):
        res = a.mvec.copy()
        res[0] = a - b[0]
        res[1] = -b[1]
        res[2] = -b[2]
        res[3] = -b[3]
        res[4] = -b[4]
        res[5] = -b[5]
        res[6] = -b[6]
        res[7] = -b[7]
        return R300.fromarray(res)


    def subs(a,b):
        res = a.mvec.copy()
        res[0] = a[0] - b
        res[1] = a[1]
        res[2] = a[2]
        res[3] = a[3]
        res[4] = a[4]
        res[5] = a[5]
        res[6] = a[6]
        res[7] = a[7]
        return R300.fromarray(res)


    def norm(a):
        return abs((a * a.Conjugate())[0]) ** 0.5
        
    def inorm(a):
        return a.Dual().norm()
        
    def normalized(a):
        return a * (1 / a.norm())

e1 = R300(1.0, 1)
e2 = R300(1.0, 2)
e3 = R300(1.0, 3)
e12 = R300(1.0, 4)
e13 = R300(1.0, 5)
e23 = R300(1.0, 6)
e123 = R300(1.0, 7)

if __name__ == '__main__':
    #print("e1*e1         :", str(e1*e1))
    #print("pss           :", str(e123))
    #print("pss*pss       :", str(e123*e123))


    a = [R300(1.0, i) for i in range(0, 8) ]
    b = [-1 * x for x in a]
    a = a + b
    print("Vectors:")
    [print(str(x)) for x in a ]
    print("Products")
    
    def javascriptCode(a,b):
        def ArnauldEncoding(x):
            answer= str(x)
            if answer[0]=="-":
                return answer[1:]+"1"
            else:
                return answer+"0"
        return "".join(["console.log(\"0b",ArnauldEncoding(a) , "\",\"*\",\"0b" , ArnauldEncoding(b),"\",\"=\",","f(0b" , ArnauldEncoding(a) , ")(0b" , ArnauldEncoding(b) , ").toString(2), \"== \",\"" , ArnauldEncoding(a * b),"\")"])
    
    def RubyCode(a,b):
        return "".join(["[","0b",str(a),",","0b",str(b),"],"]).replace("0b-","-0b")

    if True:
        Productos = ["".join([str(x),"*",str(y),"=",str(x * y)]) for x in a for y in a]
        #Productos = [javascriptCode(x,y) for x in a for y in a]
        #Productos = [RubyCode(x,y) for x in a for y in a]
        #Productos = [str(x*y) for x in a for y in a]
        
        Origen = ["1e1", "1e2", "1e3", "1e12", "1e13", "1e23", "1e123"]
        Destino = ["0010", "0100", "1000", "0110", "1010", "1100", "1110"]

        Reemplazo = dict(zip(Origen, Destino))
        Binario = Productos
        for key in sorted(Reemplazo, key=len, reverse=True): # Through keys sorted by length
            Binario = [x.replace(key,Reemplazo[key]) for x in Binario]
        [print(x) for x in Binario]
    a = a


Try it online!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Welcome to Code Golf, by the way! \$\endgroup\$ Sep 23, 2021 at 3:10
  • 7
    \$\begingroup\$ Please consider add some testcases here, so everyone may check if their answers are correct before post it. \$\endgroup\$
    – tsh
    Sep 23, 2021 at 3:43
  • 3
    \$\begingroup\$ Please add more testcases directly in your post, it's much clearer that way. \$\endgroup\$
    – Noodle9
    Sep 23, 2021 at 9:09
  • 2
    \$\begingroup\$ If we really have to support negative inputs, you should add such test cases as well. \$\endgroup\$
    – Arnauld
    Sep 23, 2021 at 12:35
  • 4
    \$\begingroup\$ For future challenges, please consider relaxing your input format. Cumbersome I/O formats is currently the #1 thing to avoid when writing challenges. It leads to boring boilerplate code which is not related to the actual task. \$\endgroup\$
    – Arnauld
    Sep 23, 2021 at 16:38

7 Answers 7

4
\$\begingroup\$

JavaScript (ES6),  73  65 bytes

Expects (a)(b), two integers where the least significant bit holds the sign (\$0\$ for positive, \$1\$ for negative) and all other bits are used to store the absolute value.

Returns the product \$c\$ in the same format.

a=>b=>a^b^(g=a=>(b/=2)&&(h=n=>b&!!n&&!h(n&~-n))(a)^g(a>>1))(a>>2)

Try it online!

How?

We compute the product \$p\$ of \$a\$ and \$b\$ as follows:

  • We start with \$p=a\operatorname{xor}b\$. This immediately gives the correct absolute value and initializes the sign according to the signs of \$a\$ and \$b\$.
  • For each set bit in \$b\$ at index \$i>0\$, we invert the sign bit of \$p\$ if there's an odd number of set bits in \$a\$ at an index greater than \$i\$.

Commented

a => b =>         // (a, b) = input integers
a ^ b ^ (         // compute a XOR b XOR ...
  g = a =>        // ... the result of the recursive function g, taking a:
    (b /= 2) &&   //   divide b by two; this is shorter than a right shift
                  //   and will eventually evaluate to zero because of
                  //   arithmetic underflow 
    ( h = n =>    //   h is another recursive function counting the bits
                  //   set in n, provided that the LSB of b is set:
      b & !!n &&  //     stop if the LSB of b is not set or n = 0
      !h(n & ~-n) //     otherwise, invert the result and do a recursive
                  //     call where the least significant bit set in n
                  //     is cleared
    )(a) ^        //   initial call to h with n = a
    g(a >> 1)     //   XOR the result with a recursive call to g with
                  //   floor(a / 2)
)(a >> 2)         // initial call to g with floor(a / 4), which discards
                  // the sign bit and the 1st bit of the absolute value
\$\endgroup\$
6
  • 1
    \$\begingroup\$ I don't program javascript, but there may be a bug test \$\endgroup\$
    – Yijapod
    Sep 27, 2021 at 5:48
  • 1
    \$\begingroup\$ @Yijapod You are not using the encoding format described in my answer. For instance -3 is encoded as 3 << 1 | 1, which is 0b111. \$\endgroup\$
    – Arnauld
    Sep 27, 2021 at 6:18
  • 1
    \$\begingroup\$ My bad!. Your code is verified. Can't link to the test, because url shorteners don't work \$\endgroup\$
    – Yijapod
    Sep 27, 2021 at 7:36
  • 1
    \$\begingroup\$ @Yijapod This is the main reason why at least a few test cases should be included in the challenge. It makes the answer validation process much easier for everyone. \$\endgroup\$
    – Arnauld
    Sep 27, 2021 at 9:43
  • \$\begingroup\$ The question said "Given two signed integers a, b". So can we assume the input is already in variables a,b? That would let you shave off the 6 characters a=>b=> at the beginning. (In my answer too.) \$\endgroup\$
    – Don Hatch
    Oct 18, 2021 at 4:59
3
\$\begingroup\$

JavaScript (ES6), 42 bytes

(standing on Arnauld's shoulders)

Using same encoding as Arnauld. That is: Expects (a)(b), two integers where the least significant bit holds the sign (\$0\$ for positive, \$1\$ for negative) and all other bits are used to store the absolute value. Returns the product \$c\$ in the same format.

a=>b=>a^b^(g=x=>x&&x^g(x/2))(g(a/4)&b/2)&1

Explanation:

  • really it's a=>b=>a^b^(g=x=>x&&x^g(x>>1))(g(a>>2)&(b>>1))&1 but using divisions instead of rightshifts to save a char each (taking advantage of the fact that the recursion stops on arithmetic underflow-- same crazy trick as Arnauld-- and that fractional parts are discarded by bitwise operators
  • since (b>>1) was changed to (b/2), the parens can be removed around the b/2 since / binds tighter than &
  • and & binds tighter than ^ so no parens needed there either
  • start with a^b, same explanation as Arnauld.
  • g(x) is "xor of all rightshifts of x", i.e. g(x) = x^(x>>1)^(x>>2)^...
  • note that g(x)&1 is the parity of the number of bits set in x
  • each bit position in g(a>>2)&(b>>1) is the parity of the number of swaps involving that position in (the magnitude part of) b, so the desired parity of the total number of swaps will be the parity of the number of bits set in g(a>>2)&(b>>1); that is, g(g(a>>2)&(b>>1))&1.
\$\endgroup\$
3
\$\begingroup\$

Python 3, 69 bytes

def g(a,b):
 r=a^b;b&=-2
 while a:a>>=1;r^=a&b&1;b=b>>1^b&1
 return r

Try it online!

The lowest bit is the sign. There is no test script and all GA packages I found are really hard to apply here, so I did not test this thoroughly. Please let me know if this is incorrect.

I'm not a code golfer, but anyone feel free to use this solution and code-golfify it.

It took me a while to come up with this algorithm... a bit hard to explain.

Does it makes sense to store the sign bit? In the end positive and negative have to be combined anyway?

Some explanation:

def g(a, b):
    r = a ^ b
    b &= -2             # I think the sign bit needs to be cleared
    while a:
        a >>= 1         # iterate through all bits
        r ^= a & b & 1  # modify sign of result
        b = (b >> 1) ^ (b & 1)  # iterate through bits of b, but lowest bit is XOR or all bits so far
    return r

The lowest bit of b is used as an aggregator of all its bits with XOR. It's tracking the parity - comparable to counting tail bits in more direct solutions. It took some thought to show that this equivalent.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! As this is a [code-golf] challenge, we require answers to make an effort to be short, such as single character variable names. This is a 68 byte implementation of your answer, if you'd like to use it. Be sure to check out our Tips for golfing in Python page for ways you can golf your program \$\endgroup\$ Dec 9, 2021 at 18:50
  • \$\begingroup\$ Thanks. I took your advice and made it shorter. \$\endgroup\$
    – Gere
    Dec 9, 2021 at 22:30
  • \$\begingroup\$ Nice method with the b parity accumulation! Note that you write b=b>>1^b&1 without parens -- the operator precedence works out. \$\endgroup\$
    – xnor
    Dec 9, 2021 at 23:45
2
\$\begingroup\$

Ruby, 98 ... 62 bytes

->c,w,d,x{[c^d,w*x*(~k=0)**((0..c+d).sum{|x|c[x]*k+=d[x-1]})]}

Try it online!

Input: [abs(a),sign(a),abs(b),sign(b)]

Output: [abs,sign]

Thanks Arnauld for the idea of splitting input and for shaving a couple of bytes.

How it works:

The sign is determined by the number of hops: example: e3*(e1e2) = -e1e3*(e2) = (-e1)*(-e2e3) = e1e2e3

In this case e3 must "hop" over e1 and e2 to get to its own place, and for an even number of hops the sign is positive.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Remember than the input is 2 signed integers. If you map them to 4 integers, the mapping is counted as code length. You can pick any encoding for signed integers, but the input is only 2 signed integers. \$\endgroup\$
    – Yijapod
    Sep 23, 2021 at 16:29
  • \$\begingroup\$ I think you can just do w*x*(-1)**... \$\endgroup\$
    – Arnauld
    Sep 23, 2021 at 16:51
  • 1
    \$\begingroup\$ @Yijapod: Then probably all signs are inverted because the parameters are given in inverted order. Hard to tell what's wrong when there is no clear test case to check. \$\endgroup\$
    – G B
    Sep 27, 2021 at 7:36
  • \$\begingroup\$ @G B I added python code generating all products for 4 vectors. It also generates test cases for your code \$\endgroup\$
    – Yijapod
    Sep 27, 2021 at 7:37
  • \$\begingroup\$ @Yijapod it seems to me like your example -0b01010 0b01000 is -e1e3*e3 .. why is that not -e1*1 and then just -e1 ? if you look at the Cayley table that you linked on bivector.net we can see that e1e3e3 should become e13e3, which becomes e1. which i would think that means means -e1e3 e3 should become -e1 \$\endgroup\$
    – don bright
    Oct 7, 2021 at 5:30
2
\$\begingroup\$

05AB1E (legacy), 35 bytes

bD€¨0ìï©C`^s€θ·<P®€S`.sR‚ζOÆ.±!P*¨ì

Input as two integers where the trailing bit of its binary representation represents the negative (0) or positive (1) (i.e. input 24 is -12/-1100 and input 25 is 12/1100).

Try it online or verify some more test cases.

Explanation:

b                    # Convert both integers in the (implicit) input-pair to a binary
                     # string
 D                   # Duplicate this pair of binary strings
  ۬                 # Remove the trailing bit from each
    0ìï              # Prepend a "0", and cast it to an integer
                     # (empty strings become "0", everything else remains the same)
       ©             # Store this in variable `®` (without popping)
        C            # Change these binary strings to integers
         `           # Pop and push both values separated to the stack
          ^          # Bitwise-XOR them together
 s                   # Swap to get the pair of binary strings again
  €θ                 # Leave just the trailing bits
                     # Convert the 0 to -1:
    ·                #  Double both: 0→0; 1→2
     <               #  Decrease both by 1: 0→-1; 2→1
      P              # Take the product of this as our starting sign
  ®                  # Push the binary string from `®` again
   €S                # Convert both to a list of bits
     `               # Pop and push the lists separated to the stack
      .s             # Get the suffices of the second one
        R            # Reverse this list of suffices
         ‚           # Pair the two lists together
          ζ          # Zip/transpose, swapping rows/columns,
                     # implicitly using a space filler if they're of unequal lengths
           O         # Sum each inner-most list
                     # (the spaces are counted as 0 in the legacy version)
            Æ        # Reduce both lists by subtracting
             .±      # Get the sign of this (-1 if <0; 0 if ==0; 1 if >0)
               !     # Get the factorial of this: -1 if -1; 1 if 0 or 1)
                P    # Take the product of these values
                 *   # Multiply it to our initial sign value
                  ¨  # Remove the trailing "1" from this sign value
                   ì # And prepend this "" or "-" in front of the XOR-ed value
                     # (after which it is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's buggy with 1 as input. [x,1] returns all the input data. \$\endgroup\$
    – Yijapod
    Oct 7, 2021 at 5:20
  • \$\begingroup\$ @Yijapod Should be fixed now, at the cost of 3 bytes. \$\endgroup\$ Oct 7, 2021 at 10:53
1
\$\begingroup\$

Retina, 102 bytes

\d\b
0
^'0P`\d+
(.+)-
-$1
+r`((0|(?<-3>1)|(1))*)((0)|1)((?<-7>.)*\*.*)1(?=(.)*)
$#3*-$1$#5$6_
--|\*.+

Try it online! Link includes test cases. Assumes the input is in the binary form as generated by the program linked in the question. (Save 9 bytes if the inputs are always padded and 7 bytes if they never include e₀). Explanation:

\d\b
0

Remove e₀ if it appears.

^'0P`\d+

Pad both numbers to the same length. (Note that when run on a test suite, all of the numbers in the suite are padded to the same length.)

(.+)-
-$1

If the second number is negative, negate both numbers.

+r`((0|(?<-3>1)|(1))*)((0)|1)((?<-7>.)*\*.*)1(?=(.)*)
$#3*-$1$#5$6_

For each 1 bit in the second number, working from e₁ upwards, use a .NET balancing group to find the matching bit in the first number and another .NET balancing group to count the parity of the 1 bits before that bit. If the parity is odd, negate the first number. Toggle the matching bit in the first number and replace the 1 bit in the second number with a _ (golfier than a 0).

--|\*.+

Remove any double negatives and the second number (which is now zero at this point).

\$\endgroup\$
1
  • \$\begingroup\$ ✓ Verified for 4 digits (encodes ±1 as ±0000) \$\endgroup\$
    – Yijapod
    Oct 3, 2021 at 19:36
0
\$\begingroup\$

Python 3, 768 bytes

i got a bit stuck on this one, wanted to post anyways in case someone else has an idea.

instead of counting bits this uses 'rewriting rules' and a dictionary to rewrite substrings of the e-string iteratively until the expression is simplified and cant be rewritten anymore.

the main problem im having is converting from integer to string and back takes a lot of bytes. the second problem is encoding the dictionary takes a lot of bytes.

main function is m(), the for -15 to 16 loop is a test loop. note i consider 0000 to be equivalent to 0001 since \$e_0^0 = e_0^1\$

rules = {'11':'','22':'','33':'','10':'-01','13':'-31','20':'-02','21':'-12','30':'-03','31':'-13','32':'-23','3-':'-3','2-':'-2','1-':'-1','0-':'-0','--':'',}
def dorules(s):
  for r in rules.keys():
    s=s.replace(r,rules[r]).replace(' ','')
  return s
def b2e(x):
  s='-' if x<0 else ''
  for i in range(1,3):
    if abs(x) & (2**i):
        s += str(i)
  return s
def e2b(x):
  s=0
  for i in x:
    try: s|=2**int(i)
    except: pass
  b=bin(s)[2:].zfill(4)
  if x=='': return b
  if x=='-': return '-'+b
  if int(x)<0: return '-'+b
  return b
def m(i,j):
  s=['',b2e(i)+b2e(j)]
  while True:
    s += [dorules(s[-1])]
    if s[-2] == s[-1] or s[-3] == s[-1]: break
  return s[-1]
def sign(x): return '-' if int(x)<0 else ''
for i in range(-15,16):
  for j in range(-15,16):
    c=e2b(m(i,j))
    print(sign(i)+bin(abs(i))[2:].zfill(4)+'*'+sign(j)+bin(abs(j))[2:].zfill(4)+'='+c)
\$\endgroup\$
0

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.