Logika ternary yang seimbang

11

Logika ternary yang seimbang

Terner biasanya nama lain untuk basis 3, yang mengatakan, setiap digit adalah 0, 1atau 2, dan setiap tempat bernilai 3 kali lebih banyak sebagai tempat berikutnya.

Terner seimbang adalah modifikasi terner yang menggunakan digit -1, 0dan 1. Ini memiliki keuntungan karena tidak memerlukan tanda. Setiap tempat masih bernilai 3 kali lipat dari tempat berikutnya. Oleh karena itu beberapa bilangan bulat positif pertama adalah [1], [1, -1], [1, 0], [1, 1], [1, -1, -1]sementara beberapa bilangan bulat negatif pertama yang [-1], [-1, 1], [-1, 0], [-1, -1], [-1, 1, 1].

Anda memiliki tiga input x, y, z. zadalah baik -1, 0atau 1, sementara xdan ydapat dari -3812798742493ke 3812798742493inklusif.

Langkah pertama adalah mengubah xdan ydari desimal ke terner seimbang. Ini akan memberi Anda 27 trit (digit TeRnary). Anda kemudian harus menggabungkan trit dari xdan yberpasangan menggunakan operasi ternary dan kemudian mengubah hasilnya kembali ke desimal.

Anda dapat memilih nilai zpeta mana dari masing-masing dari tiga operasi ternary ini:

  • A: Diberi dua trit, jika salah satu adalah nol, maka hasilnya adalah nol, jika tidak hasilnya adalah -1 jika mereka berbeda atau 1 jika mereka sama.
  • B: Diberi dua trit, jika salah satu adalah nol, maka hasilnya adalah trit yang lain, jika tidak hasilnya adalah nol jika mereka berbeda atau negasi jika mereka sama.
  • C: Diberikan dua trit, hasilnya adalah nol jika mereka berbeda atau nilainya jika mereka sama.

Contoh. Misalkan xada 29dan yada 15. Dalam terner yang seimbang, ini menjadi [1, 0, 1, -1]dan [1, -1, -1, 0]. (23 zero trit yang tersisa dihilangkan karena singkatnya.) Setelah masing-masing operasi, mereka menjadi A: [1, 0, -1, 0], B: [-1, -1, 0, -1], C: [1, 0, 0, 0]. Dikonversi kembali ke desimal hasilnya 24, -37dan 27masing - masing. Coba implementasi referensi berikut untuk lebih banyak contoh:

Implementasi referensi mengikuti langkah-langkah yang diberikan di atas tetapi Anda tentu saja bebas menggunakan algoritma apa pun yang menghasilkan hasil yang sama.

Ini adalah , jadi program atau fungsi terpendek yang tidak melanggar celah standar akan menang!

Neil
sumber
2
Jika format asli untuk angka adalah terner seimbang (bukan biner), apakah kami diizinkan untuk mengambilnya dengan cara biasa (yang tidak menghasilkan konversi ke terner seimbang)?
wizzwizz4
2
terkait
Giuseppe
1
apakah zharus salah satu -1,0,1atau dapatkah kita memilih tiga nilai yang konsisten dan berbeda? Saya telah memilih 1,2,3jawaban saya, dan ada beberapa kebingungan tentang itu.
Giuseppe
2
@ Giuseppe Maaf, hanya digit ternary seimbang yang diizinkan.
Neil
2
Saya membaca sesuatu yang melanggar ... Terlalu banyak kata dan tidak ada rumus
RosLuP

Jawaban:

2

Bersih , 231 ... 162 byte

import StdEnv
$n=tl(foldr(\p[t:s]#d=sign(2*t/3^p)
=[t-d*3^p,d:s])[n][0..26])
@x y z=sum[3^p*[(a+b)/2,[1,-1,0,1,-1]!!(a+b+2),a*b]!!(z+1)\\a<- $x&b<- $y&p<-[0..26]]

Menentukan fungsi @, mengambil tiga Intdan memberi Int.
Operator memetakan sebagai 1 -> A, 0 -> B, -1 -> C.

Cobalah online!

