airplaneExercise.scala

// Passenger 1 is 1/100 likely to randomly pick passenger two's seat.

// Passenger 2 is 1/100 likely to have been displaced by passenger 1.

// Passenger 3 is 1/100 likely to have been displaced by passenger 1.
// Passenger 3 is (1/100 * 1/99) likely to have been displaced by passenger 2. Because Passenger 2 was 1/100 likely to have been displaced by passenger 1, and if displaced 1/99 likely to have randomly chosen passenger 3's seat.
// All in all, Passenger 3 is (1/100 + (1/100 * 1/99)) likely to have been displaced.

// Passenger 4 is (1/100 + (1/100 * 1/99) + (1/100 * 1/99 * 1/98)) likely to have been displaced

object Foo {
  def probPassNDisplaced(n: Int, totalSeats: Int = 100): Double = {
    require (n > 2)
    require (n <= totalSeats)

    val probPass2Displaced: Double = 1.toDouble / totalSeats.toDouble
    val passengers: Range.Inclusive = 3 to n

    passengers.foldLeft[Double](probPass2Displaced) { (probPassNMinusOneDisplaced, passN) =>
      val seatsLeftForPassNMinusOneIfTheyWereDisplaced: Int = totalSeats + 2 - passN
      val probPassNDisplaced: Double = probPassNMinusOneDisplaced * (1.0 / seatsLeftForPassNMinusOneIfTheyWereDisplaced)
      probPassNMinusOneDisplaced + probPassNDisplaced
    }
  }
}

// Tests
val expectedProb2: Double = (1.toDouble / 100.toDouble)
val expectedProb3: Double = expectedProb2 + (expectedProb2 * (1.toDouble / 99.toDouble))
val expectedProb4: Double = expectedProb3 + (expectedProb3 * (1.toDouble / 98.toDouble))
val expectedProb5: Double = expectedProb4 + (expectedProb4 * (1.toDouble / 97.toDouble))
assert (Foo.probPassNDisplaced(3) == expectedProb3)
assert (Foo.probPassNDisplaced(4) == expectedProb4)
assert (Foo.probPassNDisplaced(5) == expectedProb5)


// Result
println(Foo.probPassNDisplaced(100)) // 0.4999999999999999