Anytime there's discussion of adding states to the United States, splitting states, or combining states, I usually start wondering about the U.S. flag and a new arrangements of stars. Currently the flag has 50 stars, one for each state, with an arrangement that looks like this:

If states combine and the flag needs fewer than 50 stars, an arrangement from a historical flag could be adopted, unless the needed number of stars is 47, 42, 41, 40, 39, 22, 19, 18, 17, 16, 14, or anything below 13, counts for which there have never been official flags. If more states are added, Wikipedia lists possible designs for up to 55 states.

I'm curious to find an algorithm that generates suitable designs for *any number* of stars. Here's a breakdown of the past and possible structures for 48–55 stars:

Stars | Overlapping grids |
---|---|

48 | 8×6 |

49 | 7×4, 7×3 |

50 | 6×5, 5×4 |

51 | 9×3, 8×3 |

52 | 7×4, 6×4 |

53 | 8×4, 7×3 |

54 | 9×6 |

55 | 9×3, 8×4 - 4 corners |

The general design priorities seem fairly evident:

- Don't use grids that are too wide or too square.
- If the number of stars can be factored into two whole numbers, use one grid.
- If the number of stars can be decomposed into two grids whose number of rows differ from each other by no more than one and whose number of columns differ from each other by no more than one, then use two overlapping grids.
- If the number of stars can be decomposed into two grids whose number of rows differ by one, whose number of columns differ by one, and whose total number of stars is four more than the desired number of stars, then omit the corner stars from the taller grid.

Here are functions to calculate arrangements under rules #2, #3, and #4, each of which implements rule #1:

```
(defn one-grid-arrangement [stars]
(loop [m (int (Math/sqrt stars))]
(when-not (zero? m)
(let [n (/ stars m)]
(if (and (= n (int n))
(< 1 (/ n m) 2))
[[n m]]
(recur (dec m)))))))
```

```
(defn two-grid-arrangement [stars]
(first
(for [n1 (range 2 (* 2 (int (Math/sqrt stars))))
m1 (range 2 n1)
n2 [n1 (dec n1)]
m2 [m1 (dec m1)]
:when (and (= stars (+ (* n1 m1) (* n2 m2)))
(< 1 (/ n1 m1) 5)
(< 1 (/ n2 m2) 5))]
[[n1 m1] [n2 m2]])))
```

```
(defn omitted-corners-arrangement [stars]
(first
(for [n1 (range 2 (* 2 (int (Math/sqrt stars))))
m1 (range 2 n1)
:let [n2 (dec n1)
m2 (inc m1)]
:when (and (= stars (- (+ (* n1 m1) (* n2 m2)) 4))
(< 1.5 (/ n1 m1) 5)
(< 1.5 (/ n2 m2) 5))]
[[n1 m1] [n2 m2 :omit-corners]])))
```

We'll pick the first arrangement that works:

```
(def arrangement (some-fn one-grid-arrangement
two-grid-arrangement
omitted-corners-arrangement))
```

Let's confirm the arrangements are what we expect:

`(map (juxt identity arrangement) (range 48 56))`

`([48 [[8 6]]] [49 [[7 4] [7 3]]] [50 [[6 5] [5 4]]] [51 [[9 3] [8 3]]] [52 [[7 4] [6 4]]] [53 [[8 4] [7 3]]] [54 [[9 6]]] [55 [[9 3] [8 4 :omit-corners]]])`

With the calculations working, let's see how the stars on the flag might look as we scale up to 100 stars:

These three simple design rules scale surprisingly far, though they don't allow for all possible counts between 50 and 100. They're unable to find acceptable patterns for 58, 61, 71, 73, 79, 82, 87, 89, 93, or 97 stars. We can, however, squeeze out designs for 58 and 79 stars if we omit corner stars from not just the taller grid but from both grids:

```
(defn omitted-corners-arrangement-2 [stars]
(first
(for [n1 (range 2 (* 2 (int (Math/sqrt stars))))
m1 (range 2 n1)
:let [n2 (dec n1)
m2 (inc m1)]
:when (and (= stars (- (+ (* n1 m1) (* n2 m2)) 8))
(< 1.5 (/ n1 m1) 5)
(< 1.5 (/ n2 m2) 5))]
[[n1 m1 :omit-corners] [n2 m2 :omit-corners]])))
```

Both arrangements produce a hexagonal design, which means a four-sided rectangle contains five-pointed stars in a six-sided formation: