Convertidor ternario equilibrado

32

Los créditos para la idea del desafío van a @AndrewPiliser. Su propuesta original en la caja de arena fue abandonada y, dado que no ha estado activo aquí durante varios meses, he asumido el desafío.

El ternario equilibrado es un sistema de numeración no estándar. Es como ternario en que los dígitos aumentan en valor en un factor de 3 a medida que avanza hacia la izquierda, así100es9y1001es 28.

Sin embargo, en lugar de tener valores de 0, 1 y 2, los dígitos tienen valores de -1, 0 y 1 . (Todavía puede usar esto para expresar cualquier número entero).

Para este desafío, el significado del dígito +1se escribirá como +, -1se escribirá como -y 0es justo 0. El ternario equilibrado no usa el -símbolo delante de los números para negarlos como lo hacen otros sistemas de numeración; vea ejemplos.

Su tarea es escribir un programa completo que tome un entero con signo decimal de 32 bits como entrada y lo convierta en ternario equilibrado. No se permiten funciones de conversión de base incorporadas de ningún tipo (Mathematica probablemente tiene una ...). La entrada puede estar en entrada estándar, argumentos de línea de comandos, etc.

Los ceros a la izquierda pueden estar presentes en la entrada pero no en la salida, a menos que la entrada lo esté 0, en cuyo caso la salida también debería estarlo 0.

Ejemplos

Estas son conversiones de ternario balanceado a decimal; Tendrás que convertir a la inversa.

+0- = 1*3^2 + 0*3^1 + -1*3^0 = 9 + 0 + -1 = 8
+-0+ = 1*3^3 + -1*3^2 + 0*3^1 + 1*3^0 = 27 + -9 + 0 + 1 = 19
-+++ = -1*3^3 + 1*3^2 + 1*3^1 + 1*3^0 = -27 + 9 + 3 + 1 = -14
Comunidad
fuente
Oh, espera, me acabo de dar cuenta de que hay una pregunta sobre la docena equilibrada : ¿es un duplicado?
Como mencioné en la caja de arena, creo que está más cerca del desafío de las representaciones phinary estándar . Pero probablemente tampoco sea un duplicado de ninguno.
Martin Ender

Respuestas:

22

Python 2: 58 caracteres

n=input()
s=""
while n:s="0+-"[n%3]+s;n=-~n/3
print s or 0

Genera el ternario balanceado dígito por dígito desde el final. El último dígito se da por el residuo n%3ser -1, 0o +1. Luego eliminamos el último dígito y dividimos entre 3 usando la división de piso de Python n=(n+1)/3. Luego, procedemos recursivamente con el nuevo último dígito hasta que el número sea 0.

Se necesita un caso especial para que la entrada 0dé en 0lugar de la cadena vacía.


Las especificaciones no permiten esto, pero si uno pudiera escribir una función en lugar de un programa y generar la cadena vacía para 0, sería posible una solución de 40 caracteres.

g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""
xnor
fuente
Mejor usar n*"."anden el caso de solo funciones. También print s or 0funciona mejor: P
Nabb
@Nabb Good call on s or 0. Lo intenté n*"."and, pero falla cuando n<0.
xnor
La respuesta más larga de @ MartinBüttner Pyth se debió al uso de un algoritmo no óptimo.
Optimizador
@Optimizer Bueno, obviamente, y es por eso que he votado a favor de la respuesta de Python que obtuvo el mejor algoritmo primero. : P
Martin Ender
6

CJam, 24 bytes

Se me ocurrió esto de forma independiente y creo que esta es, probablemente, la única forma de manejar esto.

li{_3%"0+-"=\_g+3/}h;]W%

Algorítmicamente, es similar a la respuesta de xnor.

Pruébalo en línea aquí

Cómo funciona :

li{               }h                 "Read input, convert to integer and run the code block"
                                     "until stack has 0 on top";
   _3%                               "Copy and get modulus 3";
      "0+-"=                         "Take the correct character based on the above modulus";
            \_g+                     "Swap, copy and take signum of the number and add"
                                     "that to it, incrementing the number if positive,"
                                     "decrementing otherwise";
                3/                   "Integer divide by 3 and continue until 0";
                    ;]               "Pop the residual 0 and wrap everything in array";
                      W%             "Reverse to get in binary format (right handed)";
Optimizador
fuente
¿Es necesario el bit "incremento si es positivo, decremento si es negativo"? ¿Por qué no solo incrementar?
isaacg
@isaacg Pruébalo;)
Optimizer
¿Es diferente el redondeo en la división de CJam?
isaacg
@isaacg - Redondeo - no. La división de enteros de CJam no se redondea. Pisos
Optimizador
¿Pero piso hacia cero o -inf?
isaacg
6

JavaScript (E6) 68

