Ce défi a été inspiré par un blog de programmation que je fréquente. S'il vous plaît voir le post original ici: Un puzzle de programmation
Défi
Définissez une fonction f:Q->Q
telle que f(f(n)) = -n
pour tous les entiers non nuls n
, et où Q
est l'ensemble des nombres rationnels.
Détails
Quelle que soit la langue que vous préférez, s'il vous plaît définir une fonction ou d'un programme f
qui accepte comme paramètre un nombre n
et retourne ou émet un numéro f(n)
.
Les entrées peuvent être fournies par le mécanisme le plus naturel pour votre langage: argument de fonction, lecture depuis STDIN, argument de ligne de commande, position de la pile, entrée vocale, signes de groupe, etc.
La sortie doit être une valeur renvoyée par une fonction / un programme ou imprimée sur STDOUT.
J'aimerais limiter les réponses aux fonctions qui ne tirent pas parti de l'état du programme ou de la mémoire globale / des données visibles de l'extérieur de la fonction f
. Par exemple, garder un compteur en dehors de f
cela compte combien de fois a f
été appelé et faire une négation basée sur ce compte n'est pas très difficile ou intéressant pour personne. Les décisions prises f
ne doivent s’appuyer que sur des données f
comprises dans la portée lexicale.
Cependant, cette restriction est probablement inappropriée pour certains langages orientés pile ou d'autres types de langages qui ne distinguent pas ces types de données ou de portées. S'il vous plaît utilisez votre meilleur jugement pour rester dans l'esprit de ce défi.
Notation
Les règles de golf communes au code s'appliquent - votre score est le nombre d' octets dans votre code source.
La réponse minimale nécessite que le domaine et le codomaine de f
soient un sous-ensemble des rationnels Q
. Si vous limitez votre domaine et votre codomaine f
aux entiers Z
, votre score correspond au plafond de 90% du nombre d' octets de votre code source.
Jeu décisif
En cas d'égalité, les éléments suivants seront utilisés dans l'ordre:
- Le plus petit nombre de symboles imprimables non-d'espaces blancs dans votre code source
- Date et heure de soumission de la réponse au plus tôt
modifier
Vous n'êtes pas obligé de prendre en charge des nombres de taille arbitraire. Veuillez interpréter les ensembles Z
et Q
les types de données dans la langue de votre choix (généralement des nombres entiers et des nombres à virgule flottante, respectivement).
Si votre solution repose entièrement sur la structure sous-jacente ou le modèle de bits d'un type de données, décrivez-en les limites et son utilisation.
f:Q->Q
signifie?f
est une fonction mappant les membres deQ
(nombres rationnels) sur les autres membres (éventuellement les mêmes) deQ
. voir en.wikipedia.org/wiki/Function_(mathematics)#NotationRéponses:
J, 9 points (10 caractères)
Basé sur la réponse stackoverflow :
Première idée (13 caractères):
la source
Python:
61 34 30 2927 pointsf: Q -> Q
en maths:
en Python:
testé avec
logique derrière ceci:
Lorsque vous prenez un entier
n
et le mettez dansf
vous obtiendrezx+0.5
. Ce n'est plus un entier, donc la prochaine application sera ce0.5-(x+0.5)
qui est-x
.Crédits
Grâce à
Remarques
D'abord j'ai pensé que ça irait
mais son f: N-> C et qui n'est pas autorisé: - /
la source
f=lambda x:x%1>0and(-x+x%1)or x+.1
ce qui ne fait que 34 caractères.f=lambda x:[x+.1,x%1-x](x%1>0)
a seulement 30 ansf=lambda x:[x+.5,.5-x][x%1>0]
. Notez l'utilisation de .5 au lieu de .1 pour résoudre les problèmes de précisionf:Q->Q
signifie simplement que f mappe un nombre rationnel à un nombre rationnel. Ce que ma définition de f fait.C, 41 points (41 ou 45 caractères)
Fonctionne en 32 et 64 bits.
f : Z -> Z
(saufINT_MAX
):Si nous n'avons pas à inclure,
0
nous pouvons éliminer quelques caractères (41 caractères):f : Z -> Z
(sauf0
&INT_MAX
):Cette fonction fonctionne en divisant tous les nombres entiers en 4 groupes en fonction de leur signe et de leur parité.
Nous avons donc 4 combinaisons différentes:
Comme nous devons changer le signe du nombre, mais pas la parité après deux passages, nous obtenons deux séquences différentes possibles:
Dans cet exemple, j'ai choisi le premier.
Nous devons d’abord mapper tous les entiers même positifs aux impairs négatifs. Nous faisons cela en changeant le signe et en incrémentant le nombre (vous pouvez également choisir de décrémenter le nombre à la place):
Nous devons ensuite mapper tous les entiers négatifs impairs sur des entiers même négatifs. Nous devons nous assurer que
f2(f1(n)) = -n
:En utilisant les mêmes méthodes, nous trouvons
f3
etf4
:Pour combiner ces fonctions en une seule fonction, nous observons que chaque fois que
n
nous sommes même, nous inversons le signe den
et que chaque fois quen
nous sommes positifs, nous incrémentons de un et sinon nous décrémentons de un:Ceci peut donc être réécrit comme:
où
odd(n)
renvoie1
les nombres impairs et les nombres-1
pairs.Il y a 4 solutions au total:
INT_MIN
peut toujours être considéré comme un cas de bordure dans les 4 fonctions comme-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.la source
0
avec 3 autres chiffres.Z
bonus que si vous couvrez au moins 0.Voici mon coup d'oeil.
Exemple en direct :
Les types de saisie peuvent être arbitrairement adaptés à vos besoins. Cette version fonctionne pour les littéraux entiers de magnitude inférieure à 2 ^ 32-1.
la source
f:Q->Q
, pasf:Z->Z
.f:Z->Z
, désolé pour la formulation déroutantereturn -i
JavaScript, 18
Utilisation de la nouvelle notation grosse flèche (Firefox 22).
Autre version (18):
Version précédente (20):
Exemple:
la source
Mathematica 18
Voici
⌊...⌋
la fonction de sol. Il utilise uniquement des nombres rationnels (pas des listes, des nombres complexes, etc.)la source
Langage d'assemblage x86 (FASM). L'argument et le résultat sont dans le registre eax.
Cela fonctionne correctement pour -2 ^ 30 <N <+ 2 ^ 30-1
Code exécutable de 16 octets.
la source
Common Lisp: 35 octets
Schéma (et raquette): 36 octets
Ungolfed avec des commentaires et des explications:
Pour n'importe quel nombre
x
dans[1,->]
leif
deviendra la fraction1/2
qui est un nombre exact exact dans les deux langues.La partie de division deviendra alors, de
(/ 1/2 x)
sorte que la fraction deviendra1/(x*2)
qui est toujours en dessous1
. Car1
ce sera1/2
, pour2
c'est1/4
, etc.Pour tout nombre inférieur à 1, la
if
fraction sera renvoyée-1/2
, ce qui rend la fonction do,(/ -1/2 x)
ce qui est vrai,-1/(2*x)
mais puisque nous pouvons nous attendre à ce que la valeur soit le résultat de l'exécution précédente, nous pouvons remplacer x par 1 / (x * 2) en effectuant une double application.-1/((1/(x*2))*2) = -x
Par exemple , depuis
1
tours dans1/2
la seconde application est(/ -1/2 1/2) ==> -1
la source
C, 60 (⌈66 * .9⌉)
Voici une version non condensée:
Cette méthode utilise uniquement des nombres entiers, ce qui lui donne le bonus de 90%. Je l’écrivais à l’origine en java, mais j’ai réalisé que ce programme en particulier pourrait tirer parti des opérateurs logiques de type C.
Comme il n'y a pas d'entier correspondant à
-INT_MIN
,f(f(INT_MIN))
retourne à laINT_MIN
place.La cartographie sous-jacente est algébriquement plutôt simple. L'exécution de l'instruction
x=f(x)
remplace x par:x+1
, six
est positif et impair-x+1
, six
est positif et mêmex-1
, six
est négatif et impair-x-1
, six
est négatif et mêmeLe résultat de chaque cas tombera dans le cas suivant la prochaine fois que la fonction sera appliquée à x.
Comme vous pouvez le constater, la composition d’une affaire après celle-ci cède
-x
.Le code est le résultat d'une simplification astucieuse de la fonction pour tirer parti de la structure en bits des entiers complémentaires à deux.
la source
> <> , 21 + 3 = 24 octets, 22 points
Utilisez l' interpréteur Python officiel et utilisez l'
-v
option de ligne de commande pour saisir l'entrée, au coût de 3 octets.J'ai le sentiment que cela pourrait être mieux - je vais continuer à regarder et essayer de jouer au golf.
Compte tenu des entrées
n
, les résultats du programmeoù
(n>0)
et(n<0)
sont des booléens. Cela équivaut à la réponse en gélatine Pythonmais
><>
n'a pas d'opérateur d'exponentiation intégré, nous utilisons donc(1 - 2*(n%2))
à la place de(-1)**n
.Ce qui suit est la théorie mathématique - lisez si (et seulement si) vous êtes intéressé:
Compte tenu de toute fonction
f: Z -> Z
telle quef(f(n)) = -n
pour tousn
dansZ
, on voit immédiatement quef(f(f(f(n)))) = n
, autrement dit,f^4
est la fonction d'identité. En particulier,f
est inversible, et sa fonction inverse estf^3
. Ainsif
est une permutationZ
, et depuisf^4 = Id
, il suit que chaque orbite (ou cycle) def
la taille a été soit1
,2
ou4
.Ensuite, nous voyons ça
f(0) = 0
. Preuve:,f(0) = f(-0) = f(f(f(0))) = -f(0)
doncf(0) = 0
, comme vous le souhaitez. Inversement, supposons qu’il s’agissex
d’un cycle de longueur1
ou2
alorsf(f(x)) = x
. Alors-x = x
ouix = 0
.Ainsi
f
est entièrement constitué de 4 cycles, sauf pour le point fixe (1 cycle) à0
.De plus, tous les 4 cycles doivent avoir la forme
(x, y, -x, -y)
, et en tournant le cycle, nous pouvons supposer quex
ety
sont tous deux positifs. Inversement, chaque produit de 4 cycles partitionnant les entiers non nuls en détermine le choixf
.Ainsi, chaque choix de
f
correspond uniquement à un graphe dirigé dont les sommets sont les entiers positifs, de sorte que chaque sommet est incident pour exactement une flèche, qu'elle soit entrante ou sortante. Plus précisément, dans le graphe sous-jacent sous-jacent, chaque sommet a un degré exact1
. (Chaque cycle de 4 cycles(x y -x -y)
avecx
ety
positif correspond à la flèchex --> y
.)La fonction de cette réponse (et plusieurs autres réponses ici) correspond au graphique où
1 --> 2
,3 --> 4
et en général2k-1 --> 2k
.Ces graphiques sont en bijection avec des séquences infinies de paires ordonnées
(a_n, p_n)
, où chacuna_n
est un nombre entier positif et chacunp_n
est soit0
ou1
: étant donné une séquence(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, nous avons d' abord paire1
avec1 + a_1
, et ensuite on forme soit sur la flèche1 --> 1 + a_1
ou sur la flèche en1 + a_1 --> 1
fonction de sip_1
est0
ou1
. Essentiellement, la flèche est soit un<
signe, soit un>
signe, en fonction de la parité dep_1
.Ensuite, prenez le plus petit entier positif non apparié
k
, et comptez à partir dek
, pas àa_2
pas, en sautant tout nombre déjà associé à quelque chose. Associez-vousk
au résultat et définissez le sens de la flèche en fonction de cep_2
qui précède. Puis répétez avec(a_3, p_3)
, etc.Chaque flèche sera éventuellement déterminée de cette façon, le processus est donc bien défini. La fonction dans cette réponse correspond à la séquence
(1,0), (1,0), (1,0), ...
, car au pasn
le plus petit entier non apparié est2n-1
et aucun entier plus grand que ce qui2n-1
a été jumelé avec quoi que ce soit, nous obtenons donc2n-1 --> 2n
pour chacunn
(les flèches sont orientées de cette façon car chacunp_n
est égal à0
).La cardinalité de cet ensemble est
(N*2)^N = N^N
ce qui, au dernier paragraphe de cette réponse, égale2^N
la cardinalité des nombres réels.la source
Pour corriger la réponse J précédente (je n'ai pas assez de réputation pour commenter l'original):
Il remplace simplement le
_1&^
avec1-~2*2|]
, ce qui donne le signe opposé. J'ai donc changé le-
en+
(qui ne compte que pour l'entrée de1
et_1
).Voici les tests:
Comme vous pouvez le constater, le domaine et la plage sont tous des nombres réels, mais cela ne fonctionne que pour les entiers (y compris 0).
Explication:
la source
GolfScript
ceiling(26*.9)=24
Golfscript ne gère que les entiers, appliquez donc le
Z
bonus pour un total de 24 points:Le cas particulier de 0 compte pour 8 caractères. En ignorant 0, nous pouvons avoir une réponse en 17 points:
Ce code a les effets suivants sur un entier situé
x
au-dessus de la pile:x
est 0, laissez0
sur la pile et n'appliquez plus de règles.x
est égal, niex
.x
est positif, ajouter1
.x
est négatif, soustrayez1
.Cela connecte logiquement des ensembles de 4 nombres dans un cycle, où
f
traverse des éléments du cycle, et les angles opposés du cycle sont des négatifs l'un par rapport à l'autre. Chaque entier fait partie de exactement 1 tel cycle, à l'exception de 0 qui est une casse spéciale. Par exemple, pour{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Les seuls cas de test pertinents auxquels je pouvais penser étaient un négatif impair, négatif même, positif positif, positif positif
0
, puis j'ai ajouté-1
et1
vu que leur proximité0
peut avoir causé des problèmes:Je suis sûr que le GolfScript réel peut être amélioré quelque peu. Il ne semble pas que cela devrait prendre 26 caractères! J'adorerais entendre des suggestions.
la source
Java, juste pour le plaisir
Voici une implémentation qui effectue une bijection réelle entre ℤ et ℤ², qui est une fonction impaire en même temps (g (-x) == -g (x)). Il traite l'élément ² correspondant comme un nombre complexe et le multiplie par "i", puis le reconvertit en ℤ.
f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x
La fonction s'exécute en O (1).
PS bonne année!
la source
Python 3 - 38
Semblable à la réponse de @ moose, mais
f(n) == n
. Fonctionne pour toutes les valeurs entières.la source
Perl, 33 (espace non blanc)
Modifier:
$=.".1"
raccourci à"$=.1"
(merci ardnew).Math:
Ungolfed:
Exemples:
la source
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
n'est pas libre d'état, il utilise un état via la variable$_
. De ce fait,f
n’est plus une fonction (au sens mathématique), car différentes valeurs sont possibles pour la même valeur d’entrée en fonction de l’état (la météo$_
contient unx
ou pas). Mon algorithme n'utilise pas d'état. Les informations sont codées dans la valeur de sortie. Les entiers sont convertis en nombres réels en ajoutant.1
. Et les nombres réels sont reconvertis en nombres entiers avec le signe changé.$=
?f
à définirQ->Q
) avec ce caractèrex
. aussi$=.".1"
peut être raccourci à"$=.1"
$=
est juste qu'elle ne prend que des nombres entiers. La même chose peut être réalisée en utilisant une variable ordinaire:$a=int$_[0]
. Mais cela coûte trois octets supplémentaires à cause de la fonctionint
.Julia, 26 ans
Pas super compétitif, mais très julien puisqu'il repose sur plusieurs envois. Cela rend na rationnel si c'est un Int, ou un int avec un signe moins s'il s'agit de quelque chose d'autre. On pourrait objecter qu'il s'agit de 2 fonctions, mais Julia considère qu'il s'agit d'une fonction avec deux méthodes, ce qui revient à définir une fonction avec une instruction if sur le type de
n
.la source
3==3//1
retournetrue
maisf(3//1)==f(3)
retournefalse
.Candy ,
2018 octetsUtilise le tour 3 -> 4 -> -3 -> -4 -> 3.
Pour l'invoquer, utilisez le commutateur -i sur l'interpréteur
Exemple de double invocation:
Forme longue:
la source
Dyalog APL, 9 points
La source a 9 octets de long et se qualifie pour le bonus (ce qui n’aide en rien). Il utilise également la formule de la première réponse SO.
la source
Python: 32 octets (29 points)
f: Z -> Z
Utiliser la méthode de Ben Reich.
la source
(n>0)-(n<0)
parcmp(n,0)
, pour économiser quelques octets. (Mais pas en Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
la source
Java, 113 octets
L'approche est assez simple. Il a fini par avoir plus d'octets que je ne l'aurais prévu, mais peut-être un peu plus bas.
Il crée fondamentalement 4 "zones" différentes de x, en utilisant le fait que Java laisse heureusement les variables en vrac. J'ai dû faire une conversion délicate pour les nombres négatifs, ce qui est la raison principale pour laquelle cela a été plus important que prévu.
Fonctionne pour tous les x sauf -2147483648.
la source
Même séquence de nombres (3, 4, -3, -4, 3 ...) que la réponse golfscript, mais implémentée en perl (42 caractères après la suppression des espaces)
Plus lisiblement:
Ou encore plus lisiblement:
Sortie:
la source
Sed, 25 octets.
Usage:
la source
Matlab, 26 caractères
la source
C ++ -
6355.8Voici à quoi ressemble le code:
Il ne fonctionne pas sur les entiers dont le quatrième octet est égal à 0xB car il utilise cette valeur pour garder une trace des passes. Sinon, fonctionne sur tout membre de Z, y compris zéro.
la source
f
avec une variable statique. mais alors quel est le point de lasqrt
?sqrt
car il est arrondi de toute façon avec le casting. Je vais le refactoriser pour qu'il fonctionne sans la variable statique.55.8
, mais votre code actuel est long de 62 octets. Edit: Peu importe, je n'ai pas lu la question correctement.Mise à jour avec la fonction fournie par Synthetica (évidemment celui qui devrait en avoir le crédit maintenant)
Langue: Python
Nombre de caractères: 41 y compris les espaces
la source
f=lambda x:-float(x) if str(x)==x else`x`
est un peu plus court: 41, y compris les espaces blancsf
renvoie une chaîne; le cahier des charges indique qu'il doit renvoyer un nombre rationnel.Prolog, 36 octets
Code:
A expliqué:
Exemple:
la source
Javascript ES6,
2726 octetsla source
Mouse-2002 ,
211912 bytesDéfinit une fonction
A
; appelez-le comme#A,#A,?;;
(ce qui attendra que l'utilisateur entre un nombre quelconque). Alternativement, appelez-le comme#A,#A,n;;
oùn
est n'importe quel nombre.la source
Julia, 21 ans
ensuite
p // q est la notation littérale de julia des nombres rationnels.
la source