Python 3 , 177 170 163 130 byte
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
Cobalah online!
-14 byte berkat notjagan
-33 bytes berkat Leaky Nun (dan beralih endianness)
Saya tidak punya bisnis mencoba golf apa pun di Python, tapi saya tidak ingin menggunakan Lua karena metode ini membutuhkan bilangan bulat yang tepat untuk bekerja pada sengatan panjang yang wajar. (Catatan: algoritme ini masih Sangat Lambat saat memperbesar panjang string.) Ini sebagian besar hanya untuk memberikan jawaban;)
Setiap string terbalik sendiri, dan string kosong adalah identitas. Ini hanya menjalankan xor di bawah penataan sederhana antara string dan integer non-negatif. s
adalah fungsi pembantu yang menghitung bijection (satu arah saja), dan d
merupakan kebalikannya.
Versi tidak lambat (148 byte, milik 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
Cobalah online!
Saya akan membajak ini untuk teori kelompok utama juga.
Setiap terbalik tepat adalah suatu terbalik kiri: 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
Ini juga berarti bahwa a adalah kebalikan dari inv (a) .
Identitas kanan apa pun adalah identitas kiri: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a
Identitas itu unik, mengingat identitas lain f : e = e + f = f
Jika a + x = a maka x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e
Inversi unik, jika a + x = e maka: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )
Mengikuti bukti harus membuatnya cukup mudah untuk membangun contoh tandingan untuk solusi yang diusulkan yang tidak memenuhi proposisi ini.
Berikut adalah algoritma yang lebih alami yang saya terapkan (tetapi tidak golf) di Lua . Mungkin itu akan memberi seseorang ide.
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
Idenya pada dasarnya adalah untuk memisahkan string berdasarkan kekuatan dua komponen panjangnya, dan kemudian memperlakukannya sebagai bidang dengan komponen yang hilang mewakili nol, dan setiap komponen yang tidak hilang mewakili angka dari 1 hingga 256 ^ n, jadi 256 ^ n + 1 nilai total. Kemudian representasi ini dapat ditambahkan modul-256 modul-bijaksana 256 ^ n + 1.
Catatan: Implementasi Lua ini akan memiliki masalah luapan numerik untuk string dengan ukuran lebih besar dari 7. Tetapi rangkaian string dengan panjang 7 atau kurang ditutup di bawah penambahan ini.
Cobalah online!
Jelly , 8 byte
Ini menggunakan pemetaan bijektif φ dari array byte ke integer non-negatif, XOR hasil menerapkan φ ke dua string input, kemudian menerapkan φ -1 pada hasilnya.
Array kosong adalah elemen netral dan setiap array byte adalah kebalikannya sendiri.
Cobalah online!
Bagaimana itu bekerja
sumber
ḅ⁹
juga dari bijective base 256 ke integer? Apa yangA+A
memberi?chr(-1)
?[65] + [65]
akan menghasilkan[]
.Python 2 , 114 byte
Cobalah online! Bekerja dengan XORing string yang ditafsirkan sebagai little-endian bijective base 256.
sumber
d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256
menghemat tiga byte;s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256)
hemat satu lagi.Python 2 , 197 byte
Cobalah online!
Mengubah string menjadi angka (dikurangi dengan charcode), meniadakan jika aneh, lalu membagi dua. Bukan golf seperti yang lain, tetapi lebih cepat: P
sumber
n
bukan injeksi, yang menyebabkan masalah. Misalkann("\x00\x00")==n("\xff")
ini gagal:print(f("\x00\x00","") == "\x00\x00")
1 or
=>1or