11
\$\begingroup\$

Balanced ternary logic

Ternary is normally another name for base 3, that is to say, each digit is 0, 1, or 2, and each place is worth 3 times as much as the next place.

Balanced ternary is a modification of ternary which uses digits of -1, 0 and 1. This has the advantage of not needing a sign. Each place is still worth 3 times as much as the next place. The first few positive integers are therefore [1], [1, -1], [1, 0], [1, 1], [1, -1, -1] while the first few negative integers are [-1], [-1, 1], [-1, 0], [-1, -1], [-1, 1, 1].

You have three inputs x, y, z. z is either -1, 0, or 1, while x and y can be from -3812798742493 to 3812798742493 inclusive.

The first step is to convert x and y from decimal to balanced ternary. This should give you 27 trits (TeRnary digITS). You then have to combine the trits from x and y in pairs using a ternary operation and then convert the result back to decimal.

You can choose which values of z map to one of these three ternary operations each:

  • A: Given two trits, if either is zero, then the result is zero, otherwise the result is -1 if they are different or 1 if they are the same.
  • B: Given two trits, if either is zero, then the result is the other trit, otherwise the result is zero if they are different or the negation if they are the same.
  • C: Given two trits, the result is zero if they are different or their value if they are the same.

Example. Suppose x is 29 and y is 15. In balanced ternary, these become [1, 0, 1, -1] and [1, -1, -1, 0]. (The remaining 23 zero trits have been omitted for brevity.) After each of the respective operations they become A: [1, 0, -1, 0], B: [-1, -1, 0, -1], C: [1, 0, 0, 0]. Converted back to decimal the results are 24, -37 and 27 respectively. Try the following reference implementation for more examples:

function reference(xd, yd, zd) {
    var rd = 0;
    var p3 = 1;
    for (var i = 0; i < 27; i++) {
        var x3 = 0;
        if (xd % 3 == 1) {
            x3 = 1;
            xd--;
        } else if (xd % 3) {
            x3 = -1;
            xd++;
        }
        var y3 = 0;
        if (yd % 3 == 1) {
            y3 = 1;
            yd--;
        } else if (yd % 3) {
            y3 = -1;
            yd++;
        }
        var r3 = 0;
        if (zd < 0) { // option A
            if (x3 && y3) r3 = x3 == y3 ? 1 : -1;
        } else if (zd > 0) { // option B
            if (!x3) r3 = y3;
            else if (!y3) r3 = x3;
            else r3 = x3 == y3 ? -x3 : 0;
        } else { // option C
            r3 = x3 == y3 ? x3 : 0;
        }
        rd += r3 * p3;
        p3 *= 3;
        xd /= 3;
        yd /= 3;
    }
    return rd;
}
<div onchange=r.textContent=reference(+x.value,+y.value,+z.selectedOptions[0].value)><input type=number id=x><input type=number id=y><select id=z><option value=-1>A</option><option value=1>B</option><option value=0>C</option><select><pre id=r>

The reference implementation follows the steps given above but you are of course free to use any algorithm that produces the same results.

This is , so the shortest program or function that violates no standard loopholes wins!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ If the native format for numbers is balanced ternary (as opposed to binary), are we allowed to take it as input in the usual way (which results in no conversion to balanced ternary)? \$\endgroup\$
    – wizzwizz4
    Commented Jan 2, 2018 at 13:13
  • 2
    \$\begingroup\$ related \$\endgroup\$
    – Giuseppe
    Commented Jan 2, 2018 at 13:15
  • 1
    \$\begingroup\$ does z have to be one of -1,0,1 or can we pick any three consistent and distinct values? I've selected 1,2,3 in my answer, and there's some confusion about it. \$\endgroup\$
    – Giuseppe
    Commented Jan 2, 2018 at 14:39
  • 2
    \$\begingroup\$ @Giuseppe Sorry, only balanced ternary digits are allowed. \$\endgroup\$
    – Neil
    Commented Jan 2, 2018 at 17:54
  • 2
    \$\begingroup\$ I read something trasverse... Too much words and no formula \$\endgroup\$
    – user58988
    Commented Jan 3, 2018 at 10:36

4 Answers 4

2
\$\begingroup\$

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

Defines the function @, taking three Ints and giving an Int.
Operators map as 1 -> A, 0 -> B, -1 -> C.

Try it online!

The function $ folds a lambda over the digit places [0..26], into a list of ternary digits. It uses the head of the list it yields to keep a current total difference from the requisite number (which is why it is tailed prior to returning), and sign(2*t/3^p) to determine the current digit to yield. The sign trick is equivalent to if(abs(2*t)<3^p)0(sign t).

