# 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×8 rectangular arrangement.

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≤x≤W and 0≤y≤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 < x < width and 0 < y < 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


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

1. The number of stars to put in the canton.
2. The width of the canton. (Must accept floating-point values.)
3. 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 & 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. • @primo: How do you figure that? My example has a mean distance to the nearest star of 0.289, whereas placing all 5 points in the center has a MDNS of 0.561. May 30 '14 at 12:44 • You may disregard my previous commment. I misread mean distance from every point on the canton to the nearest star, as mean distance from every star to the nearest star. May 30 '14 at 13:42 • Feel free to include jsfiddle.net/nf2mk2gr as a Stack Snippet in the question to check the output of answers, if it meets your approval. It displays the mean distance based on an N by N grid, with N progressively increasing the longer you wait. (It was written specifically for this question.) May 14 '15 at 0:50 ## 3 Answers # 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;
}

function resizeCanvas() {
cantonWidth = parseFloat($('#width').val()); cantonHeight = parseFloat($('#height').val());
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 < cantonHeight) { horizontalStars = shortSide; verticalStars = longSide; } else { horizontalStars = longSide; verticalStars = shortSide; } horizontalSpacing = cantonWidth / horizontalStars; verticalSpacing = cantonHeight / verticalStars; for (var i = 0; i < 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 < 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 > 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] < 0) star[0] = 0;
if (star[0] > cantonWidth) star[0] = cantonWidth;
if (star[1] < 0) star[1] = 0;
if (star[1] > cantonHeight) star[1] = cantonHeight;

drawStars();
updateOutputText();
}

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

