Categories
algorithm arrays javascript mathematical-optimization matrix

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

UPD: the question has been updated with specifics and code, see below.

Warning: This question is about optimizing an arrangement of items in a matrix. It is not about comparing colors. Initially, I have decided that providing context about my problem would help. I now regret this decision because the result was the opposite: too much irrelevant talk about colors and almost nothing about actual algorithms. 😔


I’ve got a box of 80 felt tip pens for my kid, and it annoys me so much that they are not sorted.

enter image description here

I used to play a game called Blendoku on Android where you need to do just that: arrange colors in such a way that they form gradients, with nearby colors being the most similar:

enter image description here

It is easy and fun to organize colors in intersecting lines like a crossword. But with these sketch markers, I’ve got a full-fledged 2D grid. What makes it even worse, colors are not extracted from a uniform gradient.

This makes me unable to sort felt tip pens by intuition. I need to do it algorithmically!

Here’s what I’ve got:

  • Solid knowledge of JavaScript
  • A flat array of color values of all pens
  • A function distance(color1, color2) that shows how similar a color pair is. It returns a float between 0 and 100 where 0 means that colors are identical.

All I’m lacking is an algorithm.

A factorial of 80 is a number with 118 digits, which rules out brute forcing.

There might be ways to make brute forcing feasible:

  • fix the position of a few pens (e. g. in corners) to reduce the number of possible combinations;
  • drop branches that contain at least one pair of very dissimilar neighbours;
  • stop after finding first satisfactory arrangement.

But I’m still lacking an actual algorithm even for than, not to mention a non-brute-forcey one.

PS Homework:

Update

Goal

Arrange a predefined set of 80 colors in a 8×10 grid in such a way that colors form nice gradients without tearing.

For reasons described below, there is no definitive solution to this question, possible solution are prone to imperfect result and subjectiveness. This is expected.

Note that I already have a function that compares two colors and tells how similar they are.

Color space is 3D

Human eye has three types of receptors to distinguish colors. Human color space is three-dimensional (trichromatic).

There are different models for describing colors and they all are three-dimensional: RGB, HSL, HSV, XYZ, LAB, CMY (note that “K” in CMYK is only required because colored ink is not fully opaque and expensive).

For example, this palette:

HS palette

…uses polar coordinates with hue on the angle and saturation on the radius. Without the third dimension (lightness), this palete is missing all the bright and dark colors: white, black, all the greys (except 50% grey in the center), and tinted greys.

This palette is only a thin slice of the HSL/HSV color space:

enter image description here

It is impossible to lay out all colors on a 2D grid in a gradient without tearing in the gradient.

For example, here are all the 32-bit RGB colors, enumerated in lexicographic order into a 2D grid. You can see that the gradient has a lot of tearing:

flat RGB palette

Thus, my goal is to find an arbitrary, “good enough” arrangment where neighbors are more or less similar. I’d rather sacrifice a bit of similarity than have a few very similar clusters with tearing between them.

This question is about optimizing the grid in JavaScript, not about comparing colors!

I have already picked a function to determine the similarity of colors: Delta E 2000. This function is specifically designed to reflect the subjective human perception of color similarity. Here is a whitepaper describing how it works.

This question is about optimizing the arrangement of items in a 2D grid in such a way that the similarity of each pair of adjacent items (vertical and horizontal) is as low as it gets.

The word “optimizing” is used not in a sense of making an algorithm run faster. It is in a sense of Mathematical optimization:

In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function.

In my case:

  • “The function” here means running the DeltaE.getDeltaE00(color1, color2) function for all adjacent items, the output is a bunch of numbers (142 of them… I think) reflecting how dissimilar all the adjacent pairs are.
  • “Maximizing or minimizing” — the goal is to minimize the output of “the function”.
  • “An input value” — is a specific arrangement of 80 predefined items in the 8×10 grid. There are a total of 80! input values, which makes the task impossible to brute force on a home computer.

Note that I don’t have a clear definition for the minimization criteria of “the function”. If we simply use the smallest sum of all numbers, then the winning result might be a case where the sum is the lowest, but a few adjacent item pairs are very dissimilar.

Thus, “the function” should maybe take into account not only the sum of all comparisons, but also ensure that no comparisons are way off.

Possible paths for solving the issue

From my previous bounty attempt on this question, I’ve learned the following paths:

  • genetic algorithm
  • optimizer/solver library
  • manual sorting with a some algorithmic help
  • something else?

The optimizer/solver library solution is what I initially was hoping for. But the mature libraries such as CPLEX and Gurobi are not in JS. There are some JS libraries but they are not well documented and have no newbie tutorials.

The genetic algorithm approach is very exciting. But it requires concieving algorithms of mutating and mating specimen (grid arrangements). Mutating seems trivial: simply swap adjacent items. But I have no idea about mating. And I have little understanding of the whole thing in general.

Manual sorting suggestions seem promising at the first glance, but fall short when looking into them in depth. They also assume using algorithms to solve certain steps without providing actual algorithms.

