{"id":102,"date":"2014-05-24T10:18:38","date_gmt":"2014-05-24T14:18:38","guid":{"rendered":"https:\/\/dorcgames.com\/blog\/?p=102"},"modified":"2014-05-24T12:49:25","modified_gmt":"2014-05-24T16:49:25","slug":"in-search-of-the-fabled-flagorithm","status":"publish","type":"post","link":"https:\/\/dorcgames.com\/blog\/?p=102","title":{"rendered":"In Search of the Fabled Flagorithm"},"content":{"rendered":"

\"My<\/a><\/p>\n

Wherein a frustrated businessman is thrust into the harsh light of international industry, and comes to grips with a challenge far greater than himself:\u00a0 The Flag Unions.<\/p>\n

What’s this got to do with HUSSAR?\u00a0 Palettes.\u00a0 It’s always palettes.<\/p>\n

<\/p>\n

I’ll paraphrase the problem I posted to Facebook in late 2012:<\/p>\n

I own a flag<\/span>-making business and have an opportunity to make a big haul on a large order, but first I need to prove out my logistics with a smaller run. I’m trying to minimize my costs.<\/span>

I have two factories (Factory A is in Algeria, and Factory B is in Brazil). Each factory has its own flag<\/span>-making machine, and each machine can only hold 5 colors of ink. Ink is horrendously expensive, so I’m trying to optimize which ink barrels go to each Factory. Changing ink is also time-consuming and expensive (damn those Brazilian and Algerian unions!), so I want to figure out which factories get which inks in advance. Also due to union rules, a flag<\/span> must be made at one and only one factory (so no printing half a flag<\/span>‘s colors in one factory and shipping it to the other to finish).<\/span>

Ink comes in the following colors: <\/span><\/p>\n

\"AvailableColors\"<\/a><\/p>\n

I’m not allowed to mix inks, again because of those pesky union rules.<\/span>

A flag<\/span> consists of between 1 and 5 colors, which is convenient because as stated before, the machines can only hold 5 inks.<\/span>

Here’s my trial order of flags, and the Factories illustrated:<\/span><\/p>\n

\"A<\/a>

A total of 6 unique colors, more than any one Factory can hold, so we definitely have to split this up!<\/p><\/div>\n

Here is a possible solution of which inks to send to each factory:<\/span><\/p>\n

\n
\"A<\/a>

An initial solution.<\/p><\/div>\n

That’s 9 barrels of ink.<\/span>

Here’s another:<\/span><\/p>\n<\/div>\n

\n
\"MapSolution2\"<\/a>

Better…but is it the best?<\/p><\/div>\n

That’s only 8 barrels of ink! Is this the best I can do, though? I’d like an algorithm that could prove that, while running in a reasonable amount of time (preferably in under a couple of seconds).<\/span>

As mentioned before, this is a trial run for moving up to the big leagues. In the big leagues, I’ll have up to 64 ink choices, my Factory machines will be upgraded to hold 16 inks, and my orders will be up to 512 unique flags with up to 16 colors in each flag<\/span>. The big-big leagues are 4096 ink choices, and 16 factories!<\/span>

There are certain heuristics that can be employed, like building a hierarchy (e.g., I know that if I can fit USA, I can certainly fit Canada or Finland as they are proper subsets), or tossing out possible solutions if the number of colors would overflow.<\/span><\/p>\n<\/div>\n

<\/div>\n
To sum up, we need to solve the following problem:<\/div>\n

Given a set of Factories (each with a fixed capacity for ink barrels) and an arbitrary set of Flags (each made up of a combination of inks), and where each Flag must be made completely at one Factory, find a method that allocates Flags to Factories such that the total number of inks is minimized.<\/em><\/div>\n

Let’s call it the Flagorithm\u2122<\/strong>, a term coined, copyrighted, patented, fiercely protected by, and used under license (with much gratitude!) from Kat over at Klobit<\/a>.<\/div>\n

What’s This Really About?<\/h2>\n

The analogy, as alluded to in the teaser, regards hardware palettes and how to distribute colors of our images across those palettes.\u00a0 As you’ll remember from the previous post<\/a>, palettes are at a premium in old school hardware, and yet capable of some fantastic effects that can really bring our games alive.\u00a0 We want to maximize our palette usage to allow as many colors onscreen as possible, and to leave room for all those cool tricks.<\/p>\n

However, it turns out this is a non-trivial problem to solve:\u00a0 determining how we allocate our images (flags) across the hardware palettes (factories) quickly becomes infeasible.\u00a0 Our worst-case scenarios can easily enter into the billions–or more!–possible combinations.\u00a0 Time to break out the ol’ computer science textbooks.<\/p>\n

Brute Force<\/h2>\n

One very valid approach might be to brute force our way through all of the various combinations.\u00a0 The issue here, of course, is how difficult that winds up being.\u00a0 Let’s consider the facts:<\/p>\n