function updateOutputText() {
starText = '';
for (var i = 0; i < stars.length; i++) {
starText += stars[i][0] + ', ' + stars[i][1] + '\n';
}
$('#coordinateList').text(starText); } function randomPoints(n) { pointsToReturn = []; for (i = 0; i < n; i++) { x = xorshift() * cantonWidth; y = xorshift() * cantonHeight; pointsToReturn.push([x, y]); } return pointsToReturn; } function xorshift() { rng_t = rng_x ^ (rng_x << 11); rng_x = rng_y; rng_y = rng_z; rng_z = rng_w; rng_w = rng_w ^ (rng_w >> 19) ^ rng_t ^ (rng_t >> 8); result = rng_w / 2147483648 return result } function nearestStar(x, y) { var distances = []; for (var i = 0; i < stars.length; i++) { star = stars[i]; distances.push(distance(x, y, star[0], star[1])); } minimum = Infinity; for (i = 0; i < distances.length; i++) { if (distances[i] < 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 < 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; } <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script> <input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'>stars <br> <input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'>width <br> <input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'>height <br> <button type='button' onclick='resetStars()'>Reset Stars</button> <button type='button' onclick='arrange()'>Arrange Stars</button> <button type='button' onclick='stop()'>Stop</button> <textarea id='stepsRemaining' rows='1' readonly></textarea> <br> <canvas id='canton' width='494' height='350'></canvas> <br> <textarea id='coordinateList' rows='50' cols='40' readonly></textarea> # 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  • After running your animation with various numbers of stars, it seems like it has a tendency to put stars close to the edges of the box. However, not knowing the true optimum arrangement, I can't tell whether this is a bug or a feature. May 15 '15 at 5:54 • @dan04 nor me - I have an idea of why it happens though. The stars near the edge are too close to it for there to be a significant probability of them moving towards it (stars mostly move towards the most isolated points, not points nearby). But they can still move towards the edge indirectly, by alternating between moving towards two distant points near the edge, resulting in a zigzag path. I suspect this means that it is necessary to have stars near the edges, but I'm looking forward to seeing another approach to see if that shares the bug/feature... May 15 '15 at 14:56 • @dan04 my second answer seems to show that the stars don't need to be as near to the edges as I thought, and gives better results than my first answer. Working directly with the mean rather than indirectly through the maximum turns out to be more effective. May 16 '15 at 22:20 Here's a simple example. It always arranges the stars into a rectangular grid, and optimizes it by choosing the factorization in which the grid cells are as close to square as possible. It works great when the number of stars has a divisor close to its square root, and pessimally when the number of stars is prime. from __future__ import division import math import sys def divisors(n): """ Return all divisors of n (including n itself) as a set. """ result = {1, n} # Use +2 instead of +1 to allow for floating-point error. for i in range(2, int(math.sqrt(n)) + 2): if n % i == 0: result.add(i) result.add(n // i) return result def squareness(width, height): """ Given the dimensions of a rectangle, return a value between 0 and 1 (1 iff width == height) measuring how close it is to being a square. """ if width and height: return min(width / height, height / width) else: return 0.0 def star_grid(num_stars, width, height): """ Return the factors (x, y) of num_stars that optimize the mean distance to the nearest star. """ best_squareness = 0.0 best_dimensions = (None, None) for nx in divisors(num_stars): ny = num_stars // nx sq = squareness(width / nx, height / ny) if sq > best_squareness: best_squareness = sq best_dimensions = (nx, ny) return best_dimensions def star_coords(num_stars, width, height): """ Return a list of (x, y) coordinates for the stars. """ nx, ny = star_grid(num_stars, width, height) for ix in range(nx): x = (ix + 0.5) * width / nx for iy in range(ny): y = (iy + 0.5) * height / ny yield (x, y) def _main(argv=sys.argv): num_stars = int(argv[1]) width = float(argv[2]) height = float(argv[3]) for coord in star_coords(num_stars, width, height): print('%g,%g' % coord) if __name__ == '__main__': _main()  # Output for 50 stars (width = 1.4, height = 1.0) A 10×5 rectangle. 0.07,0.1 0.07,0.3 0.07,0.5 0.07,0.7 0.07,0.9 0.21,0.1 0.21,0.3 0.21,0.5 0.21,0.7 0.21,0.9 0.35,0.1 0.35,0.3 0.35,0.5 0.35,0.7 0.35,0.9 0.49,0.1 0.49,0.3 0.49,0.5 0.49,0.7 0.49,0.9 0.63,0.1 0.63,0.3 0.63,0.5 0.63,0.7 0.63,0.9 0.77,0.1 0.77,0.3 0.77,0.5 0.77,0.7 0.77,0.9 0.91,0.1 0.91,0.3 0.91,0.5 0.91,0.7 0.91,0.9 1.05,0.1 1.05,0.3 1.05,0.5 1.05,0.7 1.05,0.9 1.19,0.1 1.19,0.3 1.19,0.5 1.19,0.7 1.19,0.9 1.33,0.1 1.33,0.3 1.33,0.5 1.33,0.7 1.33,0.9  # Javascript - move a star randomly if mean distance is reduced (with an animation of the process) This doesn't give such a busy animation as my first answer, having long periods with no movement as potential rearrangements are tested and rejected. However, the final result has a lower mean distance, so this method is an improvement. The approach is still very simple: • Choose a star at random • Move it a random distance in a random direction • If the mean distance is reduced, keep the new position This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. The random choice of distance to move is biased towards smaller distances, so progress is in small alterations interspersed with the occasional larger jump. Each step takes longer than in my first answer, as measuring the mean distance is a slow process requiring sampling the entire canton. 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) / 16;
}

function resizeCanvas() {
cantonWidth = parseFloat($('#width').val()); cantonHeight = parseFloat($('#height').val());
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 < cantonHeight) { horizontalStars = shortSide; verticalStars = longSide; } else { horizontalStars = longSide; verticalStars = shortSide; } horizontalSpacing = cantonWidth / horizontalStars; verticalSpacing = cantonHeight / verticalStars; for (var i = 0; i < 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');
var points = randomPoints(numberOfPoints);
currentMean = meanDistance(stars, points);
potentialStars = shiftedStars(stepSize);
potentialMean = meanDistance(potentialStars, points);
if (potentialMean < currentMean) {
stars = potentialStars;
}
drawStars();
updateOutputText();

if (maxSteps > 0) {
timeoutId = setTimeout(adjustStars, 10, stepSize * 0.999, maxSteps - 1, numberOfPoints);
}
}

function shiftedStars(stepSize) {
shifted = [];
chosenOne = Math.floor(xorshift() * stars.length);
for (i = 0; i < stars.length; i++) {
star = stars[i];
x = star[0];
y = star[1];
if (i === chosenOne) {
for (n = 0; n < 10; n++) {
x += xorshift() * stepSize;
x -= xorshift() * stepSize;
y += xorshift() * stepSize;
y -= xorshift() * stepSize;
}
if (x < 0) x = 0;
if (x > cantonWidth) x = cantonWidth;
if (y < 0) y = 0;
if (y > cantonHeight) y = cantonHeight;
}
shifted.push([x, y]);
}
return shifted;
}

function meanDistance(arrayOfStars, arrayOfPoints) {
var totalDistance = 0;
for (i = 0; i < arrayOfPoints.length; i++) {
point = arrayOfPoints[i];
x = point[0];
y = point[1];
totalDistance += nearestStarDistance(x, y, arrayOfStars);
}
}

function randomPoints(numberOfPoints) {
var arrayOfPoints = [];
for (i = 0; i < numberOfPoints; i++) {
x = xorshift() * cantonWidth;
y = xorshift() * cantonHeight;
arrayOfPoints.push([x, y]);
}
return arrayOfPoints;
}

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

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

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

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 < stars.length; i++) {
star = stars[i];
x = star[0];
y = star[1];
drawStar(x, y);
}
}

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

