## A Programming Puzzle

### June 28, 2013

Today’s exercise is a delightful little programming puzzle:

Write a function

`f`

so that`f(f(n)) = -n`

for all integersn.

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.

Advertisements

Pages: 1 2

Is there something wrong with the solution below, or is this cheating? It works for all integers.

Not nearly as elegant as Paul’s – but I was happy to have my own aha moment :)

[…] 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:

(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:

@programmingpraxis: yeah, I misunderstood the problem obviously. Sorry about that, I’ll try better next time.

Javascript solution:

Slight adjustment, please ignore previous entry:

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;

}

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.

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.

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!

Another 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?