Organizing felt tip pens: optimizing the arrangement of items in a 2D grid by similarity of adjacent items, using JS [updated]

I managed to find a solution with objective value 1861.54 by stapling a couple ideas together.

1. Form unordered color clusters of size 8 by finding a min-cost matching and joining matched subclusters, repeated three times. We use d(C1, C2) = ∑_{c1 in C1} ∑_{c2 in C2} d(c1, c2) as the distance function for subclusters C1 and C2.

2. Find the optimal 2 × 5 arrangement of clusters according to the above distance function. This involves brute forcing 10! permutations (really 10!/4 if one exploits symmetry, which I didn't bother with).

3. Considering each cluster separately, find the optimal 4 × 2 arrangement by brute forcing 8! permutations. (More symmetry breaking possible, I didn't bother.)

4. Brute force the 4¹⁰ possible ways to flip the clusters. (Even more symmetry breaking possible, I didn't bother.)

5. Improve this arrangement with local search. I interleaved two kinds of rounds: a 2-opt round where each pair of positions is considered for a swap, and a large-neighborhood round where we choose a random maximal independent set and reassign optimally using the Hungarian method (this problem is easy when none of the things we're trying to move can be next to each other).

The output looks like this:

Python implementation at https://github.com/eisenstatdavid/felt-tip-pens

The trick for this is to stop thinking about it as an array for a moment and anchor yourself to the corners.

First, you need to define what problem you are trying to solve. Normal colors have three dimensions: hue, saturation, and value (darkness), so you're not going to be able to consider all three dimensions on a two dimensional grid. However, you can get close.

If you want to arrange from white->black and red->purple, you can define your distance function to treat differences in darkness as distance, as well as differences in hue value (no warping!). This will give you a set, four-corner-compatible sorting for your colors.

Now, anchor each of your colors to the four corners, like so, defining (0:0) as black, (1:1) as white, (0,1) as red (0 hue), and (1:0) as purple-red (350+ hue). Like so (let's say purple-red is purple for simplicity):

Now, you have two metrics of extremes: darkness and hue. But wait... if we rotate the box by 45 degrees...

Do you see it? No? The X and Y axes have aligned with our two metrics! Now all we need to do is divide each color's distance from white with the distance of black from white, and each color's distance from purple with the distance of red from purple, and we get our Y and X coordinates, respectively!

Let's add us a few more pens:

Now iterate over all the pens with O(n)^2, finding the closest distance between any pen and a final pen position, distributed uniformly through the rotated grid. We can keep a mapping of these distances, replacing any distances if the respective pen position has been taken. This will allow us to stick pens into their closest positions in polynomial time O(n)^3.

However, we're not done yet. HSV is 3 dimensional, and we can and should weigh the third dimension into our model too! To do this, we extend the previous algorithm by introducing a third dimension into our model before calculating closest distances. We put our 2d plane into a 3d space by intersecting it with the two color extremes and the horizontal line between white and black. This can be done simply by finding the midpoint of the two color extremes and nudging darkness slightly. Then, generate our pen slots fitted uniformly onto this plane. We can place our pens directly in this 3D space based off their HSV values - H being X, V being Y, and S being Z.

Now that we have the 3d representation of the pens with saturation included, we can once again iterate over the position of pens, finding the closest one for each in polynomial time.

There we go! Nicely sorted pens. If you want the result in an array, just generate the coordinates for each array index uniformly again and use those in order!

Now stop sorting pens and start making code!

As it was pointed out to you in some of the comments, you seem to be interested in finding one of the global minima of a discrete optimization problem. You might need to read up on that if you don't know much about it already.

Imagine that you have an error (objective) function that is simply the sum of distance(c1, c2) for all (c1, c2) pairs of adjacent pens. An optimal solution (arrangement of pens) is one whose error function is minimal. There might be multiple optimal solutions. Be aware that different error functions may give different solutions, and you might not be satisfied with the results provided by the simplistic error function I just introduced.

You could use an off-the-shelf optimizer (such as CPLEX or Gurobi) and just feed it a valid formulation of your problem. It might find an optimal solution. However, even if it does not, it may still provide a sub-optimal solution that is quite good for your eyes.

You could also write your own heuristic algorithm (such as a specialized genetic algorithm) and get a solution that is better than what the solver could find for you within the time and space limit it had. Given that your weapons seem to be input data, a function to measure color dissimilarity, and JavaScript, implementing a heuristic algorithm is probably the path that will feel most familiar to you.

My answer originally had no code with it because, as is the case with most real-world problems, there is no simple copy-and-paste solution for this question.

Doing this sort of computation using JavaScript is weird, and doing it on the browser is even weirder. However, because the author explicitly asked for it, here is a JavaScript implementation of a simple evolutionary algorithm hosted on CodePen.

Because of the larger input size than the 5x5 I originally demonstrated this algorithm with, how many generations the algorithm goes on for, and how slow code execution is, it takes a while to finish. I updated the mutation code to prevent mutations from causing the solution cost to be recomputed, but the iterations still take quite some time. The following solution took about 45 minutes to run in my browser through CodePen's debug mode.

Its objective function is slightly less than 2060 and was produced with the following parameters.

const SelectionSize = 100;const MutationsFromSolution = 50;const MutationCount = 5;const MaximumGenerationsWithoutImprovement = 5;

It's worth pointing out that small tweaks to parameters can have a substantial impact on the algorithm's results. Increasing the number of mutations or the selection size will both increase the running time of the program significantly, but may also lead to better results. You can (and should) experiment with the parameters in order to find better solutions, but they will likely take even more compute time.

In many cases, the best improvements come from algorithmic changes rather than just more computing power, so clever ideas about how to perform mutations and recombinations will often be the way to get better solutions while still using a genetic algorithm.

Using an explicitly seeded and reproducible PRNG (rather than Math.random()) is great, as it will allow you to replay your program as many times as necessary for debugging and reproducibility proofs.

You might also want to set up a visualization for the algorithm (rather than just console.log(), as you hinted to) so that you can see its progress and not just its final result.

Additionally, allowing for human interaction (so that you can propose mutations to the algorithm and guide the search with your own perception of color similarity) may also help you to get the results you want. This will lead you to an Interactive Genetic Algorithm (IGA). The article J. C. Quiroz, S. J. Louis, A. Shankar and S. M. Dascalu, "Interactive Genetic Algorithms for User Interface Design," 2007 IEEE Congress on Evolutionary Computation, Singapore, 2007, pp. 1366-1373, doi: 10.1109/CEC.2007.4424630. is a good example of such approach.