DataPackingSmall.scala

DataPackingSmall.scala

package datapacking

object Main {

  def solve(size: Int, seq: Seq[Int]): Int = {
    
    @annotation.tailrec
    def loop(seq: Stream[Int], count: Int): Int = {
//             println(seq)
      if (seq.size <= 1) count + seq.size
      else {
        val withoutMax = seq.tail
        val filtered = withoutMax filter (_ <= size - seq.max)
        val next = if (filtered.isEmpty) withoutMax else seq diff Seq(seq.max, filtered.head)
        loop(next, count + 1)
      }
    }
    loop(seq.sorted.reverse.toStream, 0)
  }

  def test() {

    println(solve(100, Seq(10, 20, 70)) == 2)
    println(solve(100, Seq(10, 20, 1)) == 2)
    println(solve(100, Seq(100, 100, 70)) == 3)
    println(solve(100, Seq(30, 40, 60, 70)) == 2)
    println(solve(100, Seq(10, 20, 30, 40, 60)) == 3)

    val input = """3
3 100
10 20 70
4 100
30 40 60 70
5 100
10 20 30 40 60""".lines

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

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

  }

  def run() {

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

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

  def main(args: Array[String]) {
    test()
//        run()
  }

}