In vielen Sprachen können Zeichenfolgen mit "hinzugefügt" werden +. Dies ist jedoch eine echte Verkettung. Eine echte Addition würde den Gruppenaxiomen folgen:

• Es ist geschlossen (das Hinzufügen von zwei beliebigen Zeichenfolgen ist immer eine Zeichenfolge)

• Es ist assoziativ ( (a + b) + c = a + (b + c) )

• Es gibt eine Identität ( ∃e: a + e = a )

• Jedes Element hat eine Inverse ( ∀a: ∃b: a + b = e )

^{(Verkettung verstößt gegen das 4. Gruppenaxiom)}

Meine Aufgabe für Sie ist es also, eine echte Zeichenfolgenaddition zu implementieren, dh eine Funktion, die zwei Folgen von Bytes für Zeichenfolgen verwendet und eine dritte zurückgibt, sodass Ihre Funktion alle Gruppenaxiome für Folgen von Bytes erfüllt.

Es muss für alle Folgen von Bytes funktionieren, die Zeichenfolgen darstellen, einschließlich solcher mit Null-Bytes.

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

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

Probieren Sie es online!

-14 bytes dank notjagan

-33 Bytes dank Leaky Nun (und Endianness Switch)

Ich habe kein Problem damit, in Python Golf zu spielen, aber ich wollte Lua nicht verwenden, da diese Methode große exakte Ganzzahlen benötigt, um an Stichen mit angemessener Länge zu arbeiten. (Hinweis: Der Algorithmus ist beim Erhöhen der String-Länge immer noch sehr langsam.) Dies dient meist nur zur Beantwortung;)

Jede Zeichenfolge ist selbstinvers und die leere Zeichenfolge ist die Identität. Dies führt einfach xor unter einer einfachen Verknüpfung zwischen Zeichenfolgen und nicht negativen Ganzzahlen aus. sist eine Hilfsfunktion, die die Bijektion berechnet (nur in eine Richtung) und dumgekehrt ist.

Nicht langsame Version (148 Bytes, mit freundlicher Genehmigung von 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

Probieren Sie es online!

Ich werde dies auch für eine Gruppentheorie-Einführung hijacken.

Jede rechte Inverse ist eine linke 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

Dies bedeutet auch, dass a eine Inverse von inv (a) ist .

Jede rechte Identität ist eine linke Identität: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a

Die Identität ist eindeutig, wenn andere Identität f gegeben ist : e = e + f = f

Wenn a + x = a, dann ist x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e

Inverse sind eindeutig, wenn a + x = e, dann: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )

Das Befolgen der Beweise sollte es ziemlich einfach machen, Gegenbeispiele für vorgeschlagene Lösungen zu konstruieren, die diese Aussagen nicht erfüllen.

Hier ist ein natürlicherer Algorithmus, den ich in Lua implementiert habe (aber nicht golfen habe) . Vielleicht gibt es jemand eine Idee.

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

Grundsätzlich besteht die Idee darin, die Zeichenfolge auf der Grundlage der Zweierpotenzkomponenten ihrer Länge zu teilen und diese dann als Felder zu behandeln, wobei eine fehlende Komponente Null darstellt und jede nicht fehlende Komponente Zahlen von 1 bis 256 ^ n darstellt. also 256 ^ n + 1 Werte insgesamt. Dann können diese Darstellungen komponentenweise modulo 256 ^ n + 1 hinzugefügt werden.

Hinweis: Diese Lua-Implementierung weist numerische Überlaufprobleme für Zeichenfolgen mit einer Größe von mehr als 7 auf. Der Satz von Zeichenfolgen mit einer Länge von 7 oder weniger wird jedoch unter diesem Zusatz geschlossen.

Probieren Sie es online!

Gelee , 8 Bytes

‘ḅ⁹^/ḃ⁹’

Dies verwendet eine bijektive Abbildung φ von Bytearrays auf die nicht-negativen ganzen Zahlen, XORs das Ergebnis der Anwendung von φ auf zwei Eingabezeichenfolgen, und wendet dann φ- ¹ auf das Ergebnis an.

Das leere Array ist das neutrale Element und jedes Byte-Array ist seine eigene Inverse.

Probieren Sie es online!

Wie es funktioniert

‘ḅ⁹^/ḃ⁹’  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.

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''

Probieren Sie es online! Arbeitet durch XOR-Verknüpfung der als Little-Endian-Bijektivbasis 256 interpretierten Zeichenfolgen.

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]

Probieren Sie es online!

Wandelt die Zeichenfolge in eine Zahl um (durch Zeichencode verkleinert), negiert, wenn ungerade, dann halbiert. Nicht so golfig wie der andere, aber schneller: P