SmoothingWindow.scala

package lascala

object SmoothingWindow extends App {

  def minDiff(n: Int, k: Int, ss: Seq[Int]): Int = {

    def seqDiff(xs: Seq[Int], ys: Seq[Int]): Seq[Int] = xs zip ys map { case (x, y) => x - y }

    val groups = (IndexedSeq.fill(k)(List(0)) /: seqDiff(ss.tail, ss.init).zipWithIndex) {
      case (groups, (d, index)) =>
        val i = index % k
        val group = groups(i)
        groups.updated(i, (d + group.head) :: group)
    }

    val maxs = groups map (_.max)
    val mins = groups map (_.min)
    val diffs = seqDiff(maxs, mins)
    val l = diffs.max
    val remainder = ((ss.head + mins.sum) % k + k) % k
    val margin = diffs.map(l - _).sum

    if (remainder > margin) l + 1 else l
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(n, k) = lineIn.next() split ' ' map (_.toInt)
      val ss = lineIn.next() split ' ' map (_.toInt)
      lineOut(s"Case #$i: ${minDiff(n, k, ss)}")
    }

  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()
  }
}

SmoothingWindowTest.scala

import org.scalatest._

import SmoothingWindow._

class SmoothingWindowTest extends FunSuite {

  test("test #1"){
    assert(minDiff(10, 2, Seq(1,2,3,4,5,6,7,8,9)) === 5)
  }

  test("test #2"){
    assert(minDiff(100, 100, Seq(-100)) === 0)
  }

  test("test #3"){
    assert(minDiff(7, 3, Seq(0,12,0,12,0)) === 12)
  }

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

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

    lineComparison(input, expected)
  }

  test("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)
  }

  test("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.")
  }

}