N-movers: How much of the infinite board can I reach?
$begingroup$
Single moves
The board is an infinite 2 dimensional square grid, like a limitless chess board. A piece with value N (an N-mover) can move to any square that is a distance of exactly the square root of N from its current square (Euclidean distance measured centre to centre).
For example:
- A 1-mover can move to any square that is horizontally or vertically adjacent
- A 2-mover can move to any square that is diagonally adjacent
- A 5-mover moves like a chess knight
Note that not all N-movers can move. A 3-mover can never leave its current square because none of the squares on the board are a distance of exactly root 3 from the current square.
Multiple moves
If allowed to move repeatedly, some pieces can reach any square on the board. For example, a 1-mover and a 5-mover can both do this. A 2-mover can only move diagonally and can only reach half of the squares. A piece that cannot move, like a 3-mover, cannot reach any of the squares (the starting square is not counted as "reached" if no movement occurs).
The images show which squares can be reached. More details on hover. Click for larger image.
- Squares reachable in 1 or more moves are marked in black
- Squares reachable in exactly 1 move are shown by red pieces
(apart from the 3-mover, which cannot move)
What proportion of the board can a given N-mover reach?
Input
- A positive integer N
Output
- The proportion of the board that an N-mover can reach
- This is a number from 0 to 1 (both inclusive)
- For this challenge, output as a fraction in lowest terms, like 1/4, is allowed
So for input 8
, both 1/8
and 0.125
are acceptable outputs.
Scoring
This is code golf. The score is the length of the code in bytes. For each language, the shortest code wins.
Test cases
In the format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
code-golf grid chess board-game
$endgroup$
add a comment |
$begingroup$
Single moves
The board is an infinite 2 dimensional square grid, like a limitless chess board. A piece with value N (an N-mover) can move to any square that is a distance of exactly the square root of N from its current square (Euclidean distance measured centre to centre).
For example:
- A 1-mover can move to any square that is horizontally or vertically adjacent
- A 2-mover can move to any square that is diagonally adjacent
- A 5-mover moves like a chess knight
Note that not all N-movers can move. A 3-mover can never leave its current square because none of the squares on the board are a distance of exactly root 3 from the current square.
Multiple moves
If allowed to move repeatedly, some pieces can reach any square on the board. For example, a 1-mover and a 5-mover can both do this. A 2-mover can only move diagonally and can only reach half of the squares. A piece that cannot move, like a 3-mover, cannot reach any of the squares (the starting square is not counted as "reached" if no movement occurs).
The images show which squares can be reached. More details on hover. Click for larger image.
- Squares reachable in 1 or more moves are marked in black
- Squares reachable in exactly 1 move are shown by red pieces
(apart from the 3-mover, which cannot move)
What proportion of the board can a given N-mover reach?
Input
- A positive integer N
Output
- The proportion of the board that an N-mover can reach
- This is a number from 0 to 1 (both inclusive)
- For this challenge, output as a fraction in lowest terms, like 1/4, is allowed
So for input 8
, both 1/8
and 0.125
are acceptable outputs.
Scoring
This is code golf. The score is the length of the code in bytes. For each language, the shortest code wins.
Test cases
In the format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
code-golf grid chess board-game
$endgroup$
add a comment |
$begingroup$
Single moves
The board is an infinite 2 dimensional square grid, like a limitless chess board. A piece with value N (an N-mover) can move to any square that is a distance of exactly the square root of N from its current square (Euclidean distance measured centre to centre).
For example:
- A 1-mover can move to any square that is horizontally or vertically adjacent
- A 2-mover can move to any square that is diagonally adjacent
- A 5-mover moves like a chess knight
Note that not all N-movers can move. A 3-mover can never leave its current square because none of the squares on the board are a distance of exactly root 3 from the current square.
Multiple moves
If allowed to move repeatedly, some pieces can reach any square on the board. For example, a 1-mover and a 5-mover can both do this. A 2-mover can only move diagonally and can only reach half of the squares. A piece that cannot move, like a 3-mover, cannot reach any of the squares (the starting square is not counted as "reached" if no movement occurs).
The images show which squares can be reached. More details on hover. Click for larger image.
- Squares reachable in 1 or more moves are marked in black
- Squares reachable in exactly 1 move are shown by red pieces
(apart from the 3-mover, which cannot move)
What proportion of the board can a given N-mover reach?
Input
- A positive integer N
Output
- The proportion of the board that an N-mover can reach
- This is a number from 0 to 1 (both inclusive)
- For this challenge, output as a fraction in lowest terms, like 1/4, is allowed
So for input 8
, both 1/8
and 0.125
are acceptable outputs.
Scoring
This is code golf. The score is the length of the code in bytes. For each language, the shortest code wins.
Test cases
In the format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
code-golf grid chess board-game
$endgroup$
Single moves
The board is an infinite 2 dimensional square grid, like a limitless chess board. A piece with value N (an N-mover) can move to any square that is a distance of exactly the square root of N from its current square (Euclidean distance measured centre to centre).
For example:
- A 1-mover can move to any square that is horizontally or vertically adjacent
- A 2-mover can move to any square that is diagonally adjacent
- A 5-mover moves like a chess knight
Note that not all N-movers can move. A 3-mover can never leave its current square because none of the squares on the board are a distance of exactly root 3 from the current square.
Multiple moves
If allowed to move repeatedly, some pieces can reach any square on the board. For example, a 1-mover and a 5-mover can both do this. A 2-mover can only move diagonally and can only reach half of the squares. A piece that cannot move, like a 3-mover, cannot reach any of the squares (the starting square is not counted as "reached" if no movement occurs).
The images show which squares can be reached. More details on hover. Click for larger image.
- Squares reachable in 1 or more moves are marked in black
- Squares reachable in exactly 1 move are shown by red pieces
(apart from the 3-mover, which cannot move)
What proportion of the board can a given N-mover reach?
Input
- A positive integer N
Output
- The proportion of the board that an N-mover can reach
- This is a number from 0 to 1 (both inclusive)
- For this challenge, output as a fraction in lowest terms, like 1/4, is allowed
So for input 8
, both 1/8
and 0.125
are acceptable outputs.
Scoring
This is code golf. The score is the length of the code in bytes. For each language, the shortest code wins.
Test cases
In the format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
code-golf grid chess board-game
code-golf grid chess board-game
edited 2 hours ago
trichoplax
asked 5 hours ago
trichoplaxtrichoplax
7,36163975
7,36163975
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Clean, 189 185 172 171 bytes
import StdEnv
$n#r=[~n..n]
#p=[[x,y]\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\_<-iter n(q=removeDup[k\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(e=n>=e&&e>0)k])p]/toReal(n^2)
Try it online!
Finds every position reachable in the n
-side-length square cornered on the origin in the first quadrant, then divides by n^2
to get the portion of all cells reachable.
$endgroup$
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
add a comment |
$begingroup$
JavaScript (Node.js), 144 bytes
a=>Object.keys((w=F=(x,n=2)=>n*n>x?w[x]=-~w[x]:x%n?F(x,n+1):w[F(x/n,n),n]=-~w[n])(a)&&w).map(y=>z*=[,1,.5**w[y],w[y]%2?0:1/y**w[y]][y%4],z=1)&&z
Try it online!
Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.
For each prime factor $p^n$ in the factorization of the number, calculate $f(p^n)$:
- If $n$ is odd and $pequiv 3text{ (mod 4)}$ - $f(p^n)=0$. Because there is no place to go.
- If $n$ is even and $pequiv 3text{ (mod 4)}$ - $f(p^n)=frac{1}{p^n}$.
- If $p=2$ - $f(2^n)=frac{1}{2^n}$.
- If $pequiv 1text{ (mod 4)}$ - $f(p^n)=1$.
Multiply all those function values, there we are.
$endgroup$
add a comment |
$begingroup$
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)
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179747%2fn-movers-how-much-of-the-infinite-board-can-i-reach%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Clean, 189 185 172 171 bytes
import StdEnv
$n#r=[~n..n]
#p=[[x,y]\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\_<-iter n(q=removeDup[k\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(e=n>=e&&e>0)k])p]/toReal(n^2)
Try it online!
Finds every position reachable in the n
-side-length square cornered on the origin in the first quadrant, then divides by n^2
to get the portion of all cells reachable.
$endgroup$
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
add a comment |
$begingroup$
Clean, 189 185 172 171 bytes
import StdEnv
$n#r=[~n..n]
#p=[[x,y]\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\_<-iter n(q=removeDup[k\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(e=n>=e&&e>0)k])p]/toReal(n^2)
Try it online!
Finds every position reachable in the n
-side-length square cornered on the origin in the first quadrant, then divides by n^2
to get the portion of all cells reachable.
$endgroup$
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
add a comment |
$begingroup$
Clean, 189 185 172 171 bytes
import StdEnv
$n#r=[~n..n]
#p=[[x,y]\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\_<-iter n(q=removeDup[k\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(e=n>=e&&e>0)k])p]/toReal(n^2)
Try it online!
Finds every position reachable in the n
-side-length square cornered on the origin in the first quadrant, then divides by n^2
to get the portion of all cells reachable.
$endgroup$
Clean, 189 185 172 171 bytes
import StdEnv
$n#r=[~n..n]
#p=[[x,y]\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\_<-iter n(q=removeDup[k\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(e=n>=e&&e>0)k])p]/toReal(n^2)
Try it online!
Finds every position reachable in the n
-side-length square cornered on the origin in the first quadrant, then divides by n^2
to get the portion of all cells reachable.
edited 53 mins ago
answered 2 hours ago
ΟurousΟurous
6,84211034
6,84211034
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
add a comment |
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
$begingroup$
My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :)
$endgroup$
– trichoplax
2 hours ago
1
1
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
@trichoplax I've changed the tests to correspond to the question to avoid the same confusion again
$endgroup$
– Οurous
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
$begingroup$
I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here...
$endgroup$
– trichoplax
2 hours ago
add a comment |
$begingroup$
JavaScript (Node.js), 144 bytes
a=>Object.keys((w=F=(x,n=2)=>n*n>x?w[x]=-~w[x]:x%n?F(x,n+1):w[F(x/n,n),n]=-~w[n])(a)&&w).map(y=>z*=[,1,.5**w[y],w[y]%2?0:1/y**w[y]][y%4],z=1)&&z
Try it online!
Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.
For each prime factor $p^n$ in the factorization of the number, calculate $f(p^n)$:
- If $n$ is odd and $pequiv 3text{ (mod 4)}$ - $f(p^n)=0$. Because there is no place to go.
- If $n$ is even and $pequiv 3text{ (mod 4)}$ - $f(p^n)=frac{1}{p^n}$.
- If $p=2$ - $f(2^n)=frac{1}{2^n}$.
- If $pequiv 1text{ (mod 4)}$ - $f(p^n)=1$.
Multiply all those function values, there we are.
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 144 bytes
a=>Object.keys((w=F=(x,n=2)=>n*n>x?w[x]=-~w[x]:x%n?F(x,n+1):w[F(x/n,n),n]=-~w[n])(a)&&w).map(y=>z*=[,1,.5**w[y],w[y]%2?0:1/y**w[y]][y%4],z=1)&&z
Try it online!
Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.
For each prime factor $p^n$ in the factorization of the number, calculate $f(p^n)$:
- If $n$ is odd and $pequiv 3text{ (mod 4)}$ - $f(p^n)=0$. Because there is no place to go.
- If $n$ is even and $pequiv 3text{ (mod 4)}$ - $f(p^n)=frac{1}{p^n}$.
- If $p=2$ - $f(2^n)=frac{1}{2^n}$.
- If $pequiv 1text{ (mod 4)}$ - $f(p^n)=1$.
Multiply all those function values, there we are.
$endgroup$
add a comment |
$begingroup$
JavaScript (Node.js), 144 bytes
a=>Object.keys((w=F=(x,n=2)=>n*n>x?w[x]=-~w[x]:x%n?F(x,n+1):w[F(x/n,n),n]=-~w[n])(a)&&w).map(y=>z*=[,1,.5**w[y],w[y]%2?0:1/y**w[y]][y%4],z=1)&&z
Try it online!
Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.
For each prime factor $p^n$ in the factorization of the number, calculate $f(p^n)$:
- If $n$ is odd and $pequiv 3text{ (mod 4)}$ - $f(p^n)=0$. Because there is no place to go.
- If $n$ is even and $pequiv 3text{ (mod 4)}$ - $f(p^n)=frac{1}{p^n}$.
- If $p=2$ - $f(2^n)=frac{1}{2^n}$.
- If $pequiv 1text{ (mod 4)}$ - $f(p^n)=1$.
Multiply all those function values, there we are.
$endgroup$
JavaScript (Node.js), 144 bytes
a=>Object.keys((w=F=(x,n=2)=>n*n>x?w[x]=-~w[x]:x%n?F(x,n+1):w[F(x/n,n),n]=-~w[n])(a)&&w).map(y=>z*=[,1,.5**w[y],w[y]%2?0:1/y**w[y]][y%4],z=1)&&z
Try it online!
Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.
For each prime factor $p^n$ in the factorization of the number, calculate $f(p^n)$:
- If $n$ is odd and $pequiv 3text{ (mod 4)}$ - $f(p^n)=0$. Because there is no place to go.
- If $n$ is even and $pequiv 3text{ (mod 4)}$ - $f(p^n)=frac{1}{p^n}$.
- If $p=2$ - $f(2^n)=frac{1}{2^n}$.
- If $pequiv 1text{ (mod 4)}$ - $f(p^n)=1$.
Multiply all those function values, there we are.
answered 7 mins ago
Shieru AsakotoShieru Asakoto
2,455315
2,455315
add a comment |
add a comment |
$begingroup$
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)
$endgroup$
add a comment |
$begingroup$
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)
$endgroup$
add a comment |
$begingroup$
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)
$endgroup$
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)
edited 15 mins ago
answered 26 mins ago
Milo BrandtMilo Brandt
1815
1815
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f179747%2fn-movers-how-much-of-the-infinite-board-can-i-reach%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown