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.