Un programa completo, según lo solicitado, con E / S a través de una ventana emergente. El núcleo es la función R, 49 bytes.

No es muy diferente de las otras soluciones recursivas, supongo. Aprovechando la conversión automática entre cadena y número para evitar un caso especial para "0"

 alert((R=(n,d=(n%3+3)%3)=>n?R((n-d)/3+(d>1))+'0+-'[d]:'')(prompt()))

Pruebe en la consola FireFox / FireBug, utilizando solo la función R

['0','8','19','-14','414'].map(x =>x +': '+R(x))

Salida

["0: 0", "8: +0-", "19: +-0+", "-14: -+++", "414: +--0+00"]
edc65
fuente
¿Me estoy perdiendo de algo? ¿Cuál es el punto de d=(n%3+3)%3cuando se d=n%3produce el mismo valor para d?
RLH
@RLH no para valores negativos (no en JavaScript). -20% 3 === -2% 3 === -2. En cambio, -20 mod 3 debería ser 1, y (-20% 3 + 3)% 3 es de hecho 1
edc65
6

Pyth, 71 24 23

L?+y/hb3@"0+-"%b3bk|yQ0

Esta es una solución recursiva, basada en la función recursiva de 40 caracteres de @ xnor. yconstruye el ternario balanceado de la entrada, encontrando el último dígito usando el índice mod 3, y luego usa el hecho de que el resto de los dígitos son iguales al ternario balanceado para (n + 1) / 3, usando la división en pisos. Luego, llama a la función, devolviendo el resultado, o 0 si la entrada es 0.

Pruébalo aquí.

isaacg
fuente
¿Hay un intérprete de Pyth en línea?
Hay, lo agregaré a la publicación.
isaacg
Tu enlace está roto. Recomiendo ¡ Pruébelo en línea! , que utilizará a partir de ahora cuando necesite un intérprete para algo. Por cierto, su código parece no funcionar, para mí solo devuelve la entrada.
Pavel
@Pavel Funcionó hace dos años, cuando lo escribí. El intérprete actual de Pyth en línea es pyth.herokuapp.com. Si desea ejecutar el código anterior, puede consultar el intérprete desde entonces desde github.com/isaacg1/pyth , que tiene un historial completo del idioma controlado por la versión.
isaacg
3

Mathematica - 157 154 146 128

La versión de golf:

