2
\$\begingroup\$

I translated Peter Norvig Python Sudoku solver to Scala and my Scala implementation was slower in the order of few magnitudes e.g. instantaneous, in Python, vs 4 to 5 seconds. I suspected I didn't implement the algorithm to the dot or the way I use the Scala classes less than ideal. These are the crucial functions I translated from the Python functions using the same names. Thanks.

def eliminate(solution: Map[String, String], cell: String, num: Char):
Option[Map[String, String]] = {

val nums = solution(cell)

if (nums.contains(num)) {
  val updatedSoln = solution.updated(cell, nums.replace(num.toString, ""))
  val ys = updatedSoln(cell)

  val emSoln = if (ys.isEmpty) None
  else if (ys.size == 1)
    peers(cell).foldLeft(Option(updatedSoln))((s, c) =>
      s.flatMap(s2 => eliminate(s2, c, ys.head)))
  else Some(updatedSoln)

  emSoln.flatMap(s => {
    val finalSoln = peersAndSelf(cell).filter(c => s(c).contains(num))
    if (finalSoln.isEmpty) None
    else if (finalSoln.size == 1) assign(s, finalSoln.head, num)
    else emSoln
  })
 } else Some(solution)
}
def assign(solution: Map[String, String], cell: String, num: Char): Option[Map[String, String]] = {
if (debug) println(s"Assign ($cell, $num)")
solution(cell).replace(num.toString, "").foldLeft(Option(solution))((s, c) => s.flatMap(m => eliminate(m, cell, c)))
}

def search(solution: Map[String, String]): Option[Map[String, String]] =
solution.filter(_._2.size > 1).toList match {
  case Nil => Some(solution)
  case xs =>
    val (cell, nums) = xs.minBy(_._2.size)
    nums.flatMap(d => assign(solution, cell, d) match {
      case Some(x) => search(x)
      case None => None
    }).headOption
}

I am not comparing which language is faster. I happy if Python takes 300ms and the refactor Scala code takes 800ms.

Click here for the full implementation.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.