Define a function f such that f(f(n)) = -n for all non-zero integers n

43

7

This challenge was inspired by a programming blog I frequent. Please see the original post here: A Programming Puzzle


Challenge

Define a function f:Q->Q such that f(f(n)) = -n for all non-zero integers n, and whereQ is the set of rational numbers.

Details

In whatever language you prefer, please define one function or program f that accepts as parameter one number n and returns or outputs one number f(n).

Input may be provided through whichever mechanism is most natural for your language: function argument, read from STDIN, command-line argument, stack position, voice input, gang signs, etc.

Output should be a return value from a function/program or printed to STDOUT.

I would like to restrict answers to functions that do not take advantage of program state or global memory/data that is visible from outside of the function f. For example, keeping a counter outside of f that counts how many times f was called and just doing a negation based on this count isn't very challenging or interesting for anyone. The decisions f makes should rely only on data within f's lexical scope.

However, this restriction is probably inappropriate for some stack-oriented languages or other types of languages that do not distinguish these types of data or scopes. Please use your best judgement to keep with the spirit of this challenge.


Scoring

Common code golf rules apply- your score is the number of bytes in your source code.

The minimal answer requires the domain and codomain of f to be a subset of the rationals Q. If you restrict your domain and codomain of f to the integers Z, then your score is the ceiling of 90% of the number of bytes in your source code.

Tiebreak

In the event of a tie, the following will be used in order:

  1. Fewest number of printable non-whitespace symbols in your source code
  2. Earliest date and time of answer submission

Edit

You are not required to support arbitrarily sized numbers. Please interpret the sets Z and Q as datatypes in your chosen language (typically integer and floating point, respectively).

If your solution relies entirely on the underlying structure or bit pattern of a data type, please describe its limitations and how it is being used.

ardnew

Posted 2013-06-29T17:16:37.747

Reputation: 2 177

20f(n) = i*n -- pure math :P – Johannes Kuhn – 2013-06-29T17:33:37.947

8@JohannesKuhn this is why the domain and codomain are restricted to the rationals – ardnew – 2013-06-29T17:36:32.477

Could you explain what f:Q->Q means? – beary605 – 2013-06-29T17:38:18.670

@beary605 it means f is a function mapping members of Q (rational numbers) to other members (possibly the same) of Q. see http://en.wikipedia.org/wiki/Function_(mathematics)#Notation

– ardnew – 2013-06-29T17:41:15.530

What should f[6] return?: (a) 6; (b) f[6]; (c) something else? What should f[3/4] return?: (a) 3/4; (b) f[3/4]? – DavidC – 2013-06-29T18:58:11.120

@DavidCarraher that is dependent on your solution. the value of f(n) is not required to be anything other than a rational number. but the value of f(f(6)) should be -6. for your other question, 3/4 is not an integer, so it will never be input to f(f(n)). – ardnew – 2013-06-29T19:02:50.693

7

I knew I'd seen this recently, but it took a while to remember where. A less tightly specified version on StackOverflow was recently closed. Over 100 answers.

– Peter Taylor – 2013-06-29T19:36:36.660

Followup comment: you talk about "integers" and "Z": does this restrict the problem to languages with arbitrarily large integers? – Peter Taylor – 2013-06-29T19:39:37.237

@PeterTaylor oops, definitely not. i will relax that requirement – ardnew – 2013-06-29T19:43:32.077

@ardnew You say: 3/4 will never be input to f[f[n]]. But 3/4 is in f's domain so it must correspond to something in the codomain (that includes 3/4 itself). It follows that f[f[3/4]] should be in the codomain of rationals. – DavidC – 2013-06-29T19:44:05.627

In that case you'll also need to take into account that for languages which use twos complement, the minimum value of signed fixed width integer types is a fixpoint under negation due to overflow. – Peter Taylor – 2013-06-29T19:50:39.777

@DavidCarraher i agree 3/4 is in f's domain, and f(n) should be defined for all rational n. however, the challenge is to handle integer input values a certain way. you can do whatever you want with non-integer input. – ardnew – 2013-06-29T20:13:45.417

@DavidCarraher for example, if f(f(3/4)) evaluates to 438943, and f(f(n)) evaluates to -n for all integer n, then f is correct. if f(f(3/4)) evaluates to 438943 and f(f(n)) does not evaluate to -n for all integer n, then f is not correct. does this help clarify? – ardnew – 2013-06-29T20:27:28.320

@ardnew Yes, it does. Thanks. – DavidC – 2013-06-29T22:44:03.150

So just to clarify, the function needs to be able to handle any rational number (with certain size restrictions for languages without arbitrary size numbers), but only needs to satisfy the property for integers? – HyperNeutrino – 2017-04-08T21:19:36.383

lambda n:n*1j almost works for python, but on the second run the output is of the form (-n+0j) which is numerically the same, but represented differently, so I'm not sure if it counts. EDIT: oops, domain restricted to rationals anyways – Zwei – 2017-04-09T04:55:33.313

@HyperNeutrino it doesn't need to be able to handle any rational number -- that was a little misleading on my part. the intent was to prevent complex numbers while also allowing more than just the integers. it should, in principle, work for every integer though – ardnew – 2017-04-10T22:37:42.100

