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)

• Satyendra Kumar: This program is taking way too much time: 9474 ms, which is 50 times of Java version.
• Tamoghna Chowdhury: +1, but this is not really what the OP wanted. The OP wanted a time-optimised version, you just give him more idiomatic code. Maybe you should also consider performance.