Property based test with generators for algorithm: "Find the smallest positive integer that does not occur in a given sequence"

Question

I stumbled upon this challenge on stackoverflow while learning about property based testing in scala using ScalaCheck.

Find the smallest positive integer that does not occur in a given sequence

I thought of trying to write a generator driven property based test for this problem to check the validity of my program but can't seem to be able to think of a how to write a relevant test case. I understand that I could write a table driven property based testing for this use case but that limit the number of properties I could test this algo with.

import scala.annotation.tailrec

object Solution extends App {
  def solution(a: Array[Int]): Int = {
    val posNums = a.toSet.filter(_ > 0)

    @tailrec
    def checkForSmallestNum(ls: Set[Int], nextMin: Int): Int = {
      if (ls.contains(nextMin)) checkForSmallestNum(ls, nextMin + 1)
      else nextMin
    }

    checkForSmallestNum(posNums, 1)
  }
}

Answer 1

Using Scalatest's (since you did tag scalatest) Scalacheck integration and Scalatest matchers, something like

forAll(Gen.listOf(Gen.posNum[Int]) -> "ints") { ints =>
  val asSet = ints.toSet
  val smallestNI = Solution.solution(ints.toArray)
  asSet shouldNot contain(smallestNI)

  // verify that adding non-positive ints doesn't change the result
  forAll(
    Gen.frequency(
      1 -> Gen.const(0),
      10 -> Gen.negNum[Int]
    ) -> "nonPos"
  ) { nonPos =>
    // Adding a non-positive integer to the input shouldn't affect the result
    Solution.solution((nonPos :: ints).toArray) shouldBe smallestNI
  }

  // More of a property-based approach
  if (smallestNI > 1) {
    forAll(Gen.oneOf(1 until smallestNI) -> "x") { x =>
      asSet should contain(x)
    }
  } else succeed  // vacuous

  // Alternatively, but perhaps in a less property-based way
  (1 until smallestNI).foreach { x =>
    asSet should contain(x)
  }
}

Note that if scalatest is set to try forAlls 100 times, the nested property check will check values 10k times. Since smallestNI will nearly always be less than the number of trials (as listOf rarely generates long lists), the exhaustive check will in practice be faster than the nested property check.

The overall trick, is that if something is the least positive integer for which some predicate applies, that's the same as saying that for all positive integers less than that something the predicate does not apply.