You are not logged in.
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
Last edited by Mr. Anderson (June 7 2013)
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
Last edited by arithma (June 7 2013)
@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.
Last edited by m0ei (June 7 2013)
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?
Last edited by rolf (June 7 2013)
@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
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;
}
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!
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;
}
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)
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.
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)
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
>>>
I don't think the function involve even numbers.
Last edited by NuclearVision (April 1 2014)