Bilingual.scala

object Bilingual extends App {

  def sentencesToGraph(s: Vector[String]): Vector[Vector[Int]] = {
    val wordMap = ((s(0) split ' ').toSet ++ (s(1) split ' ').toSet).toVector.zipWithIndex.toMap.mapValues(_ + s.size)
    s.map(sentence => (sentence split ' ').toVector.map(wordMap)) ++ s.map(sentence => (sentence split ' ').toSet).foldLeft(Set.empty[String])(_ ++ _).toVector.map {
      word => s.zipWithIndex.filter(_._1 contains word).map(_._2)
    }
  }

  def minBi(sentences: Seq[String]): Int = {
    val g = sentencesToGraph(sentences.toVector)

    def loop(g: Vector[Vector[Int]], count: Int = 0): Int = {
      
      println(g, count)
      
      def bfs(toVisit: Seq[List[Int]], visited: Set[Int]): Option[Seq[Int]] = {
        println(s"=== $toVisit $visited")
        
        if (toVisit.isEmpty) None
        
        val candidates = for {
          next <- toVisit
          nextNode <- g(next.head) if !(visited contains nextNode)
        } yield nextNode :: next

        candidates find { _.head == 1 } match {
          case Some(root) => Some(root)
          case None       => bfs(candidates, visited ++ toVisit.map(_.head))
        }
      }
      
      bfs(Seq(List(0)), Set.empty[Int]) match {
        case None => count
        case Some(_::tail) => loop(g.map(_ diff tail.init), count+1)
      }
      
    }

    loop(g)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(r, c) = lineIn.next() split ' ' map (_.toInt)
      val grid = Vector.fill(r) { lineIn.next().toVector }
      //      lineOut(s"Case #$i: ${minArrows(grid) getOrElse "IMPOSSIBLE"}")
    }

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

BilingualTest.scala

import org.scalatest._

import Bilingual._

class BilingualTest extends FunSuite {

  test("sentencesToGraph") {
    assert(sentencesToGraph(Vector("a b", "b c")) === Vector(Vector(2, 3), Vector(3, 4), Vector(0), Vector(0, 1), Vector(1)))
  }

  test("easy") {
    assert(minBi(Seq("a b", "b c")) === 1)
  }

  ignore("sample #1") {
    assert(minBi(Seq("he loves to eat baguettes", "il aime manger des baguettes")) === 1)
  }

  ignore("sample case") {
    val input = """4
2 1
^
^
2 2
>v
^<
3 3
...
.^.
...
1 1
.""".lines

    val expected = """Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 0""".lines

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}