# Placing circles along a square spiral

In this code golf challenge, you'll be computing the placement of circles of areas $$\\pi, 2\pi, 3\pi, \dots\$$ when greedily placed along integer points in a square spiral in such a way that no two overlap.

A square spiral is a sequence in $$\\mathbb Z^2\$$ that starts at $$\(0,0)\$$ and successively wraps around the origin. (Like Arnauld, you might find inspiration from this CGSE question.)

(0, 0) -> (1, 0) -> (1, 1) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (-1, -1) -> (0, -1) -> (1, -1) -> (2, -1) -> (2, 0) -> (2, 1) -> (2, 2) -> (1, 2) -> (0, 2) -> (-1, 2) -> (-2, 2) -> (-2, 1) -> (-2, 0) -> (-2, -1) -> (-2, -2) -> (-1, -2) -> (0, -2) -> (1, -2) -> (2, -2) -> (3, -2) -> (3, -1) -> (3, 0) -> (3, 1) -> (3, 2) -> ... In this challenge, you will start at the origin, walk around the spiral, and place circles with areas $$\\pi, 2\pi, 3\pi\$$, at integer points in a greedy fashion, as shown in the GIF below.

The first seven circles are:

• a circle of area $$\\pi\$$ placed at $$\(0,0)\$$,
• a circle of area $$\2\pi\$$ placed at $$\(2,2)\$$,
• a circle of area $$\3\pi\$$ placed at $$\(-2,2)\$$,
• a circle of area $$\4\pi\$$ placed at $$\(3,-2)\$$,
• a circle of area $$\5\pi\$$ placed at $$\(-3,-3)\$$,
• a circle of area $$\6\pi\$$ placed at $$\(5,5)\$$, and
• a circle of area $$\7\pi\$$ placed at $$\(0,6)\$$. Again, the circles are placed as soon as they fit. The second circle could not be placed at $$\(1,0)\$$, $$\(1,1)\$$, $$\(0,1)\$$, $$\(-1,1)\$$, $$\(-1,0)\$$, $$\(-1, -1)\$$, $$\(0,-1)\$$, $$\(1, -1)\$$, $$\(2, -1)\$$, $$\(2, 0)\$$, or $$\(2, 1)\$$ without overlapping with the first circle, but it could be—and is—placed at $$\(2,2)\$$.

Once we've placed "all" of the blue circles, we start over. In the second generation, we place "red" circles with areas $$\\pi, 2\pi, 3\pi\$$, in a greedy fashion: Once we've placed all of the red circles from the second generation, we move onto yellow circles, cyan circles, magenta, dark green, purple, light green, orange, brown circles, and so on. # Challenge

Okay! That's a lot of setup! Here's your challenge:

Write a program that takes in two positive (alternatively, $$\0\$$-indexed) integers, g and k, and outputs the position of the circle of area $$\k\pi\$$ in the $$\g\$$-th generation.

When $$\g=1\$$, this corresponds to the blue circles; when $$\g=2\$$, this corresponds to the red circles; when $$\g=3\$$, the yellow circles, and so on.

Your program should be able to compute all of the values in the following table in practice, and it should be able to compute bigger values (without running into floating point errors) in principle.

### Data table

 g |  k | position   | (color in GIFs; for reference only)
---+----+------------+------------------------------------
1 |  1 | (0, 0)     | blue
1 |  2 | (2, 2)     | blue
1 |  3 | (-2, 2)    | blue
1 | 50 | (36, -18)  | blue
2 |  1 | (0, -4)    | red
2 |  2 | (-3, 9)    | red
2 | 14 | (-2, -59)  | red
2 | 15 | (-66, 28)  | red
3 |  1 | (-5, 2)    | yellow
3 |  2 | (4, -10)   | yellow
3 | 10 | (-58, 3)   | yellow
8 |  1 | (-6, 10)   | orange
8 |  2 | (16, 21)   | orange
8 |  3 | (-27, -19) | orange
9 |  1 | (-10, 6)   | crimson
9 |  2 | (-25, 4)   | crimson
9 |  3 | (17, -27)  | crimson

