RopeIntranet.scala

object RopeIntranet extends App {

  def numberOfIntersection(wires: Seq[(Int, Int)]): Int =
    mergeAndCountInversion(wires.sortBy(_._1).map(_._2).toList)._2

  def mergeAndCountInversion(wires: List[Int]): (List[Int], Int) =
    if (wires.size < 2) (wires, 0)
    else {
      val (xs0, ys0) = wires splitAt wires.size / 2
      val (xs, xCount) = mergeAndCountInversion(xs0)
      val (ys, yCount) = mergeAndCountInversion(ys0)

      @annotation.tailrec
      def merge(xs: List[Int], ys: List[Int], merged: List[Int], count: Int): (List[Int], List[Int], Int) =
        (xs, ys) match {
          case (Nil, ys) => (merged, ys, count)
          case (xs, Nil) => (merged, xs, count)
          case (x :: xs0, y :: ys0) =>
            val (xs1, ys1, merged1, acc1) =
              if (x <= y) (xs0, ys, x :: merged, count)
              else (xs, ys0, y :: merged, count + xs.size)
            merge(xs1, ys1, merged1, acc1)
        }

      val (merged, remainder, mergeCount) = merge(xs, ys, Nil, 0)

      (merged.reverse ::: remainder, xCount + yCount + mergeCount)
    }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val n = lineIn.next().toInt
      val wires = List.fill(n) { lineIn.next() split ' ' map (_.toInt) }.map { case Array(a, b) => (a, b) }
      lineOut(s"Case #$i: ${numberOfIntersection(wires)}")
    }

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

}

RopeIntranetTest.scala

import org.scalatest._

import RopeIntranet._

class RopeIntranetTest extends FunSuite {

  test("sample #1") {
    assert(numberOfIntersection(Vector((1, 10), (5, 5), (7, 7))) === 2)
  }

  test("sample #2") {
    assert(numberOfIntersection(Vector((1, 1), (2, 2))) === 0)
  }

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

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("A-small-practice.in").getLines()
    val expected = io.Source.fromFile("a.small.out.ref").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)
  }

}