LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 June 7 2013

Joe
Member

[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.

Offline

#2 June 7 2013

arithma
Member

Re: [Exercise] a function composition question

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

Offline

#3 June 7 2013

Joe
Member

Re: [Exercise] a function composition question

Nope!

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

Offline

#4 June 7 2013

xterm
Moderator

Re: [Exercise] a function composition question

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.

Offline

#5 June 7 2013

Mr. Anderson
Member

Re: [Exercise] a function composition question

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

Last edited by Mr. Anderson (June 7 2013)

Offline

#6 June 7 2013

Joe
Member

Re: [Exercise] a function composition question

Please note that n should be a positive integer

That doesn't answer the question then!

Offline

#7 June 7 2013

Joe
Member

Re: [Exercise] a function composition question

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)

Offline

#8 June 7 2013

Ayman
Member

Re: [Exercise] a function composition question

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.

Offline

#9 June 7 2013

Mr. Anderson
Member

Re: [Exercise] a function composition question

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

Offline

#10 June 7 2013

Mr. Anderson
Member

Re: [Exercise] a function composition question

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

Offline

#11 June 7 2013

arithma
Member

Re: [Exercise] a function composition question

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

Last edited by arithma (June 7 2013)

Offline

#12 June 7 2013

Joe
Member

Re: [Exercise] a function composition question

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

Offline

#13 June 7 2013

arithma
Member

Re: [Exercise] a function composition question

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

Offline

#14 June 7 2013

m0ei
Member

Re: [Exercise] a function composition question

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.

Last edited by m0ei (June 7 2013)

Offline

#15 June 7 2013

arithma
Member

Re: [Exercise] a function composition question

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

Offline

#16 June 7 2013

rolf
Member

Re: [Exercise] a function composition question

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?

Last edited by rolf (June 7 2013)

Offline

#17 June 7 2013

arithma
Member

Re: [Exercise] a function composition question

@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

Offline

#18 June 9 2013

Ra8
Member

Re: [Exercise] a function composition question

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

Offline

#19 June 10 2013

arithma
Member

Re: [Exercise] a function composition question

Ra8 wrote:

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 wins!

Offline

#20 June 13 2013

arithma
Member

Re: [Exercise] a function composition question

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

Offline

#21 June 25 2013

raja
Member

Re: [Exercise] a function composition question

This one is meant in jest. It works 50% of the time. The question is, using probabilistic methods, is it possible to do better than 50%?

import random

def f(n):
    return n * random.choice((-1,1))

Last edited by raja (June 25 2013)

Offline

#22 June 25 2013

arithma
Member

Re: [Exercise] a function composition question

raja wrote:

This one is meant in jest. It works 50% of the time. The question is, using probabilistic methods, is it possible to do better than 50%?

import random

def f(n):
    return n * random.choice((-1,1))

Define "probabilistic method".
In particular, if we attach to any of the deterministic methods an unused "random generation" statement, does it turn them probabilistic.

Offline

#23 June 25 2013

raja
Member

Re: [Exercise] a function composition question

Hmmm, well I'd say a good way to think about it would be, don't use any if/switch/etc... statements whose outcomes are deterministic(I'm not going for a definition of "probabilistic" or anything, just was wondering if a similar approach to the code above could be right more than 50% of the time, kinda thinking out loud).

Last edited by raja (June 25 2013)

Offline

#24 June 25 2013

raja
Member

Re: [Exercise] a function composition question

PS: Here is a simpler version(no recursion) of Arithma's solution:

def f(n):
    offset = 1 if n > 0 else (-1 if n != 0 else 0)
    if n % 2 == 1:
        return n + offset
    else:
        return - (n-offset)

Result:

>>> for i in range(-10, 11):
...  print i, "=>", f(f(i))
... 
-10 => 10
-9 => 9
-8 => 8
-7 => 7
-6 => 6
-5 => 5
-4 => 4
-3 => 3
-2 => 2
-1 => 1
0 => 0
1 => -1
2 => -2
3 => -3
4 => -4
5 => -5
6 => -6
7 => -7
8 => -8
9 => -9
10 => -10
>>> 

Offline

#25 April 1 2014

NuclearVision
Member

Re: [Exercise] a function composition question

I don't think the function involve even numbers.

Last edited by NuclearVision (April 1 2014)

Offline

Board footer