1 The smallest free number

1_the_smallest_free_number.scala

package smallest.free.number

trait Bench {
  def bench[A](body: => A) = {
    val start = System.currentTimeMillis()
    val result = body
    val end = System.currentTimeMillis()
    println(s"time: ${end - start}")
    result
  }
}

object Specification extends Bench {
  def minfree(xs: Seq[Int]) = ((Stream from 0) \\ xs).head

  implicit class SeqOps[A](us: Seq[A]) {
    def \\(vs: Seq[A]) = us.filter(!vs.contains(_))
  }
}

object ArrayBasedSolution extends Bench {
  def search(xs: Seq[Boolean]) = xs.takeWhile(x => x).length

  def checklist(xs: Seq[Int]) = {
    val n = xs.length
    val a = Array.tabulate(n + 1)(_ => false)
    xs.foreach(i => if (i <= n) a(i) = true)
    a
  }

  def minfree(xs: Seq[Int]) = search(checklist(xs))
}

object DivideAndConquerSolution extends Bench {
  def minfree(xs: Seq[Int]) = minfrom(0, xs.length, xs)

  @scala.annotation.tailrec
  def minfrom(a: Int, n: Int, xs: Seq[Int]): Int = {
    val b = a + 1 + n / 2
    val (us, vs) = xs.partition(_ < b)
    val m = us.length
    if (n == 0) {
      a
    } else if (m == b - a) {
      minfrom(b, n - m, vs)
    } else {
      minfrom(a, m, us)
    }
  }
}