29
\$\begingroup\$

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) -> ...

Example of a square spiral.


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.

Process for ten generations

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)   | orange
 9 |  2 | (-25, 4)   | orange
 9 |  3 | (17, -27)  | orange
\$\endgroup\$
7
  • \$\begingroup\$ Just to clarify, all the circles are placed on integer coordinates, correct? \$\endgroup\$ Mar 28 at 19:45
  • \$\begingroup\$ @ChartZBelatedly—that's right, I'll emphasize that in the post. \$\endgroup\$ Mar 28 at 19:45
  • 1
    \$\begingroup\$ Out of curiosity, is this related to a problem of broader mathematical interest or just a fun puzzle? \$\endgroup\$
    – Jonah
    Mar 28 at 19:50
  • 3
    \$\begingroup\$ @Jonah—just a puzzle! But I did publish an OEIS sequence back in 2017 about a related problem: A289523. \$\endgroup\$ Mar 28 at 19:52
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Mar 29 at 16:12
8
\$\begingroup\$

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
}
\$\endgroup\$
10
  • \$\begingroup\$ Wow! Just when I thought I might win this if I keep golfing. How did you do this? \$\endgroup\$
    – emanresu A
    Mar 30 at 5:49
  • \$\begingroup\$ @Ausername added an explain to it. \$\endgroup\$
    – tsh
    Mar 30 at 6:06
  • \$\begingroup\$ @Ausername I didn't read your codes yet, since my brain give up to understand any golfed codes written by others with more than 200 or 300 bytes, automatically. \$\endgroup\$
    – tsh
    Mar 30 at 6:13
  • \$\begingroup\$ You can save 3 bytes by starting with X=1: 221 bytes \$\endgroup\$
    – Arnauld
    Mar 30 at 6:17
  • \$\begingroup\$ @Arnauld Yes? but... I couldn't understand why it yield same results. \$\endgroup\$
    – tsh
    Mar 30 at 6:28
14
\$\begingroup\$

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

\$\endgroup\$
0
7
\$\begingroup\$

JavaScript (Node.js), 417 338 331 323 321 318 316 304 303 290 283 273 269 261 257 252 247 244 237 234 238 234 207 206 bytes

G=>K=>{for(l=[],w=1;w<=G;)for(x=y=t=d=_=0,i=L=1,X=l[w++]=[];++_<5e4;++t<L||(t=0,L+=d++%2,d%=4))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:x+=1-d;return X[K]}

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 0-indexed.

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

Explanation

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
      t =                    // t = distance through current leg of the spiral
      d =                    // d = direction of current leg of spiral
      _ = 0,                 // _ = meaningless counter, initialise all of these to 0 
      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.
      ++_ < 5e4;             // Repeat 50k times...
      ++t < L || (           // Increment t, if it's greater than l...
        t=0,                 // Set t to 0
        L+=d++%2,            // Change length
        d%=4                 // Turn clockwise
      )
    )
    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                 // Change y
    : x += 1 - d;                // Else change x
  return X[K]                    // Output the correct circle.
}
\$\endgroup\$
8
  • 1
    \$\begingroup\$ 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[0]-x[0])**2+(y[1]-x[1])**2)**.5<y[2]**.5+i**.5?k=0:0,k=1)+(k&&(l.push([x[0],x[1],i,w]),i++)))+(w++,i=1))?l.filter(x=>x[3]==G)[K-1].slice(0,2):0 \$\endgroup\$
    – Neil
    Mar 29 at 18:48
  • \$\begingroup\$ Not sure why ((y[0]-x[0])**2+(y[1]-x[1])**2)**.5 isn't the same as Math.hypot(y[0]-x[0],y[1]-x[1]) though. \$\endgroup\$
    – Neil
    Mar 29 at 18:49
  • \$\begingroup\$ @Neil Thanks for all of that! Managed to golf it down a bit more. You're right, ((y[0]-x[0])**2+(y[1]-x[1])**2)**.5 is the same as Math.hypot(y[0]-x[0],y[1]-x[1]). \$\endgroup\$
    – emanresu A
    Mar 30 at 5:18
  • \$\begingroup\$ @tsh Thanks for that! \$\endgroup\$
    – emanresu A
    Mar 30 at 8:48
  • \$\begingroup\$ @tsh You are too good at this. \$\endgroup\$
    – emanresu A
    Mar 30 at 8:51

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.