Python 3 , 177 170 163 130 bajtów
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
Wypróbuj online!
-14 bajtów dzięki notjagan
-33 bajtów dzięki Dziurawej Zakonnicy (i zmienionej endianowości)
Nie mam biznesu próbującego grać w golfa w Pythonie, ale nie chciałem używać Lua, ponieważ ta metoda wymaga dużych dokładnych liczb całkowitych do pracy na żądaniach o rozsądnej długości. (Uwaga: algorytm nadal jest naprawdę powolny podczas zwiększania długości łańcucha). Ma to głównie na celu udzielenie odpowiedzi;)
Każdy ciąg jest odwrotny do siebie, a pusty ciąg jest tożsamością. To po prostu wykonuje xor pod prostym biject między ciągami znaków i nieujemnymi liczbami całkowitymi. s
jest funkcją pomocniczą, która oblicza bijection (tylko w jedną stronę) i d
jest odwrotna.
Wersja bez spowolnienia (148 bajtów, dzięki uprzejmości 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
Wypróbuj online!
Mam zamiar przejąć to również dla primera teorii grup.
Każde prawo odwrotna jest lewej odwrotność 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
Oznacza to również, że a jest odwrotnością inv (a) .
Każda prawa tożsamość jest lewą tożsamością: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a
Tożsamość jest unikalna, biorąc pod uwagę inną tożsamość f : e = e + f = f
Jeśli a + x = a, to x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e
Odwrotności są unikalne, jeśli a + x = e, to: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )
Postępowanie zgodnie z dowodami powinno dość łatwo skonstruować kontrprzykłady dla proponowanych rozwiązań, które nie spełniają tych propozycji.
Oto bardziej naturalny algorytm, który zaimplementowałem (ale nie grałem w golfa) w Lua . Może da to komuś pomysł.
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
Chodzi przede wszystkim o podzielenie łańcucha w oparciu o potęgę dwóch składników jego długości, a następnie potraktowanie ich jako pól z brakującym składnikiem reprezentującym zero, a każdy brakujący składnik reprezentuje liczby od 1 do 256 ^ n, więc łącznie 256 ^ n + 1 wartości. Następnie te reprezentacje można dodać modułowo modulo 256 ^ n + 1.
Uwaga: Ta implementacja Lua będzie miała problemy z przepełnieniem numerycznym dla ciągów o rozmiarach większych niż 7. Ale zestaw ciągów o długości 7 lub mniejszej jest zamknięty w ramach tego dodatku.
Wypróbuj online!
Galaretki , 8 bajtów
Wykorzystuje to bijective mapowanie φ z tablic bajtów na nieujemne liczby całkowite, XOR wynik zastosowania φ do dwóch łańcuchów wejściowych, a następnie stosuje φ -1 do wyniku.
Pusta tablica jest elementem neutralnym, a każda tablica bajtów jest własną odwrotnością.
Wypróbuj online!
Jak to działa
źródło
ḅ⁹
od bijective base 256 do integer? CoA+A
daje?chr(-1)
?[65] + [65]
ustąpi[]
.Python 2 , 114 bajtów
Wypróbuj online! Działa poprzez XORing ciągów interpretowanych jako bijective base 256-endian.
źródło
d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256
oszczędza trzy bajty;s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256)
oszczędza jeszcze jeden.Python 2 , 197 bajtów
Wypróbuj online!
Zamienia ciąg na liczbę (redukowaną przez kod znaków), neguje, jeśli jest nieparzysty, a następnie zmniejsza o połowę. Nie tak golfowy jak drugi, ale szybszy: P
źródło
n
nie jest iniekcyjny, co powoduje problemy. Np.n("\x00\x00")==n("\xff")
Tak się nie powiedzie:print(f("\x00\x00","") == "\x00\x00")
1 or
=>1or