# Solving a digitwise addition equation in Scala

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<>();

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);

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.

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
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)}"