Okay. Thanks for clarifying. So essentially, the domain of the function needs to be a subset or be equal to Q? – HyperNeutrino – 2017-04-11T00:58:13.497

Floating point numbers and Q are certainly not the same thing. – ypercubeᵀᴹ – 2014-01-02T20:48:55.080

@ypercube right, and not all floating point implementations are the same thing either. in any case, i should have laid off the overly complicated specs – ardnew – 2014-01-03T03:23:47.047

Answers

12

J, 9 points (10 chars)

Based on stackoverflow answer:

   (*-[*_1&^)

First idea (13 chars):

   ((-*)-2&|*+:)

   ((-*)-2&|*+:) _10 _9 _8 _7 _6 _5 _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10
_9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9

   ((-*)-2&|*+:) _9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9
10 9 8 7 6 5 4 3 2 1 0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _10

randomra

Posted 2013-06-29T17:16:37.747

Reputation: 19 909

This works for integer input, but this produces imaginary output for floating point values (the function must produce rational output for rational input according to the spec) – Volatility – 2013-06-30T14:17:19.330

5@Volatility, the spec is confusing worded, but as I read it it allows restricting domain and codomain to integers. – Peter Taylor – 2013-06-30T18:18:43.440

Do you need the parentheses? – Cyoce – 2017-04-07T18:35:37.397

14

Python: 61 34 30 29 27 points

f: Q -> Q

in math:

       | 0.5-x   if x is in Q \ Z
f(x) = |
       | x+0.5   if x is in Z

in Python:

f=lambda x:.5+[x,-x][x%1>0]

tested with

filter(lambda n: n[0] != -n[1], map(lambda n:(n,f(f(n))),range(0,50)))

logic behind this:

When you take an integer n and put it into f you will get x+0.5. This is not an integer any more, so the next application will be 0.5-(x+0.5) which is -x.

Credits

Thanks to

  • Bakuriu for striping it down from 61 characters to 34 characters.
  • Volatility for further reducing code size to 30 characters.
  • copy for reducing code size to 29 characters (and fixing a potential floating point problem).
  • aditsu for mentioning an inconsistency that came with the changes above.

Notes

First I thought this would be ok

f = lambda n: 1j*n

but its f:N->C and that is not allowed :-/

Martin Thoma

Posted 2013-06-29T17:16:37.747

Reputation: 669

1Can be stripped down to: f=lambda x:x%1>0and(-x+x%1)or x+.1 which is only 34 characters long. – Bakuriu – 2013-07-01T21:04:42.103

f=lambda x:[x+.1,x%1-x](x%1>0) is only 30 – Volatility – 2013-07-01T23:15:54.413

Oops, should be f=lambda x:[x+.1,x%1-x][x%1>0] – Volatility – 2013-07-02T23:41:41.603

1One char shorter: f=lambda x:[x+.5,.5-x][x%1>0]. Note the use of .5 instead of .1 to get around precision issues – copy – 2013-07-03T09:29:23.323

I don't think this solution is correct: f(f(1.48))->f(-1)->-0.9 – AJMansfield – 2013-07-12T13:35:12.640

1@AJMansfield 1.48 is not an integer. – Martin Thoma – 2013-07-12T15:48:12.927

But, according to the problem, f:Q->Q, meaning it must work with a floating argument. – AJMansfield – 2013-07-12T15:51:50.397

1No, that doesn't mean it. If he ment that, he should have written "all rational numbers". f:Q->Q does only mean that f maps rational number to rational numbers. Which my definition of f does. – Martin Thoma – 2013-07-12T16:01:45.030

The math part doesn't match the python part. It's 0.5-x not -floor(x). – aditsu quit because SE is EVIL – 2013-12-31T22:19:40.647

@aditsu: Thanks. I've corrected it. – Martin Thoma – 2013-12-31T23:51:21.750

Does this work? f=lambda x:.5+x-2*x*(x%1>0) – Gelatin – 2014-01-02T23:21:38.633

Or even just f=lambda x:.5+[x,-x][x%1>0] – Gelatin – 2014-01-02T23:38:00.057

Even better: f=lambda x:.5+x-x%1*x*4 – Gelatin – 2014-01-16T23:50:44.983

11

C, 41 points (41 or 45 chars)

Works using both 32- and 64-bit.

f : Z -> Z (except INT_MAX):

f(n){return (abs(n)%2*2-1)*n+n?(-n<n)*2-1:0;}

If we don't have to include 0 we can shave off some chars (41 chars):

f : Z -> Z (except 0 & INT_MAX):

f(n){return (abs(n)%2*2-1)*n+(-n<n)*2-1;}

This function works by dividing all integers into 4 groups based on their sign and parity.

So we have the 4 different combinations:

+ even, + odd, - even, - odd

As we need to switch the sign of the number, but not the parity after two passes, we get two different possible sequences:

  + even -> - odd -> - even -> + odd -\
^-------------------------------------/

  + even -> + odd -> - even -> - odd -\
^-------------------------------------/

In this example I have chosen the first one.

First we need to map all even positive integers to odd negative integers. We do this by changing the sign and incrementing the number (you could also choose to decrement the number instead):

f1(n) = -n + 1

We then need to map all odd negative integers to even negative integers. We need to make sure that f2(f1(n)) = -n:

f2(f1(n)) = -n
f2(-n + 1) = -n
f2(-n) = -n - 1
f2(n) = n - 1

Using the same methods we find f3 and f4:

f3(n) = -n - 1
f4(n) =  n + 1

To combine these functions into one single function, we observe that every time n is even we switch the sign of n and every time n is positive we increment by one and otherwise we decrement by one:

f1(n) = -n + 1 (+ even)
f2(n) =  n - 1 (- odd)
f2(n) = -n - 1 (- even)
f4(n) =  n + 1 (+ odd)

This can thus be rewritten as:

f(n) = odd(n) * n + sign(n)

where odd(n) returns 1 for odd numbers and -1 for even numbers.

There are 4 solutions total:

f(n) = odd(n) * n + sign(n)  (edge cases: f(f(0))  -> -2, f(f(INT_MAX))   -> -8)
f(n) = even(n) * n - sign(n) (edge cases: f(f(0))  -> -2, f(f(INT_MIN+1)) -> -6)
f(n) = odd(n) * n - sign(n)  (edge cases: f(f(1))  -> -3, f(f(INT_MIN))   -> -5)
f(n) = even(n) * n + sign(n) (edge cases: f(f(-1)) -> -1, f(f(INT_MIN))   -> -5)

INT_MIN might always be considered an edge case in all 4 functions as -INT_MIN == INT_MIN => f(f(INT_MIN)) = INT_MIN.

Tyilo

Posted 2013-06-29T17:16:37.747

Reputation: 1 372

This is essentially the same as my GolfScript answer (except explained better). Does this work for 0? – Ben Reich – 2013-12-30T02:07:26.117

@BenReich As stated in the answer it doesn't work for 0 and 3 other numbers. – Tyilo – 2013-12-30T02:22:37.667

1@Tylio I see now. Makes sense. It seems like you should only take the Z bonus if you cover 0, at least. – Ben Reich – 2013-12-30T02:51:47.313

@BenReich Removed the bonus until I get it fixed. – Tyilo – 2013-12-30T03:40:12.320

9

Here's my go at it.

long f(int i){return i;}
int f(long i){return -i;}

Live example:

int main()
{
  for(int i=-10; i<10; i=i+3)
    std::cout << f(f(i)) << "\n";
}

The input types cn be arbitrarily tailored to suit your needs. This version works for integer literals that are smaller in magnitude than 2^32-1.

rubenvb

Posted 2013-06-29T17:16:37.747

Reputation: 224

2The problem said f:Q->Q, not f:Z->Z. – AJMansfield – 2013-07-12T13:37:45.057

@AJMansfield the scoring section of the spec was meant to offer bonus points for functions defined f:Z->Z, sorry for the confusing wording – ardnew – 2013-07-12T22:48:20.007

6the problem with this answer is it appears to define two separate functions, while the spec requires you only define one. but i don't mean to start a semantics debate, it's still a very thoughtful solution – ardnew – 2013-07-12T22:54:15.003

@ardnew, oh you're right. I was pointed to this valid objection only seconds before sharing it with the Lounge<C++> on SO chat. I do wonder what the compiler makes of this (if it doesn't inline the calls), but my assembly sucks. – rubenvb – 2013-07-13T16:25:19.207