• Just to clarify, all the circles are placed on integer coordinates, correct? Mar 28, 2021 at 19:45
• @ChartZBelatedly—that's right, I'll emphasize that in the post. Mar 28, 2021 at 19:45
• Out of curiosity, is this related to a problem of broader mathematical interest or just a fun puzzle? Mar 28, 2021 at 19:50
• @Jonah—just a puzzle! But I did publish an OEIS sequence back in 2017 about a related problem: A289523. Mar 28, 2021 at 19:52
• @Arnauld—thanks for catching this! The way I had my data represented was (-2, -59): 14, (-66, 28): 15, so I copied the 15 number, incorrectly associating it with 14. Mar 29, 2021 at 16:12

# JavaScript (ES7),  319  309 bytes

Expects (g)(k) and returns [x,y].

The formula for the spiral coordinates was inspired by this answer from Neil.

g=>k=>{a=[];p=[];r=[];H=Math.hypot;F=n=>{while((j=p[n]=-~p[n],C=_=>((i+2>>2)-i%2*j)*~-(i--&2),x=C(i=(--j*4+1)**.5|0,j-=i*i>>2),y=C(),n)&&a.every(([N,X,Y])=>~N+n|H(X,Y)<2*H(x,y))&&!F(n-1,p[n]--)||a.some(([_,X,Y,R])=>H(X-x,Y-y)<R**.5+q**.5,q=-~r[n]));a.push([n,x,y,r[n]=q])};while(~~r[g-1]<k)F(g-1);return[x,y]}


Try it online!

### How?

One tricky point in the challenge is to figure out how many circles of generation $$\n-1\$$ must be processed before we can start generation $$\n\$$.

In this implementation, we don't attempt to put a new circle of generation $$\n\$$ at $$\(x_0,y_0)\$$ until there's at least one circle of generation $$\n-1\$$ at $$\(x_1,y_1)\$$ which is at least twice as far from the center of the spiral:

$$\sqrt{{x_1}^2+{y_1}^2}\ge2\times \sqrt{{x_0}^2+{y_0}^2}$$

# JavaScript (ES2020), 417338331323321318316304303290283273269261257252247244237234238234207206205200194 193 bytes

G=>K=>eval('for(l=[],w=1;w<=G;)for(x=y=d=0,t=i=L=1,X=l[w++]=[];t--<250;t||=L+=d++%2)l.some(Z=>Z.some(([M,N],R)=>Math.hypot(M-x,N-y)<++R**.5+i**.5))?0:X[i++-1]=[x,y],d%2?y+=2-d%4:x+=1-d%4;X[K]')


Severely golfed. Very inefficient. Thanks to @Neil for getting rid of all the spare bytes I had lying around, and @tsh for removing a lot more. Takes G 1-indexed and K 0-indexed. -1 byte thanks to ophact.

Somehow beat @Arnauld, but still losing to @tsh by a lot somehow outgolfed tsh as well.

h=
G=>K=>eval('for(l=[],w=1;w<=G;)for(x=y=d=0,t=i=L=1,X=l[w++]=[];t--<250;t||=L+=d++%2)l.some(Z=>Z.some(([M,N],R)=>Math.hypot(M-x,N-y)<++R**.5+i**.5))?0:X[i++-1]=[x,y],d%2?y+=2-d%4:x+=1-d%4;X[K]')

console.log(h(2)(13))

# Explanation

Slightly different to actual code.

G =>                         // A function taking G (generation)
K => {                       // and K (circle number)
for(                       // Start a loop...
l = [],                  // l = 2d list of circles we've already found, starts empty
w = 1;                   // w = current generation, starts at 1
w <= G;                  // Looping up to the required generation...
)
for(                     // Another loop
// Initialise some variables
x = y =                // x, y = current coordinates in the spiral
d = 0                  // d = direction of current leg of spiral, initialise them all to 0
t =                    // t = distance to end of spiral
i =                    // i = current radius
L = 1,                 // L = total length of current leg of spiral
X = l[w++] = [];       // Incrememt w and append an empty list to l, which gets assigned to X.
--t < 250;             // Decrement t, if it's over 250 stop looping
t ||=                  // If t is falsy, set t to...
L +=                   // L incremented by...
d++ % 2                // direction modulo 2
)
l.some(                      // Do any values in l have the property that...
Z=>Z.some(                 // Any of their values have the property that...
([M,N],R) =>             // (M, N = coords, R = radius)
Math.hypot(M - x, N - y) // Is the distance to the point we're on right now...
< ++R ** .5 + i ** .5    // Less than the sum of their radii?
)
) ? 0 :                      // If not, we can place a circle.
X[i++ - 1] = [x,y],          // Increment i (radius of circle we're trying to place), and append the coordinate to X
d % 2 ?                      // If moving vertically
y += 2 - d % 4             // Change y
: x += 1 - d % 4;            // Else change x
return X[K]                    // Output the correct circle.
}

