De nombreuses langues permettent d'ajouter des chaînes avec +. Cependant, c'est vraiment une concaténation, un véritable ajout suivrait les axiomes de groupe:

• Il est fermé (l'ajout de deux chaînes est toujours une chaîne)

• Il est associatif ( (a + b) + c = a + (b + c) )

• Il y a une identité ( ∃e: a + e = a )

• Chaque élément a un inverse ( ∀a: ∃b: a + b = e )

^{(la concaténation viole l'axiome du 4ème groupe)}

Donc, ma tâche est d'implémenter une véritable addition de chaîne, c'est-à-dire une fonction qui prend deux séquences d'octets représentant des chaînes et en retourne une troisième de sorte que votre fonction satisfasse tous les axiomes de groupe sur les séquences d'octets.

Il doit fonctionner sur toutes les séquences d'octets représentant des chaînes, y compris celles avec des octets nuls.

Il s'agit de code-golf donc les réponses seront notées en octets avec moins d'octets étant meilleurs.

Python 3 , 177 170 163 130 130 octets

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

Essayez-le en ligne!

-14 octets grâce à notjagan

-33 octets grâce à Leaky Nun (et endianness commuté)

Je n'ai rien à faire d'essayer de jouer au golf en Python, mais je ne voulais pas utiliser Lua car cette méthode a besoin de grands entiers exacts pour fonctionner sur des piqûres de longueur raisonnable. (Remarque: l'algorithme est toujours très lent lors de l'augmentation de la longueur de la chaîne.) C'est principalement juste pour fournir une réponse;)

Chaque chaîne est auto-inverse et la chaîne vide est l'identité. Cela effectue simplement xor sous une simple bijection entre des chaînes et des entiers non négatifs. sest une fonction d'aide qui calcule la bijection (unidirectionnelle uniquement) et dest l'inverse.

Version non lente (148 octets, gracieuseté de 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

Essayez-le en ligne!

Je vais également détourner cela pour une introduction à la théorie des groupes.

Tout inverse droit est un inverse gauche: 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

Cela signifie également que a est l'inverse de inv (a) .

Toute identité de droite est une identité de gauche: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a

L'identité est unique, étant donné une autre identité f : e = e + f = f

Si a + x = a alors x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e

Les inverses sont uniques, si a + x = e alors: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )

Suivre les preuves devrait permettre de construire assez facilement des contre-exemples pour les solutions proposées qui ne satisfont pas ces propositions.

Voici un algorithme plus naturel que j'ai implémenté (mais que je n'ai pas joué au golf) à Lua . Peut-être que cela donnera une idée à quelqu'un.

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

L'idée est essentiellement de diviser la chaîne en fonction de la puissance de deux composants de sa longueur, puis de les traiter comme des champs avec un composant manquant représentant zéro, et chaque composant non manquant représentant des nombres compris entre 1 et 256 ^ n, donc 256 ^ n + 1 valeurs au total. Ensuite, ces représentations peuvent être ajoutées par module modulo 256 ^ n + 1.

Remarque: Cette implémentation Lua aura des problèmes de débordement numérique pour les chaînes de tailles supérieures à 7. Mais l'ensemble de chaînes de longueur 7 ou moins est fermé sous cet ajout.

Essayez-le en ligne!

Gelée , 8 octets

‘ḅ⁹^/ḃ⁹’

Celui-ci utilise un mappage bijectif φ des tableaux d'octets aux entiers non négatifs, XOR le résultat de l'application de φ à deux chaînes d'entrée, puis applique φ ^-1 au résultat.

Le tableau vide est l'élément neutre et chaque tableau d'octets est son propre inverse.

Essayez-le en ligne!

Comment ça marche

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

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

Essayez-le en ligne! Fonctionne en XOR les chaînes interprétées comme base bijective little-endian 256.

Python 2 , 197 octets

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]

Essayez-le en ligne!

Transforme la chaîne en un nombre (en réduisant par charcode), annule s'il est impair, puis divise par deux. Pas aussi golfique que l'autre, mais plus rapide: P