Fungsi ini $melipat lambda di atas tempat digit [0..26], menjadi daftar digit ternary. Ia menggunakan kepala dari daftar yang dihasilkannya untuk menjaga perbedaan total saat ini dari angka yang diperlukan (itulah sebabnya ia dibuntuti sebelum kembali), dan sign(2*t/3^p)untuk menentukan digit saat ini untuk menghasilkan. Trik tanda setara dengan if(abs(2*t)<3^p)0(sign t).

Suram
sumber
Saya tidak tahu Clean, tapi saya tertarik pada bagaimana Anda telah dikonversi ke terner seimbang, dengan $n(saya pikir). Bisakah Anda menambahkan penjelasan untuk itu?
Giuseppe
@ Giuseppe Tentu saja, saya akan menambahkan penjelasan hari ini ketika saya punya waktu.
Surous
@ Giuseppe apakah itu menjawab pertanyaan Anda?
Surous
Iya! Itu masuk akal. Cukup pintar!
Giuseppe
1

Jelly , 39 byte

×=
×
+ị1,-,0
A-r1¤ṗœs2ṚẎị@ȯµ€Uz0ZU⁹ŀ/ḅ3

Sebuah program penuh mengambil dua argumen, [x,y]dan z
... mana zadalah {A:-1, B:0, C:1}
yang mencetak hasilnya

Cobalah online! Catatan: metode golf membuatnya lambat - versi yang diubah ini lebih cepat (log dengan 3, ceil, dan kenaikan sebelum setiap produk Cartesian)

Bagaimana?

×=       - Link  1 (1), B: list of trits L, list of trits R
×        - L multiplied by... (vectorises):
 =       -   L equal R? (vectorises)

×        - Link -1 (2), A: list of trits L, list of trits R
×        - L multiplied by R (vectorises)

+ị1,-,0  - Link  0 (3), C: list of trits L, list of trits R
+        - L plus R (vectorises)
  1,-,0  - list of integers = [1,-1,0]
 ị       - index into (vectorises) - 1-based & modular, so index -2 is equivalent to
         -                           index 1 which holds the value 1.

A-r1¤ṗœs2ṚẎị@ȯµ€Uz0ZU⁹ŀ/ḅ3 - Main link: list of integers [X,Y], integer Z
              µ€           - for each V in [X,Y]:
A                          -   absolute value = abs(V)
    ¤                      -   nilad followed by link(s) as a nilad:
 -                         -     literal minus one
   1                       -     literal one
  r                        -     inclusive range = [-1,0,1]
     ṗ                     -   Cartesian power, e.g. if abs(V)=3: [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
                           -                   (corresponding to: [-13       ,-12      ,-11      ,-10      ,-9      ,-8      ,-7       ,-6      ,-5      ,-4       ,-3      ,-2      ,-1      ,0      ,1      ,2       ,3      ,4      ,5        ,6       ,7       ,8       ,9      ,10      ,11     ,12     ,13     ] )
        2                  -   literal two
      œs                   -   split into equal chunks           [[[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]],[[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]]
         Ṛ                 -   reverse                           [[[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]],[[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]]]
          Ẏ                -   tighten                            [[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1],[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]]
                           -                   (corresponding to: [1      ,2       ,3      ,4      ,5        ,6       ,7       ,8       ,9      ,10     ,11      ,12     ,13     ,-13       ,-12      ,-11      ,-10      ,-9      ,-8      ,-7       ,-6      ,-5      ,-4       ,-3      ,-2      ,-1      ,0      ] )
           ị@              -   get item at index V (1-based & modular)
             ȯ             -   logical OR with V (just handle V=0 which has an empty list)
                U          - upend (big-endian -> little-endian for each)
                  0        - literal zero           }
                 z         - transpose with filler  } - pad with MSB zeros
                   Z       - transpose              }
                    U      - upend (little-endian -> big-endian for each)
                       /   - reduce with:
                      ŀ    -   link number: (as a dyad)
                     ⁹     -     chain's right argument, Z
                         3 - literal three
                        ḅ  - convert from base
