Implement Malbolge's "crazy" operator

Question

One of many unique features of the Malbolge programming language is its highly unintuitive OP operator, referred to only as "op" in the documentation and source code but popularly known as the "crazy" operator. As described by Ben Olmstead, the creator of the language, in its documentation: "don't look for pattern, it's not there."

op is a "tritwise" operator -- it operates on corresponding ternary digits of its two arguments. For each trit (ternary bit), the result of op is given by the following lookup table:

           a
op(a,b)  0 1 2
       +-------
     0 | 1 0 0
   b 1 | 1 0 2
     2 | 2 2 1

For example, to calculate op(12345, 54321), first write out both numbers in ternary and then look up each pair of trits in the table:

   0121221020   (12345_3)
op 2202111220   (54321_3)
--------------
   2202220211   (54616_3)

The last important point is that all values in Malbolge are 10 trits wide, so input values should be padded with zeroes to a width of 10. (For instance, op(0, 0) is 1111111111 in ternary.)

Your task is to take two integers 0 ≤ a, b < 59049 as input, and output the integer value of op(a,b).

Test cases (in the format a b op(a,b)):

0 0 29524
1 2 29525
59048 5 7
36905 2214 0
11355 1131 20650
12345 54321 54616

Here is a reference implementation (copied directly from the Malbolge source code).

Answer 1

C (gcc), 99 98 96 bytes

• Saved a byte thanks to ceilingcat; golfing 19683 to L'䳣'.
• Saved two bytes; golfing 108609 to L'𚡁'.

M,a,l,b,o;L(g,e){for(o=b=L'䳣',l=0;o/=2.4;b/=3)M=g/b,g%=b,a=e/b,e%=b,l+=b*(L'𚡁'>>M+6*a+M&3);g=l;}

Try it online!

Answer 2

JavaScript (ES7), 56 bytes

f=(a,b,k=9)=>~k&&(a%3|b%3<<9|8)**2%82%3+3*f(a/3,b/3,k-1)

Try it online!

How?

Given \$a\$ and \$b\$ in \$[0..2]\$, we compute:

$$f(a,b)=((a+512b+8)^2 \bmod 82) \bmod 3$$

Leading to:

 a | b | 512b | a + 512b |  + 8 | squared | MOD 82 | MOD 3
---+---+------+----------+------+---------+--------+-------
 0 | 0 |    0 |      0   |    8 |      64 |   64   |   1                  a
 1 | 0 |    0 |      1   |    9 |      81 |   81   |   0                0 1 2
 2 | 0 |    0 |      2   |   10 |     100 |   18   |   0              +-------
 0 | 1 |  512 |    512   |  520 |  270400 |   46   |   1            0 | 1 0 0
 1 | 1 |  512 |    513   |  521 |  271441 |   21   |   0    -->   b 1 | 1 0 2
 2 | 1 |  512 |    514   |  522 |  272484 |   80   |   2            2 | 2 2 1
 0 | 2 | 1024 |   1024   | 1032 | 1065024 |    8   |   2
 1 | 2 | 1024 |   1025   | 1033 | 1067089 |   23   |   2
 2 | 2 | 1024 |   1026   | 1034 | 1069156 |   40   |   1

Function choice

There are several other possible candidate functions of the form:

$$f_{k,c,p,m}(a,b)=((a+kb+c)^p \bmod m) \bmod 3$$

One of the shortest ones being:

$$f(a,b)=((a+5b+2)^4 \bmod 25) \bmod 3$$

But the good thing about \$(a+512b+8)\$ is that it can be performed with bitwise operators, thus implicitly discarding the decimal parts of \$a\$ and \$b\$. This is why we can simply divide them by \$3\$ without rounding between each iteration.

Commented

f = (a, b,            // given the input integers a and b
           k = 9) =>  // and starting with k = 9
  ~k &&               // if k is not equal to -1:
    ( a % 3           //   compute (a mod 3)
      | b % 3 << 9    //   add 512 * (b mod 3)
      | 8             //   add 8
    ) ** 2            //   square the result
    % 82              //   apply modulo 82
    % 3               //   apply modulo 3, leading to crazy(a % 3, b % 3)
    + 3 * f(          //   add 3 times the result of a recursive call with:
      a / 3,          //     a / 3  \__ no rounding required
      b / 3,          //     b / 3  /   (see 'Function choice')
      k - 1           //     k - 1
    )                 //   end of recursive call

Answer 3

05AB1E, 18 bytes

Code:

