A Programming Puzzle
June 28, 2013
Today’s exercise is a delightful little programming puzzle:
Write a function
fso thatf(f(n)) = -nfor all integers n.
When I first saw this puzzle, it took me two days before I had the necessary flash of inspiration, then about two minutes to write. Do yourself a favor and don’t peek at the suggested solution until you figure it out yourself.
Your task is to write function f as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Is there something wrong with the solution below, or is this cheating? It works for all integers.
def f(n): return n * 1j for n in range(-10, 10): assert f(f(n)) == -nNot nearly as elegant as Paul’s – but I was happy to have my own aha moment :)
def f(n): return 1.0/n if abs(float(n)) >= 1.0 else int(round(-1.0/n,0)) if n else 0[…] today’s Programming Praxis exercise, our goal is to write a function such that f (f n) = -n. Let’s […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/28/programming-praxis-a-programming-puzzle/ for a version with comments):
My Perl solution:
use strict;
# Write a function
# f
# so that
# f(f(n)) = -n
# for all integers n.
# f(0) = 0
# f(n odd and positive) = n + 1
# f(n odd and negative) = n – 1
# f(n even and positive) = -(n – 1) = -n + 1
# f(n even and negative) = -(n + 1) = -n – 1
sub f($);
sub sign($);
for my $n (-5 .. 5) {
print “$n => “, f($n), ” => “, f(f($n)), “\n”;
}
sub f($) {
my $n = shift;
return ($n % 2 ? 1 : -1) * $n + sign($n);
}
sub sign($) {
my $n = shift;
return $n 0;
}
Definitely cheeting, but the perl state variables are so tempting ;)
sub fun {
my $a = shift;
state $x = 0;
($x++ % 2) ? $a : -$a;
}
I didn’t get the above solution, which keeps the constraint that the domain and range of f are the integers.
However, without that implied constraint, there are some other solutions:
Allowing the domain/range of f to be real (floats): f could be given by “return n+0.5 if n is integer, else return – floor(n)”
Allowing the domain/range of f to be complex: f could be given by “return n*i”, where “i” denotes the imaginary value of sqrt(-1)
See: https://www.informatimago.com/articles/ffn=-n/index.html
Remember, the constraint is not to use more than 32-bits. If you change the type, then you must encode it into the 32-bit (don’t take advantage of the type-tag in dynamically typed programming languages).
Ruby solution with some unnecessary monkeypatching on the Fixnum class:
class Fixnum def sign if self == 0 0 elsif self > 0 1 else -1 end end end def f(n) if n.even? n.sign * (n.abs - 1) else -n.sign * (n.abs + 1) end end(define (f n)
(make-rectangular (imag-part n) (- (real-part n))))
def f(n):
return -abs(n)
DarkoP: f(f(1)) should return -1, and f(f(-1)) should return 1. Your function returns -1 for both.
My Rackety versions: A programming puzzle: f(f(n)) = -n on jverkamp.com
I coded up about four before checking out what was here and they’re all reasonably well covered. My favorites were the complex number version:
And the stateful version:
; Use a state variable (define f4 (let ([toggle (make-parameter #t)]) (lambda (n) (toggle (not (toggle))) (if (toggle) n (- n)))))@programmingpraxis: yeah, I misunderstood the problem obviously. Sorry about that, I’ll try better next time.
Javascript solution:
f=function(n){ return (n%2===0) ? (n+1)*-1 : n+1 };Slight adjustment, please ignore previous entry:
f=function(n){ if( n%2===0) { return ( n*-1)+n/Math.abs(n); } else {return n+n/Math.abs(n)}};What about the following scheme?
(define (f x)
(if (number? x)
(lambda () (- x))
(x)))
it does not always return a number, but I think it was not required.
def f(n):
return 0 if n == 0 else 1 – n if n % 2 == 0 else n + 1 if n > 0 else n – 1
I don’t know if what I did is valid or not, but it works:
Import math
def f (n)
y = n*n
y = math.sqrt (y)
If ((y/n) == -1)
return x
Else
return -x
@Lucas: It doesn’t work. In the first place, x is undefined; I assume you meant y. In the second place, y is always positive, so if n is negative the value returned from the “then” clause will be negative, and if n is positive the value returned from the “else” clause will be negative, so this will always return a negative number. Thus, if n is negative, f(f(n)) can never be positive.
(define (f n)
( if (number? n) (lambda() (- 0 n))
(n))
@Paul – your solution doesnt seem to be correct. We need f(f(n)= -n where as yours returns n. Or am i missing something.
My solution (C/C++ like)
static run = 0
int f(n)
{
run=1;
return (pow(-1,(run-1))*n);
}
static run = 0
int f(n)
{
run++;
return (pow(-1,(run-1))*n);
}
int f(int n){
return (int) Math.pow(-1, n) * n + (-1) * Integer.signum(n);
}
Thanks for the puzzle! I have a different solution;
f(f(n)) = -n for every interger so I set where n the – n so that f(f(-n)) = n but -n = f(f(n)). Therefore:
f(f(n)) = -n f(f(f(f(n)))) = n
oh and the function: :P
int f(n) {
return n;
}
Could anybody inform me if its anywhere near to accepted :-P
f(n){
if(n is positive)
n=n*-1;
else
n=n*1;
return n;
}
int func(int n) { return (n)?pow(-1,abs(n))*n+(-1*n/abs(n)):0; }Matlab:
function y = f(n)
if size(n)==1
y(1)=-n;
y(2)=n;
else
y=n(1);
end
in bc unix command line :
define f(n)
{
return -1^(2*n – 1 ) * abs(1-n)
}
where abs is defines as:
define abs(n)
{
if(n>=0) return(n)
return(-n)
}
i just realized that this solution will not work for zero and down below :(
Is this a valid solution? (c/c++) It works, and is likely how I would code it if I really needed something that did this in the real world.
int t=0;
int f(int n) {
if (t==0) {
++t;
return n*-1;
} else {
t=0;
return n;
}
}
I was able to figure out a marginally simpler solution. And also the sourcecode feature.
bool t=true; int f(int n) { if (t) { t=!t; return n*-1; } t=true; return n; }My java solution :)
public static Integer function(Integer n) {
Integer moduloTwo=n % 2;
Boolean evenNumber=null;
evenNumber = moduloTwo==0 ? true: false;
Boolean positive=n>=0? true : false;
//add this number to close the number to Zero
Integer closerToZero=positive ? -1: 1;
if (evenNumber) return n+closerToZero;
else return -n+closerToZero;
}
My solution wasn’t nearly as elegant as a few of the others. I stashed the integer in a list.
(define (f1 n) (if (list? n) (- (car n)) (list n)))I used Clojure, which is a newer dialect of Lisp.
(defn f [n]
(if (fn? n)
(n)
(fn [] (- n)) ))
Explanation: Line 2 tests if the argument is a function. If true, the func is invoked (sans arguments) on Line3. Else (on Line4) we return a function that is a closure over n.
One can try this out at the Clojure REPL at http://tryclj.com.
> (f 5)
#
> (f (f 5))
-5
> (f (f 6))
-6
Is as simple as this:
int f( int n ) { return (n>0)?-n:n;}
or
int f( int n ) { return – abs(n); }
oops!
In python… not mathematical at all!
def f(n): if isinstance(n, int): return str(n) if isinstance(n, str): return -int(n) print f(f(3)) >>>-3 print f(f(-6)) >>>6Another possible python solution:
def f(n):
try:
return n()
except:
if n <= 0:
return n
else:
return -n
for n in xrange(-100,100):
print f(f(n))
call = -1
def f(x):
global call
call = call + 1
return ((-1)**call ) *x
doesn’t this solve the issue? (Ruby)
NVM, misread the instructions
this works too, and its one method call simpler
@George: where in the spec did it say the calls to f(1), f(2), etc. would be made in that order?