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:
- Fewest number of printable non-whitespace symbols in your source code
- 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.
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
– ardnew – 2013-06-29T17:41:15.530f
is a function mapping members ofQ
(rational numbers) to other members (possibly the same) ofQ
. see http://en.wikipedia.org/wiki/Function_(mathematics)#NotationWhat 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 off(f(6))
should be-6
. for your other question,3/4
is not an integer, so it will never be input tof(f(n))
. – ardnew – 2013-06-29T19:02:50.6937
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.660Followup 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 inf
's domain, andf(n)
should be defined for all rationaln
. 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 to438943
, andf(f(n))
evaluates to-n
for all integern
, thenf
is correct. iff(f(3/4))
evaluates to438943
andf(f(n))
does not evaluate to-n
for all integern
, thenf
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.497Floating 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