Problem 309487 · hard · Level 03 Linear Management & Searching

Is the Drill Worn Out?

Bayes' rule · law of total probability · sequential updating · hidden state

A drill in a workshop makes one part per shift. It starts sharp, and at the start of every shift a sharp drill becomes worn with probability wear (a worn drill never becomes sharp again). A sharp drill makes a faulty part with probability fault_sharp, a worn one with probability fault_worn. Nobody can see whether the drill is worn; the workshop only sees the parts.

Before the first shift, the probability that the drill is already worn is p0. parts is a string with one character per shift: "x" for a faulty part and "." for a good one. Given the state of the drill, parts are faulty independently of each other.

Write worn_watch(p0, wear, fault_sharp, fault_worn, parts, alarm) that follows the probability that the drill is worn after seeing each shift's part, and returns a tuple (day, p_day, p_last):

  • day is the first shift (counting from 1) after which that probability is at least alarm, and p_day the probability then; both are None if it never happens;
  • p_last is the probability after the last shift (or p0 if parts is empty).

The setup provides drill_log(shifts, seed, worn_from), which returns a random string of parts from a drill that is sharp before shift worn_from and worn from then on, with fault_sharp = 0.05 and fault_worn = 0.3.

Examples

Input:  p0 = 0.0, wear = 0.1, fault_sharp = 0.1, fault_worn = 0.5, parts = "x", alarm = 0.9
Output: (None, None, 0.35714285714285715)
Explanation: before the shift the drill has worn with probability 0.1. A faulty part has
probability 0.1 · 0.5 = 0.05 from a worn drill and 0.9 · 0.1 = 0.09 from a sharp one,
so after seeing it, P(worn) = 0.05 / 0.14 = 0.357.

Input:  p0 = 0.0, wear = 0.1, fault_sharp = 0.1, fault_worn = 0.5, parts = "xxx", alarm = 0.8
Output: (3, 0.9541047595064216, 0.9541047595064216)

Constraints

  • 0 <= p0 < 1, 0 <= wear < 1, 0 < fault_sharp < fault_worn < 1, 0 < alarm <= 1
  • 0 <= len(parts) <= 2 * 10**5
  • floats are compared with a tolerance of 1e-6

Goals

  • Update a probability with Bayes' rule after every observation
  • Let the prior itself change between observations with the law of total probability
  • Turn a stream of noisy observations into a well-timed alarm
Starting Python…