• Coding
  • [Exercise] a function composition question

Here's a nice little mind bender where you could find more than one solution. Here's the exercise:

Write a function f such as:
f(f(n)) == -n
And let's start off by eliminating the obvious answer, by stating that both n and f(n) are integers, excluding the possibility of using imaginary/complex numbers.
f(n) = {
   if(n % 2 == 0) return  -n/2;
   else return n*2;
}
Nope!
>>> def f(n):
...     if n%2 ==0: return -n/2
...     return n*2
...
>>> f(f(5))
-5
>>> f(f(4))
1
Is cheating allowed?
def f(n):
    if hasattr(f, 'buff'):
        if n in f.buff:
            f.buff[n] = -f.buff[n]
        else:
            f.buff[n] = n
        return f.buff[n]
    else:
        f.buff = {}
        f.buff[n] = n
        return n

assert f(f(5)) == -5
assert f(f(-5)) == 5
P.S.: Was buggy, fixed.
f(n) = {
    if (n<0)
        return n*2 
    else
    {
       if(n % 2 == 0) return  -n/2;
       else return n*2;
    }
}
Please note that n should be a positive integer
Please note that n should be a positive integer
That doesn't answer the question then!
xterm's solution achieves it by keeping state in the function (most languages would allow you to do that). Here's a simpler one that achieves it by playing with the argument's type:
def f(n):
    if isinstance(n, int):
        return str(-n)
    return int(n)
def f(n):
   if "f_res" in globals():
      globals()["f_res"]  *= -1
   else:
      globals()["f_res"] = n
       
   return globals()["f_res"]
Naive solution but works as long as there something else doesn't interfere with the f_res global and fuck it up.
as Xterm said, is this cheating?
because i thought we couldn't use those tricks.
rahmu, you wasted some precious minutes of my time :)
Your post is misleading when using "mind bender".
Oops!
No cheating:
def f(n):
    if n == 0: return 0
    if n < 0: return -f((-n))
    if n > 0:
        if n % 2 == 1: return n+1
        else: return -(n-1)

for n in range(-10,10):
    print "n: ", n, "\tf(n): ", f(n), "\tf(f(n)): ", f(f(n))
EDITS: Better code organization
@arithma you beat me to it!

I followed your idea of separating odd numbers from even ones and here's what I got:
def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n+1
        else: 
            return -1 * (n-1)
    else:
        if n % 2 == 1:
            return n-1
        else:
            return  -1 * (n+1)
Yours looks neater though!

@Mr. Anderson: sorry I wasted "precious minutes of [your] time".
This is an interesting question, and solutions can run wild.
A clue: prime numbers?
def f(n):
    if isinstance(n, type(lambda: None)):
        return n()
    else:
        return (lambda: -n)
The function returns a lambda that returns -n.

Edit:
Useless to check if n is a lambda, I could simply check if it's an int.
def f(n):
    if isinstance(n, int):
        return (lambda: -n)
    else:
        return n()

Just payed attention to Rahmu's solution, I guess mine is similar to his.
This one out of the bus on the way home:
def factors2(x):
    n = 0
    while x%2==0:
        x /= 2
        n += 1
    return n

def f(n):
    if n==0: return 0
    if n<0: return -(f(-n))
    if n>0:
        if n%2==1:
            return 2*n
        else:
            if(factors2(n)%2==0):
                return 2*n
            else:
                return -n/2

for n in range(0,10):
    print "n: ", n, "\tf(n): ", f(n), "\tf(f(n)): ", f(f(n)), "\tf(f(f(n))): ", f(f(f(n)))
This is impossible.
The outer function would need to know what happened inside the inner function. We cannot embed this information inside the number without modifying the number, or without using tricks such as global variables...

Edit: uh wait, there is a mathematical solution?
@rolf: I am assuming that f is a function from an integer to an integer in the mathematical/pure sense. That is to say that running f on an int on some disconnected computer, taking the integer output and passing it through another computer with the same algorithm should make absolutely no difference.
An easy solution is to map positive normal numbers into a series of ones (ie 5 to 11111). Then a series of ones to negative that number. A negative normal number to a a series of ones with a negative sign. And a series of ones with a negative sign to positive normal numbers.
def f(n):
    if n == 0: return 0
    if n > 0:
        if str(n).replace("1", "") == "":
            return -len(str(n))
        else:
            return int("1"*n)
    else:
        if str(-n).replace("1", "") == "":
            return len(str(-n))
        else:
            return -int("1"*(-n))

for n in range(0,10):
    print n, "\t\t", f(n), "\t\t", f(f(n)), "\t\t", f(f(f(n)))
Which outputs:
0 		0 		0 		0
1 		-1 		1 		-1
2 		11 		-2 		-11
3 		111 		-3 		-111
4 		1111 		-4 		-1111
5 		11111 		-5 		-11111
6 		111111 		-6 		-111111
7 		1111111 		-7 		-1111111
8 		11111111 		-8 		-11111111
9 		111111111 		-9 		-111111111
It works except for 1, because it's confused for a series of 1 of length one. Luckily, all other digits other than one work.
def f(n):
    if n == 0: return 0
    if n > 0:
        if str(n).replace("2", "") == "":
            return -len(str(n))
        else:
            return int("2"*n)
    else:
        if str(-n).replace("2", "") == "":
            return len(str(-n))
        else:
            return -int("2"*(-n))

for n in range(0,10):
    print n, "\t\t", f(n), "\t\t", f(f(n)), "\t\t", f(f(f(n)))
NOTHING IS IMPOSSIBLE :D
I took advantage of overflow:
int f(int x)
{
    int v= (1<<31)-1;
    int abs=max(x,-x);
    if(abs<v/2)
        return v+x+1;
    else
        return v-x+1;
}
Ra8 wroteI took advantage of overflow:
int f(int x)
{
    int v= (1<<31)-1;
    int abs=max(x,-x);
    if(abs<v/2)
        return v+x+1;
    else
        return v-x+1;
}
Ra8 wins!
Here's a bit of bit play I was intending to do from a while ago. All the bit mangling made it more difficult.
#include <iostream>
#include <assert.h>
using namespace std;

uint f(uint n){
    uint v = 1U<<30;
    return n+v;
}

uint fwd(int n){
    if(abs(n)<(1<<30)){
        if(n<0)
            return abs(n)+(2<<30); //quad 2
        else
            return n; //quad 0
    }
    else{
        if(n<0)
            return abs(n)|(3<<30); //quad 3
        else
            return n; // quad 1
    }
}

int rvr(uint n){
    uint s = n>>30;
    if(s == 0){
        return n;
    }
    if(s == 1){
        return n;
    }
    if(s == 2){
        return -(n&((~0U)>>2));
    }
    if(s == 3){
        return -((n&((~0U)>>2))|(1<<30));
    }
    assert(0);
    return 0;
}

int next(int n){
    uint m = fwd(n);
    m = f(m);
    return rvr(m);
}

int main()
{
    int x = 501;
//    cout << hex;
    cout << x << endl;
    x = next(x);
    cout << x << endl;
    x = next(x);
    cout << x << endl;
    x = next(x);
    cout << x << endl;
    x = next(x);
    cout << x << endl;
    return 0;
}