Placing circles along a square spiral

Question

In this code golf challenge, you'll be computing the placement of (open) 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 code-golf 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

Answer 1

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}$$

Answer 2

JavaScript (ES2020), 417 338 331 323 321 318 316 304 303 290 283 273 269 261 257 252 247 244 237 234 238 234 207 206 205 200 194 193 186 182 183 182 bytes

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

Try It Online?

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 1-indexed. -1 byte thanks to ophact.

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

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
    G--;                     // Looping G times...
  )                          
    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[G] = [];         // Add an empty list to l, which gets assigned to X.
      t--,
      K << 3 * G >= i;       // Every generation, search for 8x less circles (probably enough, can always be increased)              
      d % 2 ?                // If moving vertically
        y += 2 - d % 4       // Change y
      : x += 1 - d % 4,      // Else change x
      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++] = [x,y]               // Increment i (radius of circle we're trying to place), and append the coordinate to X
                                 // The above is returned when the loop ends because i is too large.
}

Answer 3

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!

• -3 bytes by Arnauld

---

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
}