1
$\begingroup$

I am given the following function as a brain teaser:

def t(x, y, z):
    if x <= z:
        return y
    else:
        return t(t(x  - 1 , y  , z ) , t(y  - 1 , z  , x ) , t (z  - 1 , x  , y ))

the task is to remove the recursion in the else-branch. the only allowed expressions are of type arithmetic (+,-,*,/,%), logical (&&,||,!), relational (<,<=,==,>=,>,!=) and if-else.

My first approach was to order the input in lexicographical order and trying to deduce a relationship which seemed to look like like this initially:

else:
    if y > x
        return x
    else:
        return z

but that does not work, a counterexample is t(20, 7, 18)=8. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '>'-relation between the variables but I did not get far with that either.

$\endgroup$
2
$\begingroup$

Here is an equivalent way to calculate $t(x,y,z)$.

We distinguish between three cases:

  1. $x \leq z$: the answer is $y$.

  2. $x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise.

  3. $x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise.

You should be able to prove this characterization by induction. The second case is identical to the third case, except that the condition $y \leq x$ is replaced by the condition $y \leq x+1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yes thats it, thanks! tbh, I don't even know how to approach multidimensional induction (I was not even sure if it is applicable to this question), but I will try to figure it out by reading some sources. How long did it take you to get to the solution? $\endgroup$ – Doflaminhgo Nov 19 '19 at 9:58
  • 1
    $\begingroup$ It took about an hour. I looked at the sequences $t(x,0,z),t(x,1,z),\ldots$ for various small values of $x,z$, and the pattern was obvious. $\endgroup$ – Yuval Filmus Nov 19 '19 at 11:28
  • $\begingroup$ okay, based on your last comment I managed to find a slightly more verbose solution compared to yours, which should be equivalent (no min-function, but more if-elses). I honestly don't see how it's obvious though, it took me a couple hours and I probably could not even have done it, if I didn't glance at your solution beforehand (the odd-even-relations were difficult for me to spot). So thanks again! $\endgroup$ – Doflaminhgo Nov 19 '19 at 22:06

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.