# Implement true string addition

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 so answers will be scored in bytes with less bytes being better.

# Python 3, 177170163 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!

• Fun fact: Because every element is its own inverse, this group is also abelian. Aug 26, 2017 at 5:39

# 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.

• I was wondering which esolangs had bijective base conversion builtins...
– Neil
Aug 15, 2017 at 9:16
• Shouldn´t that be base 257? Aug 27, 2017 at 17:12
• @Titus No, the digits of bijective base 256 range from 1 to 256 (inclusive). Aug 27, 2017 at 17:19
• So ḅ⁹ is from bijective base 256 to integer? What does A+A give? chr(-1)? Aug 27, 2017 at 17:23
• @Titus The base-to-integer conversion process is identical for bijective and "normal" bases. [65] + [65] will yield []. Aug 27, 2017 at 22:35

# 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)\$$.

# 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.

• d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256 saves three bytes; s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256) saves one more.
– Lynn
Aug 14, 2017 at 10:13
• @Lynn Is that second one going to work for large d?
– Neil
Aug 14, 2017 at 10:25
• How does this work if the strings are not of the same length? Aug 26, 2017 at 18:05
• @WheatWizard The length of the strings is irrelevant. There's a bijective mapping from the set of strings to the set of integers. The integer values are then XORed, and the mapping reversed.
– Neil
Aug 26, 2017 at 18:07
• @Neil Ok thanks I see now. Aug 26, 2017 at 18:09

# 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

• 193 bytes Aug 14, 2017 at 4:24
• n is not injective, which causes problems. E.g. n("\x00\x00")==n("\xff") so this fails: print(f("\x00\x00","") == "\x00\x00") Aug 14, 2017 at 4:41
• :| oh no that's going to be so costly to fix Aug 14, 2017 at 6:16
• 1 or => 1or Aug 20, 2017 at 16:41

# 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