Example of use of Karnaugh maps (fun stuff) in business application code (boring stuff)

Introduction

In Computer Science (CS), you'll encounter a lot of awesome theoretical concepts that are forgotten once you start working on a job where you don't need to apply them very often.

One very interested subject taught in CS is Karnaugh Maps, which takes a truth table as input and outputs the minimal equation that behaves exactly as the given truth table. You can see an example in the following figure:

You can always come with excuses to apply things like this in your job and have some healthy fun; and we did just that back in 2011, we took a requirement and apply this technique to do some optimization. First let me give you some context.

Context

As I told you, back in 2011 we developed an application that lets clients transmit information to our servers. Prior to the transmission, the client data must meet some criteria defined by a set of rules; our users generates such rules using a graphical language in a server side app (also developed by us) and then this server applications sends the bundle with the rules to the client app so it can apply them to the user data files.

The server side app UI mimics a spreadsheet program in several ways and features a graphical rules language.

The following figure depicts the application flow:

The graphical rules language (GRL) has support for functions. Users has several functions at their disposal to choose from. Sometimes a requirement consisted in adding a particular function to the GRL in order to help with some particular task, calculate the number of days between two given dates, percentages, interests rates, and so on.

The validation function

User data files are a collection of "~" separated fields, values are spread over several lines. File size can range from several Kb to some Gb, and validation speed is an important aspect of the client app.

One day users requiered clients to send a collection of values (like a set) encoded in just one field value. For it, they were also needing a new function that could check if the values sent by the user contained valid elements. The next figure will depict the general idea:

To encode the set in one field, we proposed the use of binary encoded values and our users (without much knowledge about binary encoding) agreed; so, if the users defined valid values to be: 1 (00001₂), 2 (00010₂), 4 (00100₂) and 16 (10000₂) and a client wanted to send 1 and 16 (because he/she just has those two values to report), the client just need to send the result of the binary OR, i.e., 1 OR 16 = 1 + 16 = 17 (100012) as the field value.

To validate the sent result, the required function just need to check if the bits set in the sent result are also set in a valid mask (yes, there should be a mask created with the binary OR of all the valid values). An example of a Java code that does this is the following:

This was a first solution to the problem. After some though it came to us that we could improve this solution a little further and get some fun by doing it.

Using Karnaugh maps to optimize the validation function

Applying Karnaugh maps in the proccess explained above we get following; first we drew the truth table for our validation function working at bit level of the function result:

From the above we can derive this Karnaugh map and its resulting equation:

So, how do we apply this? Basically we are working at bit level on both the sent value and the mask, once the algebraic equation is applied the resulting value should be -1, that is, all resulting bits should be 1; if just one of the bits of the result is 0 then it means there is an invalid value (one of the items seleted by the client is not present in the list of valid values defined by the users) and we should reject it. The following example visually exposes the aforementioned explanation:

So, the code for the function simplifies to this:

Another solution

Another approach to solve the problem is to work with the complement of the function in the truth table, aiming to find when the function should be invalid instead of when is valid, which yields a map with less 1 values to simplify:

The code for this function works different than the previous solution, for this case we are looking that all the resulting bits should be 0, which means that if one of the bits is set then there is an invalid value. The following example shows the same situation as above applying the new equation.

And the code for this solution is the following:

Conclussions

Simpler code doesn't necesarilly means more readable code, as you can see in both of the examples above, the code would be harder to understand for somebody unexperienced with the codebase and can even catch out of guard those who has most of the experience with the project code. Despite being an elegant solution, maintaining such code will require the coder to even review Karnaugh maps theory, besides that, any performance gains would be only noticeable if you execute the method around 1000000000 times (tested in a i7 machine with 8 gb of ram on jdk 7), and all of this could label this solution with the Accidental complexity tag.

Anyway, solving this rather simple problem and then doing the optimization using something that is not frequent in the context of backend business code was a really gratifying experience in terms of getting out of the routine and getting a lot fun. Maybe you can use this as an inspiration to tacle a requirement in a different and unorthodox way.