Two recent posts in Bartosz’s programming cafe describe nice application of list monad to solve the following puzzle:

Each letter corresponds to single digit. There are a lot of methods to solve this. Bartosz is using list monad which is very simular to list comprehension methods which were described here. While this maybe not the fastest way to solve this specific puzzle, his approach shows the ways to solve large cluster of similar but smaller problems which we meet at basic “production” level. SEND+MORE problem may be is not so good example to show power of list monad because of one very important problem i want to discuss in this post.

Let’s rephrase the puzzle – we have 8 different variables and have find all combinations which satisfy some constraints.

Straightforward solution – form all possible combinations of variables and filter them using constraint conditions. To form such combinations we use general iteration over the list of possible values.

The problem: when the list of values is not small enough or count of variables is greater than 3 we could face performance problem as iterations become too long.

Size of SEND+MORE puzzle is close enough to meet this problem but still modern cpu could handle it straightforward way.

SLIGHTLY DIFFERENT WAY

The main idea is to separate iterations, data and constraints. And the most important: we need to split one global constraint into smaller constraints and apply them as early as possible.

And while doing that i want to maintain the simplicity of Bartosz’s solution.

To make it all work i will use some tools from my previous post . Main parts are currying of functions and functional piping.

DATA:

I use shared_ptr to access data here – that’s not important in this particular example. Even raw pointers could show the idea. The important part is the list of possible values called digits, and pointers to all variables.

Next – let’s define CONSTRAINTS:

Constraint is a function which returns “true” if given value has passed the condition. So constraint any gives green light to every integer. to_fn function here is just converting lambda into std::function.

Instead of trying to invent some tricky constrains we go very simple and logical way – our constraint just defines how we add decimal numbers. Nothing more – nothing else. r0,r1,r2,r3 – are numbers which go on next column during  addition.

Only one ‘not so nice’ step here is setting r through pointer.  This is done to be able to use it during the following more deep constraints.

After definition i’m wrapping function into universal class which could handle currying and piping – see this post for details.

The last column of digits is an exception – so we have to define separate constraint for it:

Note that we are also checking for first number to be non zero.

So finally instead of one global constraint we have 4 smaller constrains and could apply them sooner to decrease amount of iterations.

ITERATIONS

Functional iterator is simple:

This function is just picking all possible values from the list, apply constraint and if it was positive check, calls process method for reduced list of values (which does not contain picked value).

The last piece is the function to print the result:

FINALLY

Sorry that i’m using my ‘<<‘ notation for currying here – as this might be not ideal solution. I hope this will not prevent you to understand the idea of segregation. Of cause operation overloading could be changed to some another notation. Note that i use left and right currying together inside constraints.

This is compact enough to show the main idea – decomposing iterations and constraints.

My debug version is solving this puzle in 7ms.

PS. What I don’t like about this solution is using pointers too much. But we could change the design to pass data along functional chain without using pointers, but this could make the solution a bit more complicated. May be i will fix it later. Also i’m looking for the way to get rid of  ‘)))))))’ stuff.

PS2: Whole puzzle solution together:

PS3. Bartosz’s programming cafe is a very good place to visit.