Conversor ternário equilibrado

32

Os créditos para a ideia do desafio vão para @AndrewPiliser. Sua proposta original na caixa de areia foi abandonada e, como ele não está ativo aqui há vários meses, assumi o desafio.

O ternário equilibrado é um sistema numérico não padrão. É como ternário, pois os dígitos aumentam em valor por um fator de 3 à medida que você vai para a esquerda - assim100é9e1001é 28.

No entanto, em vez de ter valores de 0, 1 e 2, os dígitos têm valores de -1, 0 e 1 . (Você ainda pode usar isso para expressar qualquer número inteiro.)

Para esse desafio, o significado do dígito +1será escrito como +, -1será escrito como -e 0é justo 0. O ternário balanceado não usa o -símbolo na frente dos números para negá-los como outros sistemas numéricos - veja exemplos.

Sua tarefa é escrever um programa completo que use um número inteiro decimal de 32 bits como entrada e o converta em um ternário balanceado. Nenhuma função de conversão básica embutida de qualquer tipo é permitida (o Mathematica provavelmente possui uma ...). A entrada pode estar na entrada padrão, argumentos de linha de comando etc.

Os zeros à esquerda podem estar presentes na entrada, mas não na saída, a menos que a entrada esteja 0, nesse caso a saída também deve estar 0.

Exemplos

São conversões de ternário balanceado para decimal; você terá que converter para o outro lado.

+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
Comunidade
fonte
Oh, espere, acabei de notar que há uma pergunta sobre dúzia equilibrada - isso é uma duplicata?
Como mencionei na sandbox, acho que está mais próximo do desafio sobre as representações fárias padrão . Mas provavelmente também não é uma duplicata.
Martin Ender

Respostas:

22

Caracteres Python 2: 58

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

Gera o ternário balanceado, dígito por dígito, a partir do final. O último dígito é dada pelo resíduo n%3ser -1, 0ou +1. Em seguida, removemos o último dígito e dividimos por 3 usando a divisão do piso do Python n=(n+1)/3. Em seguida, prosseguimos recursivamente com o novo último dígito até o número ser 0.

Um caso especial é necessário para a entrada 0fornecer, 0em vez da string vazia.


As especificações não permitem isso, mas se alguém pudesse escrever uma função em vez de um programa e gerar a string vazia para 0, seria possível uma solução de 40 caracteres.

g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""
xnor
fonte
Melhor usar n*"."andno caso apenas de função. Também print s or 0funciona melhor: P
Nabb 22/11
@ Nabb Boa chamada s or 0. Eu tentei n*"."and, mas falha quando n<0.
Xnor
A resposta mais longa do @ MartinBüttner Pyth se deveu apenas ao uso de um algoritmo não ideal.
Optimizer
@ Optimizer Bem, obviamente, e é por isso que votei na resposta do Python que obteve o melhor algoritmo primeiro. : P
Martin Ender
6

CJam, 24 bytes

Eu vim com isso de forma independente e acho que essa é, provavelmente, a única maneira de lidar com isso.

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

Algoritmicamente, é semelhante à resposta do xnor.

Experimente online aqui

Como 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)";
Optimizer
fonte
O bit "incremento se positivo, decremento se negativo" é necessário? por que não apenas incrementar?
Isaacg
@isaacg Experimente;)
Optimizer
O arredondamento na divisão do CJam é diferente?
Isaacg
@isaacg - Arredondamento - não. A divisão inteira CJam não arredonda. Ele pavimenta
Optimizer
Mas andar em direção a zero ou -inf?
Isaacg
6

JavaScript (E6) 68

Um programa completo, conforme solicitado, com E / S via pop-up. O núcleo é a função R, 49 bytes.

Não é tão diferente das outras soluções recursivas, eu acho. Aproveitando a conversão automática entre string e número para evitar um caso especial para "0"

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

Teste no console do FireFox / FireBug, usando apenas a função R

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

Saída

["0: 0", "8: +0-", "19: +-0+", "-14: -+++", "414: +--0+00"]
edc65
fonte
Estou esquecendo de algo? Para que serve d=(n%3+3)%3quando d=n%3produz o mesmo valor d?
RLH 27/01
@RLH não para valores negativos (não em JavaScript). -20% 3 === -2% 3 === -2. Em vez disso -20 mod 3 deve ser 1, e (-20% 3 + 3)% 3 é um fato
edc65
6

Pyth, 71 24 23

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

Esta é uma solução recursiva, baseada na função recursiva de 40 caracteres do @ xnor. yconstrói o ternário balanceado da entrada, localizando o último dígito usando o índice mod 3 e, em seguida, usa o fato de que o restante dos dígitos é igual ao ternário balanceado para (n + 1) / 3, usando a divisão com piso. Em seguida, chama a função, retornando o resultado ou 0 se a entrada for 0.

Experimente aqui.

isaacg
fonte
Existe um intérprete Pyth online?
Existe, eu vou adicioná-lo ao post.
Isaacg
Seu link está quebrado. Eu recomendo Experimente online! , que você usará a partir de agora sempre que precisar de um intérprete para qualquer coisa. A propósito, seu código parece não funcionar, para mim, basta retornar a entrada.
Pavel
@ Pavel Funcionou há dois anos, quando eu escrevi. O intérprete Pyth on-line atual é pyth.herokuapp.com Se você deseja executar o código acima, pode fazer o check-out do intérprete em github.com/isaacg1/pyth , que possui um histórico controlado da versão completa do idioma.
Isaacg
3

Mathematica - 157 154 146 146 128

A versão golfed:

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)&

E com recuo para legibilidade:

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]

Saída:

