Programming Praxis

A Programming Puzzle

June 28, 2013 9:00 AM

Today’s exercise is a delightful little programming puzzle:

Write a function f so that f(f(n)) = -n for 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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

45 Responses to “A Programming Puzzle”

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)) == -n
```
By Paul on June 28, 2013 at 9:23 AM
Not 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
```
By George on June 28, 2013 at 9:45 AM
[…] today’s Programming Praxis exercise, our goal is to write a function such that f (f n) = -n. Let’s […]

By Programming Praxis – A Programming Puzzle | Bonsai Code on June 28, 2013 at 11:40 AM
My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/28/programming-praxis-a-programming-puzzle/ for a version with comments):
```
f :: Integer -> Integer
f n = n * (2 * mod n 2 - 1) + signum n
```
By Remco Niemeijer on June 28, 2013 at 11:40 AM
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;
}

By mvaneerde on June 28, 2013 at 12:00 PM
Definitely cheeting, but the perl state variables are so tempting ;)
sub fun { my $a = shift; state $x = 0; ($x++ % 2) ? $a : -$a; }

By shtipki on June 28, 2013 at 12:52 PM
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)

By ye on June 28, 2013 at 2:08 PM
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).

By Pascal Bourguignon on June 28, 2013 at 6:29 PM

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

By magni- on June 29, 2013 at 1:11 PM

(define (f n)
(make-rectangular (imag-part n) (- (real-part n))))

By me on June 29, 2013 at 2:09 PM
def f(n):
return -abs(n)

By DarkoP on June 29, 2013 at 6:14 PM
DarkoP: f(f(1)) should return -1, and f(f(-1)) should return 1. Your function returns -1 for both.

By programmingpraxis on June 29, 2013 at 7:52 PM
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:
```
; Rotate in the complex numbers
(define (f1 n)
  (* n 0+1i))
```
And the stateful version:
```
; Use a state variable
(define f4
  (let ([toggle (make-parameter #t)])
    (lambda (n)
      (toggle (not (toggle)))
      (if (toggle) n (- n)))))
```
By JP on June 29, 2013 at 7:57 PM
@programmingpraxis: yeah, I misunderstood the problem obviously. Sorry about that, I’ll try better next time.

By DarkoP on June 29, 2013 at 8:19 PM
Javascript solution:
```
f=function(n){ return (n%2===0) ? (n+1)*-1 : n+1 };
```
By Tom Scheper (@csstom) on June 30, 2013 at 8:56 AM
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)}};
```
By Tom Scheper (@csstom) on June 30, 2013 at 10:28 AM
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.

By Lorenzo on July 1, 2013 at 7:33 AM
def f(n):
return 0 if n == 0 else 1 – n if n % 2 == 0 else n + 1 if n > 0 else n – 1

By Anonymous on July 1, 2013 at 2:06 PM
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

By Lucas on July 4, 2013 at 12:57 PM
@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.

By programmingpraxis on July 4, 2013 at 1:08 PM
(define (f n)
( if (number? n) (lambda() (- 0 n))
(n))

By Sergey on July 4, 2013 at 4:44 PM
@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);
}

By ad on July 5, 2013 at 12:46 PM
static run = 0
int f(n)
{
run++;
return (pow(-1,(run-1))*n);
}

By ajitd on July 5, 2013 at 12:47 PM
int f(int n){
return (int) Math.pow(-1, n) * n + (-1) * Integer.signum(n);
}

By wngcsk on July 5, 2013 at 5:52 PM
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

By Jeremy Loons on July 6, 2013 at 3:03 PM
f(n){
if(n is positive)
n=n*-1;
else
n=n*1;
return n;
}

By ravee chauhan on July 8, 2013 at 11:24 AM

int func(int n)
{
return (n)?pow(-1,abs(n))*n+(-1*n/abs(n)):0;
}

By novatech on July 8, 2013 at 5:16 PM

Matlab:

function y = f(n)
if size(n)==1
y(1)=-n;
y(2)=n;
else
y=n(1);
end

By Joe on July 9, 2013 at 1:10 PM
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)
}

By et on July 9, 2013 at 11:55 PM
i just realized that this solution will not work for zero and down below :(

By et on July 10, 2013 at 12:19 AM
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;
}
}

By DGriffin on July 10, 2013 at 2:42 AM
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;
}
```
By DGriffin on July 10, 2013 at 3:02 AM
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;
}

By gabriell on July 14, 2013 at 11:26 AM
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)))
```
By fisherro on July 15, 2013 at 8:01 PM
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

By Vish K on July 25, 2013 at 8:54 PM
Is as simple as this:

int f( int n ) { return (n>0)?-n:n;}

or

int f( int n ) { return – abs(n); }

By Fera on August 6, 2013 at 11:45 AM
oops!

By Fera on August 6, 2013 at 11:47 AM

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

By Sam on August 6, 2013 at 11:14 PM

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

By Josh on September 20, 2013 at 1:09 PM
call = -1
def f(x):
global call
call = call + 1
return ((-1)**call ) *x

By said on October 10, 2013 at 12:12 AM
doesn’t this solve the issue? (Ruby)
```
def f (n)
  n < 0 ? n : - n
end
```
By George on January 23, 2014 at 2:11 AM
NVM, misread the instructions

By George on January 23, 2014 at 2:15 AM

def f(n)
  #my version of a ruby static method variable (similar to C++ static function variables)
  $count = $count.nil? ? 0 : ($count + 1)
  return -n if $count.even? || $count == 0
  n
end

By George on January 23, 2014 at 3:16 AM

this works too, and its one method call simpler

def f(n)
  #my version of a ruby static method variable (similar to C++ static function variables)
  $count = $count.nil? ? 0 : ($count + 1)
  return -n if $count.odd?
  n
end

By George on January 23, 2014 at 7:22 PM

@George: where in the spec did it say the calls to f(1), f(2), etc. would be made in that order?

By mvaneerde on January 23, 2014 at 8:35 PM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

A Programming Puzzle

Share this:

Related

45 Responses to “A Programming Puzzle”

Leave a Reply