The Star-Spangled Code Challenge The flag of the United States of America contains, in its canton, 50 stars, representing the 50 states.



In the past, when there were fewer states, there were of course fewer stars, and they were arranged differently.  For example, from 1912-1959 (after the admission of New Mexico and Arizona but before Alaska), there were 48 stars in a 6&times;8 rectangular arrangement.



The 37-star flag used from 1867-1877 (after the admission of Nebraska but before Colorado) had an asymmetric star pattern.



In case a 51st state is added in the future, the Army Institute of Heraldry has already developed a preliminary design for a new flag.



But there's no general algorithm for arranging the stars, so let's make one!

The challenge

Write a program that will, for a given number of stars to place in the canton (blue part) of a US flag, output optimal coordinates at which to place those stars.  The coordinate system is defined with the canton [not the flag as a whole] with 0&le;x&le;W and 0&le;y&le;H.

For the purpose of this challenge, an “optimal” arrangement is defined as one that minimizes the mean (Euclidean) distance between a point in the canton and the center of the nearest star.

A straightforward (if maybe suboptimal) algorithm to approximate this value is:

def mean_distance_to_nearest_star(stars, width, height, point_density=100):
   """
   Approximate the mean distance between a point in the rectangle
   0 &lt; x &lt; width and 0 &lt; y &lt; height, and the nearest point in stars.

   stars -- list of (x, y) points
   width, height -- dimensions of the canton
   """
   total = 0.0
   nx = round(width * point_density)
   ny = round(height * point_density)
   for ix in range(nx):
       x = (ix + 0.5) * width / nx
       for iy in range(ny):
          y = (iy + 0.5) * width / ny
          min_dist = float('inf')
          for sx, sy in stars:
              min_dist = min(min_dist, math.hypot(x - sx, y - sy))
          total += min_dist
   return total / (nx * ny)


Your program shall take three command-line arguments (not counting the program name itself):


The number of stars to put in the canton.
The width of the canton.  (Must accept floating-point values.)
The height of the canton.  (Must accept floating-point values.)


