Balanced Ternary Converter

Question

^{Credits for the challenge idea go to @AndrewPiliser. His original proposal in the sandbox was abandoned and since he has not been active here for several months, I have taken over the challenge.}

Balanced ternary is a non-standard numeral system. It is like ternary in that the digits increase in value by a factor of 3 as you go further to the left - so 100 is 9 and 1001 is 28.

However, instead of having values of 0, 1 and 2, the digits have values of -1, 0, and 1. (You can still use this to express any integer.)

For this challenge, the digit meaning +1 will be written as +, -1 will be written as -, and 0 is just 0. Balanced ternary does not use the - symbol in front of numbers to negate them like other numeral systems do - see examples.

Your task is to write a complete program which takes a 32-bit decimal signed integer as input and converts it to balanced ternary. No built-in base conversion functions of any sort are allowed (Mathematica probably has one...). Input can be on standard input, command-line arguments, etc.

Leading zeroes may be present in input but not in output, unless the input is 0, in which case the output should also be 0.

Examples

These are conversions from balanced ternary to decimal; you will have to convert the other way.

+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

Answer 1

Python 2: 58 chars

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

Generates the balanced ternary digit-by-digit from the end. The last digit is given by the residue n%3 being -1,0, or +1. We then remove the last digit and divide by 3 using Python's floor-divide n=(n+1)/3. Then, we proceed recursively with the new last digit until the number is 0.

A special case is needed for the input 0 to give 0 rather than the empty string.

---

The specs don't allow this, but if one could write a function instead of a program and output the empty string for 0, a 40 char solution would be possible.

g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""

Answer 2

CJam, 24 bytes

I came up with this independently and I think this is, most probably, the only way to handle this.

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

Algorithmically, its similar to xnor's answer.

Try it online here

How it works:

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

Answer 3

JavaScript (E6) 68

A complete program, as requested, with I/O via popup. The core is the R function, 49 bytes.

Not so different from the other recursive solutions, I guess. Taking advantage of the automatic conversion between string and number to avoid a special case for "0"

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

Test in FireFox/FireBug console, using just the R function

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

Output

["0: 0", "8: +0-", "19: +-0+", "-14: -+++", "414: +--0+00"]

Answer 4

Pyth, 71 24 23

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

This is a recursive solution, based on @xnor's 40 character recursive function. y constructs the baanced ternary of the input, by finding the last digit using the mod 3 index, and then uses the fact that the rest of the digits are equal to the balanced ternary for (n+1)/3, using floored division. Then, it calls the function, returning the result, or 0 if the input is 0.

Try it here.

Answer 5

Mathematica, 54 characters

Similar to xnor's recursion

Unicode symbols are used to replace Floor,Part,!=

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

Output

Stored as f for brevity and written without unicode incase you can't view

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

+0-
+-0+
-+++
+--0+00

Answer 6

Mathematica - 157 154 146 128

The golfed version:

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

And with indentation for legibility:

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

Usage:

f[414]

Output:

+--0+00

Many thanks to Martin Büttner in reducing the number of characters.

Answer 7

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/!/-/

Try it online!

Explanation

The first half of the code (less the first line) translates decimal to unary and comes straight from "Tips for golfing in sed." Then it translates unary to balanced ternary one trit at a time, which I'll demonstrate by working an example manually.

Before the final output, the ternary digits -, 0, and + are represented by !, :, and +, respectively.

For an interesting result, we start with -48, which has been converted to unary (with the - intact). To calculate the first (right-most) trit, we have to calculate the remainder of 48÷3. We can do this by replacing the 111s with 3s:

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

48÷3 has no remainder, so no 1s remain, and we know our first trit is : (for 0), so we replace it:

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

Now we have our "ones place," so we know the remaining 3s represent the threes place. To keep the math working we have to divide them by 3, i.e. replace them with 1s:

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

Let's double-check our math: We have 16 (unary 1111111111111111) in the threes place and zero (:) in the ones place. That's 3✕16 + 1✕0 = 48. So far so good.

Now we start again. Replace 111s with 3s:

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

This time our remainder is 1, so we put + in the threes place and replace the remaining 3s with 1s:

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

Sanity check time: We have a 5 (unary 11111) in the nines place, 1 (+) in the threes place, and 0 (:) in the ones place: 9✕5 + 3✕1 + 1✕0 = 48. Great! Again we replace the 111s with 3s:

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

This time our remainder is 2 (11). That takes up two trits (+!), which means we have a carry. Just like in decimal arithmetic that means we take the rightmost digit and add the rest to the column to the left. In our system, that means we put ! in the nines place and add another three to its left, then replace all of the 3s with 1s to represent the 27s place:

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

Now we don't have any 3s left, so we can replace any remaining unary digits with their corresponding trits. Two (11) is +!:

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

In the actual code this is done in two steps, s/1/+/ and y/1:/!0/, to save bytes. The second step also replaces :s with 0s, so it actually does this:

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

Now we check if we have a negative number. We do, so we have to get rid of the sign and then invert each trit:

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

Finally, we replace !s with -s:

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

That's it!

Answer 8

Clojure, 172 bytes