Code boilerplate and color samples

I have prepared a code boilerplate in JS: https://codepen.io/lolmaus/pen/oNxGmqz?editors=0010

Note: the code takes a while to run. To make working with it easier, do the following:

  • Login/sign up for CodePen in order to be able to fork the boilerplate.
  • Fork the boilerplate.
  • Go to Settings/Behavior and make sure automatic update is disabled.
  • Resize panes to maximize the JS pane and minimize other panes.
  • Go to Change view/Debug mode to open the result in a separate tab. This enables console.log(). Also, if code execution freezes, you can kill the render tab without losing access the coding tab.
  • After making changes to code, hit save in the code tab, then refresh the render tab and wait.
  • In order to include JS libraries, go to Settings/JS. I use this CDN to link to code from GitHub: https://www.jsdelivr.com/?docs=gh


Source data:

const data = [
{index: 1, id: "1", name: "Wine Red", rgb: "#A35A6E"},
{index: 2, id: "3", name: "Rose Red", rgb: "#F3595F"},
{index: 3, id: "4", name: "Vivid Red", rgb: "#F4565F"},
// ...
];

Index is one-based numbering of colors, in the order they appear in the box, when sorted by id. It is unused in code.

Id is the number of the color from pen manufacturer. Since some numbers are in form of WG3, ids are strings.


Color class.

This class provides some abstractions to work with individual colors. It makes it easy to compare a given color with another color.

  index;
id;
name;
rgbStr;
collection;

constructor({index, id, name, rgb}, collection) {
this.index = index;
this.id = id;
this.name = name;
this.rgbStr = rgb;
this.collection = collection;
}

// Representation of RGB color stirng in a format consumable by the `rgb2lab` function
@memoized
get rgbArr() {
return [
parseInt(this.rgbStr.slice(1,3), 16),
parseInt(this.rgbStr.slice(3,5), 16),
parseInt(this.rgbStr.slice(5,7), 16)
];
}

// LAB value of the color in a format consumable by the DeltaE function
@memoized
get labObj() {
const [L, A, B] = rgb2lab(this.rgbArr);
return {L, A, B};
}
// object where distances from current color to all other colors are calculated
// {id: {distance, color}}
@memoized
get distancesObj() {
return this.collection.colors.reduce((result, color) => {
if (color !== this) {
result[color.id] = {
distance: this.compare(color),
color,
};
}

return result;
}, {});
}

// array of distances from current color to all other colors
// [{distance, color}]
@memoized
get distancesArr() {
return Object.values(this.distancesObj);
}

// Number reprtesenting sum of distances from this color to all other colors
@memoized
get totalDistance() {
return this.distancesArr.reduce((result, {distance}) => {
return result + distance;
}, 0);
}
// Accepts another color instance. Returns a number indicating distance between two numbers.
// Lower number means more similarity.
compare(color) {
return DeltaE.getDeltaE00(this.labObj, color.labObj);
}
}


Collection: a class to store all the colors and sort them.

class Collection {
// Source data goes here. Do not mutate after setting in the constructor!
data;

constructor(data) {
this.data = data;
}

// Instantiates all colors
@memoized
get colors() {
const colors = [];
data.forEach((datum) => {
const color = new Color(datum, this);
colors.push(color);
});

return colors;
}
// Copy of the colors array, sorted by total distance
@memoized
get colorsSortedByTotalDistance() {
return this.colors.slice().sort((a, b) => a.totalDistance - b.totalDistance);
}
// Copy of the colors array, arranged by similarity of adjacent items
@memoized
get colorsLinear() {
// Create copy of colors array to manipualte with
const colors = this.colors.slice();

// Pick starting color
const startingColor = colors.find((color) => color.id === "138");

// Remove starting color
const startingColorIndex = colors.indexOf(startingColor);
colors.splice(startingColorIndex, 1);

// Start populating ordered array
const result = [startingColor];

let i = 0;

while (colors.length) {

if (i >= 81) throw new Error('Too many iterations');
const color = result[result.length - 1];
colors.sort((a, b) => a.distancesObj[color.id].distance - b.distancesObj[color.id].distance);

const nextColor = colors.shift();
result.push(nextColor);
}

return result;
}
// Accepts name of a property containing a flat array of colors.
// Renders those colors into HTML. CSS makes color wrap into 8 rows, with 10 colors in every row.
render(propertyName) {
const html =
this[propertyName]
.map((color) => {
return `
<div
class="color"
style="--color: ${color.rgbStr};"
title="${color.name}\n${color.rgbStr}"
>
<span class="color-name">
${color.id}
</span>
</div>
`;
})
.join("\n\n");

document.querySelector('#box').innerHTML = html;
document.querySelector('#title').innerHTML = propertyName;
}
}


Usage:

const collection = new Collection(data);
console.log(collection);
collection.render("colorsLinear"); // Implement your own getter on Collection and use its name here


Sample output:

enter image description here