Implement true string addition

Question

Many languages allow strings to be "added" with +. However this is really concatenation, a true addition would follow the group axioms:

• It is closed (the addition of any two strings is always a string)

• It is associative ( \$\forall a b . (a + b) + c = a + (b + c)\$)

• There is an identity (\$\exists e . \forall a . a + e = a\$)

• Every element has an inverse (\$\forall a . ∃b . a + b = e\$)

^{(concatenation violates the 4th group axiom)}

So my task to you is to implement a true string addition, that is a function that takes two sequences of bytes representing strings and returns a third such that your function satisfies all the group axioms on sequences of bytes.

It must work on all sequence of bytes representing strings including those with null bytes.

This is code-golf so answers will be scored in bytes with less bytes being better.

Answer 1

Python 3, 177 170 163 130 bytes

lambda a,b:s(d(a)^d(b))
def s(n,x=0,s=''):
 while n:n-=1;s+=chr(n%256);n>>=8
 return s
def d(n,c=0):
 while s(c)!=n:c+=1
 return c

Try it online!

-14 bytes thanks to notjagan

-33 bytes thanks to Leaky Nun (and switched endianness)

I have no business trying to golf anything in Python, but I didn't want to use Lua since this method needs large exact integers to work on reasonable length stings. (Note: the algorithm is still Really Slow when ramping up the string length.) This is mostly just to provide an answer ;)

Each string is self-inverse, and the empty string is the identity. This simply performs xor under a simple bijection between strings and non-negative integers. s is a helper function that computes the bijection (one way only), and d is the inverse.

Non-slow version (148 bytes, courtesy of Leaky Nun):

lambda a,b:s(d(a)^d(b))
def s(n,x=0,s=''):
 while n:n-=1;s=chr(n%256)+s;n>>=8
 return s
def d(n,c=0):
 while n:c=c*256+ord(n[0])+1;n=n[1:]
 return c

Try it online!

I'm going to hijack this for a group-theory primer as well.

Any right inverse is a left inverse: inv(a) + a = (inv(a) + a) + e = (inv(a) + a) + (inv(a) + inv(inv(a))) = inv(a) + (a + inv(a)) + inv(inv(a)) = (inv(a) + e) + inv(inv(a)) = inv(a) + inv(inv(a)) = e

This also means that a is an inverse of inv(a).

Any right identity is a left identity: e + a = (a + inv(a)) + a = a + (inv(a) + a) = a

The identity is unique, given other identity f: e = e + f = f

If a + x = a then x = e: x = e + x = (inv(a) + a) + x = inv(a) + (a + x) = inv(a) + a = e

Inverses are unique, if a + x = e then: x = e + x = (inv(a) + a) + x = inv(a) + (a + x) = inv(a) + e = inv(a)

Following the proofs should make it fairly easy to construct counterexamples for proposed solutions that don't satisfy these propositions.

Here's a more natural algorithm I implemented (but didn't golf) in Lua. Maybe it will give someone an idea.

