Skip to main content
Code Golf

Return to Answer

added 365 characters in body; added 15 characters in body
Source Link
Milo Brandt
Milo Brandt
  • 271
  • 1
  • 6

Mathematica, 80 bytes

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

This code basically takes advantage of the LatticeReduce command to answeris mostly reliant on a mathematical theorem. The basic idea is that the question by processingcode asks for the setdensity of possible moves directlya lattice given some generating set.

It first generates the possible displacementsMore precisely, we are given some collection of the movements byvectors - namely, those whose length equalsquared is N - and asked to compute the square rootdensity of n; it does this by testing every possible vector in a 2n+1 x 2n+1 square around the origin. Then, the code outputs 0 if this empty. Otherwise, it feedsset of possible sums of these vectors to LatticeReduce, which outputs a pair ofcompared to all integer vectors such. The math at play is that moves by those vectors and their oppositeswe can reach the exact same positionsalways find two vectors (latticeand their opposite) that "generate" (i.e. whose sums are) the same set as the original moves can reachcollection. OneLatticeReduce does exactly that.

If you have just two vectors, you can imagine tiling the whole plane with rhombidrawing an identical parallelogram centered at each reachable point, but whose sidesedge lengths are representedthe given vectors, such that the plane is completely tiled by these two vectorsparallelograms. - and in each rhombus(Imagine, there must be exactly one reachable pointfor instance, a lattice of "diamond" shapes for n=2). The area of this rhombuseach parallelogram is the determinant of the pair oftwo generating vectors. The desired proportion of the plane is the reciprocal of this area, since each parallelogram has just one reachable point in it.

The code is a fairly straightforward implementation: Generate the vectors, use LatticeReduce, take the determinant, then take the reciprocal. (It can probably be better golfed, though)

Mathematica, 80 bytes

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

This code basically takes advantage of the LatticeReduce command to answer the question by processing the set of possible moves directly.

It first generates the possible displacements of the movements by length equal to the square root of n; it does this by testing every possible vector in a 2n+1 x 2n+1 square around the origin. Then, the code outputs 0 if this empty. Otherwise, it feeds these vectors to LatticeReduce, which outputs a pair of vectors such that moves by those vectors and their opposites can reach the exact same positions (lattice) that the original moves can reach. One can imagine tiling the whole plane with rhombi whose sides are represented by these two vectors - and in each rhombus, there must be exactly one reachable point. The area of this rhombus is the determinant of the pair of vectors. The proportion of the plane is the reciprocal of this.

Mathematica, 80 bytes

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

This code is mostly reliant on a mathematical theorem. The basic idea is that the code asks for the density of a lattice given some generating set.

More precisely, we are given some collection of vectors - namely, those whose length squared is N - and asked to compute the density of the set of possible sums of these vectors, compared to all integer vectors. The math at play is that we can always find two vectors (and their opposite) that "generate" (i.e. whose sums are) the same set as the original collection. LatticeReduce does exactly that.

If you have just two vectors, you can imagine drawing an identical parallelogram centered at each reachable point, but whose edge lengths are the given vectors, such that the plane is completely tiled by these parallelograms. (Imagine, for instance, a lattice of "diamond" shapes for n=2). The area of each parallelogram is the determinant of the two generating vectors. The desired proportion of the plane is the reciprocal of this area, since each parallelogram has just one reachable point in it.

The code is a fairly straightforward implementation: Generate the vectors, use LatticeReduce, take the determinant, then take the reciprocal. (It can probably be better golfed, though)

Source Link
Milo Brandt
Milo Brandt
  • 271
  • 1
  • 6

Mathematica, 80 bytes

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

This code basically takes advantage of the LatticeReduce command to answer the question by processing the set of possible moves directly.

It first generates the possible displacements of the movements by length equal to the square root of n; it does this by testing every possible vector in a 2n+1 x 2n+1 square around the origin. Then, the code outputs 0 if this empty. Otherwise, it feeds these vectors to LatticeReduce, which outputs a pair of vectors such that moves by those vectors and their opposites can reach the exact same positions (lattice) that the original moves can reach. One can imagine tiling the whole plane with rhombi whose sides are represented by these two vectors - and in each rhombus, there must be exactly one reachable point. The area of this rhombus is the determinant of the pair of vectors. The proportion of the plane is the reciprocal of this.