La question: étant donné un nombre n
≥ 2, combien de paires distinctes de points sur un réseau n
-dimensionnel n x n x n x n x n x n ... x n
, où les coordonnées vont de 0
à n - 1
, sont-elles au moins n
éloignées? Les paires {(2,1,3,1), (3,2,1,3)}
et {(3,2,1,3), (2,1,3,1)}
ne sont pas considérées comme distinctes les unes des autres, car elles sont constituées des deux mêmes points dans l'ordre inverse. Notez que le nombre total de paires croît très rapidement. Le nombre de paires au total va 6
, 351
, 32 640
, 4 881 250
, 1 088 367 840
, etc.
Cas de test:
2 -> 0 (all pairs are at most a distance of sqrt(2) < 2 apart)
3 -> 28 (They must either be (2,2,1) or a permutation apart, or (2,2,2) apart. Each corner
has three non-corner (2,2,1) points corresponding to it. And each corner is associated
with a corner pair that is a (2,2,2). Thus. 3.5 * 8 = 28.
4 -> 4,888
5 -> 1,501,948
6 -> 486,039,360 (I would like someone to verify this if possible)
Votre code devrait fonctionner pour n <= 5, au moins en théorie. Ne codez pas en dur, c'est une faille standard.
n=15
facilementn=20
mais souffre fortement d'un débordementall pairs are at most a distance of sqrt(2) apart
mais cela devrait être spécifié plus clairement.Réponses:
MATL , 12 octets
Essayez-le en ligne!
Explication
la source
Gelée ,
1413 octets1 octet merci à Dennis.
Essayez-le en ligne!
Version maffs rapide
Essayez-le en ligne!
la source
æ.`½
parÆḊ€
.n=5
, mais pas en une minute. (cela peut prendre plus que l'âge de l'univers, soyez prudent) Ce n'est pas le code le plus rapide, alors pourquoi prendre la peine de faire fonctionner votre code rapidement?Python 2 ,
137133 octetsMr Xcoder & ovs: -4 octets. Essayez-le en ligne!
la source
f=
)J , 40 octets
Essayez-le en ligne!
Expirera sur TIO pendant 5 si vous utilisez une précision étendue (
5x
au lieu de5
). Je ne vais pas prendre la peine d'essayer avec 6 sur mon ordinateur car cela va sans doute planter l'interprète.Vous cherchez des conseils sur le golf, en particulier la partie après la génération des coordonnées. Je pense qu'il devrait y avoir un moyen de retirer certains des bouchons.
]<:[:+/&.:*:"1
peut être remplacé de manière équivalente par*:<:[:+/"1[:*:
.Explication
Cette explication se fait sur le REPL (trois espaces indiquent une commande, aucun espace n'indique une sortie). Je vais construire la réponse.
Génération des coordonnées
#~ #: i.@^~
donne toutes les coordonnées qui nous intéressent sur le réseau.^~
est un nombre élevé à lui-même eti.
donne la plage [0, n) où n est son entrée.@
compose ces fonctions.#~
copie un numéro seul, par exemple#:
convertit son argument droit en la base spécifiée par le tableau donné comme argument gauche. Le nombre de chiffres du tableau correspond au nombre de chiffres de cette sortie de base (et vous pouvez avoir une base mixte). Par exemple,Donc, tous ensemble, cela dit énumérer à travers toutes les valeurs de base n (où n est l'entrée) jusqu'à n ^ n, nous donnant effectivement nos coordonnées.
Obtention des distances entre chaque paire
D'abord, nous prenons la différence de chaque coordonnée avec toutes les autres en utilisant la dyade
/
-table et~
-reflexive. Notez que cela ne tient pas compte du fait que l'ordre n'a pas d'importance pour les paires: cela génère des distances en double.Ensuite, nous utilisons ce verbe
+/&.:*:
sur chaque coordonnée (at"1
, aka rang un). Ce verbe est sum (+/
) sous (&.:
) square (*:
). Under applique le verbe droit (carré) puis recueille ses résultats et le donne comme argument au verbe gauche (somme). Il applique ensuite l'inverse du verbe droit (qui serait racine carrée).Sans surprise, de nombreuses distances sont les mêmes.
Comptage des distances supérieures ou égales à l'entrée
La dernière partie consiste à voir si la distance est supérieure ou égale à l'entrée utilisant
]<:
. Ensuite, tous les résultats sont additionnés à l'aide de+/^:_
(somme jusqu'à convergence), en comptant le nombre de valeurs véridiques. Ensuite, cette valeur est divisée par 2 (2%~
, ici~
signifie échanger l'ordre des arguments fournis à%
). La raison pour laquelle nous pouvons diviser par 2 est parce que pour chaque appariement véridique, il y en aura un autre pour l'ordre inversé, sauf pour les appariements qui sont une coordonnée avec lui-même. C'est ok, cependant, car ceux-ci entraîneront une distance de 0.la source
+/@,@(-:@<:+/&.:*:@:-"1/~)#~#:i.@^~