BadHorse.scala

object BadHorse extends App {

  def isSplittable(pairs: List[(String, String)], memo: Map[String, Boolean] = Map.empty[String, Boolean]): Boolean = {
    println(memo)
    pairs match {
      case Nil => true

      case (i, j) :: xs if memo contains i =>
        if ((memo contains j) && (memo(i) == memo(j))) false
        else isSplittable(xs, if (memo contains j) memo else memo + (j -> !memo(i)))

      case (i, j) :: xs if memo contains j =>
        isSplittable(xs, memo + (i -> !memo(j)))

      case (i, j) :: xs if !(memo contains j) =>
        isSplittable(xs, memo + (i -> false) + (j -> true))
    }
  }

  def brutalSplit(pairs: List[(String, String)]): Boolean = {

    def until(n: BigInt, acc: List[BigInt] = List.empty[BigInt]): List[BigInt] = if (n == 0) acc else until(n - 1, n - 1 :: acc)

    val ns = until(BigInt(2) pow pairs.size)

    val map = (Map.empty[String, Int] /: (pairs.flatMap { case (i, j) => List(i, j) }.toSet.toList.zipWithIndex)) {
      case (map, (name, index)) => map + (name -> index)
    }

    def isCorrectDivision(n: BigInt): Boolean = pairs forall {
      case (i, j) =>
        n.testBit(map(i)) != n.testBit(map(j))
    }

    ns exists isCorrectDivision
  }

  def process(iter: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to iter.next().toInt) {
      val m = iter.next().toInt
      val pairs = List.fill(m) {
        val Array(a, b) = iter.next() split ' '
        (a, b)
      }
      lineOut(s"Case #$i: ${if (brutalSplit(pairs)) "Yes" else "No"}")
    }

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

}