27 May 2015

Recursive Parallel Search

Bartosz Milewski has been discussing monadic programming in C++. In this post he presents a recursive version of the flatMap-based solution of the "Send more money" cryptarithmetic puzzle.

(BTW: Bartosz' writings always make for excellent reading if you're at all interested in functional programming.)

Here's a Java version of the recursive approach. I have already discussed the non-recursive solution in a previous blog entry. The main advantage over the original solution is that the recursive approach is less redundant and much easier to generalize. The main drawback is that on my machine it is about 6 times slower.

Please note how easy it is to parallelize this recursive solution when using persistent collections, in this case the ones from the TotallyLazy framework. Please spend a minute thinking about how you would go about coding this solution using only classes from the JDK. It's not trivial. (I would guess the same is true of the C++ implementation).

So here goes:

import static com.googlecode.totallylazy.collections.PersistentList.constructors.list;
import static;
import static;

import java.util.Collection;
import java.util.List;
import java.util.Map;

import com.googlecode.totallylazy.collections.PersistentList;
import com.googlecode.totallylazy.collections.PersistentMap;

public class SendMoreMoneyRecursive {

    static final PersistentList<Character> LETTERS = list(uniqueChars("sendmoremoney"));
    static final PersistentList<Integer> DIGITS = list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

    public static void main(String[] args) {
        SendMoreMoneyRecursive puzzle = new SendMoreMoneyRecursive();
        Collection<String> solutions = puzzle.solve(LETTERS, DIGITS);
        System.out.println("There are " + solutions.size() + " solutions: " + solutions);

    Collection<String> solve(PersistentList<Character> str, PersistentList<Integer> digits) {
        PersistentMap<Character, Integer> subst = map();
        Collection<String> solutions = go(str, digits, subst).collect(toList());
        return solutions;

    Stream<String> go(PersistentList<Character> str, PersistentList<Integer> digits,
            PersistentMap<Character, Integer> subst) {
        // Each level of nesting accomplishes one substitution of a character by a number. 
        // The recursion ends when we run out of characters to substitute.
        if (str.isEmpty()) {
            return prune(subst);
        return -> go(str.tail(), digits.delete(n), subst.insert(str.head(), n)));

    Stream<String> prune(PersistentMap<Character, Integer> subst) {
        // we know that we never look up a value that’s not in the map
        if (subst.get('s') == 0 || subst.get('m') == 0) {
            return Stream.empty();
        int send = toNumber(subst, "send");
        int more = toNumber(subst, "more");
        int money = toNumber(subst, "money");
        return send + more == money ? Stream.of(solution(send, more, money)) : Stream.empty();

    String solution(int send, int more, int money) {
        return "(" + send + "," + more + "," + money + ")";

    static final int toNumber(Map<Character, Integer> subst, String word) {
        assert word.length() > 0;
        return word.chars().map(x -> subst.get((char)x)).reduce((x, y) -> 10 * x + y).getAsInt();

    static List<Character> uniqueChars(String s) {
        return s.chars().distinct().mapToObj(d -> Character.valueOf((char) d)).collect(toList());

No comments:

Post a Comment