Jonathan Allan
sumber
Saya tidak bisa seumur hidup saya membaca bahasa golf, jadi ketika Anda mengatakan 'lambat', seberapa buruk kompleksitas waktu?
Οurous
Untuk mendapatkan terner seimbang N, ia membuat daftar semua (3 ^ n) panjang abs (N) daftar trit (0, -1, dan 1). Jadi O (3 ^ maks (abs (X), abs (Y)))
Jonathan Allan
Terima kasih, dan untuk penjelasannya saya melihat Anda menambahkan juga!
Kamis
1
Juga menambahkan versi yang lebih cepat menggunakan metode yang sama :)
Jonathan Allan
1

R , 190 172 151 byte

function(a,b,z){M=t(t(expand.grid(rep(list(-1:1),27))))
P=3^(26:0)
x=M[M%*%P==a,]
y=M[M%*%P==b,]
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%P}

Cobalah online!

Hitung semua kombinasi trit dan pilih yang benar. Ini benar-benar akan menimbulkan kesalahan memori 27, karena 3^27jumlahnya agak besar, tetapi secara teori akan berhasil. TIO link hanya memiliki 11dukungan bilangan trit; Saya tidak yakin pada titik berapa kali kesalahan memori habis, dan saya tidak ingin Dennis marah kepada saya karena menyalahgunakan TIO!

jawaban lama, 170 byte

Yang ini harus bekerja untuk semua input, walaupun dengan hanya integer 32-bit, ada kemungkinan ketidaktepatan karena R akan secara otomatis mengubahnya double.

function(a,b,z){x=y={}
for(i in 0:26){x=c((D=c(0,1,-1))[a%%3+1],x)
y=c(D[b%%3+1],y)
a=(a+1)%/%3
b=(b+1)%/%3}
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%3^(26:0)}

Cobalah online!

Dibutuhkan -1untuk A, 0untuk B, dan 1untuk C.

Port pendekatan dalam jawaban ini untuk mengkonversi ke terner seimbang, meskipun karena kami dijamin tidak memiliki lebih dari 27 trit seimbang, itu dioptimalkan untuk itu.

R , 160 byte

function(a,b,z){s=sample
x=y=rep(0,27)
P=3^(26:0)
while(x%*%P!=a&y%*%P!=b){x=s(-1:1,27,T)
y=s(-1:1,27,T)}
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%P}

Cobalah online!

Versi ini akan berakhir sangat lambat. Bogosort dari konversi basis, fungsi ini secara acak mengambil trit sampai entah bagaimana secara ajaib ( 3^-54kemungkinan itu terjadi) menemukan trit yang tepat untuk adan b, dan kemudian melakukan operasi yang diperlukan. Ini pada dasarnya tidak akan pernah selesai.

Giuseppe
sumber
Saya pikir zdibatasi untuk {-1, 0, 1}.
Erik the Outgolfer
@EriktheOutgolfer Anda dapat memilih masing-masing nilai zpeta ke salah satu dari tiga operasi ternary ini: [...]
Dennis
@ Dennis zadalah salah satu -1,, 0atau1 , dan saya pikir itu adalah "nilai-nilai z" yang dimaksud.
Erik the Outgolfer
Ini perbedaan dua-byte, menggantikan switch(z,...)dengan switch(z+2,...)sehingga akan menjadi perubahan sepele terlepas.
Giuseppe
0

Jelly , 47 byte

×=
×
N0⁼?ȯȧ?"
ḃ3%3’
0Çḅ3$$⁼¥1#ḢÇṚµ€z0Z⁹+2¤ŀ/Ṛḅ3

Cobalah online!

Program lengkap.

-1= C, 0= A, 1=B

Argumen 1: [x, y]
Argumen 3:z

Erik the Outgolfer
sumber
Saya tidak berpikir mengambil xdan ydalam terner seimbang diperbolehkan: "x dan y dapat dari -3812798742493 menjadi 3812798742493 inklusif. Langkah pertama adalah mengubah x dan y dari terner desimal ke seimbang."
Jonathan Allan
@JonathanAllan klarifikasi komentar
Erik the Outgolfer
... tetapi format asli untuk angka tidak seimbang terner di Jelly.
Jonathan Allan
@ Jonathan Allan Oh, sepertinya saya salah paham ....
Erik the Outgolfer
@Jonathan Allan eugh ... diperbaiki
Erik the Outgolfer