# Output for 50 stars

(width = 1.4, height = 1.0)

Mean distance estimated at 0.06402754713808706.

Coordinates:

0.08147037630270487, 0.07571240182553095
0.24516777356538358, 0.0803538189052793
0.431021735247462, 0.07821284835132788
0.6001163609128221, 0.08278495286739646
0.7668077034213632, 0.0821321119375313
0.941333266969696, 0.08040530195264808
1.1229190363750599, 0.07255685332834291
1.3074771164489858, 0.07681674948141588
0.09227450444336446, 0.2257047798057907
0.33559513774978766, 0.20668611954667682
0.5182463448452704, 0.23841239342827816
0.6630614113293541, 0.26097114328053417
0.821886619004045, 0.23577904321258844
1.012597304977012, 0.23308200382761057
1.174938874706673, 0.22593017096601203
1.3285181935709358, 0.24024108928169902
0.0746772556909648, 0.3920030109869904
0.23006559905554042, 0.3204287339854068
0.4086004105498357, 0.3507788129168045
0.5669847710831315, 0.4371913211100495
0.7399474422203116, 0.41599441829489137
0.9099913571857917, 0.36933063808924294
1.1170137101288482, 0.3905679602615213
1.3037811235560612, 0.3979526346564911
0.09290206345982034, 0.5678420747594305
0.23463227399157258, 0.47552307265325633
0.4042403660145938, 0.5030345851947539
0.6611151741402685, 0.5918138006294138
0.8237963249937061, 0.5663224022272697
0.9812774216782155, 0.5032518469083094
1.146386501309064, 0.570255729516661
1.3185563715676663, 0.5571870810112576
0.07541940949872694, 0.7356649763259809
0.2877585652075202, 0.6321535875762999
0.4952646673275116, 0.6343336480073624
0.6965646728710738, 0.9178076185211137
0.7903485281657828, 0.7508031981325222
0.9774998621426763, 0.6683301268754337
1.1539480102558823, 0.7513836972857155
1.3177199931376755, 0.7245296168327016
0.22215183098388988, 0.7769843436963862
0.4048364942297627, 0.7779653803681718
0.5021290208205218, 0.9254525763987298
0.6058821167972933, 0.7683130432395833
0.8777330967719849, 0.9201076171801651
0.9894820530574747, 0.8172934111543102
1.1143371956097312, 0.9265012354173626
1.3045771339439551, 0.9069856484512913
0.0930066325438706, 0.9157592790749175
0.2959676633891297, 0.9251379492518523