(let[s "0+-"](loop[x(Integer.(read-line))xs '()](if(= 0 x)(println(apply str xs))(let[y(mod x 3)x(int (Math/floor(/ x 3.0)))](recur(if(= y 2)(inc x)x)(cons(get s y)xs))))))

Readable version:

(let [s "0+-"]
  (loop [x  (Integer. (read-line))
         xs '()]
    (if (= 0 x)
      (apply str xs)
      (let [y (mod x 3)
            x (int (Math/floor (/ x 3.0)))]
        (recur (if (= y 2) (inc x) x) (cons (get s y) xs))))))

Answer 9

Stax, 17 bytes

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

Run and debug it

Shortest answer so far, but should be easily beaten by some golfing languages. The algorithm is the same as @xnor's Python answer.

ASCII equivalent:

z{"0+-";3%@+,^3/~;wr

Answer 10

JavaScript 108 102 (ES6, no recursive calls)

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}

Original entry at 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}

Not as fancy as @edc65's answer... I'd appreciate any help reducing this further...

Answer 11

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

Is this the longest Clojure answer so far?

Ungolfed (with comments):

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

Answer 12

8th, 179 171 167 characters

Here it is a complete program in 8th which takes a decimal signed integer as input and converts it to balanced ternary

 
: 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
 

Test

 
? 414
+--0+00
 

The first time the program asks for a number to convert (as required). Then, it is possible to invoke the word f to convert more numbers as in the following line:

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

Output

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

Code explanation

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

This is the code for input handling. The core of the code is inside the word f. Away from the golf course I would have used the word >bt instead of f. Here it is an ungolfed version of f (with comments):

 
: 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
;
 

Answer 13

Brainfuck, 406 340 335 bytes

code (with added newlines for readability):

-[+>+[+<]>+]>-<,[->->+<<]+>[[-]<->]<[>>,<]>[<]>>>>++<<<[>-[<->-----]<+++>>>[>]>>++>++<<<<[[->>+>>+<<<<]<]>>>++>++<
[[-<<<<<+>>>>>]<<<<+++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]->[-]-->+[+[-<<+>>]>]>>]<<<<<<[[->>>+<<<]<]>,]
<<[>>>>>[[-<->]>]<<[++++<]<]>>>>>[>]+[<--[>->]>[-<+>]<]<<++>+<[>-]>[-<++>>]<<[>>--[<+>++++++]<<---[>++<++[>+++<-]]>.[-]<<]

Takes input as decimal string with an optional leading - This is my first non-trivial Brainfuck program so there is certainly room for improvement.

Try it online

Commented version of code:

-[+>+[+<]>+]>-  constant 45
<,[->->+<<]+>[[-]<->]<[>>,<]>[<]> remember sign
>>>++<<< load 2 in cell 3
[ while input is not EOF
>-[<->-----]<+++ subtract 48 (ascii 0) from input
>>>[>]>>++>++<<<<[[->>+>>+<<<<]<]>>>++>++<  multiply by 10 (add number to shifted copy)
[  add next digit and handle carries
[-<<<<<+>>>>>]
<<<<+++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<] 
->[-]-->+[+[-<<+>>]>]>>
]
<<<<<<[[->>>+<<<]<]>
,] reset to start of loop
<<[>>>>>[[-<->]>]<<[++++<]<] flip number if negative
>>>>>[>]+[<--[>->]>[-<+>]<]<<++ strip leading zeros
>+<[>-]>[-<++>>]<< ensure zero is printed
[ print the number
  >>--[<+>++++++]< load 43 (char code of plus)
  <---[>++<++[>+++<-]]>.[-]<<
]

Answer 14

Java, 327 269 characters

My first try in code golfing. I don't know any of those really short languages, so here's a solution in Java. I'd appreciate advice to further shorten it.

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

Try it here : http://ideone.com/fxlBBb

EDIT

Replaced BufferedReader by Scanner, allowing me to remove throws clause, but had to change import (+2 chars). Replaced Integer by int. Unfortunately, program won't compile if there isn't String[] h in main.

Answer 15

JavaScript (ES6), 51 bytes

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

Loop through characters. First multiply previous total times 3, then if isNaN(character) is true, convert the string (character + "1") to a number and add it, otherwise zero.

Answer 16

Stax, 14 bytes

ü♣ê⌠yù∞♪♦X=/ƒ├

Run and debug it

Answer 17

05AB1E, 20 bytes

ΔYÝ<ÀÅв3βʽ¾}…0+-ÅвJ

Try it online!

Answer 18

APL(NARS), 26 chars, 52 bytes

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

test:

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

possible it could be less if ⊥ is used but it is forbidden...

Answer 19

Python 3, 66

Python 2 answer from xnor, ported to Python 3. Note that official support for Python 2 ceases on January 1 2020.

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

Answer 20

Raku (Perl 6) (rakudo), 52 53 bytes

{.&(my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''})||0}

Attempt This Online!

Explanation

{.&(my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''})||0}
    my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''}      # g returns '' for 0
              g(-+^$_ div 3)                          # g(($_ + 1) div 3)
 .&(                                           )      # call g($_)
                                                ||0   # if this is falsy, then return 0