Scala graph coloring

Question

i have solved this problem https://leetcode.com/problems/find-eventual-safe-states/submissions/

import scala.collection.mutable


object Solution {
  def eventualSafeNodes(graph: Array[Array[Int]]): List[Int] = {
    val seen = mutable.HashSet[Int]()
    val safeNodes = mutable.ArrayBuffer[Int]()

    val  color_of = mutable.HashMap[Int, Int]().withDefaultValue(0)

    def is_safe(node: Int): Boolean = {
      color_of(node) = 1 
      for (neb <- graph(node)) {
        if (color_of(neb) == 1) {
          return false;
        } else if (color_of(neb) == 0) {
          if (!is_safe(neb)) {
            return false;
          }
        }
      }
      color_of(node) = 2
      return true
    }
    for (i <- 0 until graph.size) {
      if (color_of(i) == 2) {
        safeNodes.append(i)
      } else if (color_of(i) == 0) {
        if (is_safe(i)) {
          safeNodes.append(i)
        }
      }
    }
    return safeNodes.toList
  }
}

I would love some pointers on idiomatic code!

Answer 1

A few observations.

comments - These online code challenges don't tend to encourage code comments because, really, who's ever going to see it? After completing the challenge you will probably never return to it. Still, if it's going to be offered for code review you might pretty it up to make things easier for the reviewers.

unused - val seen is never referenced.

magic numbers - So 2 is "safe" and 1 is "unsafe" and ... This calls out for an enumeration. Then you could if (color_of(i) == Color.SAFE), and .withDefaultValue(Color.UNKNOWN), etc.

0 until graph.size - Use graph.indices instead.

return - Idiomatic Scala almost never uses return. In your case it's understandable since there are a couple of places where you want the iterations to terminate ASAP. Scala has a few different options for achieving that. One of the most common is using recursion.

if..else - In Scala the if..else construct is an expression, with a return value, and not a statement. For this, and other reasons, idiomatic Scala seldom invokes an if without a concluding else.

mutables - Perhaps the most obvious anti-Scala practice in the code is the use of mutable data structures. This isn't surprising since there is often a slight performance penalty when adhering to FP principles of immutability. Many of these online code challenges are much more difficult, if not impossible, without mutation.

So, can this be solved without mutation? I don't know. I came pretty close by using only the mutability inherent in the received Array.

def eventualSafeNodes(graph: Array[Array[Int]]): List[Int] = {

  def isSafe(xs :Array[Int], seen :Set[Int]) :Boolean =
    xs.isEmpty || xs.forall(x => !seen(x) && isSafe(graph(x), seen+x))

  graph.indices.foldRight(List.empty[Int]){ case (x, acc) =>
    if (isSafe(graph(x), Set(x))) {
      graph(x) = Array.empty[Int]  //leave marker - safe
      x :: acc                     //save index
    } else {
      graph(x) = Array(x)          //leave marker - unsafe
      acc                          //accumulator unchanged
    }
  }
}