\$\endgroup\$
4
  • \$\begingroup\$ I don't know Clean, but I'm intrigued at how you've converted to balanced ternary, with $n(I think). Could you add an explanation for that? \$\endgroup\$
    – Giuseppe
    Commented Jan 4, 2018 at 13:43
  • \$\begingroup\$ @Giuseppe Absolutely, I'll add an explaination today when I've got time. \$\endgroup\$
    – Οurous
    Commented Jan 4, 2018 at 19:14
  • \$\begingroup\$ @Giuseppe does that answer your question? \$\endgroup\$
    – Οurous
    Commented Jan 4, 2018 at 20:16
  • \$\begingroup\$ Yes! That makes sense. Quite clever! \$\endgroup\$
    – Giuseppe
    Commented Jan 4, 2018 at 20:20
1
\$\begingroup\$

Jelly, 39 bytes

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

A full program taking two arguments, [x,y], and z
...where z is {A:-1, B:0, C:1}
which prints the result

Try it online! Note: the golfed method makes it slow - this altered version is faster (logs by 3, ceils and increments prior to each Cartesian product)

How?

×=       - 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
\$\endgroup\$
4
  • \$\begingroup\$ I can't for the life of me read golfing languages, so when you say 'slow', how bad is the time complexity? \$\endgroup\$
    – Οurous
    Commented Jan 2, 2018 at 23:23
  • \$\begingroup\$ To get the balanced ternary of N it creates a list of all (3^n) length abs(N) lists of trits (0,-1, and 1). So O(3^max(abs(X),abs(Y))) \$\endgroup\$ Commented Jan 3, 2018 at 0:04
  • \$\begingroup\$ Thanks, and for the explanation I see you added too! \$\endgroup\$
    – Οurous
    Commented Jan 3, 2018 at 0:07
  • 1
    \$\begingroup\$ Also added a speedier version using the same method :) \$\endgroup\$ Commented Jan 3, 2018 at 0:10
1
\$\begingroup\$

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}

Try it online!

Computes all combinations of trits and selects the right one. It'll actually throw a memory error with 27, since 3^27 is a somewhat large number, but it would in theory work. The TIO link has only 11 trit integer support; I'm not sure at what point it times out or memory errors first, and I don't want Dennis to get mad at me for abusing TIO!

old answer, 170 bytes

This one should work for all inputs, although with only 32-bit integers, there's the possibility of imprecision as R will automatically convert them to 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)}

Try it online!

Takes -1 for A, 0 for B, and 1 for C.

Ports the approach in this answer for converting to balanced ternary, although since we're guaranteed to have no more than 27 balanced trits, it's optimized for that.

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}

Try it online!

This version will terminate extremely slowly. The bogosort of base conversion, this function randomly picks trits until it somehow magically (3^-54 chance of it occurring) finds the right trits for a and b, and then does the required operation. This will basically never finish.

\$\endgroup\$
4
  • \$\begingroup\$ I think z is restricted to {-1, 0, 1}. \$\endgroup\$ Commented Jan 2, 2018 at 13:54
  • \$\begingroup\$ @EriktheOutgolfer You can choose which values of z map to one of these three ternary operations each: [...] \$\endgroup\$
    – Dennis
    Commented Jan 2, 2018 at 14:30
  • \$\begingroup\$ @Dennis z is either -1, 0, or 1, and I think those are the "values of z" being referred to. \$\endgroup\$ Commented Jan 2, 2018 at 14:33
  • \$\begingroup\$ It's a two-byte difference, replacing switch(z,...) with switch(z+2,...) so it would be a trivial change regardless. \$\endgroup\$
    – Giuseppe
    Commented Jan 2, 2018 at 14:41
0
\$\begingroup\$

Jelly, 47 bytes

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

Try it online!

Full program.

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

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

\$\endgroup\$
8
  • \$\begingroup\$ I don't think taking x and y in balanced ternary is allowed: "x and y can be from -3812798742493 to 3812798742493 inclusive. The first step is to convert x and y from decimal to balanced ternary." \$\endgroup\$ Commented Jan 2, 2018 at 19:18
  • \$\begingroup\$ @JonathanAllan comment clarification \$\endgroup\$ Commented Jan 2, 2018 at 19:29
  • \$\begingroup\$ ...but the native format for numbers is not balanced ternary in Jelly. \$\endgroup\$ Commented Jan 2, 2018 at 19:30
  • \$\begingroup\$ @JonathanAllan Oh, looks like I misunderstood.... \$\endgroup\$ Commented Jan 2, 2018 at 19:30
  • \$\begingroup\$ @JonathanAllan eugh...fixed \$\endgroup\$ Commented Jan 2, 2018 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.