function string_to_list(s)
  local list_val = {}
  local pow2 = 2 ^ (math.log(#s, 2) // 1) -- // 1 to round down
  local offset = 0
  list_val.p = pow2
  while pow2 > 0 do
    list_val[pow2] = 0
    if pow2 & #s ~= 0 then
      for k = 1, pow2 do
        list_val[pow2] = 256 * list_val[pow2] + s:byte(offset + k)
      end
      list_val[pow2] = list_val[pow2] + 1
      offset = offset + pow2
    end
    pow2 = pow2 // 2
  end
  return list_val
end

function list_to_string(list_val)
  local s = ""
  local pow2 = list_val.p
  while pow2 > 0 do
    if list_val[pow2] then
      local x = list_val[pow2] % (256 ^ pow2 + 1)
      if x ~= 0 then
        x = x - 1
        local part = ""
        for k = 1, pow2 do
          part = string.char(x % 256) .. part
          x = x // 256
        end
        s = s .. part
      end
    end
    pow2 = pow2 // 2
  end
  return s
end

function list_add(list_val1, list_val2)
  local result = {}
  local pow2 = math.max(list_val1.p, list_val2.p)
  result.p = pow2
  while pow2 > 0 do
    result[pow2] = (list_val1[pow2] or 0) + (list_val2[pow2] or 0)
    pow2 = pow2 // 2
  end
  return result
end

function string_add(s1, s2)
  return list_to_string(list_add(string_to_list(s1), string_to_list(s2)))
end

The idea is basically to split the string based on the power-of-two components of its length, and then treat these as fields with a missing component representing zero, and each non-missing component representing numbers from 1 up to 256^n, so 256^n+1 values total. Then these representations can be added component-wise modulo 256^n+1.

Note: This Lua implementation will have numeric overflow problems for strings of sizes greater than 7. But the set of strings of length 7 or less is closed under this addition.

Try it online!

Answer 2

Python 3.8, 93 bytes

f=lambda a,b,L=len:f(c:=a.rstrip(x:=a[-1]),x*(L(a)-L(c)^L(b)-L(d:=b.lstrip(x)))+d)if a else b

Try it online!

This doesn’t use base conversion or character codes at all. It works on strings over any alphabet \$\mathcal A\$.

We define addition by concatenation \$a + b = ab\$ except when \$a\$ ends with the same character \$\mathtt x\$ that starts \$b\$, in which case we use

$$\underbrace{\mathtt{xx\cdots x}}_{\text{$i$ times}} + \underbrace{\mathtt{xx\cdots x}}_{\text{$j$ times}} = \underbrace{\mathtt{xx\cdots x}}_{\text{$i \oplus j$ times}},$$

where \$\oplus\$ is bitwise XOR, perhaps repeatedly if \$i = j\$. For example,

$$\mathtt{uuzzzzzyxx} + \mathtt{xxyzzzv} = \mathtt{uuzzzzzzv},$$

because \$2 \oplus 2 = 0\$, \$1 \oplus 1 = 0\$, and \$5 \oplus 3 = 6\$. The identity is the empty string, and the inverse of a string is its reversal.

This describes the free product of \$|\mathcal A|\$ copies of the group \$(\mathbb N, \oplus)\$.

Answer 3

Jelly, 8 bytes

‘ḅ⁹^/ḃ⁹’

This uses a bijective mapping φ from byte arrays to the non-negative integers, XORs the result of applying φ to two input strings, then applies φ^-1 to the result.

The empty array is the neutral element and every byte arrays is its own inverse.

Try it online!

How it works

‘ḅ⁹^/ḃ⁹’  Main link. Argument: [A, B] (pair of byte arrays)

‘         Increment all integers in A and B.
 ḅ⁹       Convert from base 256 to integer.
   ^/     XOR the resulting integers.
     ḃ⁹   Convert from integer to bijective base 256.
       ’  Subtract 1.

Answer 4

Python 2, 114 bytes

lambda a,b:s(d(a)^d(b))
d=lambda s:s and d(s[1:])*256+ord(s[0])+1or 0
s=lambda d:d and chr(~-d%256)+s(~-d/256)or''

Try it online! Works by XORing the strings interpreted as little-endian bijective base 256.

Answer 5

Python 2, 197 bytes

def n(s):
 n=s and ord(s[0])+1 or 0
 for c in s[1:]:n=n*256+ord(c)
 return(-1)**n*n/2
def f(l,r,s=""):
 i=n(l)+n(r)
 i=abs(i*2+(i<=0))
 while i>257:s=chr(i%256)+s;i/=256
 return["",chr(i-1)+s][i>0]

Try it online!

Turns the string into a number (reducing by charcode), negates if odd, then halves. Not as golfy as the other one, but faster :P

Answer 6

JavaScript (Node.js), 119 bytes

a=>b=>q(p(a)^p(b));p=x=>Buffer(x,h=0).map(c=>h=h*256-~c)|h;q=(n,i=0)=>n<2**i?i?q(n>>8,i-8)+Buffer([n]):'':q(n-2**i,i+8)

Try it online!

xor of id of string