DiamondInheritance.scala

object DiamondInheritance extends App {

  def isDiamond(inheritances: Seq[Int]*): Boolean = {

    val map = inheritances.zipWithIndex.map(m => (m._2 + 1, m._1)).toMap

    def dfs(visiting: Int, visited: Set[Int]): Option[Set[Int]] = {

      //      println(s"$visiting $visited")

      if (visited contains visiting) None
      else map(visiting).foldLeft[Option[Set[Int]]](Option(visited + visiting)) {
        (visitedOption, j) =>
          for {
            visited <- visitedOption
            set <- dfs(j, visited)
          } yield (visited ++ set)
      }

    }
    
//    def isDiamond0(from: Seq[Int]): Boolean = {
//      val i = from.head
//      val result = dfs(i, Set.empty)
//      
//      result match {
//        case None => true
//        case Some(set) => isDiamond0(from.filterNot(set.contains))
//      }
//    }
//    
//    isDiamond0(1 to inheritances.size)
    
    (1 to inheritances.size).exists(i => dfs(i, Set.empty).isEmpty)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) = {

    for (i <- 1 to lineIn.next().toInt) {

      val n = lineIn.next().toInt
      val inheritances = Seq.fill(n)(lineIn.next().split(' ').map(_.toInt).toList.tail)
      lineOut(s"Case #$i: ${if (isDiamond(inheritances: _*)) "Yes" else "No"}")
    }
  }

  val writer = new java.io.PrintWriter("a.large.out")
  try {
    process(io.Source.fromFile("A-large-practice.in").getLines)(writer.println)
  } finally {
    writer.flush(); writer.close()
  }

}

DiamondInheritanceTest.scala

import org.scalatest._

import DiamondInheritance._

class DiamondInheritanceTest extends FunSuite {

  test("sample case #1") {
    assert(isDiamond(Seq(2), Seq(3), Seq()) === false)
  }

  test("sample case #2") {
    assert(isDiamond(Seq(2, 3), Seq(4), Seq(5), Seq(5), Seq()) === true)
  }
  
  test("sample case #3") {
    assert(isDiamond(Seq(2, 3), Seq(3), Seq()) === true)
  }

  test("multiple root") {
    assert(isDiamond(Seq(), Seq(3,4), Seq(4), Seq()) === true)
    
  }
  

  test("sample case") {
    val input = """3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0""".lines

    val expected = """Case #1: No
Case #2: Yes
Case #3: Yes""".lines

    process(input) { s =>
      for (line <- s.lines)
        assert(line === expected.next())
    }
  }

  test("full small case") {
    val input = io.Source.fromFile("A-small-practice.in").getLines()
    val expected = io.Source.fromFile("a.small.out.ref").getLines()

    process(input) { s =>
      for (line <- s.lines)
        assert(line.trim === expected.next().trim)
    }
  }

  ignore("full large case") {
    val input = io.Source.fromFile("A-large-practice.in").getLines()
    val expected = io.Source.fromFile("a.large.out.ref").getLines()

    process(input) { s =>
      for (line <- s.lines)
        assert(line.trim === expected.next().trim)
    }
  }
}