3Tm+3Bø5+3m5(^3%3β

Uses the 05AB1E encoding. Try it online!

Algorithm Explanation

In order to get the number padded with zeroes, we need to add 59049 to both numbers (because 59049 in ternary is 10000000000). We do not have to leave out the leading 1 as \$(1, 1) \rightarrow 0\$. We convert the numbers from decimal to ternary and join each pair as each own number.

For example, for input 12345 and 54321, these get mapped to:

$$ \begin{array} & 12345 \rightarrow & 1 & 0 & 1 & 2 & 1 & 2 & 2 & 1 & 0 & 2 & 0 \\ 54321 \rightarrow & 1 & 2 & 2 & 0 & 2 & 1 & 1 & 1 & 2 & 2 & 0 \end{array} $$

Which gives the following list of joined integers:

$$ 11, 2, 12, 20, 12, 21, 21, 11, 2, 22, 0 $$

These integers need to be mapped by the given lookup table in the OP. The formula we currently use that maps these numbers to their corresponding trits (\$0 \rightarrow 1, 10 \rightarrow 0, \dots\$) is:

$$ f(x) = \left((x + 5)^3 \oplus -5\right) \text{ mod }3 $$

Whereas \$\oplus\$ denotes the bitwise xor function.

Eventually after mapping this function on the list of joined integers, we treat this resulting list as a number represented in base 3 and convert it from base 3 to decimal.

Code Explanation

3Tm+                  # Add 59049 to pad the ternary number with zeroes.
    3B                # Convert to base 3.
      ø               # Zip the list to get each joined integer.
       5+             # Add 5 to each element.
         3m           # Raise each element to the power of 3.
           5(^        # XOR each element with -5.
              3%      # Modulo each element with 3.
                3β    # Convert from base 3 to decimal.

Answer 4

C (gcc), 74 72 71 bytes

f(a,b,i,r){for(r=0,i=59049;i/=3;)r+=(108609>>a/i%3*2+b/i%3*6&3)*i;i=r;}

Try it online!

Breakdown

The truth table

           a
op(a,b)  0 1 2
       +-------
     0 | 1 0 0
   b 1 | 1 0 2
     2 | 2 2 1

Can be thought of as a 3x3 array, where a is the column, and b is the row. Transforming that into a one-dimensional list gives us 100102221. To save space we avoid lists and strings and make it into a number instead. To do that, we flip the order and transform every trit into a 2-bit number. Glue them together and we have a binary number we can "index" into by shifting to the right by 2 * (b * 3 + a) and masking:

 1 0 0 1 0 2 2 2 1
 1 2 2 2 0 1 0 0 1
011010100001000001

Next, we massage the expression using the power of operation precedence to become the abomination above.

3^9 = 19683 so that is a good loop limit. Since we multiply the counter by 3 each time, we can write the limit as 2e4 instead. Also we save ourselves the bother of pow() or similar.

On second thought, let's start at 3^10 and work downwards with a pre-loop divide-and-test.

Answer 5

R, 64 62 bytes

function(a,b,x=3^(9:0))30801%/%x[a%/%x%%3*3+b%/%x%%3+1]%%3%*%x

Try it online!

Thanks to JAD for some black magic golfing tricks and -2 bytes!

30801, when converted to a 10-trit ternary integer, is 1120020210 which just adds a trailing zero to the operation table, when read down the columns. Then we convert the ternary digits of a and b elementwise into an integer and use that as an index into the ternary digits of 30801.

Answer 6

Haskell, 108 bytes

2%2=1
_%2=2
0%_=1
2%1=2
_%_=0
g=take 10.map(`mod`3).iterate(`div`3)
(foldr((.(3*)).(+))0.).(.g).zipWith(%).g

Try it online!

Answer 7

APL (Dyalog), 41 25 bytes

9 bytes saved thanks to @Adám

3⊥(b⊤6883)[3⊥⍉⎕⊤⍨3,b←9⍴3]

Try it online!

Answer 8

Jelly,  23  18 bytes

-1 thanks to Erik the Outgolfer (rearrange 3*⁵¤ to ⁵3*)

⁵3*+b3Zḅ3ị⁽½Ṡb3¤ḅ3

A monadic link accepting a list of two integers.

Try it online! Or see a test-suite.

⁹*%733%3 is a byte longer than ị⁽½Ṡb3¤ :(

How?

⁵3*+b3Zḅ3ị⁽½Ṡb3¤ḅ3 - Link: [a, b]      e.g. [11355,1131]
⁵                  - literal ten            10
 3                 - literal three          3
  *                - exponentiation         59049
   +               - addition (vectorises)  [70404,60180]
     3             - literal three          3
    b              - to base (vectorises)   [[1,0,1,2,0,1,2,0,1,2,0],[1,0,0,0,1,1,1,2,2,2,0]]
      Z            - transpose              [[1,1],[0,0],[1,0],[2,0],[0,1],[1,1],[2,1],[0,2],[1,2],[2,2],[0,0]]
        3          - literal three          3
       ḅ           - from base (vectorises) [4,0,3,6,1,4,7,2,5,8,0]
               ¤   - nilad followed by link(s) as a nilad:
          ⁽½Ṡ      -   literal 3706         3706
              3    -   literal three        3
             b     -   to base              [1,2,0,0,2,0,2,1]
         ị         - index into             [0,1,0,0,1,0,2,2,2,1,1]
                 3 - literal three          3
                ḅ  - from base              20650

---

Also 18: ⁵3*+b3ZḌ19*%74%3ḅ3 (uses a magic-formula after getting the pair-wise trits of converting from base ten then taking 19 to that power, modulo 74, modulo 3 to get the required trits of the output - found using a search in Python)

Answer 9

Python 2, 79 65 63 61 bytes

thanks to Arnauld for his formula (-2 bytes).

f=lambda a,b,i=9:i+1and(a%3+b%3*5+2)**4%25%3+f(a/3,b/3,i-1)*3

Try it online!

Answer 10

J, 37 bytes

((3 3$d 30801){~{@,.)&.(d=.(10$3)&#:)

Explanation:

((3 3$d 30801){~{@,.)&.(d=.(10$3)&#:)   
                       (d=.(10$3)&#:)   convert to 10 trits, and name this function as d
                     &.                 ... which is done on both args and inverted on the result
                {@,.                    make boxed indices: 1 2 3 4 {@,. 5 6 7 8  ->  1 5 ; 2 6 ; 3 7 ; 4 8
              {~                        index out of a lookup table
 (3 3$d 30801)                          reusing the trits conversion function to make the table

Ended up being relatively readable, tbh.

Answer 11

Python 2, 90 87 bytes

f=lambda a,b,A='':f(a/3,b/3,'100102221'[a%3+b%3*3]+A)if a+b else int(A.rjust(10,'1'),3)

Try it online!

Answer 12

Charcoal, 31 bytes

Ｉ↨³⮌⭆χ§200211⁺∨﹪÷θＸ³ι³¦⁴﹪÷ηＸ³ι³

Try it online! Link is to verbose version of code. Explanation:

     χ                          Predefined variable 10
    ⭆                           Map over implicit range and join
                    ι        ι  Current index
                  Ｘ³       Ｘ³   Power of 3
                 θ              Input `a`
                          η     Input `b`
                ÷        ÷      Integer divide
               ﹪     ³  ﹪     ³ Modulo by 3
              ∨       ¦⁴        Replace zero ternary digit of `a` with 4
             ⁺                  Add
      §200211                   Index into literal string `200211`
   ⮌                            Reverse
 ↨³                             Convert from base 3
Ｉ                               Cast to string
                                Implicitly print

Alternative solution, also 31 bytes:

Ｉ↨³Ｅ↨⁺Ｘ³χ賧200211⁺∨ι⁴§↨⁺Ｘ³χη³κ

Try it online! Link is to verbose version of code.

        χ                  χ    Predefined variable 10
      Ｘ³                 Ｘ³     Power of 3 i.e. 59049
         θ                      Input `a`
                            η   Input `b`
     ⁺                  ⁺       Sum
    ↨     ³            ↨     ³  Convert to base 3
   Ｅ                            Map over elements
                    ι           Current ternary digit of `a`
                   ∨ ⁴          Replace zero with 4
                      §       κ Index into ternary digits of `b`
                  ⁺             Add
           §200211              Index into literal string `200211`
 ↨³                             Convert from base 3
Ｉ                               Cast to string
                                Implicitly print

Answer 13

Stax, 22 bytes

é╨¼aûé∟ç⌂zπb![5┬◘«╜‼╞♠

Run and debug it

Answer 14

K (ngn/k), 25 22 bytes

3/(3\10267)@3/+(10#3)\

Try it online!

Answer 15

Ruby, 70 bytes

->a,b,l=10{l>0?6883.digits(3)[8-b%3*3-a%3]*3**(10-l)+f[a/3,b/3,l-1]:0}

Try it online!

Decomposes a and b recursively until we get 10 digits of each. 6883 gives the flattened ternary table (reversed). Reconstructs from ternary to decimal by multiplying by 3**(10-l).

Answer 16

Cjam, 31 bytes

{{3bA0e[\}2*.{3*+"100102221"=}}

Try it online!

Answer 17

J, 43 bytes

3#.((3 3$t 6883){~<@,~"0)&(_10{.t=.3&#.inv)

It can certainly be golfed further.

Explanation:

                         &(               ) - for both arguments
                                t=.3&#.inv  - convert to base 3 (and name the verb t)
                           _10{.            - pad left with zeroes
   (              <@,~"0)                   - box the zipped pairs (for indexing)
    (3 3$t 6883)                            - the lookup table
                {~                          - use the pairs as indeces in the table
3#.                                         - back to decimal  

Try it online!

Answer 18

Pyth 26 25 24 bytes

Saved 1 byte, thanks to @ErikTheOutgolfer

Save another byte, inspired by @JonathanAllan's answer

im@j3422 3id3Cm.[0Tjd3Q3

Input is a 2 element list [a,b]. Try it online here, or verify all test cases here.

im@j3422 3id3Cm.[0Tjd3Q3   Implicit: Q=eval(input())
              m       Q    Map each element d of the input using:
                   jd3       Convert to base 3
               .[0T          Pad to length 10 with 0's
             C             Transpose
 m                         Map each element d of the above using:
   j3422 3                   The lookup table [1,1,2,0,0,2,0,2]
  @                          Modular index into the above using
          id3                Convert d to base 10 from base 3
i                      3   Convert to base 10 from base 3, implicit print

Answer 19

Japt, 24 23 bytes

Getting the ball rolling on Japt's run as language of the month - I fully expect to be outgolfed on this!

Takes input in reverse order as an integer array (i.e., [b,a]).

ms3 ùTA y_n3 g6883ì3Ãì3

Try it

ms3 ùTA y_n3 g6883ì3Ãì3      :Implicit input of array U=[b,a]
m                            :Map
 s3                          :  Convert to base-3 string
    ù                        :Left pad each
     T                       :  With zero
      A                      :  To length 10
        y                    :Transpose
         _                   :Map
          n3                 :  Convert from base-3 string to decimal
             g               :  Index into
              6883ì3         :    6883 converted to a base-3 digit array
                    Ã        :End map
                     ì3      :Convert from base-3 digit array to decimal

Answer 20

MMIX, 77 bytes (17 instrs + 9 data bytes)

00000000: e303000a f4040010 e3020000 e3050001  ẉ¤¡½ṡ¥¡Ñẉ£¡¡ẉ¦¡¢
00000010: 25030301 1d000003 fe060006 1d010103  %¤¤¢ø¡¡¤“©¡©ø¢¢¤
00000020: feff0006 28060606 200606ff 80060406  “”¡©(©©© ©©”⁰©¥©
00000030: 18060506 20020206 28050505 5b03fff5  𩦩 ££©(¦¦¦[¤”ṫ
00000040: f8030000 01010200 00020002 01        ẏ¤¡¡¢¢£¡¡£¡£¢

malop   SET   $3,10         // i = 10
        GETA  $4,1F         // oparr = {1,1,2,0,0,2,0,2,1}
        SET   $2,0          // r = 0
        SET   $5,1          // p = 1
0H      SUB   $3,$3,1       // loop: i--
        DIV   $0,$0,3
        GET   $6,rR         // x:xr = x /% 3
        DIV   $1,$1,3
        GET   $255,rR       // y:yr = y /% 3
        2ADDU $6,$6,$6
        ADD   $6,$6,$255
        LDB   $6,$4,$6      // j = oparr[xr * 3 + yr]
        MUL   $6,$5,$6      // j *= p
        ADD   $2,$2,$6      // r += j
        2ADDU $5,$5,$5      // p *= 3
        PBNZ  $3,0B         // if(i) goto loop
        POP   3,0           // return r
1H      BYTE  1,1,2,0,0,2,0,2,1

Answer 21

Perl 5 -p, 102 bytes

sub t{map{("@_"%3,$_[0]/=3)[0]}0..9}@a=t$_;@b=t<>}{$\=(1,1,2,0,0,2,0,2,1)[(3*pop@a)+pop@b]+$\*3while@a

Try it online!

Answer 22

Wolfram Language (Mathematica), 75 72 60 bytes

(d=IntegerDigits)[6883,3][[{1,3}.d[#,3,10]+1]]~FromDigits~3&

Try it online!

un-golfed version:

M[{a_, b_}] := 
  FromDigits[{1, 0, 0, 1, 0, 2, 2, 2, 1}[[
    IntegerDigits[a, 3, 10] + 3*IntegerDigits[b, 3, 10] + 1
  ]], 3];

Both a and b are converted to ten-trit lists, then used pairwise as a 2D index into a lookup table of numbers {1, 0, 0, 1, 0, 2, 2, 2, 1}. The result is again interpreted as a ten-trit list and converted back to integer form.

The lookup table is coded as IntegerDigits[6883,3], which is short because we are recycling the IntegerDigits symbol.