Lógica ternaria equilibrada

11

Lógica ternaria equilibrada

Ternario es normalmente otro nombre para la base 3, es decir, cada dígito es 0, 1o 2, y cada lugar vale 3 veces más que el siguiente lugar.

El ternario equilibrado es una modificación del ternario que utiliza dígitos de -1, 0y 1. Esto tiene la ventaja de no necesitar una señal. Cada lugar todavía vale 3 veces más que el siguiente. Los primeros números enteros positivos son, por lo tanto [1], [1, -1], [1, 0], [1, 1], [1, -1, -1]mientras que los primeros son números enteros negativos [-1], [-1, 1], [-1, 0], [-1, -1], [-1, 1, 1].

Tienes tres entradas x, y, z. zes o bien -1, 0, o 1, mientras que xy ypuede ser desde -3812798742493a 3812798742493inclusive.

El primer paso es convertir xy yde decimal a ternario equilibrado. Esto debería darte 27 trits (dígitos digitales). Luego tiene que combinar los trits desde xy yen pares usando una operación ternaria y luego convertir el resultado a decimal.

Puede elegir qué valores de zmapear a una de estas tres operaciones ternarias cada uno:

  • A: Dado dos trits, si cualquiera es cero, entonces el resultado es cero; de lo contrario, el resultado es -1 si son diferentes o 1 si son iguales.
  • B: Dados dos trits, si uno es cero, entonces el resultado es el otro trit, de lo contrario el resultado es cero si son diferentes o la negación si son iguales.
  • C: Dados dos trits, el resultado es cero si son diferentes o su valor si son iguales.

Ejemplo. Supongamos que xes 29y yes 15. En ternario equilibrado, estos se convierten en [1, 0, 1, -1]y [1, -1, -1, 0]. (Los 23 trits cero restantes se han omitido por brevedad). Después de cada una de las operaciones respectivas se convierten en A: [1, 0, -1, 0], B: [-1, -1, 0, -1], C: [1, 0, 0, 0]. Convertidos a decimales los resultados son 24, -37y 27respectivamente. Pruebe la siguiente implementación de referencia para obtener más ejemplos:

La implementación de referencia sigue los pasos anteriores, pero, por supuesto, puede utilizar cualquier algoritmo que produzca los mismos resultados.

Este es el , por lo que gana el programa o la función más corta que no viole ninguna laguna estándar.

Neil
fuente
2
Si el formato nativo para los números es ternario balanceado (en oposición al binario), ¿se nos permite tomarlo como entrada de la manera habitual (lo que resulta en no conversión a ternario balanceado)?
wizzwizz4
2
relacionado
Giuseppe
1
¿ ztiene que ser uno de -1,0,1los tres valores consistentes o distintos? He seleccionado 1,2,3en mi respuesta, y hay algo de confusión al respecto.
Giuseppe
2
@Giuseppe Lo sentimos, solo se permiten dígitos ternarios balanceados.
Neil
2
Leí algo transversal ... Demasiadas palabras y sin fórmula
RosLuP

Respuestas:

2

Limpio , 231 ... 162 bytes

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

Define la función @, tomando tres Intsy dando un Int.
Los operadores mapean como 1 -> A, 0 -> B, -1 -> C.

Pruébalo en línea!

La función $pliega una lambda sobre los lugares de los dígitos [0..26], en una lista de dígitos ternarios. Utiliza el encabezado de la lista que produce para mantener una diferencia total actual del número requerido (por lo que se sigue antes de regresar), y sign(2*t/3^p)para determinar el dígito actual a ceder. El truco del signo es equivalente a if(abs(2*t)<3^p)0(sign t).

Οurous
fuente
No sé Clean, pero estoy intrigado por cómo te has convertido en ternario equilibrado, con $n(creo). ¿Podría agregar una explicación para eso?
Giuseppe
@Giuseppe Absolutamente, agregaré una explicación hoy cuando tenga tiempo.
Precioso
@Giuseppe, ¿eso responde a tu pregunta?
Οurous
¡Si! Eso tiene sentido. ¡Muy inteligente!
Giuseppe
1

Jalea , 39 bytes

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

Un programa completo que toma dos argumentos [x,y], y z
... ¿dónde zestá el {A:-1, B:0, C:1}
que imprime el resultado?

Pruébalo en línea! Nota: el método de golf lo hace lento: esta versión alterada es más rápida (registra 3, techos e incrementos antes de cada producto cartesiano)

¿Cómo?

×=       - 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
fuente
Por mi vida no puedo leer idiomas de golf, así que cuando dices 'lento', ¿qué tan mala es la complejidad del tiempo?
Precioso
Para obtener el ternario equilibrado de N, crea una lista de todas las listas de trits de longitud (3 ^ n) abs (N) de trits (0, -1 y 1). So O (3 ^ max (abs (X), abs (Y)))
Jonathan Allan
Gracias, y por la explicación, veo que también agregaste.
Οurous
1
También agregó una versión más rápida usando el mismo método :)
Jonathan Allan
1

R , 190 172 151 bytes

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}

Pruébalo en línea!

Calcula todas las combinaciones de trits y selecciona la correcta. Realmente arrojará un error de memoria 27, ya que 3^27es un número algo grande, pero en teoría funcionaría. El enlace TIO solo es 11compatible con trit integer; No estoy seguro de en qué momento se agota el tiempo o los errores de memoria primero, ¡y no quiero que Dennis se enoje conmigo por abusar de TIO!

respuesta anterior, 170 bytes

Este debería funcionar para todas las entradas, aunque con solo enteros de 32 bits, existe la posibilidad de imprecisión ya que R los convertirá automáticamente 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)}

Pruébalo en línea!

Toma -1para A, 0para By 1para C.

Transmite el enfoque de esta respuesta para la conversión a ternario equilibrado, aunque dado que tenemos la garantía de no tener más de 27 trits equilibrados, está optimizado para eso.

R , 160 bytes

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}

Pruébalo en línea!

Esta versión terminará extremadamente lentamente. El bogosort de la conversión de base, esta función selecciona aleatoriamente los trits hasta que de alguna manera mágica ( 3^-54posibilidad de que ocurra) encuentre los trits correctos para ay b, y luego realice la operación requerida. Esto básicamente nunca terminará.

Giuseppe
fuente
Creo que zestá restringido a {-1, 0, 1}.
Erik the Outgolfer
@EriktheOutgolfer Puede elegir qué valores de zmapa para una de estas tres operaciones ternarias cada uno: [...]
Dennis
@Dennis zes o bien -1, 0o1 , y creo que esos son los "valores de z" hacía referencia.
Erik the Outgolfer
Es una diferencia de dos bytes, reemplazando switch(z,...)por switch(z+2,...)lo que sería un cambio trivial independientemente.
Giuseppe
0

Jalea , 47 bytes

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

Pruébalo en línea!

Programa completo

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

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

Erik el Outgolfer
fuente
No creo que se permita tomar xy yen ternario balanceado: "x e y pueden ser de -3812798742493 a 3812798742493 inclusive. El primer paso es convertir x e y de decimal a ternario balanceado".
Jonathan Allan
@JonathanAllan comentario aclaración
Erik the Outgolfer
... pero el formato nativo para números no está equilibrado en Jelly.
Jonathan Allan
@JonathanAllan Oh, parece que no he entendido bien ...
Erik the Outgolfer
@JonathanAllan eugh ... arreglado
Erik the Outgolfer el