8
\$\begingroup\$

Your task is to write a program that finds the largest radius that N circles can have and still fit inside of a rectangle that is X by Y pixels large. (similar to this wikipedia article) Your program must find the largest possible radius and optimal position of these N circles so that

  1. No two circles overlap
  2. All of the circles fit inside of the rectangle.

Your program should then print this to the console:

Highest possible radius: <some_number>
Circle 1 Focus: (x, y)
Circle 2 Focus: (x, y)
...
Circle N-1 Focus: (x, y)
Circle N Focus: (x, y) 

(Obviously, you must replace some_number with the radius your program calculates, N with the number of circles you end up using, and x and y with the actual coordinates of the circle)

Lastly, it should create and save a picture with these circles drawn.

Rules:

  1. This program must run with any size of rectangle, and any number of circles and still get a valid answer. You can use command line arguments, user input, hard coded variables, or anything else you want.

  2. If any circle overlaps or does not fit entirely inside of the box, your submission is invalid.

  3. Each circle must have the same radius.

  4. Just to make this reasonable and do-able, all numbers must be precise to the 2nd decimal place.

This is code golf, so shortest program (as of 10/28/2014) wins.

\$\endgroup\$
  • 6
    \$\begingroup\$ FYI doing this optimally is not exactly easy. "Solutions (not necessarily optimal) have been computed for every N≤10,000." \$\endgroup\$ – Calvin's Hobbies Oct 23 '14 at 4:13
  • 1
    \$\begingroup\$ Would you allow a solution that iterates over every possibility? By which I mean every possible center and radius for each circle up to machine precision, not every qualitative configuration. \$\endgroup\$ – xnor Oct 23 '14 at 5:16
  • 4
    \$\begingroup\$ Not to mention that if the program must run with any number of circles, the sample output would require it to be able to produce an English name for any number. \$\endgroup\$ – Peter Taylor Oct 23 '14 at 8:41
  • 3
    \$\begingroup\$ Did you mean "to the second decimal place"? Because the hundredth seems neither very reasonable nor very doable. ;) Although, if you only want so little precision we might as well do everything in integers. We can't really plot it more accurately anyway if 1 unit corresponds to 1 pixel. \$\endgroup\$ – Martin Ender Oct 23 '14 at 18:52
  • 3
    \$\begingroup\$ This challenge is literally impossible, at least in 2014. The optimal solution to this problem is not known to mathematics, so it will be completely impossible to check whether answers are valid or not. I think it might be possible to save this with a little thought, e.g. by saying that your program becomes invalid if anyone finds a better solution for any values of x, y and N. Or just making it code-challenge, with the score based on the largest radius your program can find. But as it's written now there's no way you can possibly get any valid answers. \$\endgroup\$ – Nathaniel Oct 24 '14 at 5:16
8
\$\begingroup\$

JavaScript 782 725 characters

first post, be gentle!

The program is now called via the wrapped function. Eg: (function(e,f,g){...})(100,200,10).

function C(e,f,g,c,a,d){if(0>g-a||g+a>e||0>c-a||c+a>f)return d;for(var b in d)if(Math.sqrt(Math.pow(d[b].x-g,2)+Math.pow(d[b].y-c,2))<2*a)return d;d.push({x:g,y:c});for(b=0;b<Math.PI;)XX=Math.cos(b)*a*2+g,YY=Math.sin(b)*a*2+c,d=C(e,f,XX,YY,a,d),b+=.01;return d}
(function(e,f,g){var c=e+f,a,d;for(a=[];a.length<g;)a=d=c,a=C(e,f,a,d,c,[]),c-=.01;console.log("Highest possible radius: "+Math.round(100*c)/100);e='<svg width="'+e+'" height="'+f+'"><rect width="'+e+'" height="'+f+'" style="fill:red" />';for(var b in a)console.log("Circle "+b+" Focus: ("+Math.round(100*a[b].x)/100+", "+Math.round(100*a[b].y)/100+")"),e+='<circle cx="'+a[b].x+'" cy="'+a[b].y+'" r="'+c+'" fill="blue" />';console.log(e+"</svg>")})(400,300,13);


Test 1

(function(e,f,g){...})(200,200,4)

Highest possible radius: 49.96
Circle 1 Focus: (49.97, 49.97) 
Circle 2 Focus: (149.91, 49.97) 
Circle 3 Focus: (149.99, 149.91) 
Circle 4 Focus: (50.05, 149.91) 
<svg width="200" height="200"><rect width="200" height="200" style="fill:blue;" /><circle cx="49.97000000021743" cy="49.97000000021743" r="49.960000000217434" fill="white" /><circle cx="149.9100000006523" cy="49.97000000021743" r="49.960000000217434" fill="white" /><circle cx="149.98958489212322" cy="149.90996831285986" r="49.960000000217434" fill="white" /><circle cx="50.04958489168835" cy="149.90996831285986" r="49.960000000217434" fill="white" /></svg>

Obviously we would expect the radius to be exactly 50, but for reasons discussed in the question's comments, I couldn't reasonably make it happen. The SVG looks like this...

200 200 4


Test 2

(function(e,f,g){...})(100,400,14)

