41
\$\begingroup\$

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

\$\endgroup\$
  • 28
    \$\begingroup\$ can this be answered in Malboge? ;) \$\endgroup\$ – Display name Jul 2 '18 at 12:10
  • 3
    \$\begingroup\$ I guess Malbolge is a good golfing language now! \$\endgroup\$ – Ethan Jul 2 '18 at 17:49
  • 7
    \$\begingroup\$ For what it's worth, 54616_3 doesn't mean "this other thing is the decimal number 54616, but represented as base three". It means "Read 54616 as base 3". Which, of course, you can't do (there are digits that Valve can't count to in there). It'd still probably be just as clear if you got rid of the _3 entirely, and more accurate. \$\endgroup\$ – Nic Hartley Jul 2 '18 at 19:31
  • \$\begingroup\$ @Orangesandlemons I guess just using the operator in Malbolge would fall under the standard loophole. Reimplementing it using different code would be okay. \$\endgroup\$ – Paŭlo Ebermann Jul 2 '18 at 23:31
  • 7
    \$\begingroup\$ @PaŭloEbermann No, that's not a loophole. \$\endgroup\$ – user202729 Jul 3 '18 at 3:06

21 Answers 21

43
\$\begingroup\$

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!

\$\endgroup\$
  • 14
    \$\begingroup\$ I like the naming scheme! \$\endgroup\$ – Matthieu M. Jul 2 '18 at 9:15
28
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think (1581093>>b%3*2+a%3*8&3) saves a whole byte! \$\endgroup\$ – Neil Jul 1 '18 at 18:28
  • \$\begingroup\$ @Neil Unfortunately, I'm passing a/3 and b/3 without rounding. That would fail because of that. \$\endgroup\$ – Arnauld Jul 1 '18 at 18:47
  • 9
    \$\begingroup\$ Interesting how you found a pattern which does not exist. \$\endgroup\$ – Erik the Outgolfer Jul 2 '18 at 15:14
  • \$\begingroup\$ Is there any reason to prefer k = 9 ... => ~k && ... to k = 10 ... => k && ... ? \$\endgroup\$ – Falco Jul 3 '18 at 12:49
  • 1
    \$\begingroup\$ @Falco No, it's neither shorter nor more efficient in any way. I'd just tend to prefer 0-indexed stuff, so I'd rather mimic for(k=9;k>=0;k--) than for(k=10;k>=1;k--). \$\endgroup\$ – Arnauld Jul 3 '18 at 12:59
13
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Can 3Tm+3Bø19sm74%3%3β be golfed? \$\endgroup\$ – Jonathan Allan Jul 1 '18 at 20:54
  • \$\begingroup\$ @JonathanAllan Nice find! It does however seem impossible to golf it any further without using some other kind of black magic formula. \$\endgroup\$ – Adnan Jul 1 '18 at 21:38
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 62 bytes Yay for operator precedence! \$\endgroup\$ – JAD Jul 3 '18 at 11:53
  • 1
    \$\begingroup\$ Yeah, this way, you first index x using [.*]. Then all the %any% operations happen. The fun part is that if you see 30801%/%x%%3 as f=function(x)30801%/%x%%3, that f(x[index]) == (f(x))[index]. Saving the braces :) \$\endgroup\$ – JAD Jul 3 '18 at 12:49
  • \$\begingroup\$ @JAD fascinating! And as I comment above, basically black magic. \$\endgroup\$ – Giuseppe Jul 3 '18 at 12:50
  • 1
    \$\begingroup\$ I'll happily admit that this took a lot of fiddling :P \$\endgroup\$ – JAD Jul 3 '18 at 12:50
10
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

APL (Dyalog), 41 25 bytes

9 bytes saved thanks to @Adám

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Takes inputs in reversed order, 25 bytes: 3⊥(b⊤6883)[3⊥⍉⎕⊤⍨3,b←9⍴3] \$\endgroup\$ – Adám Jul 2 '18 at 9:50
  • \$\begingroup\$ @Adám thanks! that's some neat stuff. I guess I've gone a bit rusty :P \$\endgroup\$ – Uriel Jul 2 '18 at 10:33
6
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ 18 bytes (note: there should really be a "prepend y 0s"built-in) \$\endgroup\$ – Erik the Outgolfer Jul 1 '18 at 21:12
  • \$\begingroup\$ Ugh I thought that looked awkward. Thanks! \$\endgroup\$ – Jonathan Allan Jul 1 '18 at 21:14
  • \$\begingroup\$ Many things look awkward, sometimes you have to get used to them. :P \$\endgroup\$ – Erik the Outgolfer Jul 1 '18 at 21:15
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Here is a test-suite - I stole the wrapping code from Galen Ivanov's answer. \$\endgroup\$ – Jonathan Allan Jul 3 '18 at 6:56
  • \$\begingroup\$ Welcom to PPCG! Nice solution! Here is a TIO link to it. \$\endgroup\$ – Galen Ivanov Jul 3 '18 at 7:01
  • \$\begingroup\$ 30 \$\endgroup\$ – FrownyFrog Jul 3 '18 at 11:23
  • 2
    \$\begingroup\$ 28 \$\endgroup\$ – FrownyFrog Jul 3 '18 at 11:31
  • \$\begingroup\$ @FrownyFrog nice! \$\endgroup\$ – Jonah Aug 19 at 2:31
3
\$\begingroup\$

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!

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

Charcoal, 31 bytes

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

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

     χ                          Predefined variable 10
    ⭆                           Map over implicit range and join
                    ι        ι  Current index
                  X³       X³   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
I                               Cast to string
                                Implicitly print

Alternative solution, also 31 bytes:

I↨³E↨⁺X³χ賧200211⁺∨ι⁴§↨⁺X³χη³κ

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

        χ                  χ    Predefined variable 10
      X³                 X³     Power of 3 i.e. 59049
         θ                      Input `a`
                            η   Input `b`
     ⁺                  ⁺       Sum
    ↨     ³            ↨     ³  Convert to base 3
   E                            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
I                               Cast to string
                                Implicitly print
\$\endgroup\$
2
\$\begingroup\$

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

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

Cjam, 31 bytes

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

Try it online!

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

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!

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

Stax, 22 bytes

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

Run and debug it

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

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

K (ngn/k), 25 22 bytes

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

Try it online!

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

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

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!

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

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.

\$\endgroup\$

Your Answer

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

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