Solving a digitwise addition equation in Scala

Question

I've written the following codes in Scala and Java to solve cryptarithmatic problems.

E.g. For SEND+SOME=MONEY, assign the digits 0 to 9 such that the equation holds true. The algorithm I've used is backtracking without pruning.

Scala Implementation:

package recursion.flavors.decisions
import scala.language.dynamics 
import scala.collection.mutable.HashSet
import scala.collection.mutable.Set
import scala.collection.mutable.HashMap
import scala.collection.mutable.Map

object Cryptarithmatic {
  /**
   * Assign digits to letters such that, given condition is satisfied.
   * e.g. SEND + MORE = MONEY
   */
  class Puzzle{
    var operand1 = "send"
    var operand2 = "more"
    var res = "money"

    def allLetters():List[Char] = {
      var set:Set[Char] = HashSet()
      operand1 foreach {  c => set += c } 
      operand2 foreach {  c => set += c } 
      res foreach {  c => set += c } 

      set.toList.sorted
    }
  }

  def main(args: Array[String]): Unit = {
      var time = System.currentTimeMillis()
      println(clist)

      for(i <- 0 to 9 ){
        usedDigits = Set[Int]() 

        if(dumbSolver(i, clist)){
           println(assignment)
           println(System.currentTimeMillis() - time)
           println(cnt)
           return
        }
      }
  }


  var puzzle = new Puzzle()
  val clist =  puzzle.allLetters()
  var assignment:Map[Char,Int] = HashMap()
  var usedDigits = Set[Int]()

  val isSafe = (choice:Int) => {
//    if(pruned(a)) false

    !usedDigits.contains(choice)
  }

  var cnt = 0
  def dumbSolver(indx:Int, lettersToAssign:List[Char]):Boolean ={
    if(assignment.size == clist.size) 
                return puzzleSolved(assignment)

    cnt += 1
    val choices = 0 to 9

    choices filter isSafe foreach  { choice=>

        assignment += (lettersToAssign(indx) -> choice)
        usedDigits += choice

        if(dumbSolver(indx+1, lettersToAssign)) return true

        assignment -= lettersToAssign(indx)
        usedDigits -= choice
    }

    false
  }

  def puzzleSolved(assignment: Map[Char,Int]):Boolean = {
    getValue(puzzle.operand1) + getValue(puzzle.operand2) == getValue(puzzle.res) 
  }

  def getValue(a:String ):Int = {
        a.foldLeft(0){ (res,c) => 10 * res + assignment(c) }
    }

  def pruned(assign: (Char, Int)): Boolean = {
   false
  }

}

Output in Scala:

List(d, e, m, n, o, r, s, y)
Map(n -> 3, e -> 5, s -> 7, m -> 0, d -> 1, y -> 6, r -> 2, o -> 8)
963
114685

And the same algorithm in Java:

package recursion.flavors.decisions;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public class CryptarithmaticJava {

    static class Puzzle{
        String a = "send", b ="more", c ="money";

        public List<Character> allLetters() {
            Set<Character> set = new HashSet<>();
            for(char c: a.toCharArray()) set.add(c);
            for(char c: b.toCharArray()) set.add(c);
            for(char c: c.toCharArray()) set.add(c);

            return set.stream().sorted().collect(Collectors.toList());
        }

    }

    Puzzle puzzle = new Puzzle();
    Map<Character, Integer> assignments = new HashMap<Character, Integer>();
    Set<Integer> usedDigits = new HashSet<>();
    List<Character> clist = puzzle.allLetters();

    public static void main(String[] args) {
        new CryptarithmaticJava().solve();
    }

    long cnt = 0;

    private void solve() {
         long time = System.currentTimeMillis();

         System.out.println(clist);
         for (int i = 0; i < 10; i++) {
            usedDigits.clear();

            if (solve(i, clist)) {
                System.out.println(assignments);
                System.out.println(System.currentTimeMillis()- time);
                System.out.println(cnt);
                return;
            }
         }      
    }

    private boolean solve(int i, List<Character> lettersToAssign) {
        if(assignments.size() == lettersToAssign.size()) return puzzleSolved();

        cnt++;
        for (int n = 0; n < 10; n++) {
            if(!usedDigits.contains(n)){

                assignments.put(lettersToAssign.get(i), n);
                usedDigits.add(n);

                if(solve(i+1, lettersToAssign)) return true;

                assignments.remove(lettersToAssign.get(i));
                usedDigits.remove(n);
            }
        }
        return false;
    }

    private  boolean puzzleSolved() {
        int av = getValue(puzzle.a);
        int bv = getValue(puzzle.b);
        int resultv = getValue(puzzle.c);
        return av + bv == resultv;
    }

    private int getValue( String a) {
        int res = 0;
        for (int i = 0; i < a.length(); i++) {
            res = 10 * res + assignments.get(a.charAt(i));
        }
        return res;
    }

    private static void printSol(Map<Character, Integer> map) {
        Set<Entry<Character, Integer>> set = map.entrySet();
        for (Entry<Character, Integer> entry : set) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

Output in Java:

[d, e, m, n, o, r, s, y]
{r=2, s=7, d=1, e=5, y=6, m=0, n=3, o=8}
195
114685

The output clarifies that both algorithms are recurring the same number of times, but the time taken by the Scala version is 7 times higher than Java version.

Is there to speed up the Scala version? I've tried removing closures, method calls from the Scala code, but it doesn't make a significant difference.

Answer 1

It's reasonably well known that Scala adds some runtime overhead and often runs slower than the equivalent Java code. (Still, 7 times slower does seem a bit excessive.)

That being said, writing Scala in a Java-equivalent fashion is usually a pretty bad idea. You get the worst of both worlds: the code verbosity of Java and the runtime overhead of Scala.

Here's a different approach that uses a few Scala idioms and Standard Library utilities to do essentially the same thing. It's not a very clever algorithm, it's basically brute force, but it gets the job done with fewer lines of code.

class Translater(word: String, layout: String) {
  private val indices = word.map(layout.indexOf(_))
  def apply(digits: String): String = {
    val translated = indices.map(digits).mkString
    if (translated.head == '0') "0"  // multi-digit number can't start with 0
    else translated
  }
}

val (strA, strB, strC) = ("send", "more", "money")
println(s"$strA + $strB == $strC")
val layout: String = (strA + strB + strC).distinct
val opA  = new Translater(strA, layout)
val opB  = new Translater(strB, layout)
val sumC = new Translater(strC, layout)

val results = for {
  cmb <- "0123456789".combinations(layout.length)
  prm <- cmb.permutations
  if opA(prm).toInt + opB(prm).toInt ==  sumC(prm).toInt
} yield s"${opA(prm)} + ${opB(prm)} == ${sumC(prm)}"

if (results.isEmpty) println("none found")
else results.foreach(println)