+--0+00

Muito obrigado a Martin Büttner na redução do número de caracteres.

Tally
fonte
3

Mathematica, 54 caracteres

Semelhante à recursão do xnor

Símbolos Unicode são usadas para substituir Floor, Part,!=

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

Saída

Armazenado quanto fà brevidade e escrito sem unicode, você não pode ver

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

+0-
+-0+
-+++
+--0+00
milhas
fonte
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/!/-/

Experimente online!

Explicação

A primeira metade do código (menos a primeira linha) converte decimal em unário e vem diretamente de " Dicas para jogar golfe no sed ". Em seguida, ele traduz unário para ternário equilibrado, um trit de cada vez, o que demonstrarei trabalhando um exemplo manualmente.

Antes da saída final, os dígitos ternários -, 0e +são representados por !, :e +, respectivamente.

Para um resultado interessante, começamos com -48, que foi convertido em unário (com o -intacto). Para calcular o primeiro trit (mais à direita), temos que calcular o restante de 48 ÷ 3. Podemos fazer isso substituindo 111s por 3s:

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

48 ÷ 3 não tem resto, então não há mais 1s, e sabemos que nosso primeiro ponto é :(para 0), então o substituímos:

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

Agora, temos o nosso "local de quem", para que saibamos que os 3s restantes representam o terceiro lugar. Para manter a matemática funcionando, precisamos dividi-los por 3, ou seja, substituí-los por 1s:

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

Vamos verificar novamente nossa matemática: temos 16 (unário 1111111111111111) nos três lugares e zero ( :) nos mesmos . Isso é 3✕16 + 1✕0 = 48. Até agora tudo bem.

Agora vamos começar de novo. Substitua 111s por 3s:

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

Desta vez, o restante é 1, então colocamos +em três lugares e substituímos os 3s restantes por 1s:

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

Tempo de verificação da sanidade: Temos um 5 (unário 11111) no lugar dos noves, 1 ( +) no :terceiro e 0 ( ) no primeiro: 9✕5 + 3✕1 + 1✕0 = 48. Ótimo! Novamente, substituímos 111s por 3s:

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

Desta vez, o restante é 2 ( 11). Isso ocupa dois trits ( +!), o que significa que temos um carry. Assim como na aritmética decimal, significa que pegamos o dígito mais à direita e adicionamos o restante à coluna à esquerda. Em nosso sistema, isso significa que colocamos !o lugar dos noves e adicionamos outros três à sua esquerda e substituímos todos os 3s por 1s para representar o lugar dos 27s:

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

Agora não temos mais 3s, para que possamos substituir os dígitos unários restantes pelos seus trits correspondentes. Dois ( 11) são +!:

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

No código real, isso é feito em duas etapas s/1/+/e y/1:/!0/, para salvar bytes. O segundo passo também substitui :s por 0s, portanto, ele realmente faz isso:

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

Agora verificamos se temos um número negativo. Como fazemos, temos que nos livrar do sinal e depois inverter cada trit:

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

Finalmente, substituímos !s por -s:

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

É isso aí!

Jordânia
fonte
2

Stax , 17 bytes

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

Execute e depure

A resposta mais curta até agora, mas deve ser facilmente derrotada por alguns idiomas do golfe. O algoritmo é o mesmo que a resposta Python do @ xnor.

Equivalente ASCII:

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

JavaScript 108 102 (ES6, sem chamadas 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 às 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}

Não é tão chique quanto a resposta da @ edc65 ... eu apreciaria qualquer ajuda para reduzir isso ainda mais ...

WallyWest
fonte
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))))))))))))

Essa é a resposta mais longa do Clojure até agora?

Sem Golfe (com comentários):

(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
fonte
1

8th , 179 171 167 caracteres

Aqui está um programa completo no dia 8, que pega um número inteiro com sinal decimal como entrada e o converte em ternário balanceado

 
: 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
 

Teste

 
? 414
+--0+00
 

A primeira vez que o programa solicita um número para converter (conforme necessário). Em seguida, é possível invocar a palavra fpara converter mais números, como na seguinte linha:

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

Saída

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

Explicação do código

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

Este é o código para manipulação de entrada. O núcleo do código está dentro da palavra f. Longe do campo de golfe, eu teria usado a palavra em >btvez de f. Aqui está uma versão não destruída de f(com comentários):

 
: 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
fonte
0

Java, 327 269 ​​caracteres

Minha primeira tentativa no código de golfe. Eu não conheço nenhuma dessas linguagens realmente curtas, então aqui está uma solução em Java. Eu gostaria de receber conselhos para reduzi-lo ainda mais.

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);}}

Experimente aqui: http://ideone.com/fxlBBb

EDITAR

Substituído BufferedReaderpor Scanner, permitindo remover a throwscláusula, mas tive que alterar a importação (+2 caracteres). Substituído Integerpor int. Infelizmente, o programa não será compilado se não houver String[] hno main.

Thrax
fonte
11
Você pode salvar alguns bytes usando um em Scannervez do seu BufferedReader. Além disso, String[] he throws java.lang.Exceptionprovavelmente não são necessários, você pode salvar mais alguns bytes usando em intvez de Integer.
0

JavaScript (ES6), 51 bytes

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

Repete os caracteres. Primeiro multiplique o total total de vezes anterior 3 e, se isNaN (caractere) for verdadeiro, converta a string (caractere + "1") em um número e adicione-o, caso contrário, zero.

Grax32
fonte
0

APL (NARS), 26 caracteres, 52 bytes

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

teste:

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

possível, poderia ser menor se ⊥ for usado, mas é proibido ...

RosLuP
fonte