32
\$\begingroup\$

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
\$\endgroup\$

16 Answers 16

22
\$\begingroup\$

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""
\$\endgroup\$
  • \$\begingroup\$ Better to use n*"."and in the function-only case. Also print s or 0 works better :P \$\endgroup\$ – Nabb Nov 22 '14 at 20:53
  • \$\begingroup\$ @Nabb Good call on s or 0. I had tried n*"."and, but it fails when n<0. \$\endgroup\$ – xnor Nov 22 '14 at 20:54
  • \$\begingroup\$ @MartinBüttner Pyth's longer answer was just due to use of a non optimal algorithm. \$\endgroup\$ – Optimizer Nov 22 '14 at 23:06
  • \$\begingroup\$ @Optimizer Well, obviously, and that's why I've upvoted the Python answer that got the better algorithm first. :P \$\endgroup\$ – Martin Ender Nov 22 '14 at 23:12
6
\$\begingroup\$

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)";
\$\endgroup\$
  • \$\begingroup\$ Is the "increment if positive, decrement if negative" bit necessary? why not just increment? \$\endgroup\$ – isaacg Nov 22 '14 at 21:36
  • \$\begingroup\$ @isaacg Try it out ;) \$\endgroup\$ – Optimizer Nov 22 '14 at 21:39
  • \$\begingroup\$ Is the rounding on CJam's division different? \$\endgroup\$ – isaacg Nov 22 '14 at 22:44
  • \$\begingroup\$ @isaacg - Rounding - no. CJam integer division does not round. It floors \$\endgroup\$ – Optimizer Nov 22 '14 at 23:03
  • \$\begingroup\$ But floor towards zero or -inf? \$\endgroup\$ – isaacg Nov 22 '14 at 23:04
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there an online Pyth interpreter? \$\endgroup\$ – user16402 Nov 25 '14 at 15:16
  • \$\begingroup\$ There is, I'll add it to the post. \$\endgroup\$ – isaacg Nov 25 '14 at 16:19
  • \$\begingroup\$ Your link is broken. I reccomend Try it online!, which you will use from now on whenever you need an interpreter for anything. By the way, your code appears to not work, for me it just return the input. \$\endgroup\$ – Pavel Dec 10 '16 at 9:24
  • \$\begingroup\$ @Pavel It worked two years ago, when I wrote it. The current online Pyth interpreter is pyth.herokuapp.com If you want to run the above code, you can check out the interpreter from back then from github.com/isaacg1/pyth , which has a complete version controlled history of the language. \$\endgroup\$ – isaacg Dec 11 '16 at 5:36
5
\$\begingroup\$

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"]
\$\endgroup\$
  • \$\begingroup\$ Am I missing something? What's the point of d=(n%3+3)%3 when d=n%3 yields the same value for d? \$\endgroup\$ – RLH Jan 27 '16 at 20:17
  • \$\begingroup\$ @RLH not for negative values (not in JavaScript). -20%3 === -2%3 === -2. Instead -20 mod 3 should be 1, and (-20%3+3)%3 is 1 indeed \$\endgroup\$ – edc65 Jan 27 '16 at 21:07
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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
;
 
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might be able to save a few bytes by using a Scanner instead of your BufferedReader. Also, String[] h and throws java.lang.Exception probably aren't necessary, and you might save a few more bytes by using int instead of Integer. \$\endgroup\$ – user16402 Nov 25 '14 at 19:48
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Stax, 14 bytes

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

Run and debug it

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 20 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy