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

About these ads

Pages: 1 2

45 Responses to “A Programming Puzzle”

  1. Paul said

    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
    
  2. George said

    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
    
  3. […] today’s Programming Praxis exercise, our goal is to write a function such that f (f n) = -n. Let’s […]

  4. 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
    
  5. mvaneerde said

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

  6. shtipki said

    Definitely cheeting, but the perl state variables are so tempting ;)

    sub fun {
    my $a = shift;
    state $x = 0;
    ($x++ % 2) ? $a : -$a;
    }

  7. ye said

    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)

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

  9. magni- said

    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
    
  10. me said

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

  11. DarkoP said

    def f(n):
    return -abs(n)

  12. programmingpraxis said

    DarkoP: f(f(1)) should return -1, and f(f(-1)) should return 1. Your function returns -1 for both.

  13. JP said

    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)))))
    
  14. DarkoP said

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

  15. Javascript solution:

    f=function(n){ return (n%2===0) ? (n+1)*-1 : n+1 };
  16. 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)}};
  17. Lorenzo said

    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.

  18. Anonymous said

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

  19. Lucas said

    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

  20. programmingpraxis said

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

  21. Sergey said

    (define (f n)
    ( if (number? n) (lambda() (- 0 n))
    (n))

  22. ad said

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

  23. ajitd said

    static run = 0
    int f(n)
    {
    run++;
    return (pow(-1,(run-1))*n);
    }

  24. wngcsk said

    int f(int n){
    return (int) Math.pow(-1, n) * n + (-1) * Integer.signum(n);
    }

  25. Jeremy Loons said

    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

  26. ravee chauhan said

    f(n){
    if(n is positive)
    n=n*-1;
    else
    n=n*1;
    return n;
    }

  27. novatech said
    int func(int n)
    {
    return (n)?pow(-1,abs(n))*n+(-1*n/abs(n)):0;
    }
    
  28. Joe said

    Matlab:

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

  29. et said

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

  30. et said

    i just realized that this solution will not work for zero and down below :(

  31. DGriffin said

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

  32. DGriffin said

    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;
    }
    
  33. gabriell said

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

  34. fisherro said

    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)))
    
  35. Vish K said

    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

  36. Fera said

    Is as simple as this:

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

    or

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

  37. Sam said

    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
    
  38. Josh said

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

  39. said said

    call = -1
    def f(x):
    global call
    call = call + 1
    return ((-1)**call ) *x

  40. George said

    doesn’t this solve the issue? (Ruby)

    def f (n)
      n < 0 ? n : - n
    end
    
  41. George said

    NVM, misread the instructions

  42. George said
    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
    
  43. George said

    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
    
  44. mvaneerde said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: