9
\$\begingroup\$

The question: Given an a number n ≥ 2, how many distinct pairs of points on an n-dimensional n x n x n x n x n x n ... x n lattice, where the coordinates range from 0 to n - 1, are a distance at least n apart? The pairs {(2,1,3,1), (3,2,1,3)} and {(3,2,1,3), (2,1,3,1)} are not considered distinct from each other, as they consist of the same two points in reverse order. Note that the total number of pairs grows very rapidly. The number of total pairs goes 6, 351, 32 640, 4 881 250, 1 088 367 840, etc.

Test cases:

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)

Your code should work for n <= 5, at least in theory. Don't hardcode it, that's a standard loophole.

\$\endgroup\$
  • \$\begingroup\$ tio.run/##bZLbboMwDIav4Sm8SpWSAONQbRfVuhepqgmRsEaioQpU256e2UkZh/… \$\endgroup\$ – Leaky Nun Dec 21 '17 at 2:04
  • \$\begingroup\$ ^ a program that can produce results for n=15 easily \$\endgroup\$ – Leaky Nun Dec 21 '17 at 2:05
  • \$\begingroup\$ tinyurl.com/ya2kmb24 <-- ported to C which can calculate up to n=20 but suffers heavily from overflow \$\endgroup\$ – Leaky Nun Dec 21 '17 at 3:51
  • \$\begingroup\$ How are you measuring distance? Euclidean metric? Or given that it's a lattice are you using L_1? \$\endgroup\$ – Peter Taylor Dec 21 '17 at 9:28
  • \$\begingroup\$ @PeterTaylor from the test cases, it's clear that we're using Euclidean distance all pairs are at most a distance of sqrt(2) apart but that should be specified more clearly. \$\endgroup\$ – Giuseppe Dec 21 '17 at 14:10
3
\$\begingroup\$

MATL, 12 bytes

tt:Z^tZPR>~z

Try it online!

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 13 bytes

1 byte thanks to Dennis.

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

Try it online!

Quick maffs version

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ What interpreter do you use to run this? I want to try it but TIO is too slow for n=5 (timed out after 1 minute) prntscr.com/hqbcph \$\endgroup\$ – bushdid911 Dec 21 '17 at 1:02
  • \$\begingroup\$ @bushdid911 if you try to break the limit, broken the limit will be \$\endgroup\$ – Leaky Nun Dec 21 '17 at 1:02
  • \$\begingroup\$ You can replace æ.`½ with ÆḊ€. \$\endgroup\$ – dylnan Dec 21 '17 at 1:04
  • \$\begingroup\$ @bushdid911 It can run n=5, just not in one minute. (it may take more than the age of the universe, be careful) This is not fastest code, so why bother make your code run fast? \$\endgroup\$ – user202729 Dec 21 '17 at 1:04
  • 1
    \$\begingroup\$ @bushdid911 I made a fast(er) version. \$\endgroup\$ – Leaky Nun Dec 21 '17 at 1:36
2
\$\begingroup\$

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

Mr Xcoder & ovs: -4 bytes. Try it online!

\$\endgroup\$
  • \$\begingroup\$ 135 bytes. (No need to include f=) \$\endgroup\$ – Mr. Xcoder Dec 21 '17 at 7:13
  • \$\begingroup\$ 133 bytes \$\endgroup\$ – ovs Dec 21 '17 at 9:59
2
\$\begingroup\$

J, 40 bytes

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

Try it online!

Will time out on TIO for 5 if you use extended precision (5x instead of 5). I'm not going to bother trying with 6 on my computer since that will no doubt crash the interpreter.

Looking for advice on golfing, specifically the part past the generation of the coordinates. I feel like there ought to be a way to remove some of the caps.

]<:[:+/&.:*:"1 may be equivalently replaced by *:<:[:+/"1[:*:.

Explanation

This explanation is done on the REPL (three spaces indicate a command, no spaces indicate an output). I will be building up to the answer.

Generating the coordinates

#~ #: i.@^~ gives all the coordinates we care about on the lattice.

^~ is a number raised to itself, and i. gives the range [0,n) where n is its input. @ composes those functions.

   i.@^~ 2
0 1 2 3

#~ copies a number by itself, e.g.

   #~ 3
3 3 3

#: converts its right argument to the base specified by the array given as its left argument. The number of digits in the array corresponds to the number of digits in that base output (and you can have a mixed base) For example,

   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

So, all together, this says enumerate through all of the values base n (where n is the input) up to n^n, effectively giving us our coordinates.

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

Getting the distances between each pair

First we take the difference of each coordinate with all of the others using the dyad /-table and ~-reflexive. Note that this doesn't account for the fact that order doesn't matter for the pairs: this generates duplicate distances.

  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

Then we use this verb +/&.:*: on each coordinate (at "1, aka rank one). This verb is sum (+/) under (&.:) square (*:). Under applies the right verb (square) then collects its results and gives it as the argument to the left verb (sum). It then applies the inverse of the right verb (which would be square root).

   +/&.:*: 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

Unsurprisingly, many distances are the same.

Counting the distances greater than or equal to the input

The last part is seeing if the distance is greater than or equal to the input using ]<:. Then all of the results are summed using +/^:_ (sum until converge), counting the number of truthy values. Then this value is divided by 2 (2%~, here ~ means swap the order of the arguments supplied to %). The reason why we can divide by 2 is because for each truthy pairing, there will be another one for the flipped order except for pairings which are a coordinate with itself. That's ok, though, since those will result in a distance of 0.

\$\endgroup\$
  • 1
    \$\begingroup\$ 35 bytes with +/@,@(-:@<:+/&.:*:@:-"1/~)#~#:i.@^~ \$\endgroup\$ – miles Dec 23 '17 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.