Agora estamos pensando em n dimensões!

9

A questão: dado um número n≥ 2, quantos pares de pontos distintos em uma rede ntridimensional n x n x n x n x n x n ... x n, onde as coordenadas variam de 0até n - 1, estão a uma distância pelo menos n distante? Os pares {(2,1,3,1), (3,2,1,3)}e {(3,2,1,3), (2,1,3,1)}não são considerados distintos um do outro, pois consistem nos mesmos dois pontos na ordem inversa. Observe que o número total de pares cresce muito rapidamente. O número de pares totais vai 6, 351, 32 640, 4 881 250, 1 088 367 840, etc.

Casos de teste:

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)

Seu código deve funcionar para n <= 5, pelo menos em teoria. Não codifique, isso é uma brecha padrão.

fraudado
fonte
^ Um programa que pode produzir resultados para n=15facilmente
Leaky Nun
tinyurl.com/ya2kmb24 <- portado para C, que pode calcular-se a n=20, mas sofre fortemente de transbordamento
gotejante Nun
Como você está medindo a distância? Métrica euclidiana? Ou como é uma treliça, você está usando L_1?
Peter Taylor
@PeterTaylor dos casos de teste, é claro que estamos usando a distância euclidiana, all pairs are at most a distance of sqrt(2) apartmas isso deve ser especificado com mais clareza.
21717 Giuseppe

Respostas:

3

MATL , 12 bytes

tt:Z^tZPR>~z

Experimente online!

Explicação

tt   % Implicit input n. Duplicate twice
     % STACK: n, n, n
:    % Range [1 2 ... n]
     % STACK: n, n, [1 2 ... n]
Z^   % Cartesian power. Gives an n^n × n matrix C where each row is a Cartesian tuple
     % STACK: n, C
t    % Duplicate
     % STACK: n, C, C
ZP   % Euclidean distance. Gives an n^n × n^n matrix D of pairwise distances
     % STACK: n, D
R    % Upper triangular part: sets elements below the main diagonal to 0. Call that U
     % STACK: n, U
>~   % Less than or equal? Element-wise. Gives a true-false matrix B
     % STACK: n, B
z    % Number of nonzeros. Implicitly display
     % STACK: number of entries in B that equal true
Luis Mendo
fonte
2

Geléia , 14 13 bytes

1 byte graças a Dennis.

ṗ⁸Œc_/€ÆḊ€<ċ0

Experimente online!

Versão rápida dos maffs

ŒgL€!P:@L!$×P
²S<
ḶœċçÐḟ²ð>0S’2*×⁸ạ⁹$Ѥð€S

Experimente online!

Freira Furada
fonte
Qual intérprete você usa para executar isso? Eu quero tentar, mas o TIO é muito lento para n = 5 (tempo limite esgotado após 1 minuto) prntscr.com/hqbcph
rigged
@ bushdid911 se você tentar quebrar o limite, quebrado o limite será
Leaky Nun
Você pode substituir æ.`½por ÆḊ€.
dylnan
@ bushdid911 Ele pode funcionar n=5, mas não em um minuto. (pode demorar mais do que a idade do universo, tenha cuidado) Este não é um código mais rápido; então, por que se preocupar em fazer seu código rodar mais rápido?
usar o seguinte comando
11
@ bushdid911 Fiz uma versão rápida (er).
Leaky Nun
2

Python 2 , 137 133 bytes

lambda n:sum(n*n<=sum((o[i]-p[i])**2for i in range(n))for o,p in q(q(range(n),repeat=n),repeat=2))/2
from itertools import*
q=product

Sr. Xcoder & ovs: -4 bytes. Experimente online!

dylnan
fonte
135 bytes . (Não há necessidade de incluir f=)
Mr. Xcoder
133 bytes
ovs
2

J , 40 bytes

2%~[:+/^:_]<:[:+/&.:*:"1[:-"1/~#~#:i.@^~

Experimente online!

O TIO atingirá o tempo limite de 5 se você usar precisão estendida (em 5xvez de 5). Não vou me incomodar em tentar com 6 no meu computador, pois isso sem dúvida trará o intérprete.

Procurando conselhos sobre golfe, especificamente a parte que passou após a geração das coordenadas. Eu sinto que deveria haver uma maneira de remover algumas das tampas.

]<:[:+/&.:*:"1pode ser substituído equivalentemente por *:<:[:+/"1[:*:.

Explicação

Esta explicação é feita no REPL (três espaços indicam um comando, nenhum espaço indica uma saída). Eu estarei construindo a resposta.

Gerando as coordenadas

#~ #: i.@^~ fornece todas as coordenadas com as quais nos preocupamos na treliça.

^~é um número elevado a si mesmo e i.fornece o intervalo [0, n) onde n é sua entrada. @compõe essas funções.

   i.@^~ 2
0 1 2 3

#~ copia um número sozinho, por exemplo

   #~ 3
3 3 3

#:converte seu argumento da direita na base especificada pela matriz fornecida como argumento da esquerda. O número de dígitos na matriz corresponde ao número de dígitos na saída base (e você pode ter uma base mista). Por exemplo,

   3 3 3 #: 0
0 0 0
   5 5 #: 120
4 0
NB. If you want 120 base 5 use #.inv
   #.inv 120
4 4 0

Então, todos juntos, isso diz enumerar todos os valores base n (onde n é a entrada) até n ^ n, efetivamente fornecendo nossas coordenadas.

   (#~ #: i.@^~) 2
0 0
0 1
1 0
1 1

Obtendo as distâncias entre cada par

Primeiro, tomamos a diferença de cada coordenada com todas as outras usando a díade /-table e ~-reflexive. Observe que isso não explica o fato de que a ordem não importa para os pares: isso gera distâncias duplicadas.

  NB. 2 {. takes the first two elements (I'm omitting the rest).
  2 {. -"1/~ (#~ #: i.@^~) 2
 0  0
 0 _1
_1  0
_1 _1

 0  1
 0  0
_1  1
_1  0

Em seguida, usamos esse verbo +/&.:*:em cada coordenada (em "1, também conhecido como um). Este verbo é soma ( +/) sob ( &.:) quadrado ( *:). Sob aplica o verbo da direita (quadrado), em seguida, coleta seus resultados e o fornece como argumento para o verbo da esquerda (soma). Em seguida, aplica o inverso do verbo certo (que seria a raiz quadrada).

   +/&.:*: 3 4
5
   +/&.:*:"1 ([: -"1/~ #~ #: i.@^~) 2
      0       1       1 1.41421
      1       0 1.41421       1
      1 1.41421       0       1
1.41421       1       1       0

Sem surpresa, muitas distâncias são as mesmas.

Contando as distâncias maiores ou iguais à entrada

A última parte é ver se a distância é maior ou igual à entrada usada ]<:. Em seguida, todos os resultados são somados usando +/^:_(soma até convergir), contando o número de valores verdadeiros. Então esse valor é dividido por 2 ( 2%~, aqui ~significa trocar a ordem dos argumentos fornecidos %). A razão pela qual podemos dividir por 2 é porque, para cada pareamento de verdade, haverá outro para a ordem invertida, exceto para os pares que são coordenados consigo. Tudo bem, porém, já que esses resultam em uma distância de 0.

Cole
fonte
11
35 bytes com+/@,@(-:@<:+/&.:*:@:-"1/~)#~#:i.@^~
milhas