Terapkan penambahan string yang benar

29

Banyak bahasa memungkinkan string untuk "ditambahkan" dengan +. Namun ini benar-benar rangkaian, tambahan yang benar akan mengikuti aksioma grup:

  • Ditutup (penambahan dua string selalu berupa string)

  • Ini asosiatif ( (a + b) + c = a + (b + c) )

  • Ada identitas ( ∃e: a + e = a )

  • Setiap elemen memiliki kebalikan ( ∀a: ∃b: a + b = e )

(Rangkaian melanggar aksioma kelompok ke-4)

Jadi tugas saya kepada Anda adalah untuk menerapkan penambahan string yang benar, yaitu fungsi yang mengambil dua urutan byte yang mewakili string dan mengembalikan sepertiga sehingga fungsi Anda memenuhi semua aksioma grup pada urutan byte.

Ini harus bekerja pada semua urutan byte yang mewakili string termasuk yang dengan byte nol.

Ini adalah sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte lebih baik.

Wisaya Gandum
sumber

Jawaban:

5

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. sadalah fungsi pembantu yang menghitung bijection (satu arah saja), dan dmerupakan 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!

tehtmi
sumber
Fakta menyenangkan: Karena setiap elemen adalah kebalikannya sendiri, grup ini juga abelian.
Wheat Wizard
4

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

‘ḅ⁹^/ḃ⁹’  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.
Dennis
sumber
Saya bertanya-tanya esolang mana yang memiliki builtin basis konversi bijective ...
Neil
Bukankah itu seharusnya basis 257?
Titus
@Titus Tidak, angka-angka dari basis bijective 256 berkisar dari 1 hingga 256 (inklusif).
Dennis
Begitu ḅ⁹juga dari bijective base 256 ke integer? Apa yang A+Amemberi? chr(-1)?
Titus
@Titus Proses konversi basis ke bilangan bulat identik untuk basis bijektif dan "normal". [65] + [65]akan menghasilkan [].
Dennis
3

Python 2 , 114 byte

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

Cobalah online! Bekerja dengan XORing string yang ditafsirkan sebagai little-endian bijective base 256.

Neil
sumber
d=lambda s:s>''and-~ord(s[0])+d(s[1:])*256menghemat tiga byte; s=lambda d:d*'?'and chr(~-d%256)+s(~-d/256)hemat satu lagi.
Lynn
@ Lynn Apakah yang kedua akan bekerja untuk d besar?
Neil
Bagaimana cara kerjanya jika senarnya tidak sama panjang?
Wheat Wizard
@WheatWizard Panjang string tidak relevan. Ada pemetaan bijective dari set string ke set integer. Nilai integer kemudian XOR, dan pemetaan dibalik.
Neil
@Neil Ok terima kasih saya mengerti sekarang.
Wheat Wizard
1

Python 2 , 197 byte

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]

Cobalah online!

Mengubah string menjadi angka (dikurangi dengan charcode), meniadakan jika aneh, lalu membagi dua. Bukan golf seperti yang lain, tetapi lebih cepat: P

Khusus ASCII
sumber
193 bytes
officialaimm
1
nbukan injeksi, yang menyebabkan masalah. Misalkan n("\x00\x00")==n("\xff")ini gagal:print(f("\x00\x00","") == "\x00\x00")
tehtmi
: | oh tidak, itu akan sangat mahal untuk memperbaikinya
ASCII
1 or=>1or
Zacharý