DataPacking.scala

DataPacking.scala

package datapacking

object DataPacking {

  def solve(size: Int, seq: Seq[Int]): Int = {
    @annotation.tailrec
    def find(count: Int, size: Int, seq: Seq[Int]): Int = {
      if (seq.size == 0) count
      else {
        val diff = size - seq.head
        val filtered = lessPop(diff, seq.tail)
        // println(f"$count $size - ${seq.head} = $diff ${seq.tail} $filtered")
        find(count - (seq.tail.size - filtered.size), size, filtered)
      }
    }
    find(seq.size, size, seq)
  }

  def lessPop(max: Int, seq: Seq[Int]): Seq[Int] = {
    @annotation.tailrec
    def lessPop(idx: Int, max: Int, find: Int, seq: Seq[Int]): Seq[Int] = {
      if (seq.size == idx) {
        if (find > -1) seq.take(find) ++ seq.drop(find + 1) else seq
      } else {
        val pop = seq(idx)
        // println(f"idx:$idx max:$max pop:$pop") 
        // if (find > -1) println(f"find:${seq(find)}");
        if (pop == max) lessPop(seq.size, max, idx, seq)
        else if (find == -1 && pop < max || find > -1 && pop < max && seq(find) < pop) lessPop(idx + 1, max, idx, seq)
        else lessPop(idx + 1, max, find, seq)
      }
    }
    lessPop(0, max, -1, seq)
  }

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

  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 test() {
    println(solve(66, Seq(54, 27, 13, 46, 23, 40, 21, 44)) == 5)
    println(solve(100, Seq(10, 20, 70)) == 2)
    println(solve(100, Seq(30, 40, 60, 70)) == 2)
    println(solve(100, Seq(10, 20, 30, 40, 60)) == 3)
    println(solve(700, Seq(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)) == 5)
    println(solve(407, Seq(148, 345, 227, 353, 248, 369, 344, 319, 75, 78)) == 7)
  }

  def lineTest() {
    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 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")
    }
  }

}