Highest possible radius: 26.55
Circle 1 Focus: (26.56, 26.56) 
Circle 2 Focus: (79.68, 26.56) 
Circle 3 Focus: (132.8, 26.56) 
Circle 4 Focus: (185.92, 26.56) 
Circle 5 Focus: (239.04, 26.56) 
Circle 6 Focus: (292.16, 26.56) 
Circle 7 Focus: (345.28, 26.56) 
Circle 8 Focus: (372.63, 72.1) 
Circle 9 Focus: (319.52, 73.25) 
Circle 10 Focus: (265.47, 72.64) 
Circle 11 Focus: (212.35, 73.25) 
Circle 12 Focus: (159.23, 72.64) 
Circle 13 Focus: (106.11, 73.25) 
Circle 14 Focus: (52.99, 72.64) 
<svg width="400" height="100"><rect width="400" height="100" style="fill:blue;" /><circle cx="26.560000000311106" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="79.68000000093332" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="132.80000000155553" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="185.92000000217774" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="239.04000000279996" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="292.16000000342217" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="345.2800000040444" cy="26.560000000311106" r="26.550000000311105" fill="white" /><circle cx="372.6271770491687" cy="72.09972230654316" r="26.550000000311105" fill="white" /><circle cx="319.5195599732359" cy="73.24663493712801" r="26.550000000311105" fill="white" /><circle cx="265.47097406711805" cy="72.63752174440503" r="26.550000000311105" fill="white" /><circle cx="212.35454341475625" cy="73.25330971030218" r="26.550000000311105" fill="white" /><circle cx="159.23097406587362" cy="72.63752174440503" r="26.550000000311105" fill="white" /><circle cx="106.11454341351183" cy="73.25330971030218" r="26.550000000311105" fill="white" /><circle cx="52.99097406462921" cy="72.63752174440503" r="26.550000000311105" fill="white" /></svg>

And the SVG looks like this...

enter image description here


Test 3

(function(e,f,g){...})(400,400,3)

Highest possible radius: 101.68
Circle 1 Focus: (101.69, 101.69) 
Circle 2 Focus: (298.23, 153.98) 
Circle 3 Focus: (154.13, 298.19) 
<svg width="400" height="400"><rect width="400" height="400" style="fill:blue;" /><circle cx="101.69000000059772" cy="101.69000000059772" r="101.68000000059772" fill="white" /><circle cx="298.2343937547503" cy="153.97504264473156" r="101.68000000059772" fill="white" /><circle cx="154.13153961740014" cy="298.19269546075066" r="101.68000000059772" fill="white" /></svg>

And the SVG looks like this...

enter image description here

They aren't all pretty.


How it works

Ungolfed code below. This program has two assumptions:

  1. One circle will always be in the corner. This seems like a pretty safe bet.
  2. Every circle will always be touching another circle. I don't see why they wouldn't be.

The program starts by calculating a large radius based on the box dimensions. It then tries to fit one circle in the corner of the box. If that circle fits, it extends a diameter line from that circle and tries to create a circle at the end of the line. If the new circle fits, another line will be extended from the new circle. If it doesn't fit, the line will swing 360 degrees, checking for open spaces. If the box fills up before the desired number of circles are created, the radius is reduced and it all starts over again.


Ungolfed Code (snippet)

// this functions attempts to build a circle
// at the given coords. If it works, it will
// spawn additional circles.
function C(x, y, X, Y, r, cc){

	// if this circle does not fit in the rectangle, BAIL
	if(X-r < 0 || X+r > x || Y-r < 0 || Y+r > y)
		return cc;
	
	// if this circle is too close to another circle, BAIL
	for(var c in cc){
		if( Math.sqrt(Math.pow(cc[c].x - X, 2) + Math.pow(cc[c].y - Y, 2)) < (r*2) )
			return cc;
	}
	
	// checks passed so lets call this circle valid and add it to stack
	cc.push({"x": X, "y": Y});
	
	// now rotate to try to find additional spots for circles
	var a = 0; // radian for rotation
	while(a < Math.PI){
		XX = Math.cos(a)*r*2 + X;
		YY = Math.sin(a)*r*2 + Y;
		cc = C(x, y, XX, YY, r, cc);
		a += .01; // CHANGE FOR MORE OR LESS PRECISION
	}
	
	return cc;
}

// this function slowly reduces the radius
// and checks for correct solutions
// also prints svg graphic code

(function B(x, y, n){

	var r = x + y; // pick a big radius
	var X, Y; // these are the coords of the current circle. golf by combining this with `var r..`?
	var cc = []; // array of coordinates of the circles
	
	// while we cant fit n circles, reduce the radius and try again
	while(cc.length < n){
		X = Y = r;
		cc = C(x, y, X, Y, r, []);
		r-=.01; // CHANGE FOR MORE OR LESS PRECISION
	}
	
	console.log('Highest possible radius: ' + Math.round(r*100)/100);
	var s = '<svg width="' + x + '" height="' + y + '"><rect width="' + x + '" height="' + y + '" style="fill:red" />';
	for(var c in cc){
		console.log('Circle '+c+' Focus: (' + Math.round(cc[c].x*100)/100 + ', ' + Math.round(cc[c].y*100)/100 + ')');
		s += '<circle cx="' + cc[c].x + '" cy="' + cc[c].y + '" r="' + r + '" fill="blue" />';
	}
	s += '</svg>';
	console.log(s);
	document.write(s);
})(150, 150, 5);

\$\endgroup\$

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.