• I got it down to 338: h=(G,K,l=[],p=[],x=y=t=P=d=0,i=w=L=1,a=([...Array(5e4)].map(_=>p.push([x,y])+(d?d<2?y++:d<3?x--:y--:x++,++t==L&&(t=0,++P>1&&(L++,P=0))+(d=(d+1)%4)))))=>[...Array(G)].map(_=>p.map(x=>l.map(y=>((y-x)**2+(y-x)**2)**.5<y**.5+i**.5?k=0:0,k=1)+(k&&(l.push([x,x,i,w]),i++)))+(w++,i=1))?l.filter(x=>x==G)[K-1].slice(0,2):0
– Neil
Mar 29, 2021 at 18:48
• Not sure why ((y-x)**2+(y-x)**2)**.5 isn't the same as Math.hypot(y-x,y-x) though.
– Neil
Mar 29, 2021 at 18:49
• @Neil Thanks for all of that! Managed to golf it down a bit more. You're right, ((y-x)**2+(y-x)**2)**.5 is the same as Math.hypot(y-x,y-x). Mar 30, 2021 at 5:18
• @tsh Thanks for that! Mar 30, 2021 at 8:48
• @tsh You are too good at this. Mar 30, 2021 at 8:51

# JavaScript (Node.js), 211 bytes

g=>k=>{for(N=1;n=N;N*=2)for(G=g,C=[];G--;n-=r*3)for(o=[x=X=0,Y=y=s=1];x<n;o[[x+Y,y+X]]?0:[X,Y]=[Y,-X])if(!(o[[x+=X,y-=Y]]=C.some(([X,Y,R])=>Math.hypot(X-x,Y-y)<R+r,r=s**.5)||s++-k|G*C.push([x,y,r])))return[x,y]}


Try it online!

g=>  // input: generation
k=>{ // input: circle area
for(
N=1; // Search bound, we try to search generation 1
// circles in [-N,N]x[-N,N]
n=N; // Search bound of current generation
N*=2 // If we cannot locate (g,k) circle
// we try a larger bound later
)
for(
G=g, // Number of generation (count down)
C=[]; // All Circles found yet
G--; // Count down 1 generation
// I'm not quite sure if next line is correct.
// But it passes all testcases, at least.
// Change to n=n/4-r*4 would somehow ensure
// its correctness, but also make it slow as hell.
n-=r*3 // A smaller search bound for next generation
)
for(
o=[ // All points visited, stored by key
// For example, if (3, 4) is visited
// o['3,4'] would be something truthy
x= // Current x
X=0, // Current x axis direction
Y= // -Y is current y axis direction
y= // current y
s=1 // current circle area is s*PI
]; // Values initialized in Array o are harmless garbage
// As index 0 or 1 is not in x,y format
x<n; // Search in the bound
o[[x+Y,y+X]]?0: // If the left side point is not visited
[X,Y]=[Y,-X] // we turn left
)
if(!( // !(a||b) iff !a&&!b, known as De Morgan's laws
o[
[x+=X,y-=Y] // Move one step forward
]= // Mark current point visited
// Is there a circle intersect with current one (if
// we placed it here)?
C.some(([X,Y,R])=>Math.hypot(X-x,Y-y)<R+r,r=s**.5)||
// If no such circle, we need to place a circle here
s++-k| // Is current area equals to user input k?
// Increase the area for next circle by s++
// | do not use short-circuit evaluation
G* // Is current generation counted down to 0?
C.push([x,y,r]) // Push it to list of circles
// C.push(...) always returns positive
// So multiply by G is harmless
))
return[x,y] // Return current circle if it is asked for
}

• Wow! Just when I thought I might win this if I keep golfing. How did you do this? Mar 30, 2021 at 5:49
• You can save 3 bytes by starting with X=1: 221 bytes Mar 30, 2021 at 6:17