are 2 functions different the name is different for the machine and for me – RosLuP – 2017-04-06T22:01:03.527

1I think you can remove the space in return -i – Cyoce – 2017-04-07T18:36:43.357

6

JavaScript, 18

f=n=>n%1?.5-n:n+.5

Using the new fat arrow notation (Firefox 22).

Other version (18):

f=n=>n%1?-.5/n:.5/n

Previous version (20):

f=n=>n-~~n?.5-n:n+.5

Example:

> [-3,-2,-1,1,2,3].map(f).map(f)
[3, 2, 1, -1, -2, -3]

copy

Posted 2013-06-29T17:16:37.747

Reputation: 6 466

10Looks like JavaScript is evolving into CoffeeScript. – Peter Taylor – 2013-06-29T21:13:15.867

4

Mathematica 18

f=#+1/2-4#(#-⌊#⌋)&

Here ⌊...⌋ is the floor function. It uses only rational numbers (not lists, complex numbers, etc)

f[10]
f[f[10]]

21/2

-10

f[-5]
f[f[-5]]

-9/2

5

ybeltukov

Posted 2013-06-29T17:16:37.747

Reputation: 1 841

3

x86 assembly language (FASM). The argument and the result are in eax register.

It works properly for -2^30 < N < +2^30-1

16 bytes executable code.

        use32

f_n:
        lea     edx, [2*eax]
        xor     edx, eax
        btc     eax, 30
        shl     edx, 1
        jnc     .end
        neg     eax
.end:
        retn

johnfound

Posted 2013-06-29T17:16:37.747

Reputation: 131

Nitpicking your numbers; 2E30 would be 2 * 10^30, not 2^30 as I think you want. – Nick T – 2013-12-30T02:22:34.200

@NickT My mistake. Fixed. – johnfound – 2014-02-01T11:14:58.610

I'm pretty sure you are supposed to count the bytes in the source code. – nyuszika7h – 2014-04-28T12:49:23.227

3

Common Lisp: 35 bytes

(defun f(x)(/(if(> 1 x)-1/2 1/2)x))

Scheme (and Racket): 36 bytes

(define(f x)(/(if(> 1 x)-1/2 1/2)x))

Ungolfed with comments and explanation:

(define (f x)
  (/             ;; divide
     (if (> 1 x) ;; if x is below 1 
         -1/2    ;; then -1/2 (the fraction)
         1/2)    ;; else 1/2 (the fraction)
      x))        ;; gets divided with x

For any number x in [1,->] the if will turn into the fraction 1/2 which is a real exact number in both languages.

The divide part will then become (/ 1/2 x) so the fraction will become 1/(x*2) which always is below 1. For 1 it will be 1/2, for 2 it's 1/4, etc.

For any number below 1 the if will turn in to the fraction -1/2, which makes the function do (/ -1/2 x) which is -1/(2*x) but since we can expect the value to be result of the previous run we can substitute x for 1/(x*2) making a double application -1/((1/(x*2))*2) = -x

E.g. since 1 turns into 1/2 the second application is (/ -1/2 1/2) ==> -1

Sylwester

Posted 2013-06-29T17:16:37.747

Reputation: 3 678

How does this work? – AJMansfield – 2014-04-25T21:36:44.417

@AJMansfield added some info. Just ask if there is anything unclear. Reading LISP syntax is like greek if you haven't learned it and it takes some weeks to get used to. – Sylwester – 2014-04-25T23:12:27.317

3

C, 60 (⌈66 * .9⌉)

int f(int x){if(!x&1||!~x)return ~x;if(x<0)return x-1;return x+1;}

Here is an uncondensed version:

int f(int x){
    if(!x&1 || !~x) return ~x;
    if(x<0) return x-1;
    return x+1;
}

This method works using only integers, so it gets the 90% score bonus. I was originally writing it in java, but realized that this program in particular could benefit from C-style logical operators.

As there is no integer corresponding to -INT_MIN, f(f(INT_MIN)) returns INT_MIN instead.

The underlying mapping is algebraically rather simple. Executing the statement x=f(x) replaces x with:

  • x+1, if x is positive and odd
  • -x+1, if x is positive and even
  • x-1, if x is negative and odd
  • -x-1, if x is negative and even

The result of each case will fall under the next case the next time the function is applied to x.

As you can see, composing a case with the case following it yields -x.

The code is a result of some clever simplification of the function to take advantage of the bit structure of two's compliment integers.

AJMansfield

Posted 2013-06-29T17:16:37.747

Reputation: 2 758

3

><>, 21 + 3 = 24 bytes, 22 points

