26
\$\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\$
10
  • \$\begingroup\$ Just to clarify, all the circles are placed on integer coordinates, correct? \$\endgroup\$ – caird coinheringaahing 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\$ – Peter Kagey Mar 28 at 19:52
  • 1
    \$\begingroup\$ @Arnauld I have different results entirely - (-46, -28) for k=14 and (4,-46) for k=15. The weird thing is about half the testcases are actually working... \$\endgroup\$ – A username Mar 29 at 8:37
  • 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\$ – Peter Kagey Mar 29 at 16:12
13
\$\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
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\$ – A username 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
7
\$\begingroup\$

JavaScript (Node.js), 417 338 331 323 321 318 316 304 303 290 283 bytes

h=(G,K,l=[],p=[],x=y=t=P=d=0,i=w=L=1)=>[...Array(5e4)].map(_=>p.push([x,y])+(d%2?y+=2-d:x+=1-d,++t<L||(t=0,L+=P,P=!P,d=++d%4)))&&[...Array(G)].map(_=>p.map(([m,n])=>l.some(([M,N,R])=>Math.hypot(M-m,N-n)<R**.5+i**.5)||l.push([m,n,i++,w]))+(w+=i=1))&&l.filter(x=>x[3]==G)[K].slice(0,2)

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.

Explanation

h=(                                      // declare function
  G,K,                                   // takes G and K
  l=[],p=[],x=y=t=P=d=0,i=w=L=1          // init some variables: l is list of circles, p is points on spiral. x, y, d, p, L, and t are used in spiral calculation, i tracks current circle size, w tracks current generation
  )=>
                                         // This whole bit generates the points on the spiral
    [...Array(5e4)].map(_=>              // Do 50k times to generate 50k points on spiral
      p.push([x,y])+                     //push current x and y to points array
      (d%2?y+=2-d:x+=1-d,        //change x or y depending on d (direction)
        ++t<L||                          //increment t (tracks how far before next turn), if t + 1 is not less than L (length of line in spiral we are currently on):
          (t=0,                          //set t to 0, 
           L+=P,P=!P                     //If p = 1, increment l, and set P to 0, else set P to 1
           ,d=++d%4)                     // then turn left.
       )
    )&&
    [...Array(G)].map(_=>                // do generation times:
      p.map(([m,n])=>                    // for each point in spiral, taking m and n using destructuring syntax
        l.some(([M,N,R])=>               // check if for each existing circle, taking M, N and R using destructuring syntax
          Math.hypot(M-m,N-N)            // check if distance between current point's center and current circle's center
          <y[2]**.5+i**.5)               // is less than sum of radii
        ||l.push([x[0],x[1],i++,w])      // if not,  add current position to list of circles.
      )+
      (w+=i=1)                           // increment w and set i to 1
    )&&                                  // finally, yield:
    l                                    // list of circles
    .filter(x=>x[3]==G)                  // only ones of correct generation
    [K]                                  // correct item (0-indexed)
    .slice(0,2)                          // only items 1 and 2 (x and y)
\$\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\$ – A username Mar 30 at 5:18
  • \$\begingroup\$ @tsh Thanks for that! \$\endgroup\$ – A username Mar 30 at 8:48
  • \$\begingroup\$ @tsh You are too good at this. \$\endgroup\$ – A username 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.