f=(s="";n=#;i=Ceiling@Log[3,Abs@#]~Max~0;While[i>=0,s=s<>Which[n>=(1+3^i)/2,n-=3^i;"+",n>-(1+3^i)/2,"0",1>0,n+=3^i;"-"];i--];s)&

Y con sangría para legibilidad:

f = (s = ""; n = #; i = Ceiling@Log[3, Abs@#]~Max~0;
 While[i >= 0, 
  s = s<>Which[
   n >= (1 + 3^i)/2, n -= 3^i; "+",
   n > -(1 + 3^i)/2, "0", 
   1 > 0, n += 3^i; "-"
  ];
 i--];
s)&

Uso:

f[414]

Salida:

+--0+00

Muchas gracias a Martin Büttner por reducir el número de personajes.

Cuenta
fuente
3

Mathematica, 54 caracteres

Similar a la recursión de xnor

Símbolos Unicode se utilizan para reemplazar Floor, Part,!=

If[(t=⌊(#+1)/3⌋)≠0,#0@t,""]<>{"0","+","-"}〚#~Mod~3+1〛&

Salida

Almacenado como fbrevedad y escrito sin Unicode en caso de que no pueda ver

f=If[(t=Floor[(#+1)/3])!=0,#0@t,""]<>{"0","+","-"}[[#~Mod~3+1]]&
f /@ {8, 19, -14, 414} // Column

+0-
+-0+
-+++
+--0+00
millas
fuente
3

GNU sed, 236 bytes

/^0/bV
:
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;-]/s/;/&&&&&&&&&&/g
t
y/;/1/
:V
s/111/3/g
s/3\b/3:/
s/311/33!/
s/31/3+/
y/3/1/
tV
s/1/+/
y/1:/!0/
/-/{s/-//
y/+!/!+/
}
y/!/-/

Pruébalo en línea!

Explicación

La primera mitad del código (menos la primera línea) traduce decimal a unario y viene directamente de " Consejos para jugar golf en sed ". Luego traduce unario a ternario equilibrado un trit a la vez, lo que demostraré trabajando un ejemplo manualmente.

Antes de la salida final, los dígitos ternarios -, 0y +están representados por !, :y +, respectivamente.

Para un resultado interesante, comenzamos con -48, que se ha convertido a unario (con el -intacto). Para calcular el primer trit (más a la derecha), tenemos que calcular el resto de 48 ÷ 3. Podemos hacer esto reemplazando la 111s con 3s:

-111111111111111111111111111111111111111111111111 │ s/111/3/g
# => -3333333333333333

48 ÷ 3 no tiene resto, por lo que no 1quedan s, y sabemos que nuestro primer trit es :(para 0), por lo que lo reemplazamos:

-3333333333333333 │ s/3\b/3:/
# => -3333333333333333:

Ahora tenemos nuestro "lugar de unos", por lo que sabemos que los 3s restantes representan el lugar de tres. Para mantener las matemáticas funcionando, tenemos que dividirlas entre 3, es decir, reemplazarlas con 1s:

-3333333333333333: │ y/3/1/
# => -1111111111111111:

Revisemos nuestras matemáticas: tenemos 16 (unario 1111111111111111) en el lugar de tres y cero ( :) en el lugar de las unidades. Eso es 3✕16 + 1✕0 = 48. Hasta ahora todo bien.

Ahora comenzamos de nuevo. Reemplace 111s con 3s:

-1111111111111111: │ s/111/3/g
# => -333331:

Esta vez nuestro resto es 1, así que colocamos +el lugar de tres y reemplazamos los 3s restantes con 1s:

-333331: │ s/31/3+/; y/3/1/
# => -11111+:

Tiempo de comprobación de cordura: Tenemos un 5 (unario 11111) en el lugar de los nueve, 1 ( +) en el lugar de los tres y 0 ( :) en el lugar de las unidades: 9✕5 + 3✕1 + 1✕0 = 48. ¡Genial! Nuevamente reemplazamos la 111s con 3s:

-11111+: │ s/111/3/g
# => -311+:

Esta vez nuestro resto es 2 ( 11). Eso ocupa dos trits ( +!), lo que significa que tenemos un carry. Al igual que en la aritmética decimal, eso significa que tomamos el dígito más a la derecha y agregamos el resto a la columna a la izquierda. En nuestro sistema, eso significa que colocamos !el lugar de los nueves y agregamos otros tres a su izquierda, luego reemplazamos todos los 3s con 1s para representar el lugar 27:

-311+: │ s/311/33!/; y/3/1/
# => -11!+:

Ahora no nos quedan 3s, por lo que podemos reemplazar los dígitos unarios restantes con sus trits correspondientes. Dos ( 11) es +!:

-11!+: │ s/11/+!/
# => -+!!+:

En el código real, esto se hace en dos pasos s/1/+/y y/1:/!0/para guardar bytes. El segundo paso también reemplaza :s con 0s, por lo que en realidad hace esto:

-11!+: │ s/1/+/; y/1:/+0/
# => -+!!+0

Ahora verificamos si tenemos un número negativo. Lo hacemos, así que tenemos que deshacernos del signo y luego invertir cada trit:

-+!!+0 │ /-/ { s/-//; y/+!/!+/; }
# => !++!0

Finalmente, reemplazamos !s con -s:

!++!0 │ y/!/-/
# => -++-0

¡Eso es!

Jordán
fuente
2

Stax , 17 bytes

ë1·âΓM¿├>Ö≥Er☺à┤3

Ejecutar y depurarlo

La respuesta más corta hasta ahora, pero debería ser fácilmente superada por algunos idiomas de golf. El algoritmo es el mismo que la respuesta Python de @ xnor.

ASCII equivalente:

z{"0+-";3%@+,^3/~;wr
Weijun Zhou
fuente
1

JavaScript 108 102 (ES6, sin llamadas recursivas)

t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v="0+-"[r=(a%3+3)%3]+v,2==r&&++a,a=a/3|0;return v}

Entrada original en 108

t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v=(N?"0-+":"0+-")[r=a%3]+v,2==r&&++a,a/=3,a|=0;return v}

No es tan elegante como la respuesta de @ edc65 ... Agradecería cualquier ayuda para reducir esto aún más ...

WallyWest
fuente
1

Clojure, 242 bytes

#(clojure.string/join""(map{1"+"0"0"-1"-"}(loop[x(vec(map read-string(clojure.string/split(Integer/toString % 3)#"")))](let[y(.indexOf x 2)](if(< y 0)x(let[z(assoc x y -1)](recur(if(= y 0)(vec(cons 1 z))(assoc z(dec y)(inc(x(dec y))))))))))))

¿Es esta la respuesta Clojure más larga hasta ahora?

Sin golf (con comentarios):

(use '[clojure.string :only (split join)]);' (Stupid highlighter)
; Import functions

(defn ternary [n]
  (join ""
  ; Joins it all together
    (map {1 "+" 0 "0" -1 "-"}
    ; Converts 1 to +, 0 to 0, -1 to -
      (loop [x (vec (map read-string (split (Integer/toString n 3) #"")))]
      ; The above line converts a base 10 number into base 3,
      ; and splits the digits into a list (8 -> [2 2])
        (let [y (.indexOf x 2)]
        ; The first occurrence of 2 in the list, if there is no 2,
        ; the .indexOf function returns -1
          (if (< y 0) x
          ; Is there a 2? If not, then output the list to
          ; the map and join functions above.
            (let [z (assoc x y -1)]
            ; Converts where the 2 is to a -1 ([2 2] -> [-1 2])
              (recur
                (if (= y 0) (vec (cons 1 z))
                  ; If 2 is at the 0th place (e.g. [2 2]),
                  ; prepend a 1 (e.g. [-1 2] -> [1 -1 2])
                  (assoc z (dec y) (inc (x (dec y)))))))))))))
                  ; Else increment the previous index
                  ; (e.g. [1 -1 2] -> [1 0 -1])
clismique
fuente
1

, 179 171 167 caracteres

Aquí es un programa completo en octavo que toma un entero con signo decimal como entrada y lo convierte en ternario equilibrado

 
: f "" swap repeat dup 3 n:mod ["0","+","-"] swap caseof rot swap s:+ swap dup n:sgn n:+ 3 n:/mod nip while drop s:rev ;
"? " con:print 16 null con:accept >n
f cr . cr
 

Prueba

 
? 414
+--0+00
 

La primera vez que el programa solicita un número para convertir (según sea necesario). Entonces, es posible invocar la palabra fpara convertir más números como en la siguiente línea:

 
[ 8 , 19 , -14 , ] ( nip dup . space f . cr ) a:each drop 
 

Salida

 
8 +0-
19 +-0+
-14 -+++
 

Explicación del código

 
"? " con:print 16 null con:accept >n
 

Este es el código para el manejo de entrada. El núcleo del código está dentro de la palabra f. Lejos del campo de golf , habría usado la palabra en >btlugar de f. Aquí hay una versión sin golf de f(con comentarios):

 
: f \ n -- s
    ""   \ used for the first symbol concatenation
    swap \ put number on TOS to be used by loop
    repeat
        dup 
        3 n:mod      \ return the remainder of the division by 3
        [ "0" , "+" , "-" , ] 
        swap caseof  \ use remainder to take proper symbol
        rot          \ put previous symbol on TOS 
        swap         \ this is required because "" should come first
        s:+          \ concatenate symbols
        swap         \ put number on TOS 
        dup
        n:sgn n:+    \ add 1 if positive or add -1 if negative
        3 n:/mod nip \ put quotient only on TOS
    while drop
    s:rev            \ reverse the result on TOS
;
 
Chaos Manor
fuente
0

Java, 327 269 ​​caracteres

Mi primer intento en el golf de código. No conozco ninguno de esos lenguajes realmente cortos, así que aquí hay una solución en Java. Agradecería consejos para acortarlo aún más.

import java.util.*;class a{public static void main(String[] h){int i=Integer.parseInt(new Scanner(System.in).nextLine());String r="";while(i!=0){if(i%3==2||i%3==-1){r="-"+r;}else if(i%3==1||i%3==-2){r="+"+r;}else{r="0"+r;}i=i<0?(i-1)/3:(i+1)/3;}System.out.println(r);}}

Pruébelo aquí: http://ideone.com/fxlBBb

EDITAR

Reemplazado BufferedReaderpor Scanner, lo que me permite eliminar la throwscláusula, pero tuve que cambiar la importación (+2 caracteres). Sustituido Integerpor int. Por desgracia, el programa no se compila si no es String[] hen main.

Thrax
fuente
1
Es posible que pueda guardar algunos bytes utilizando un en Scannerlugar de su BufferedReader. Además, String[] hy throws java.lang.Exceptionprobablemente no sea necesario, y puede guardar algunos bytes más al usar en intlugar de Integer.
0

JavaScript (ES6), 51 bytes

v=>[...v].map(x=>t=3*t+((+x!=+x)?(x+1)-0:0),t=0)&&t

Recorrer los personajes. Primero multiplique el total anterior por 3, luego, si isNaN (carácter) es verdadero, convierta la cadena (carácter + "1") en un número y agréguelo, de lo contrario cero.

Grax32
fuente
0

APL (NARS), 26 caracteres, 52 bytes

{+/(3*¯1+⍳≢⍵)ׯ2+⌽'-0+'⍳⍵}

prueba:

  h←{+/(3*¯1+⍳≢⍵)ׯ2+⌽'-0+'⍳⍵}
  h '+0-'
8
  h '+-0+'
19
  h '-+++'
¯14
  h ,'-'
¯1
  h ,'0'
0
  h ,'+'
1

posible, podría ser menos si se usa ⊥ pero está prohibido ...

RosLuP
fuente