:0)$:0($:1$2%2*-*+-n;

Use the official Python interpreter, and use the -v command line option to enter input, at a cost of 3 bytes.

I have a feeling that this could be better--I'll keep looking at it and try to golf it down.

Given input n, the program outputs

(n>0) - ((n<0) + n * (1 - 2*(n%2)))

where (n>0) and (n<0) are booleans. This is equivalent to Gelatin's Python answer

(n>0) - (n<0) - n * (-1)**n

but ><> doesn't have a built-in exponentiation operator so we use (1 - 2*(n%2)) in place of (-1)**n.

What follows is mathematical theory -- read if (and only if) you are interested:

Given any function f: Z -> Z such that f(f(n)) = -n for all n in Z, we see immediately that f(f(f(f(n)))) = n, or in other words, f^4 is the identity function. In particular, f is invertible, and its inverse function is f^3. Thus f is a permutation of Z, and since f^4 = Id, it follows that every orbit (or cycle) of f has size either 1, 2, or 4.

Next, we see that f(0) = 0. Proof: f(0) = f(-0) = f(f(f(0))) = -f(0), so f(0) = 0, as desired. Conversely, suppose x is in a cycle of length 1 or 2, so f(f(x)) = x. Then -x = x so x = 0.

Thus f is made up entirely of 4-cycles, except for the fixed point (1-cycle) at 0.

Further, every 4-cycle must have the form (x, y, -x, -y), and by rotating the cycle around we may assume that x and y are both positive. Conversely, every such product of 4-cycles partitioning the nonzero integers determines a choice of f.

Thus each choice of f corresponds uniquely to a directed graph whose vertices are the positive integers, such that every vertex is incident to exactly one arrow, either entering or exiting. More precisely, in the underlying undirected graph, every vertex has degree exactly 1. (Each 4-cycle (x y -x -y) with x and y positive corresponds to the arrow x --> y.)

The function in this answer (and several other answers here) corresponds to the graph where 1 --> 2, 3 --> 4, and in general 2k-1 --> 2k.

Such graphs are in bijection with infinite sequences of ordered pairs (a_n, p_n), where each a_n is a positive integer and each p_n is either 0 or 1: given a sequence (a_1, p_1), (a_2, p_2), (a_3, p_3), ..., we first pair 1 with 1 + a_1, and then we form either the arrow 1 --> 1 + a_1 or the arrow 1 + a_1 --> 1 depending on whether p_1 is 0 or 1. Essentially, the arrow is either a < sign or a > sign, depending on the parity of p_1.

Next, take the smallest unpaired positive integer k, and count up from k, exactly a_2 steps, SKIPPING any number that is already paired with something. Pair k with the result, and set the direction of the arrow depending on p_2 as above. Then repeat with (a_3, p_3), etc.

Each arrow will eventually be determined this way, so the process is well defined. The function in this answer corresponds to the sequence (1,0), (1,0), (1,0), ..., since at step n the smallest unpaired integer is 2n-1 and no integers larger than 2n-1 have been paired with anything, so we get 2n-1 --> 2n for each n (arrows are oriented this way because each p_n equals 0).

The cardinality of this set is (N*2)^N = N^N, which by the last paragraph of this answer equals 2^N, the cardinality of the real numbers.

mathmandan

Posted 2013-06-29T17:16:37.747

Reputation: 943

Command line options are usually a byte each. – cat – 2016-05-22T12:20:11.433

@cat See the "Special invocations" section at this meta post.

– mathmandan – 2016-05-22T15:34:13.747

2

To fix the earlier J answer (I don't have enough reputation to comment on the original):

(*+[*1-~2*2|])

It just replaces the _1&^ with 1-~2*2|], which gives the opposite sign. So I changed the - to a + (which only matters on input of 1 and _1).

Here are the tests:

   (*+[*1-~2*2|])6 3 _9 _8 1r2 _4.6 0 1 _1
7 _2 8 _9 1 7.28 0 2 _2
   (*+[*1-~2*2|])7 _2 8 _9 1 7.28 0 2 _2
_6 _3 9 8 0 _10.3568 0 _1 1

   NB. f^:2 = f@:f
   (*+[*1-~2*2|])^:(2)6 3 _9 _8 1r2 _4.6 0 1 _1
_6 _3 9 8 2 _5.0832 0 _1 1

As you can see, the domain and range are of all real numbers, but it only works for integers (including 0).

Explanation:

(   *     + [ *  1-~    2*     2|]    )
 signum n + n * pred (twice (n mod 2))

James Wood

Posted 2013-06-29T17:16:37.747

Reputation: 406

2

GolfScript ceiling(26*.9)=24

Golfscript only handles integers, so apply the Z bonus for a total of 24 points:

.{..0>2*(\)2%!2*(@*+}{ }if

The special case of 0 accounts for 8 characters. Ignoring 0, we can have a 17 point answer:

..0>2*(\)2%!2*(@*+

This code does the following to an integer x on top of the stack:

  • If x is 0, leave 0 on the stack and apply no more rules.
  • If x is even, negate x.
  • If x is positive, add 1.
  • If x is negative, subtract 1.

This logically connects sets of 4 numbers in a cycle, where f traverses elements of the cycle, and opposite corners of the cycle are negatives of each other. Every integer is part of exactly 1 such cycle, except 0 which is special cased. For example, for {-8, -7, 7, 8}:

  • 7 f -> 8
  • 8 f -> -7
  • -7 f -> -8
  • -8 f -> 7

The only relevant test cases I could think of were a negative odd, negative even, positive odd, positive even, 0, and then I threw in -1 and 1 since their proximity to 0 may have caused problems:

[-10 -5 -1 0 1 5 10]
{.{..0>2*(\)2%!2*(@*+}{ }if}:f;
{f f}%
-> [10,5,1,0,-1,-5,-10]

I'm sure the actual GolfScript can be improved somewhat. It doesn't feel like it should take up 26 characters! Would love to hear some suggestions.

Ben Reich

Posted 2013-06-29T17:16:37.747

Reputation: 1 577

2

Java, just for fun

Here's an implementation that does an actual bijection between ℤ and ℤ², which is an odd function at the same time (g(-x) == -g(x)). It treats the corresponding ℤ² element as a complex number and multiplies it by "i", then converts back to ℤ.

f(x)=g⁻¹(ig(x))
f(f(x))=g⁻¹(-g(x))=-x

The function runs in O(1).

public class Ffn {
    public static int f(int n) {
        if (n == 0) {
            return 0;
        }
        // adjust sign
        int s = n > 0 ? 1 : -1;
        int m = n * s;
        // calculate square "radius"
        int r = (int) (Math.sqrt(2 * m - 1) + 1) / 2;
        int q = r * 2;
        // starting point
        int x = r, y = r;
        int k = q * (r - 1) + 1;

        if (m - k < q) {
            // go left
            x -= m - k;
        }
        else {
            // go left
            x -= q;
            // go down
            y -= m - k - q;
        }

        // multiply by i
        int x2 = -y * s, y2 = x * s;
        // adjust sign
        s = y2 < x2 || y2 == x2 && x2 < 0 ? -1 : 1;
        x2 *= s;
        y2 *= s;

        if (y2 == r) {
            // go left
            k += r - x2;
        }
        else {
            // go left and down
            k += q + r - y2;
        }
        return k * s;
    }

    public static void main(final String... args) {
        for (int i = 0; i < 1000000; ++i) {
            if (f(f(i)) != -i || f(f(-i)) != i) {
                System.out.println(i);
            }
        }
    }
}

P.S. Happy New Year!

aditsu quit because SE is EVIL

Posted 2013-06-29T17:16:37.747

Reputation: 22 326

I believe the whitespace is unnecessary. – pppery – 2019-08-26T12:50:58.877

2

Python 3 - 38

Similar to @moose's answer, but, f(n) == n. Works for all integer values.

f=lambda x:x*(isinstance(x,int)*2.0-1)

cjfaure

Posted 2013-06-29T17:16:37.747

Reputation: 4 213

2

Perl, 33 (non-whitespace)

sub f{($=)=@_;$=-$_[0]?-$=:"$=.1"}

Edit:

  • $=.".1" shortened to "$=.1" (thanks ardnew).

Math:

Math

Ungolfed:

# script.pl
sub f {
  ($=) = @_;   # short for $= = int($_[0]); 
               # "int" is implicit in assignments to $=;
               # ($=) can be prepended by "local" to get
               # the function free of side effects.

  $= - $_[0] ? # short for $= != $_[0], check if input is integer
    -$=        # input is not an integer  
  : $= . ".1"  # input is integer
}  

# Testing
chomp;
$_ = sprintf "f(f($_)) = f(%s) = %s\n", f($_), f(f($_));

Examples:

perl -p script.pl
7
f(f(7)) = f(7.1) = -7
2
f(f(2)) = f(2.1) = -2
0
f(f(0)) = f(0.1) = 0
-1
f(f(-1)) = f(-1.1) = 1
-10
f(f(-10)) = f(-10.1) = 10
-1.23
f(f(-1.23)) = f(1) = 1.1
3.4
f(f(3.4)) = f(-3) = -3.1
1.0
f(f(1.0)) = f(1.1) = -1

Heiko Oberdiek

Posted 2013-06-29T17:16:37.747

Reputation: 3 841

robust solution- the floating point test cases you demo'd aren't required per spec (should have offered bonus points for that!). here's your same algorithm with a few cleanups coming in at 22 chars: sub f{yzxzzc?-$_:x.$_} – ardnew – 2014-04-22T03:20:10.577

1@ardnew: Thanks. But I disagree that your solution uses the same algorithm. The algorithm sub f{yzxzzc?-$_:x.$_} is not state free, it uses a state via the variable $_. Because of this, f is no longer a function (in the mathematical sense), because different values are possible for the same input value depending on the state (weather $_ contains a x or not). My algorithm does not use a state, The information is encoded in the output value. Integers are converted to real numbers by adding .1. And real numbers are converted back to integers with the sign switched. – Heiko Oberdiek – 2014-04-22T03:41:59.137

interesting- no state data is used in your implementation because of the initial assignment and not because of some special property of $=? – ardnew – 2014-04-22T13:08:01.730

i didn't realize i also failed my own requirement (that f be defined Q->Q) with that x char. also $=.".1" can be shortened to "$=.1" – ardnew – 2014-04-22T13:31:35.660

@ardnew: The special property of $= is just that it only takes integer numbers. The same can be achieved by using an ordinary variable: $a=int$_[0]. But that costs three additional bytes because of function int. – Heiko Oberdiek – 2014-04-22T13:44:22.930

2

Julia, 26

julia> f(n::Int)=n//1
f (generic function with 1 method)
julia> f(n)=int(-n)
f (generic function with 2 methods)
julia> f(f(4))
-4

Not super competitive, but very Julian since it relies on multiple dispatch. It just makes n a Rational if its an Int, or an int with a minus sign if it is anything else. One might object that this is 2 functions, but Julia considers this to be one function with two methods, and it is equivalent to defining one function with an if statment on the type of n.

gggg

Posted 2013-06-29T17:16:37.747

Reputation: 1 715

It's not what a mathematician would call a function: in Julia 3==3//1 returns true but f(3//1)==f(3) returns false. – Omar – 2015-01-29T23:17:17.593

2

Candy, 20 18 bytes

Uses the 3 -> 4 -> -3 -> -4 -> 3 trick.

~A2%{|m}1A0>{+|-}.

To invoke it use the -i switch on the interpreter

Example of double-invokation:

$ candy -i 7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 8
$ candy -i 8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -7
$ candy -i -7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -8
$ candy -i -8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 7

Long form:

peekA
pushA
digit2
mod          # even/odd
if
else
  negate     # negate even numbers
endif
digit1
pushA
digit0
greater      # positive/negative
if
  add        # add two numbers from stack (original stack value, and delta)
else
  sub        # diff two numbers from stack (original stack value, and delta)
endif
retSub

Dale Johnson

Posted 2013-06-29T17:16:37.747

Reputation: 509

2

Dyalog APL, 9 points

×-⍨⊢ׯ1*⊢

The source is 9 bytes long and qualifies for the bonus (which doesn't help at all). It also uses the formula from the top SO answer.

lirtosiast

Posted 2013-06-29T17:16:37.747

Reputation: 20 331

1

Updated with function supplied by Synthetica (obviously the one who should get credit for this now)

Language: Python

Number of characters: 41 including whitespace

f=lambda x:-float(x) if str(x)==x else`x`

HolySquirrel

Posted 2013-06-29T17:16:37.747

Reputation: 147

On integers f returns a string; the specification says it must return a rational number. – Omar – 2015-01-29T23:24:21.467

All that whitespace! – cat – 2016-05-22T12:21:44.370

You don't need the f= part. Please also remove the extra whitespace. – HyperNeutrino – 2017-04-08T21:44:24.730

35 bytes: lambda x:[<backtick>x<backtick>,-float(x)][str(x)==x] – HyperNeutrino – 2017-04-08T21:45:23.000

Please provide also the name of the language that you used an provide also the character count. – ProgramFOX – 2013-12-30T15:23:53.473

I like how this also works with non-integers. Well done. :) – cjfaure – 2014-02-04T08:57:51.653

f=lambda x:-float(x) if str(x)==x else\x`` is quite a bit shorter: 41 including whitespace – ɐɔıʇǝɥʇuʎs – 2014-04-25T22:21:02.167

Thanks Synthetica, I didn't even know about the backticks trick! :D – HolySquirrel – 2014-04-26T23:33:22.663

1

Python: 32 bytes (29 points)

f: Z -> Z

f=lambda n:(n>0)-(n<0)-n*(-1)**n

Using Ben Reich's method.

Gelatin

Posted 2013-06-29T17:16:37.747

Reputation: 115

In Python 2, you can replace (n>0)-(n<0) with cmp(n,0), to save a few bytes. (But not in Python 3: https://docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )

– mathmandan – 2015-12-08T07:10:06.773

1

GTB, 22

@S;N,"--$x?N)→N~N#~-N&

Timtech

Posted 2013-06-29T17:16:37.747

Reputation: 12 038

1

Java, 113 bytes

The approach is pretty simple. It ended up more bytes than I anticipated, but can perhaps be golfed down a bit.

public class F{public static int f(int x){if(x<0)x+=-2147483647-++x;x+=1073741824;return x<0?-2147483647-++x:x;}

It basically creates 4 different "areas" of x, utilizing the fact that Java happily lets variables wrap around. I had to do some tricky conversion for negative numbers which is the main reason this ended up bigger than anticipated.

Works for all x besides -2147483648.

FIQ

Posted 2013-06-29T17:16:37.747

Reputation: 519

1

Same sequence of numbers (3, 4, -3, -4, 3 ...) as the golfscript answer, but implemented in perl (42 chars after whitespace is stripped)

sub f{($_[0]%2?1:-1)*$_[0]+($_[0]<0?-1:1)}

More legibly:

sub f { ($_[0] % 2 ? $_[0] : -$_[0] ) + ( $_[0] < 0 ? -1 : 1 ) }

Or even more legibly:

sub f {
  my $n = shift;
  my $sign = $n >= 0 ? 1 : -1;
  # note that in perl $n % 2 is the same as int($n) % 2
  if( $n % 2 ) {
    # odd: add one to magnitude
    return $n + $sign
  } else {
    # even: subtract one from magnitude then invert
    return -($n - $sign)
  }
}

Output:

ski@anito:~/mysrc/.../acme$ echo 3 | perl -e 'sub f{($_[0]%2?1:-1)*$_[0] + ($_[0]<0?-1:1)}; my $x = <>; for(0..10) { print "$_: $x\n"; $x = f($x); }'
0: 3
1: 4
2: -3
3: -4
4: 3
5: 4
6: -3
7: -4
8: 3
9: 4
10: -3

skibrianski

Posted 2013-06-29T17:16:37.747

Reputation: 1 197

The above also works for non-integers:

ski@anito:~/mysrc/.../acme$ echo 1.1234 | perl -e 'sub f{($_[0]%2?1:-1)*$_[0] + ($_[0]<0?-1:1)}; my $x = <>; for(0..4) { print "$_: $x\n"; $x = f($x); }'
0: 1.1234
1: 2.1234
2: -1.1234
3: -2.1234
4: 1.1234
 – skibrianski  – 2014-02-04T20:12:58.263

1

Sed, 25 bytes.

|sed s/0+/0-/|sed s/^/0+/

Usage:

$ echo 1.23 |sed s/0+/0-/|sed s/^/0+/
0+1.23
$ echo 0+1.23 |sed s/0+/0-/|sed s/^/0+/
0+0-1.23

Ken A

Posted 2013-06-29T17:16:37.747

Reputation: 585

1

Matlab, 26 characters

f=@(n) (n<0)-(n<0)-n*(-1)^n

bla

Posted 2013-06-29T17:16:37.747

Reputation: 111

2This is not a valid answer, as the domain and codomain of the function must not be complex. – Wrzlprmft – 2014-04-25T12:44:03.307

oh, I'm sorry... I just read the title and wasn't that careful... Let's see if I can edit this somewhat – bla – 2014-04-25T19:20:13.433

1

C++ - 63 55.8

This is how the code looks:

int f(int n){return (n&45056?n^45056:n|45056)*(n&45056?-1:1);}

It doesn't work on integers whose fourth byte is equal to 0xB as it uses that value to keep track of passes. Otherwise works on any member of Z, including zero.

Darkgamma

Posted 2013-06-29T17:16:37.747

Reputation: 181

The restriction that the fourth byte cannot equal 0xB unfortunately makes this not a valid answer to the challenge, which requires it work on (at least) all integers. – pppery – 2019-08-26T12:55:09.560

can you explain this one? at first inspection it looks like you're keeping a counter of calls to f with a static variable. but then what's the point of the sqrt? – ardnew – 2014-04-26T02:01:57.467

I seem to have misunderstood the question; thought that a static variable was okay since C++ is a stack-oriented language, but I'll fix the code. Otherwise I have no idea why I needed sqrt as it gets rounded down anyway with type casting. I'll refactor it so it works without the static variable. – Darkgamma – 2014-04-26T09:57:29.063

I have no idea where you got the 55.8 from, but your current code is 62 bytes long. Edit: Never mind, I didn't read the question properly. – nyuszika7h – 2014-04-28T12:47:03.113

1

Prolog, 36 bytes

Code:

X*Y:-X//1=:=X,Y is 0.5+X;Y is 0.5-X.

Explained:

Dyadic predicate which converts integers to floats and floats back to negated integers.

Example:

10*X.
X = 10.5

10*Y,Y*X.
X = -10,
Y = 10.5

Emigna

Posted 2013-06-29T17:16:37.747

Reputation: 50 798

1

Javascript ES6, 27 26 bytes

a=>a%1?-Math.floor(a):a+.2

SuperJedi224

Posted 2013-06-29T17:16:37.747

Reputation: 11 342

1

Mouse-2002, 21 19 12 bytes

$A1%[1%_|1%]

Defines a function A; call it like #A,#A,?;; (which will wait for the user to enter any number). Alternatively, call it like #A,#A,n;; where n is any number.

cat

Posted 2013-06-29T17:16:37.747

Reputation: 4 989

1

Julia, 21

f(x)=(1-2(1>x>-1))/2x

Then

julia> f(f(12//1))
-12//1

p//q is julia's literal notation of rational numbers.

mschauer

Posted 2013-06-29T17:16:37.747

Reputation: 1 348

0

Forth, 37 bytes

: f 9 @ if negate 0 else 1 then 9 ! ; 

Works at least in durexforth (it should at least, I couldn't type the whole line in because VICE was being stupid with my keybaord layout so I couldn't type the :). To run it in gforth you need to do variable 9 before, since it doesn't allow writing to arbitrary memory locations.

(Forth sadly doesn't work with floating point numbers.)

2xsaiko

Posted 2013-06-29T17:16:37.747

Reputation: 699

0

C, 80 bytes

#include <math.h>
double z(double x){return x==0.0?x:fabs(x)>0.5?0.5/x:-0.5/x;}

for to test

#include <stdio.h>      
#define P printf
#define R return
main()
{double i, j;
 for(i=-20;i<20;i+=1)
       P("z(z(%f))=%f\n", i, z(z(i)) );
 for(i=-2;i<-1;i+=0.1)
       P("z(z(%f))=%f\n", i, z(z(i)) );
 for(i= 2;i<3;i+=0.1)
       P("z(z(%f))=%f\n", i, z(z(i)) );
 P("z(z(%f))=%f\n", 0.1245447, z(z(0.1245447)) );
 R 0;
}

results where you can see that this is for every number in double except 0 and 2 other

/*
z(z(-20.000000))=20.000000
z(z(-19.000000))=19.000000
z(z(-18.000000))=18.000000
z(z(-17.000000))=17.000000
z(z(-16.000000))=16.000000
z(z(-15.000000))=15.000000
z(z(-14.000000))=14.000000
z(z(-13.000000))=13.000000
z(z(-12.000000))=12.000000
z(z(-11.000000))=11.000000
z(z(-10.000000))=10.000000
z(z(-9.000000))=9.000000
z(z(-8.000000))=8.000000
z(z(-7.000000))=7.000000
z(z(-6.000000))=6.000000
z(z(-5.000000))=5.000000
z(z(-4.000000))=4.000000
z(z(-3.000000))=3.000000
z(z(-2.000000))=2.000000
z(z(-1.000000))=1.000000
z(z(0.000000))=0.000000
z(z(1.000000))=-1.000000
z(z(2.000000))=-2.000000
z(z(3.000000))=-3.000000
z(z(4.000000))=-4.000000
z(z(5.000000))=-5.000000
z(z(6.000000))=-6.000000
z(z(7.000000))=-7.000000
z(z(8.000000))=-8.000000
z(z(9.000000))=-9.000000
z(z(10.000000))=-10.000000
z(z(11.000000))=-11.000000
z(z(12.000000))=-12.000000
z(z(13.000000))=-13.000000
z(z(14.000000))=-14.000000
z(z(15.000000))=-15.000000
z(z(16.000000))=-16.000000
z(z(17.000000))=-17.000000
z(z(18.000000))=-18.000000
z(z(19.000000))=-19.000000
z(z(-2.000000))=2.000000
z(z(-1.900000))=1.900000
z(z(-1.800000))=1.800000
z(z(-1.700000))=1.700000
z(z(-1.600000))=1.600000
z(z(-1.500000))=1.500000
z(z(-1.400000))=1.400000
z(z(-1.300000))=1.300000
z(z(-1.200000))=1.200000
z(z(-1.100000))=1.100000
z(z(2.000000))=-2.000000
z(z(2.100000))=-2.100000
z(z(2.200000))=-2.200000
z(z(2.300000))=-2.300000
z(z(2.400000))=-2.400000
z(z(2.500000))=-2.500000
z(z(2.600000))=-2.600000
z(z(2.700000))=-2.700000
z(z(2.800000))=-2.800000
z(z(2.900000))=-2.900000
z(z(0.124545))=-0.124545
*/

RosLuP

Posted 2013-06-29T17:16:37.747

Reputation: 3 036