Python 3 , 177 170 163 130 байт
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
Попробуйте онлайн!
-14 байт благодаря нотаджану
-33 байта благодаря Leaky Nun (и переключаемому порядку байтов)
Я не имею никакого дела, пытаясь играть в гольф на Python, но я не хотел использовать Lua, так как этот метод требует больших точных целых чисел, чтобы работать с жалами разумной длины. (Примечание: алгоритм все еще очень медленный при увеличении длины строки.) Это в основном просто для предоставления ответа;)
Каждая строка является самообращенной, а пустая строка является идентификатором. Это просто выполняет xor при простой биекции между строками и неотрицательными целыми числами. s
является вспомогательной функцией, которая вычисляет биекцию (только в одну сторону) и d
является обратной.
Немедленная версия (148 байт, предоставлено 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
Попробуйте онлайн!
Я собираюсь угнать это и для учебника по теории групп.
Любое право обратного левая обратный: INV (а) + а = (INV (а) + а) + е = (INV (а) + а) + (INV (а) + INV (INV (а))) = inv (a) + (a + inv (a)) + inv (inv (a)) = (inv (a) + e) + inv (inv (a)) = inv (a) + inv (inv (a) ) = е
Это также означает, что a является инверсией inv (a) .
Любое правое тождество является левым тождеством: e + a = (a + inv (a)) + a = a + (inv (a) + a) = a
Идентичность уникальна, учитывая другую идентичность f : e = e + f = f
Если a + x = a, то x = e : x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + a = e
Инверсии уникальны, если a + x = e, то: x = e + x = (inv (a) + a) + x = inv (a) + (a + x) = inv (a) + e = inv (a )
Следование доказательствам должно облегчить построение контрпримеров для предложенных решений, которые не удовлетворяют этим предложениям.
Вот более естественный алгоритм, который я реализовал (но не играл в гольф) в Lua . Может быть, это даст кому-то идею.
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
Идея в основном состоит в том, чтобы разделить строку на основе степеней двух компонентов ее длины, а затем обработать их как поля с отсутствующим компонентом, представляющим ноль, и каждый не пропущенный компонент, представляющий числа от 1 до 256 ^ n, итого 256 ^ n + 1 значений. Затем эти представления могут быть добавлены компонентно по модулю 256 ^ n + 1.
Примечание. Эта реализация Lua будет иметь проблемы с переполнением чисел для строк размером более 7. Но набор строк длиной 7 или меньше закрыт при этом добавлении.
Попробуйте онлайн!
Желе , 8 байт
При этом используется биективное отображение φ из байтовых массивов в неотрицательные целые числа, XOR - результат применения φ к двум входным строкам, затем применяет φ -1 к результату.
Пустой массив является нейтральным элементом, и каждый байтовый массив имеет свой собственный обратный.
Попробуйте онлайн!
Как это работает
источник
ḅ⁹
от биективного основания 256 до целого числа? ЧтоA+A
дает?chr(-1)
?[65] + [65]
даст[]
.Python 2 , 114 байт
Попробуйте онлайн! Работы по XORing строк интерпретируются как байтовое основание с прямым порядком байтов 256.
источник
d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256
сохраняет три байта;s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256)
сохраняет еще один.Python 2 , 197 байт
Попробуйте онлайн!
Превращает строку в число (с уменьшением на код), отрицает, если нечетное, затем делится на два Не так как в гольфе, как другой, но быстрее: P
источник
n
не является инъективным, что вызывает проблемы. Например,n("\x00\x00")==n("\xff")
это не удается:print(f("\x00\x00","") == "\x00\x00")
1 or
=>1or