4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ This program is taking way too much time: 9474 ms, which is 50 times of Java version. \$\endgroup\$ – Satyendra Kumar Sep 6 '16 at 17:58
  • \$\begingroup\$ +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. \$\endgroup\$ – Tamoghna Chowdhury Jan 4 '17 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.