29
\$\begingroup\$

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 ( (a + b) + c = a + (b + c))

  • There is an identity (∃e : a + e = a)

  • Every element has an inverse (∀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.

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Fun fact: Because every element is its own inverse, this group is also abelian. \$\endgroup\$ – Sriotchilism O'Zaic Aug 26 '17 at 5:39
4
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Lynn Aug 14 '17 at 10:13
  • \$\begingroup\$ @Lynn Is that second one going to work for large d? \$\endgroup\$ – Neil Aug 14 '17 at 10:25
  • \$\begingroup\$ How does this work if the strings are not of the same length? \$\endgroup\$ – Sriotchilism O'Zaic Aug 26 '17 at 18:05
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Aug 26 '17 at 18:07
  • \$\begingroup\$ @Neil Ok thanks I see now. \$\endgroup\$ – Sriotchilism O'Zaic Aug 26 '17 at 18:09
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 193 bytes \$\endgroup\$ – officialaimm Aug 14 '17 at 4:24
  • 1
    \$\begingroup\$ n is not injective, which causes problems. E.g. n("\x00\x00")==n("\xff") so this fails: print(f("\x00\x00","") == "\x00\x00") \$\endgroup\$ – tehtmi Aug 14 '17 at 4:41
  • \$\begingroup\$ :| oh no that's going to be so costly to fix \$\endgroup\$ – ASCII-only Aug 14 '17 at 6:16
  • \$\begingroup\$ 1 or => 1or \$\endgroup\$ – Zacharý Aug 20 '17 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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