# Scala graph coloring

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!

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

• thanks for the review. Is it really bad to use mutable data structures in scala? As you say, it makes solving problems much harder, but it also means a java-dev can't be productive from the get-go. Dec 20, 2019 at 13:15
• Of course Java-devs can approach Scala as a "better Java" and be productive from the get-go, but you specifically asked for "pointers on idiomatic code" and Scala is designed to be a Functional Programming language. FP practices takes some getting used to (brain rewiring) but I've found it to be quite rewarding.
– jwvh
Dec 20, 2019 at 20:33