(If your preferred programming language doesn't support command-line arguments, do something reasonably equivalent, and document it in your answer.)

The output should consist of comma-separated X and Y values, one to a line.  (Order of the points doesn't matter.)

For example:

~$ flagstar 5 1.4 1.0
0.20,0.20
0.20,0.80
0.70,0.50
1.20,0.20
1.20,0.80


Additional rules &amp; notes


I have the right to close loopholes in the rules at any time.
Deadline for answers is Friday, July 4 at 24:00 CDT (UTC-05:00).  Due to lack of answers, the deadline has been extended.  TBA.
Include in your answer:


Your program's code
An explanation of how it works
Its output with the command-line arguments 50 1.4 1.0

Your program must run within a reasonable amount of time: At most 5 min on a typical PC.  I won't be ultra-strict about this, but will disqualify your program if it takes hours.
Your program must be deterministic, i.e., always give exactly the same output for the same arguments.  So, don't depend on time() or rand().  Monte Carlo methods are OK as long as you roll your own PRNG.
Only the center points of the stars matter.  Don't worry about trying to avoid overlap or anything like that.


Scoring


Minimize the mean distance from a point in the canton to the nearest star.  (See above.)
You may be scored based on any historical US flags, between 13 and 50 stars.  The exact algorithm for weighting scores into a single ranking will be posted later.
In case of a tie, the winner will be chosen by number of net upvotes.
I will probably post a program of my own, but will exclude myself from being eligible for the checkmark.
Javascript - move stars towards most isolated point

(with an animation of the process)

The approach is very simple:


choose a large number of random points
find the nearest star to each
choose the point for which the nearest star is most distant
move that star nearer to that point


This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. This reduces the maximum distance from a point to the nearest star, indirectly reducing the mean distance from a point to the nearest star.

As required by the question, this does not use the built in random function, instead using xorshift.

Much of the code covers set up and animation - the part that applies the algorithm is the function adjustStars.

Code

You can watch the process in progress in the Stack Snippet below.



stars = [];
timeoutId = 0;

resetRandomNumberGenerator();

function resetRandomNumberGenerator() {
  rng_x = 114; // Numbers for the random number generator.
  rng_y = 342;
  rng_z = 982;
  rng_w = 443;
}

$(document).ready(function() {
  c = document.getElementById('canton');
  ctx = c.getContext('2d');
  resizeCanvas();
});

function stop() {
  clearTimeout(timeoutId);
}

function arrange() {
  clearTimeout(timeoutId);
  resetStars();
  resetRandomNumberGenerator();
  maxStepSize = Math.min(cantonWidth, cantonHeight) / 4;
  adjustStars(maxStepSize, 8000, 10000);
}

function resizeCanvas() {
  cantonWidth = parseFloat($('#width').val());
  cantonHeight = parseFloat($('#height').val());
  starRadius = cantonHeight / 20;
  document.getElementById('canton').width = cantonWidth;
  document.getElementById('canton').height = cantonHeight;
  ctx.fillStyle = 'white';
  resetStars();
}

function resetStars() {
  stop();
  stars = [];
  population = parseInt($('#stars').val(), 10);
  shortSide = Math.floor(Math.sqrt(population));
  longSide = Math.ceil(population / shortSide);
  if (cantonWidth &lt; cantonHeight) {
    horizontalStars = shortSide;
    verticalStars = longSide;
  } else {
    horizontalStars = longSide;
    verticalStars = shortSide;
  }
  horizontalSpacing = cantonWidth / horizontalStars;
  verticalSpacing = cantonHeight / verticalStars;
  for (var i = 0; i &lt; population; i++) {
    x = (0.5 + (i % horizontalStars)) * horizontalSpacing;
    y = (0.5 + Math.floor(i / horizontalStars)) * verticalSpacing;
    stars.push([x, y]);
  }
  drawStars();
  updateOutputText();
}

function adjustStars(stepSize, maxSteps, numberOfPoints) {
  $('#stepsRemaining').text(maxSteps + ' steps remaining');
  points = randomPoints(numberOfPoints);
  mostIsolatedPoint = 0;
  distanceToNearestStar = 0;
  for (var i = 0; i &lt; numberOfPoints; i++) {
    point = points[i];
    x = point[0];
    y = point[1];
    star = stars[nearestStar(x, y)];
    d = distance(x, y, star[0], star[1]);
    if (d &gt; distanceToNearestStar) {
      distanceToNearestStar = d;
      mostIsolatedPoint = i;
    }
  }
  point = points[mostIsolatedPoint];
  x = point[0];
  y = point[1];

  starToMove = nearestStar(x, y);

  star = stars[starToMove];
  separationX = x - star[0];
  separationY = y - star[1];
  if (separationX || separationY) {
    hypotenuse = distance(x, y, star[0], star[1]);
    currentStep = Math.min(stepSize, hypotenuse / 2);
    deltaX = currentStep * separationX / hypotenuse;
    deltaY = currentStep * separationY / hypotenuse;
    star[0] += deltaX;
    star[1] += deltaY;
    if (star[0] &lt; 0) star[0] = 0;
    if (star[0] &gt; cantonWidth) star[0] = cantonWidth;
    if (star[1] &lt; 0) star[1] = 0;
    if (star[1] &gt; cantonHeight) star[1] = cantonHeight;

    drawStars();
    updateOutputText();
  }

  if (maxSteps &gt; 0) {
    timeoutId = setTimeout(adjustStars, 10, stepSize * 0.9992, maxSteps - 1, numberOfPoints);
  }
}

function updateOutputText() {
  starText = '';
  for (var i = 0; i &lt; stars.length; i++) {
    starText += stars[i][0] + ', ' + stars[i][1] + '\n';
  }
  $('#coordinateList').text(starText);
}

function randomPoints(n) {
  pointsToReturn = [];
  for (i = 0; i &lt; n; i++) {
    x = xorshift() * cantonWidth;
    y = xorshift() * cantonHeight;
    pointsToReturn.push([x, y]);
  }
  return pointsToReturn;
}

function xorshift() {
  rng_t = rng_x ^ (rng_x &lt;&lt; 11);
  rng_x = rng_y;
  rng_y = rng_z;
  rng_z = rng_w;
  rng_w = rng_w ^ (rng_w &gt;&gt; 19) ^ rng_t ^ (rng_t &gt;&gt; 8);
  result = rng_w / 2147483648
  return result
}

function nearestStar(x, y) {
  var distances = [];
  for (var i = 0; i &lt; stars.length; i++) {
    star = stars[i];
    distances.push(distance(x, y, star[0], star[1]));
  }
  minimum = Infinity;
  for (i = 0; i &lt; distances.length; i++) {
    if (distances[i] &lt; minimum) {
      minimum = distances[i];
      nearest = i;
    }
  }
  return nearest;
}

function distance(x1, y1, x2, y2) {
  var x = x2 - x1;
  var y = y2 - y1;
  return Math.sqrt(x * x + y * y);
}

function drawStars() {
  ctx.clearRect(0, 0, cantonWidth, cantonHeight);
  for (i = 0; i &lt; stars.length; i++) {
    star = stars[i];
    x = star[0];
    y = star[1];
    drawStar(x, y);
  }
}

function drawStar(x, y) {
  ctx.beginPath();
  ctx.moveTo(x, y - starRadius);
  ctx.lineTo(x - 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.lineTo(x + 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x - 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x + 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.fill();
}
canvas {
  margin: 0;
  border: medium solid gray;
  background-color: blue;
}
&lt;script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"&gt;&lt;/script&gt;
&lt;input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'&gt;stars
&lt;br&gt;
&lt;input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'&gt;width
&lt;br&gt;
&lt;input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'&gt;height
&lt;br&gt;
&lt;button type='button' onclick='resetStars()'&gt;Reset Stars&lt;/button&gt;
&lt;button type='button' onclick='arrange()'&gt;Arrange Stars&lt;/button&gt;
&lt;button type='button' onclick='stop()'&gt;Stop&lt;/button&gt;
&lt;textarea id='stepsRemaining' rows='1' readonly&gt;&lt;/textarea&gt;
&lt;br&gt;
&lt;canvas id='canton' width='494' height='350'&gt;&lt;/canvas&gt;
&lt;br&gt;
&lt;textarea id='coordinateList' rows='50' cols='40' readonly&gt;&lt;/textarea&gt;




Output for 50 stars

(width = 1.4, height = 1.0)

Mean distance estimated at 0.0655106697162357.

Coordinates:

0.028377044205135808, 0.2128159150679491
0.10116766857540277, 0.05156676609341312
0.2903566419069437, 0.07216263690037035
0.49154061258041604, 0.004436102736309105
0.6930026352073071, 0.07060477929576484
1.0988644764108417, 0.022979778480838074
1.1735677936511582, 0.18600858289592742
1.3056806950504931, 0.062239869036660435
0.3967626880807638, 0.24483447327177033
0.27004118129346155, 0.40467589936498805
0.4996665039421278, 0.13023282430440133
0.5148978532656602, 0.6161298793146592
0.5907056537744844, 0.2614323599301046
0.8853042432872087, 0.048123917861564044
0.7753680330575412, 0.22938793622044834
1.365432954694329, 0.2355377720528128
0.1985172068244217, 0.23551298706793927
0.4477558465270544, 0.4170264112485973
0.6084424566752479, 0.7764909501169484
0.6099528761580699, 0.4395002434593519
0.9506038166406011, 0.34903243854585914
1.1898331497634231, 0.5756784243472182
1.0933574395540542, 0.46422120794648786
1.1516574254138159, 0.2930213338333888
0.07646053006349718, 0.40665000611360175
0.0634456093015551, 0.5853189455014883
0.3470036636019768, 0.5938838331082922
0.7591083341283029, 0.4005456925638841
0.9745306853981277, 0.184624209972443
1.3552011948311598, 0.549607060691302
1.3334000268566828, 0.7410204535471169
1.2990417572304487, 0.39571229988825735
0.05853941030364222, 0.7734808757471414
0.19396697551982484, 0.5678753467094985
0.7103231124251072, 0.5955041661956884
0.6168410756137566, 0.948561537739087
0.8967624790188228, 0.5368666961690878
0.9751229155529001, 0.8323724819557795
0.9987127931392165, 0.652902038374714
1.3231032600971289, 0.9164326184290812
0.20785221980162555, 0.7566700629874374
0.3987967842137651, 0.7678025218448816
0.44395949605458546, 0.9137553802571048
0.775611700149756, 0.9029717946067138
0.806442448003616, 0.7328147396477286
0.9481952441521928, 0.9872963855418118
1.1528689317425114, 0.9346775634274639
1.1651295140721658, 0.7591158327925681
0.09316709042512515, 0.934205211493484
0.2769325337580081, 0.9341145493466471