StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The most important thing is to have the code that declares what the inputs are and their relative priorities be simple, short and elegant. Here is one way to write that code:</p> <pre><code>PreferencedDecisionMaker pdm = new PreferencedDecisionMaker(); pdm.Push(false, leftExists, rightExists, upExists, downExists); pdm.Push(0); pdm.Push(false, leftFree, rightFree, upFree, downFree ); pdm.Push(false, pushedLeft, pushedRight, pushedUp, pushedDown); pdm.Push(1); switch(pdm.Decision) { case 1: GoLeft(); break; case 2: GoRight(); break; case 3: GoUp(); break; case 4: GoDown(); break; } </code></pre> <p>Here the inputs are declared in essentially a tabular format. The priority of each input is defined by the ordering of the rows. Each column corresponds to a possible output.</p> <p><strong>The "complexity" of this code is n×m.</strong></p> <p>(Although I've used indentation to make this look like a table, more complicated input conditions won't allow each row to exist neatly on a single line. This doesn't matter: the important bit is that there are only n×m declarations. Being able to make it look like a table when the conditions are short is just a nice bonus.)</p> <p>Less important is the actual behind-the-scenes code to make the decision (the <code>PreferencedDecisionMaker</code> type). There are a few ways to calculate the best output decision based on priority. Superpig suggested scoring, which is good. But I've ended up going for an option-elimination approach using a bit-field. I've posted my code for this below.</p> <p>Using a bit-field has the big advantage of not needing to allocate heap memory for arrays. The only downside is that it's limited to 32 options.</p> <p>The following code hasn't been thoroughly tested. And I haven't filled out all 32 versions of the <code>Push</code> method. It uses a mutable struct, which is "naughty" - converting it to an immutable struct should be straightforward. Or you could make it a class - but then you lose the benefit of avoiding heap allocation.</p> <pre><code>struct PreferencedDecisionMaker { private uint availableOptionsBits; private static readonly int[] MultiplyDeBruijnBitPosition = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; public int Decision { get { uint v = availableOptionsBits; // Find position of lowest set bit in constant time // http://stackoverflow.com/a/757266/165500 return MultiplyDeBruijnBitPosition[((uint)((v & -v) * 0x077CB531U)) >> 27]; } } private void InternalPush(uint preference) { if(availableOptionsBits == 0) availableOptionsBits = preference; else { uint combinedBits = availableOptionsBits & preference; if(combinedBits != 0) availableOptionsBits = combinedBits; } } public void Push(int option) { if(option < 0 || option >= 32) throw new ArgumentOutOfRangeException("Option must be between 0 and 31"); InternalPush(1u << option); } // ... etc ... public void Push(bool p0, bool p1, bool p2, bool p3, bool p4) { InternalPush((p0?1u:0u) | ((p1?1u:0u)<<1) | ((p2?1u:0u)<<2) | ((p3?1u:0u)<<3) | ((p4?1u:0u)<<4)); } // ... etc ... } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload