18
\$\begingroup\$

The TAK function is defined as follows for integers \$x\$, \$y\$, \$z\$:

$$ t(x, y, z) = \begin{cases} y, & \text{if $x \le y$} \\ t(t(x-1,y,z), t(y-1,z,x), t(z-1,x,y)), & \text{otherwise} \end{cases} $$

Since it can be proved that it always terminates and evaluates to the simple function below,

$$ t(x, y, z) = \begin{cases} y, & \text{if $x \le y$} \\ z, & \text{if $x > y$ and $y \le z$} \\ x, & \text{otherwise} \end{cases} $$

your job is not to just implement the function, but count the number of calls to \$t\$ when initially called with the given values of \$x\$, \$y\$, and \$z\$. (As per the standard rules, you don't need to implement \$t\$ if there is a formula for this value.)

You may assume that the three input values are nonnegative integers.

Note that the task is slightly different from the definition of the function \$T\$ (the number of "otherwise" branches taken) on the Mathworld page.

Standard rules apply. The shortest code in bytes wins.

Test cases

(x, y, z) -> output

(0, 0, 1) -> 1
(1, 0, 2) -> 5
(2, 0, 3) -> 17
(3, 0, 4) -> 57
(4, 0, 5) -> 213
(5, 0, 6) -> 893

(1, 0, 0) -> 5
(2, 0, 0) -> 9
(2, 1, 0) -> 9
(3, 0, 0) -> 13
(3, 1, 0) -> 29
(3, 2, 0) -> 17
(4, 0, 0) -> 17
(4, 1, 0) -> 89
(4, 2, 0) -> 53
(4, 3, 0) -> 57
(5, 0, 0) -> 21
(5, 1, 0) -> 305
(5, 2, 0) -> 149
(5, 3, 0) -> 209
(5, 4, 0) -> 213

Python implementation was used to generate the test cases.

\$\endgroup\$
1
  • \$\begingroup\$ So far I've noticed that (using this question's definition of T rather than that of the linked article) T(x+1,y+1,z+1)=T(x,y,z) and also T(x,y,z)=T(y,z,x) if x>y and y>>z, but I haven't been able to come up with anything more general. \$\endgroup\$
    – Neil
    Commented Jan 27 at 8:35

7 Answers 7

6
\$\begingroup\$

JavaScript (ES6), 73 bytes

Using a single recursive function

Expects (x, y, z).

f=(x,y,z,w)=>x>(r=y)?f(x-1,y,z)+f(y-1,z,x,w=r)+f(z-1,x,y,z=r)-~f(w,z,r):1

Try it online!

Commented

f = (                     // f is a recursive function taking:
  x, y, z,                //   (x, y, z) = input integers
  w                       //   w = local variable
) =>                      //
x > (r = y) ?             // save y in the global r; if x is greater than y:
  f(x - 1, y, z) +        //   process the 1st recursive call
  f(y - 1, z, x, w = r) + //   save r in w and process the 2nd recursive call
  f(z - 1, x, y, z = r) - //   save r in z and process the 3rd recursive call
  ~f(w, z, r)             //   last recursive call, using the previous results
                          //   add all returned values together, and add 1
:                         // else:
  1                       //   stop and return 1

JavaScript (ES6), 76 bytes

Using a wrapper function

Expects [x, y, z].

Simply does exactly what is said on the tin.

a=>(r=0,(t=(x,y,z)=>++r&&x>y?t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)):y)(...a),r)

Try it online!

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

Jelly, (22?) 26 bytes

ṙJ_JỊ$ṙ-Ñ€Ñ
‘ɼṛṖṪÇ}ṢƑ?
Çṛ®

A full program that accepts a list of three non-negative integers, [x, y, z], and prints the call count. (Or 22 bytes as a monadic Link that accepts the same and accumulates in the register (?) - remove the last line.)

Try it online! or see the test suite.

How?

There's probably a clever way to produce the count, but this implements the description from the question.

ṙJ_JỊ$ṙ-Ñ€Ñ - Link 1: [x, y, z]
 J          - indices {[x, y, z]} -> [1, 2, 3]
ṙ           - {[x, y, z]} rotate left by -> [[y, z, x], [z, x, y], [x, y, z]]
     $      - last two links as a monad - f([x, y, z]):
   J        -   indices {[x, y, z]} -> [1, 2, 3]
    Ị       -   insignificant?      -> [1, 0, 0]
  _         - subtract     -> [[y-1, z, x], [z-1, x, y], [x-1, y, z]]
      ṙ-    - rotate right -> [[x-1, y, z], [y-1, z, x], [z-1, x, y]]
        р  - call Link 2 for each
          Ñ - call link 2
           - 

‘ɼṛṖṪÇ}ṢƑ? - Link 2, t: [x, y, z]
 ɼ         - apply to the register and yield:
