Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Introduction

Let's define a ternary function as a function from the three-element set S = {0,1,2} to itself: it associates to each element of S another element of S. One example of a ternary function f is

f(0) = 0; f(1) = 2; f(2) = 0

There are exactly 27 different ternary functions, and we represent them with integers from 0 to 26: a function f is encoded as f(0) + 3*f(1) + 9*f(2). The example function above is encoded as the number 6.

We can apply two ternary functions f and g in sequence, and if f(g(k)) == g(f(k)) holds for all k in S, then the functions commute. Your task is to verify whether this is the case.

Input

Your inputs are two integers in the inclusive range from 0 to 26. They represent two ternary functions f and g. Input must be taken in decimal, binary or unary (string of 1s) format.

Output

Your output is a truthy value if f and g commute, and a falsey value if they don't. You may not assume that the inputs are ordered.

Examples

Consider the inputs 5 and 16. They encode the ternary functions

f(0) = 2; f(1) = 1; f(2) = 0
g(0) = 1; g(1) = 2; g(2) = 1

We have f(g(1)) == f(2) == 0 and g(f(1)) == g(1) == 2, so f and g don't commute and the correct output is falsey.

On the other hand, the inputs 3 and 10 encode the ternary functions

f(0) = 0; f(1) = 1; f(2) = 0
g(0) = 1; g(1) = 0; g(2) = 1

and it can be verified that f(g(k)) == g(f(k)) holds for all k in S. Then the correct output is truthy.

Here is the 27×27 table of all possible inputs, with + marking a truthy output and - a falsey output:

+ - - + - - + - - + - - + - - + - - + - - + - - + - -
- + - - - - - - - - - - + - - - - - - - - + - - - - -
- - + - - - - - - - - - - - - - - - - - - + - - + - -
+ - - + - - - - - - + - - + - - - - + - - + - - - - -
- - - - + - - - - - - - - + - - - - - - - + - - - - -
- - - - - + - - - - - - - + - - - - - - - + - - - - -
+ - - - - - + - - - - - - - - - - - - - - + - - - - -
- - - - - - - + - - - + - - - - - - - - - + - - - - -
- - - - - - - - + - - - - - - - - - + - - + - - - - -
+ - - - - - - - - + - - - - - - - - - - - + - - - - -
- - - + - - - - - - + - - - - - - - - - - + - - - - -
- - - - - - - + - - - + - - - - - - - - - + - - - - -
+ + - - - - - - - - - - + + - - - - - - - + + - - - -
- - - + + + - - - - - - + + + - - - - - - + + + - - -
- - - - - - - - - - - - - + + - - - - - - + - - - - -
+ - - - - - - - - - - - - - - + - - - - - + - - - - -
- - - - - - - - - - - - - - - - + - - - - + - + - - -
- - - - - - - - - - - - - - - - - + - - - + + - - - -
+ - - + - - - - + - - - - - - - - - + - - + - - - - +
- - - - - - - - - - - - - - - - - - - + - + - - - - +
- - - - - - - - - - - - - - - - - - - - + + - - - - +
+ + + + + + + + + + + + + + + + + + + + + + + + + + +
- - - - - - - - - - - - + + - - - + - - - + + - - - +
- - - - - - - - - - - - - + - - + - - - - + - + + - +
+ - + - - - - - - - - - - - - - - - - - - + - + + - +
- - - - - - - - - - - - - - - - - - - - - + - - - + +
- - - - - - - - - - - - - - - - - - + + + + + + + + +

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

share|improve this question
    
Can the input be an array with the two numbers? – Luis Mendo Mar 24 at 21:52
1  
@DonMuesli That's allowed as per consensus on Meta. – Zgarb Mar 24 at 21:56

Jelly, 17 14 13 bytes

+13ḃ3Um0ị2/⁼/

Try it online! or verify all 27×27 cases.

How it works

+13ḃ3Um0ị2/⁼/  Main link. Argument: [f, g] (encoded as integers)

+13            Add 13 ([1, 1, 1] in base 3) to f and g.
   ḃ3          Convert f + 13 and g + 13 to bijective base 3.
               Bijective base 3 uses the digits 1 to 3 instead of 0 to 2.
               This yields [[f(2)+1, f(1)+1, f(0)+1], [g(2)+1, g(1)+1, g(0)+1]].
               The increments account for 1-based indexing.
     U         Reverse each digit array.
               This yields [[f(0)+1, f(1)+1, f(2)+1], [g(0)+1, g(1)+1, g(2)+1]].
      m0       Concatenate the list with a reversed copy of itself.
        ị2/    Split the result into pairs, and reduce each one by indexing.
               This computes g○f and f○g.
          ⁼/   Reduce by match; return 1 iff g○f = f○g.
share|improve this answer
    
I've copied your idea of verifying all test cases and displaying the matrix :-) – Luis Mendo Mar 24 at 22:33

MATL, 19 18 bytes

I:PII$YAZ{Y:)1Mw)=

Truthy is an array with all ones. Falsy is an array containing at least one zero.

Try it online! or verify all cases (takes a few seconds).

       % implicitly input an array of two numbers
I:P    % push [3 2 1]
I      % push 3
I$     % specify that the next function takes 3 inputs
YA     % convert input to base 3 with alphabet [3 2 1] and 3 digits. Gives 2x3 array
Z{     % convert into cell of two cells, one with each row
Y:     % split cell array. We have two arrays on the stack, one per function
)      % index operation to compute f ∘ g. Function composition is indexing
1M     % push the two arrays again
w      % swap the two arrays
)      % index operation to compute g ∘ f
=      % test for equality element-wise
       % implicitly display
share|improve this answer
    
I think usually only the empty list is considered falsy. – Timtech Mar 24 at 21:53
1  
@Timtech That depends on the language. In MATL, arrays that contains zeroes are falsy. – Dennis Mar 24 at 21:55
    
Okay, just checking... – Timtech Mar 24 at 22:05
    
@Timtech Sure! Here it is in more detail: An expression is true when its result is nonempty and contains only nonzero elements (logical or real numeric) – Luis Mendo Mar 24 at 22:08

Python 2, 61 bytes

lambda m,n:all(n/3**(m/i%3)%3==m/3**(n/i%3)%3for i in[1,3,9])

Given an input i, we can implement the function represented by n by doing n/3**i%3 to extract the ith ternary digit of n. The function checks that the same result is gotten for each of 0,1,2 when applying the functions in either order. Actually, since the first step is doing 3**, this tests with [1,3,9] instead.

The code reuse looks wasteful, but I didn't see a better way. Compare:

q=lambda x,i:x/3**i%3;lambda m,n:all(q(m,q(n,i))==q(n,q(m,i))for i in[0,1,2])
share|improve this answer

Mathematica, 77 bytes

Reverse[#][[#2+{1,1,1}]]==Reverse[#2][[#+{1,1,1}]]&@@IntegerDigits[{##},3,3]&

Mathematica's One-based indexing strikes again!

share|improve this answer
1  
Shorter to assign {1,1,1} to a variable and use that. – CalculatorFeline Mar 25 at 2:32

JavaScript (ES7), 68 bytes

(a,b)=>![0,1,2].some(n=>t(a,t(b,n))-t(b,t(a,n)),t=(a,n)=>a/3**n%3|0)

Unfortunately base 3 conversion was too expensive:

(a,b)=>[0,1,2].every(n=>a[b[n]]==b[a[n]],g=a=>(27+a).toString(3).slice(1),a=g(a),b=g(b))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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