LogSet.scala

package lascala

object LogSet extends App {

  def originalSet(es: Seq[Int], fs: Seq[Int]): Seq[Int] = {
    val ss = (es zip fs).flatMap { case (e, f) => Seq.fill(f)(e) }.sorted.reverse.toList
    def elements(ss: List[Int]): List[Int] = ss match {

      case x :: y :: Nil => (x - y) :: Nil
      case x :: y :: tt =>
        val diff = x - y
        def pairs(ss: List[Int]): List[(Int, Int)] = {
          ss match {
            case Nil => Nil
            case x :: xs =>
              (x, x - diff) :: pairs(xs diff List(x - diff))
          }
        }
        diff :: elements(pairs(ss).unzip._2)
    }

    def findSubset(abss: Seq[Int], target: Int): Option[Seq[Int]] = {

      abss match {
        case Nil =>
          if (target == 0) Some(Seq.empty[Int]) else None
        case x :: xs =>
          val try1 = findSubset(xs, target - x)
          if (try1.nonEmpty) Some(x +: try1.get)
          else {
            val try2 = findSubset(xs, target)
            if (try2.nonEmpty) Some(try2.get)
            else None
          }
      }
    }

    val abss = elements(ss).sorted

    val positives = findSubset(abss, ss.head).get

    ((abss diff positives).map(-_) ++ positives).sorted
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val p = lineIn.next().toInt
      def ints() = lineIn.next().split(' ').map(_.toInt)

      lineOut(s"Case #$i: ${originalSet(ints(), ints()).mkString(" ")}")
    }

  val filename = "B-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()
  }

}

LogSetTest.scala

package lascala

import org.scalatest._

import LogSet._

class LogSetTest extends FunSuite {

  test("sample #1") {
    assert(originalSet(0 to 7, Seq.fill(8)(1)) === Seq(1, 2, 4))
  }

  test("sample #2") {
    assert(originalSet(Seq(0, 1, 2, 3), Seq(1, 3, 3, 1)) === Seq(1, 1, 1))
  }

  test("sample #3") {
    assert(originalSet(Seq(0, 1, 3, 4), Seq(4, 4, 4, 4)) === Seq(0, 0, 1, 3))
  }

  test("sample #4") {
    assert(originalSet(Seq(-1, 0, 1), Seq(1, 2, 1)) === Seq(-1, 1))
  }

  test("sample #5") {
    assert(originalSet(Seq(-2, -1, 0, 1, 2), Seq(1, 2, 2, 2, 1)) === Seq(-2, 1, 1))
  }

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

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

  ignore("full large case") {
    val input = io.Source.fromFile("B-large-practice.in").getLines()
    val expected = io.Source.fromFile("B-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.")
  }

}