‘          -   increment
   Ṗ       - pop {[x, y, z]} -> [x, y]
  ṛ        - right argument -> [x,y]
         ? - if...
        Ƒ  - ...condition: is {[x, y]} invariant under?:
       Ṣ   -                 sort
    Ṫ      - ...then: tail -> y
     Ç}    - ...else: call Link 1 as a monad - f(x, y, z)

Çṛ® - Main Link: [x, y, z]
Ç   - call Link 2 as a monad - t(x, y, z)
  ® - recall from the register -> count
 ṛ  - right argument -> count
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Ñ calls link 2 from link 1, doesn't it? \$\endgroup\$
    – Neil
    Commented Jan 26 at 2:22
  • \$\begingroup\$ Corrected, thanks! \$\endgroup\$ Commented Jan 26 at 2:48
  • 1
    \$\begingroup\$ I don’t think the 22 is valid. It seems akin to storing the result in a variable, and also the monadic link is not reusable since it doesn’t initialise the register. Overall good solution though \$\endgroup\$ Commented Jan 26 at 7:37
3
\$\begingroup\$

Perl 5 -Mfeature+signatures -ap, 83 bytes

sub f($x,$y,$z){++$;;$y<$x?f(f($x-1,$y,$z),f($y-1,$z,$x),f($z-1,$x,$y)):$y}f@F;$_=$

Try it online!

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

Python 2, 103 bytes

def t(x,y,z):t.c+=1;return t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y))if x>y else y
t.c=0
t(*input())
print t.c

Attempt This Online!

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

Charcoal, 116 bytes

≔⦃⦄θ⊞υE³NFυ«≔I⪫()⪫ι,ηF¬§θη¿‹§ι¹§ι⁰«≔EιEι⁻§ι⁺μξ¬ξζ⊞ζEζ§λ∨¬‹§λ¹§λ⁰⊗¬‹§λ²§λ¹≔Eζ§θI⪫()⪫λ,ε¿⬤ελ§≔θη⊕ΣεF⊞Oζι⊞υ뻧≔θη¹»I§θη

Attempt This Online! Link is to verbose version of code. Explanation: Charcoal isn't really suited for this.

≔⦃⦄θ

Start with an empty dictionary which will hold T(x, y, z) for each required tuple.

⊞υE³N

Start with the input tuple.

Fυ«

Loop over the required tuples as they are found.

≔I⪫()⪫ι,η

Convert the tuples from a list to a Python tuple so that they can be used as a dictionary key.

F¬§θη

Test to see whether this tuple's T value is already known.

¿‹§ι¹§ι⁰«

Test to see whether this is a trivial tuple.

≔EιEι⁻§ι⁺μξ¬ξζ

Generate the dependent tuples, (x-1, y, z), (y-1, z, x) and (z-1, x, y).

⊞ζEζ§λ∨¬‹§λ¹§λ⁰⊗¬‹§λ²§λ¹

Also generate the fourth tuple by calculating t for each of these tuples nonrecursively.

≔Eζ§θI⪫()⪫λ,ε

Get any T values we have for these tuples already.

¿⬤ελ

If all of these tuples already have T values, then...

§≔θη⊕Σε

... take the sum and set this as the T value for the required tuple.

F⊞Oζι⊞υλ

Otherwise push all of the tuples to the list for reprocessing because it's simpler that way.

»§≔θη¹

If this is a trivial tuple then just set its T value to 1.

»I§θη

Output the T value of the input tuple.

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

05AB1E, 30 bytes

"¼Â¦`@iÅsë2Ý._εć<š®.V}®.V"©.V¾

Input as a triplet \$[x,y,z]\$.

Try it online or verify all test cases.

Explanation:

"..."        # Push the recursive string explained below
     ©       # Store it in variable `®` (without popping)
      .V     # Pop and evaluate it as 05AB1E code
        ¾    # Push counter variable `¾`
             # (which is output implicitly as result)

¼            # Increase the counter variable `¾` by 1 (starts at 0 by default)
            # Bifurcate the current triplet; short for Duplicate & Reverse copy
             # (which will use the implicit input-triplet in the first iteration)
 ¦           # Remove the first item of the reversed triplet (the z)
  `          # Pop and push y and x separated to the stack
   @i        # Pop both, and if x>=y:
     Ås      #  Pop the triplet, and push its middle: y
    ë        # Else:
     2Ý      #  Push list [0,1,2]
       ._    #  Rotate the triplet that many times towards the left: [[x,y,z],[y,z,x],[z,x,y]]
     ε       #  Map over each rotated triplet:
      ć      #   Extract its head; push remainder-pair and first item separately
       <     #   Decrease this first item by 1
        š    #   Prepend it back to the pair
         ®.V #   Do a recursive call by evaluating string `®`
     }®.V    #  After the map: do a recursive call on the resulting triplet as well
\$\endgroup\$
0
\$\begingroup\$

AWK, 82 bytes

func t(x,y,z){$0=++c;return x>y?t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)):y}t($1,$2,$3)1

Attempt This Online!

\$\endgroup\$

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.