[Exercise] a function composition question

Joe

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.

arithma

f(n) = {
   if(n % 2 == 0) return  -n/2;
   else return n*2;
}

Joe

Nope!

>>> def f(n):
...     if n%2 ==0: return -n/2
...     return n*2
...
>>> f(f(5))
-5
>>> f(f(4))
1

xterm

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.

mr-anderson

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

Joe

Please note that n should be a positive integer

That doesn't answer the question then!

Joe

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)

Ayman

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.

mr-anderson

as Xterm said, is this cheating?
because i thought we couldn't use those tricks.

mr-anderson

rahmu, you wasted some precious minutes of my time :)
Your post is misleading when using "mind bender".

arithma

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

Joe

@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".

arithma

This is an interesting question, and solutions can run wild.
A clue: prime numbers?

m0ei

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.

arithma

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

rolf

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?

arithma

@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

Ra8

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;
}

arithma

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!

arithma

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;
}