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
Pruébalo en línea!
-14 bytes gracias a notjagan
-33 bytes gracias a Leaky Nun (y endianness conmutada)
No tengo nada que tratar de jugar golf en Python, pero no quería usar Lua ya que este método necesita enteros grandes y exactos para trabajar en picaduras de longitud razonable. (Nota: el algoritmo sigue siendo realmente lento cuando aumenta la longitud de la cadena). Esto es principalmente para proporcionar una respuesta;)
Cada cadena es autoinversa, y la cadena vacía es la identidad. Esto simplemente realiza xor bajo una biyección simple entre cadenas y enteros no negativos. s
es una función auxiliar que calcula la biyección (solo en un sentido) y d
es la inversa.
Versión no lenta (148 bytes, cortesía 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
Pruébalo en línea!
Voy a secuestrar esto para una cartilla de teoría de grupo también.
Cualquier inverso a la derecha es un inverso a la izquierda: 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
Esto también significa que a es un inverso de inv (a) .
Cualquier identidad correcta es una identidad izquierda: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a
La identidad es única, dada otra identidad f : e = e + f = f
Si a + x = a, entonces x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e
Las inversiones son únicas, si a + x = e entonces: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )
Seguir las pruebas debería facilitar bastante la construcción de contraejemplos para las soluciones propuestas que no satisfacen estas proposiciones.
Aquí hay un algoritmo más natural que implementé (pero no jugué al golf) en Lua . Tal vez le dará una idea a alguien.
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
La idea es básicamente dividir la cadena en función de la potencia de dos componentes de su longitud, y luego tratarlos como campos con un componente faltante que representa cero, y cada componente no faltante representa números desde 1 hasta 256 ^ n, entonces 256 ^ n + 1 valores totales. Luego, estas representaciones se pueden agregar en el módulo de componentes 256 ^ n + 1.
Nota: Esta implementación de Lua tendrá problemas de desbordamiento numérico para cadenas de tamaños mayores que 7. Pero el conjunto de cadenas de longitud 7 o menos se cierra con esta adición.
Pruébalo en línea!
Jalea , 8 bytes
Esto utiliza un mapeo biyectivo φ de conjuntos de bytes a enteros no negativos, XOR el resultado de aplicar φ a dos cadenas de entrada, luego aplica φ -1 al resultado.
La matriz vacía es el elemento neutral y cada matriz de bytes es su propio inverso.
Pruébalo en línea!
Cómo funciona
fuente
ḅ⁹
es de la base biyectiva 256 a entero? ¿QuéA+A
da?chr(-1)
?[65] + [65]
cederá[]
.Python 2 , 114 bytes
Pruébalo en línea! Funciona mediante XORing las cadenas interpretadas como base biyectiva little-endian 256.
fuente
d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256
guarda tres bytes;s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256)
salva uno másPython 2 , 197 bytes
Pruébalo en línea!
Convierte la cadena en un número (reduciendo por charcode), niega si es impar, luego reduce a la mitad. No tan golfoso como el otro, pero más rápido: P
fuente
n
no es inyectiva, lo que causa problemas. Por ejemplo,n("\x00\x00")==n("\xff")
esto falla:print(f("\x00\x00","") == "\x00\x00")
1 or
=>1or