I’ve been playing around with a few multi-paradigm programming languages. The most recent one is called Picat. It’s a hybrid language that is a mix of logic, imperative, actor, and functional paradigms with built-in constraint solvers and planners. That’s a lot to take in so whenever I’m faced with a language with roots in the logic paradigm the first thing I try to do is solve “SEND + MORE = MONEY” cryptarithmetic puzzle. It’s a small and manageable problem and there are at least two ways to solve it so it allows one to exercise several features of the logic and constraint paradigms.

# SEND + MORE = MONEY

I mentioned there are at least two ways to solve the problem. If you search around you will find both approaches. My favored approach is the sum-carry method. I like it because it has a dataflow flavor and is the algorithm that most people learn in grade school so it also has an imperative aspect. The other approach is much more declarative but I think exercises fewer parts of the language. The sum-carry method forces calculation of carries which can sometimes be hard to express as a linear constraint and seeing how that works in the language is a good thing to know in general when working on other problems.

Here’s a high-level view of what the sum-carry method comes down to

1 2 3 4 5 6 |
C4 C3 C2 C1 S E N D + M O R E -------------- M O N E Y |

So we just need to express the above as a set of constraints in Picat to solve the problem.

# Preliminaries

Downloading and installing Picat is left as an exercise for the reader so assuming you have Picat installed and working I’m going to present the solution.

First we need to import `cp`

module so Picat knows we are going to use (c)onstraint (p)ropagation/solving

1 2 |
import cp. |

We next need a predicate for expressing sums and carries

1 2 3 4 5 |
sum_carry(A, B, S, C1, C2) => T #= A + B + C1, S #= T mod 10, C2 #= cond(T #> 9, 1, 0). % if T > 9 then 1 else 0 |

There is a lot going on in those few lines. Picat is a logical language so it uses logical variables and pattern-matching/unification. It’s not unification like Prolog so there are some subtle differences. I’m going to show an example of how to use the above predicate in the Picat shell so you can get a feel for what is going on (you can start the Picat shell by just invoking the main Picat binary).

First we need to compile/load the file (I put it in a folder called `test`

and called the file `constraint.pi`

)

1 2 |
Picat> cl("test/constraint.pi") |

After the file is compiled/loaded we can use our definition

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Picat> % 1 + 2 = S and C is the final carry Picat> sum_carry(1, 2, S, 0, C) S = 3 C = 0 yes Picat> % A slightly more complicated case: 5 + 5 = S and C is the final carry Picat> sum_carry(5, 5, S, 0, C) S = 0 C = 1 yes Picat> % Another sum but now with a leftover carry from a previous sum Picat> % 5 + 5 + (C1 = 1) = S and C is the final carry Picat> sum_carry(5, 6, S, 1, C) S = 2 C = 1 yes |

So far we have provided enough constraints for Picat to find a solution. So what happens when we don’t provide enough constraints?

1 2 3 4 5 6 |
Picat> sum_carry(A, 6, S, 1, C) A = DV_011a68_-72057594037927935..72057594037927935 S = DV_012028_0..9 C = DV_012f28_0..1 yes |

Picat does the most sensible thing possible and provides us with the data structures that we can then pass to a solver to get a solution. The problem is unconstrained so there are many solutions

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Picat> sum_carry(A, 6, S, 1, C), solve([A, S, C]) A = -72057594037927935 S = 2 C = 0 ?; A = -72057594037927934 S = 3 C = 0 ?; A = -72057594037927933 S = 4 C = 0 ?; A = -72057594037927932 S = 5 C = 0 ? |

You can keep going to find “all” the solutions but it gets tedious. Notice how the variables are constrained to a specific range and how they’re actually beyond the range that our problem requires. Armed with this new knowledge we can improve our definition

1 2 3 4 5 6 |
sum_carry(A, B, S, C1, C2) => A :: 0..9, B :: 0..9, C1 :: 0..1, T #= A + B + C1, S #= T mod 10, C2 #= cond(T #> 9, 1, 0). |

Now our variables are constrained to a range that is sensible for the problem we are trying to solve. Range constraints are expressed with `::`

. If you compile and run the new version you will get the following output

1 2 3 4 5 6 7 8 |
Picat> sum_carry(A, B, S, C1, C2) A = DV_013718_0..9 B = DV_0137b0_0..9 S = DV_013fe8_0..9 C1 = DV_013848_0..1 C2 = DV_014410_0..1 yes |

That’s definitely more sensible for our problem.

I’m going to need one more predicate/function for printing the results and then we can solve the original problem.

1 2 3 4 5 6 7 8 9 10 11 12 |
print_result(S, E, N, D, M, O, R, Y) => writef("SEND + MORE = MONEY\n"), F = "%d%d%d%d", A = to_fstring(F, S, E, N, D), B = to_fstring(F, M, O, R, E), Sum = to_fstring("%d%d%d%d%d\n", M, O, N, E, Y), writef(A), writef(" + "), writef(B), writef(" = "), writef(Sum). |

Picat has format strings and I/O functions but I haven’t done too much with those yet.

# Solution

All we need to do is declare our variables and use `sum_carry`

to express the constraints

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
main => Digits = [S, E, N, D, M, O, R, Y], Digits :: 0..9, all_different(Digits), Carry = [C1, C2, C3, C4], Carry :: 0..1, S #> 0, M #> 0, sum_carry(D, E, Y, 0, C1), % D + E -> Y, C1 sum_carry(N, R, E, C1, C2), % N + R + C1 -> E, C2 sum_carry(E, O, N, C2, C3), % E + O + C2 -> N, C3 sum_carry(S, M, O, C3, C4), % S + M + C3 -> O, C4 M #= C4, solve(Digits), print_result(S, E, N, D, M, O, R, Y). |

If you put the above in a file and invoke it you will get the final solution

1 2 3 4 |
$ ./picat test/constraint.pi SEND + MORE = MONEY 9567 + 1085 = 10652 |

Unfortunately the constraint/logic programming paradigm is underutilized. You can rectify the situation by learning a little bit of Prolog and Picat and looking for opportunities where they can be used. Some problems are custom made for logic/constraint programming and knowing when you can apply the paradigm is almost like having a superpower.