use super::{binomial, error, scalar};
use crate::{Context, Error, Outcome, number, re};
use num_bigint::BigInt;
use num_integer::Integer;
use num_rational::BigRational;
use num_traits::{Signed, ToPrimitive, Zero};
pub(super) fn evaluate(input: &str) -> Outcome {
let fields = input
.strip_prefix("probability_report(")?
.strip_suffix(')')?;
Some((|| {
let fields: Vec<_> = fields.split("; ").collect();
let mut labels = Vec::new();
let mut display = Vec::new();
for field in &fields {
let (label, raw) = field
.split_once(": ")
.ok_or_else(|| error("invalid_expression"))?;
let count = re!(r"^sequences with exactly -?\d+ heads$").is_match(label);
if count {
let value = raw
.parse::<BigInt>()
.map_err(|_| error("invalid_expression"))?;
if value < BigInt::zero() {
return Err(error("invalid_expression"));
}
} else {
let value = raw
.replace(',', "")
.parse::<f64>()
.map_err(|_| error("invalid_expression"))?;
if !value.is_finite() || value < 0.0 {
return Err(error("invalid_expression"));
}
if !matches!(label, "mean" | "variance") && value > 1.0 {
return Err(error("invalid_probability"));
}
}
labels.push(label);
let label = if re!(r"(?i)^p\([a-z][∩∪|][a-z]\)$").is_match(label) {
label.to_ascii_uppercase()
} else {
label.to_string()
};
display.push(format!("{label}: {raw}"));
}
let suppliers = labels
.iter()
.enumerate()
.all(|(i, label)| *label == format!("supplier {} given defective", i + 1));
let pair = labels.join("; ");
if !(suppliers && !labels.is_empty()) && (labels.len() != 2 || !re!(r"(?i)^(?:mean; variance|exactly -?\d+ heads; at least -?\d+ heads|both \w+; second \w+ given first \w+|returned; online given returned|at least -?\d+ successes; -?\d+ successes given at least -?\d+|p\([a-z][∩∪][a-z]\); p\([a-z]\|[a-z]\)|sequences with exactly -?\d+ heads; probability)$").is_match(&pair)) {
return Err(error("invalid_expression"));
}
Ok(display.join("; "))
})())
}
pub(super) fn rewrite(input: &str, context: &Context) -> Outcome {
let s = input.trim().trim_end_matches(['.', '?']);
let model = Model { context };
if let Some(result) = finite_wording(s, &model) {
return Some(result);
}
if let Some(result) = additional_wording(s, &model) {
return Some(result);
}
if let Some(c) = re!(r"(?i)^a fair coin is (?:flipped|tossed) (.+?) times[.;] (?:calculate the )?probability of exactly (.+?) heads(?: and the probability of at least (.+?) heads)?$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
let exact = model.count(&c[2], "invalid_success_count")?;
let value = distribution.event(exact, Event::Exact);
if let Some(tail) = c.get(3) {
let tail = model.count(tail.as_str(), "invalid_success_count")?;
return Ok(report(&[
(format!("exactly {exact} heads"), value),
(format!("at least {tail} heads"), distribution.event(tail, Event::Tail)),
]));
}
Ok(literal(value))
})());
}
if let Some(c) =
re!(r"(?i)^a fair (?:six-sided )?die is rolled (.+?) times; probability of no (.+?)s$")
.captures(s)
{
return Some((|| {
let distribution = model.binomial(&c[1], "1/6")?;
let face = model.count(&c[2], "invalid_success_count")?;
if !(1..=6).contains(&face) {
return Err(error("invalid_success_count"));
}
Ok(literal(distribution.event(0, Event::Exact)))
})());
}
if let Some(c) = re!(r"(?i)^a basketball player makes each free throw with probability (.+?) independently; probability they make exactly (.+?) of (.+)$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[3], &c[1])?;
let successes = model.count(&c[2], "invalid_success_count")?;
Ok(literal(distribution.event(successes, Event::Exact)))
})());
}
if let Some(c) = re!(r"(?i)^a call center resolves (.+?) of calls on the first attempt\. in (.+?) independent calls, probability between (.+?) and (.+?) inclusive are resolved first try$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[2], &c[1])?;
let low = model.count(&c[3], "invalid_success_count")?;
let high = model.count(&c[4], "invalid_success_count")?;
if low > high {
return Err(error("invalid_success_count"));
}
Ok(literal(distribution.interval(low, high)))
})());
}
if let Some(c) = re!(r"(?i)^a server is available (.+?) of the time\. over (.+?) independent intervals, probability it is unavailable in exactly (.+)$").captures(s) {
return Some((|| {
let availability = model.probability(&c[1])?;
let distribution = model.binomial(&c[2], &format!("1-({availability:e})"))?;
let successes = model.count(&c[3], "invalid_success_count")?;
Ok(literal(distribution.event(successes, Event::Exact)))
})());
}
if let Some(c) = re!(r"(?i)^for a binomial (?:model|variable|random variable) with n\s*=\s*(.+?) and p\s*=\s*(.+?), give the mean and variance$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], &c[2])?;
let n = distribution.weights.len() - 1;
let p = distribution.p;
Ok(report(&[
("mean".into(), model.calculate(&format!("{n}*({p:e})"))?),
("variance".into(), model.calculate(&format!("{n}*({p:e})*(1-({p:e}))"))?),
]))
})());
}
if let Some(c) = re!(r"(?i)^a machine succeeds on each independent attempt with probability (.+?)\. in (.+?) attempts, calculate the probability of at least (.+?) successes and the conditional probability of (.+?) successes given at least (.+)$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[2], &c[1])?;
let tail = model.count(&c[3], "invalid_success_count")?;
let exact = model.count(&c[4], "invalid_success_count")?;
let condition = model.count(&c[5], "invalid_success_count")?;
let denominator = distribution.event(condition, Event::Tail);
let joint = if exact < condition { 0.0 } else { distribution.event(exact, Event::Exact) };
let conditional = model.conditional(joint, denominator)?;
Ok(report(&[
(format!("at least {tail} successes"), distribution.event(tail, Event::Tail)),
(format!("{exact} successes given at least {condition}"), conditional),
]))
})());
}
if let Some(c) = re!(r"(?i)^a bag has (.+?) (\w+) and (.+?) (\w+) balls\. draw (.+?) without replacement; probability both are (\w+)$").captures(s) {
return Some((|| {
let a = model.population(&c[1])?;
let b = model.population(&c[3])?;
if !c[2].eq_ignore_ascii_case(&c[6]) || c[2].eq_ignore_ascii_case(&c[4]) {
return Err(error("invalid_probability_model"));
}
let draws = model.population(&c[5])?;
if draws != 2 {
return Err(error("invalid_sample_count"));
}
Ok(literal(model.hypergeometric(a + b, a, draws, draws)?))
})());
}
if let Some(c) = re!(r"(?i)^a bag contains (.+?) (\w+) and (.+?) (\w+) marbles; two are drawn without replacement\. find the probability both are (\w+) and the probability the second is (\w+) given the first is (\w+)$").captures(s) {
return Some((|| {
let a = model.population(&c[1])?;
let b = model.population(&c[3])?;
if !c[2].eq_ignore_ascii_case(&c[5]) || !c[2].eq_ignore_ascii_case(&c[6])
|| !c[4].eq_ignore_ascii_case(&c[7]) || c[2].eq_ignore_ascii_case(&c[4]) {
return Err(error("invalid_probability_model"));
}
let both = model.hypergeometric(a + b, a, 2, 2)?;
if b == 0 {
return Err(error("undefined_conditional_probability"));
}
let conditional = model.calculate(&format!("{a}/{}", a + b - 1))?;
Ok(report(&[
(format!("both {}", c[5].to_ascii_lowercase()), both),
(format!("second {} given first {}", c[6].to_ascii_lowercase(), c[7].to_ascii_lowercase()), conditional),
]))
})());
}
if let Some(c) = re!(r"(?i)^choose (.+?) people from (.+?) (\w+) and (.+?) (\w+); probability the group has exactly (.+?) (\w+)$").captures(s) {
return Some((|| {
let a = model.population(&c[2])?;
let b = model.population(&c[4])?;
if !c[3].eq_ignore_ascii_case(&c[7]) || c[3].eq_ignore_ascii_case(&c[5]) {
return Err(error("invalid_probability_model"));
}
let draws = model.population(&c[1])?;
let successes = model.count(&c[6], "invalid_success_count")?;
Ok(literal(model.hypergeometric(a + b, a, draws, successes)?))
})());
}
if let Some(c) = re!(r"(?i)^a box contains (.+?) (\w+), (.+?) (\w+)\. select (.+?) without replacement; probability exactly (.+?) is (\w+)$").captures(s) {
return Some((|| {
let total = model.population(&c[1])?;
let category = model.population(&c[3])?;
if !c[4].eq_ignore_ascii_case(&c[7]) {
return Err(error("invalid_probability_model"));
}
let draws = model.population(&c[5])?;
let successes = model.count(&c[6], "invalid_success_count")?;
Ok(literal(model.hypergeometric(total, category, draws, successes)?))
})());
}
if let Some(c) = re!(r"(?i)^among (.+?) students, (.+?) study (\w+), (.+?) study (\w+), and (.+?) study both\. given a student studies (\w+), what is the probability they also study (\w+)$").captures(s) {
return Some((|| {
let total = model.population(&c[1])?;
let a = model.population(&c[2])?;
let b = model.population(&c[4])?;
let both = model.population(&c[6])?;
if !c[3].eq_ignore_ascii_case(&c[7]) || !c[5].eq_ignore_ascii_case(&c[8])
|| c[3].eq_ignore_ascii_case(&c[5]) {
return Err(error("invalid_probability_model"));
}
if a > total || b > total || both > a.min(b) || a + b - both > total {
return Err(error("invalid_population"));
}
Ok(literal(model.conditional(both as f64, a as f64)?))
})());
}
if let Some(c) = re!(r"(?i)^a disease affects (.+?) of people\. a test has (.+?) sensitivity and (.+?) specificity\. what is the probability someone has the disease given a positive result$").captures(s) {
return Some((|| {
let prevalence = model.probability(&c[1])?;
let sensitivity = model.probability(&c[2])?;
let specificity = model.probability(&c[3])?;
let joint = model.calculate(&format!("({prevalence:e})*({sensitivity:e})"))?;
let positive = model.calculate(&format!("({joint:e})+(1-({prevalence:e}))*(1-({specificity:e}))"))?;
Ok(literal(model.conditional(joint, positive)?))
})());
}
if let Some(c) = re!(r"(?i)^a factory gets (.+?) of parts from (\w+) and (.+?) from (\w+)\. defect rates are (.+?) and (.+?)\. given a part is defective, probability it came from (\w+)$").captures(s) {
return Some((|| {
let priors = model.priors(&[&c[1], &c[3]])?;
let (a, b) = (priors[0], priors[1]);
if c[2].eq_ignore_ascii_case(&c[4]) {
return Err(error("invalid_probability_model"));
}
let rate_a = model.probability(&c[5])?;
let rate_b = model.probability(&c[6])?;
let joint_a = model.calculate(&format!("({a:e})*({rate_a:e})"))?;
let joint_b = model.calculate(&format!("({b:e})*({rate_b:e})"))?;
let selected = if c[7].eq_ignore_ascii_case(&c[2]) { joint_a }
else if c[7].eq_ignore_ascii_case(&c[4]) { joint_b }
else { return Err(error("invalid_probability_model")); };
Ok(literal(model.conditional(selected, model.calculate(&format!("({joint_a:e})+({joint_b:e})"))?)?))
})());
}
if let Some(c) = re!(r"(?i)^a store sells (.+?) of its goods online; (.+?) of online orders and (.+?) of in-store orders are returned\. find the probability a randomly selected sale is returned and the probability it was online given that it was returned$").captures(s) {
return Some((|| {
let online = model.probability(&c[1])?;
let rate_online = model.probability(&c[2])?;
let rate_store = model.probability(&c[3])?;
let joint = model.calculate(&format!("({online:e})*({rate_online:e})"))?;
let returned = model.calculate(&format!("({joint:e})+(1-({online:e}))*({rate_store:e})"))?;
let conditional = model.conditional(joint, returned)?;
Ok(report(&[("returned".into(), returned), ("online given returned".into(), conditional)]))
})());
}
None
}
fn additional_wording(s: &str, model: &Model<'_>) -> Outcome {
if let Some(c) = re!(r"(?i)^a biased coin has p\(heads\)=(.+?) on each independent toss; what is the probability of exactly (.+?) heads in (.+?) tosses as a reduced fraction$").captures(s) {
return Some((|| {
let (numerator, denominator) = model.exact(&probability_expression(&c[1]))?
.ok_or_else(|| error("invalid_probability_model"))?;
let probability = BigRational::new(numerator, denominator);
if probability.is_negative() || probability > BigRational::from_integer(1.into()) {
return Err(error("invalid_probability"));
}
let trials = model.count(&c[3], "invalid_trial_count")?;
let heads = model.count(&c[2], "invalid_success_count")?;
if trials < 0 { return Err(error("invalid_trial_count")); }
if trials > 10_000 { return Err(error("probability_limit")); }
if heads < 0 { return Err(error("invalid_success_count")); }
if heads > trials { return Ok("rational(0,1) in reduced fraction".into()); }
let (p, q) = (probability.numer(), probability.denom());
if p.is_zero() || p == q {
let certain = (p.is_zero() && heads == 0) || (p == q && heads == trials);
return Ok(format!("rational({},1) in reduced fraction", u8::from(certain)));
}
if q.bits().saturating_mul(trials as u64) > 100_000 {
return Err(error("probability_limit"));
}
let combinations = super::super::integer_queries::choose(
&BigInt::from(trials), &BigInt::from(heads), false)?;
let numerator = combinations * p.clone().pow(heads as u32) * (q - p).pow((trials - heads) as u32);
let denominator = q.clone().pow(trials as u32);
let gcd = numerator.gcd(&denominator);
let expression = format!("rational({},{}) in reduced fraction", numerator / &gcd, denominator / gcd);
if expression.len() > 4_096 { return Err(error("probability_limit")); }
Ok(expression)
})());
}
if let Some(c) = re!(r"(?i)^a sensor alarms with probability (.+?) per trial independently; calculate the probability of at least one alarm in (.+?) trials$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[2], &c[1])?;
Ok(literal(distribution.event(1, Event::Tail)))
})());
}
if let Some(c) = re!(r"(?i)^a fair coin is tossed (.+?) times; calculate the probability of exactly (.+?) heads as a fraction$").captures(s) {
return Some((|| {
let trials = model.count(&c[1], "invalid_trial_count")?;
let heads = model.count(&c[2], "invalid_success_count")?;
if trials < 0 { return Err(error("invalid_trial_count")); }
if trials > 10_000 { return Err(error("probability_limit")); }
let denominator = BigInt::from(1) << trials as usize;
let numerator = if (0..=trials).contains(&heads) {
super::super::integer_queries::choose(&BigInt::from(trials), &BigInt::from(heads), false)?
} else {
BigInt::zero()
};
let gcd = numerator.gcd(&denominator);
Ok(format!("rational({},{}) in reduced fraction", numerator / &gcd, denominator / gcd))
})());
}
if let Some(c) = re!(r"(?i)^a fair coin is tossed (.+?)(?: independent)? times[.;] (?:what is the |compute the exact )probability of (.+) heads$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
Ok(literal(coin_event(model, &distribution, &c[2])?))
})());
}
if let Some(c) =
re!(r"(?i)^for (.+?) independent flips of a fair coin, find p\((.+) heads\)$").captures(s)
{
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
Ok(literal(coin_event(model, &distribution, &c[2])?))
})());
}
if let Some(c) = re!(r"(?i)^(.+?) fair coins are tossed independently\. given that at least (.+?) shows heads, what is the probability both show heads$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
if distribution.weights.len() != 3 { return Err(error("invalid_probability_model")); }
let threshold = model.count(&c[2], "invalid_success_count")?;
let joint = if threshold > 2 { 0.0 } else { distribution.event(2, Event::Exact) };
Ok(literal(model.conditional(joint, distribution.event(threshold, Event::Tail))?))
})());
}
if let Some(c) = re!(r"(?i)^a fair coin is tossed (.+?) times\. given at least (.+?) heads, what is the probability there are exactly (.+?) heads$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
let threshold = model.count(&c[2], "invalid_success_count")?;
let successes = model.count(&c[3], "invalid_success_count")?;
let joint = if successes < threshold { 0.0 } else { distribution.event(successes, Event::Exact) };
Ok(literal(model.conditional(joint, distribution.event(threshold, Event::Tail))?))
})());
}
if let Some(c) = re!(r"(?i)^a fair coin is tossed (.+?) times\. find the exact number of sequences with exactly (.+?) heads, then give the probability$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "0.5")?;
let trials = distribution.weights.len() - 1;
let successes = model.count(&c[2], "invalid_success_count")?;
let count = if successes < 0 || successes > trials as i64 { BigInt::zero() }
else { super::super::integer_queries::choose(&BigInt::from(trials), &BigInt::from(successes), false)? };
Ok(format!("probability_report(sequences with exactly {successes} heads: {count}; probability: {})", number(distribution.event(successes, Event::Exact))))
})());
}
if let Some(c) = re!(r"(?i)^flip a fair coin until the first (head|tail)\. what is the probability the first (head|tail) occurs on toss (.+)$").captures(s) {
return Some((|| {
if !c[1].eq_ignore_ascii_case(&c[2]) { return Err(error("invalid_probability_model")); }
let toss = model.count(&c[3], "invalid_trial_count")?;
if toss < 1 { return Err(error("invalid_trial_count")); }
Ok(literal(model.calculate(&format!("(1/2)^{toss}"))?))
})());
}
if let Some(c) = re!(r"(?i)^roll a fair six-sided die (.+?) times independently\. find the probability of exactly (.+?) (ones|twos|threes|fours|fives|sixes)$").captures(s) {
return Some((|| {
let distribution = model.binomial(&c[1], "1/6")?;
let successes = model.count(&c[2], "invalid_success_count")?;
Ok(literal(distribution.event(successes, Event::Exact)))
})());
}
if let Some(c) = re!(r"(?i)^a fair six-sided die is rolled until a (.+?) appears\. what is the probability it appears within (.+?) rolls$").captures(s) {
return Some((|| {
let face = model.count(&c[1], "invalid_success_count")?;
if !(1..=6).contains(&face) { return Err(error("invalid_success_count")); }
let trials = model.count(&c[2], "invalid_trial_count")?;
if trials < 0 { return Err(error("invalid_trial_count")); }
Ok(literal(model.calculate(&format!("1-(5/6)^{trials}"))?))
})());
}
if let Some(c) = re!(r"(?i)^a (?:bag has|box contains) (.+?) (\w+) and (.+?) (\w+) (?:balls|tokens)\. (?:draw|select) (.+?) without replacement\. (?:what is the probability exactly (.+?) are (\w+)|find the chance of at least (.+?) (\w+) tokens)$").captures(s) {
return Some((|| {
let a = model.population(&c[1])?;
let b = model.population(&c[3])?;
let draws = model.count(&c[5], "invalid_sample_count")?;
let (raw, label, tail) = if let Some(exact) = c.get(6) { (exact.as_str(), &c[7], false) }
else { (&c[8], &c[9], true) };
if !c[2].eq_ignore_ascii_case(label) || c[2].eq_ignore_ascii_case(&c[4]) {
return Err(error("invalid_probability_model"));
}
let successes = model.count(raw, "invalid_success_count")?;
let value = if tail { model.hypergeometric_tail(a+b, a, draws, successes)? }
else { model.hypergeometric(a+b, a, draws, successes)? };
Ok(literal(value))
})());
}
if let Some(c) = re!(r"(?i)^([a-z]) and ([a-z]) are events with p\(([a-z])\)=(.+?), p\(([a-z])\)=(.+?), p\(([a-z])∩([a-z])\)=(.+?)\. find p\(([a-z])∪([a-z])\) and p\(([a-z])\|([a-z])\)$").captures(s) {
return Some((|| {
if !same(&c[1], &[&c[3],&c[7],&c[10],&c[12]]) || !same(&c[2], &[&c[5],&c[8],&c[11],&c[13]]) || c[1].eq_ignore_ascii_case(&c[2]) {
return Err(error("invalid_probability_model"));
}
let (a, b, joint) = model.joint(&c[4], &c[6], &c[9])?;
let union = model.calculate(&format!("({a:e})+({b:e})-({joint:e})"))?;
let conditional = model.conditional(joint, b)?;
let (a_label,b_label) = (c[1].to_ascii_uppercase(), c[2].to_ascii_uppercase());
Ok(report(&[(format!("P({a_label}∪{b_label})"), union), (format!("P({a_label}|{b_label})"), conditional)]))
})());
}
if let Some(c) = re!(r"(?i)^events ([a-z]) and ([a-z]) have probabilities (.+?) and (.+?), and are independent\. given ([a-z]) or ([a-z]) occurs, what is p\(([a-z])∩([a-z])\)$").captures(s) {
return Some((|| {
if !same(&c[1], &[&c[5],&c[7]]) || !same(&c[2], &[&c[6],&c[8]]) || c[1].eq_ignore_ascii_case(&c[2]) { return Err(error("invalid_probability_model")); }
let a = model.probability(&c[3])?;
let b = model.probability(&c[4])?;
let joint = model.calculate(&format!("({a:e})*({b:e})"))?;
let union = model.calculate(&format!("({a:e})+({b:e})-({joint:e})"))?;
Ok(literal(model.conditional(joint, union)?))
})());
}
if let Some(c) = re!(r"(?i)^for independent events ([a-z]) and ([a-z]) with probabilities (.+?) and (.+?), calculate p\(([a-z])∩([a-z])\), then p\(([a-z])\|([a-z])\)$").captures(s) {
return Some((|| {
if !same(&c[1], &[&c[5],&c[7]]) || !same(&c[2], &[&c[6],&c[8]]) || c[1].eq_ignore_ascii_case(&c[2]) { return Err(error("invalid_probability_model")); }
let a = model.probability(&c[3])?;
let b = model.probability(&c[4])?;
let joint = model.calculate(&format!("({a:e})*({b:e})"))?;
let conditional = model.conditional(joint, b)?;
let (a_label,b_label) = (c[1].to_ascii_uppercase(),c[2].to_ascii_uppercase());
Ok(report(&[(format!("P({a_label}∩{b_label})"),joint),(format!("P({a_label}|{b_label})"),conditional)]))
})());
}
if let Some(c) = re!(r"(?i)^a screening test has sensitivity (.+?) and specificity (.+?)\. disease prevalence is (.+?); calculate the probability of disease given a positive result$").captures(s) {
return Some((|| {
let sensitivity = model.probability(&c[1])?;
let specificity = model.probability(&c[2])?;
let prior = model.probability(&c[3])?;
Ok(literal(model.posterior(&[prior,1.0-prior], &[sensitivity,1.0-specificity])?[0]))
})());
}
if let Some(c) = re!(r"(?i)^a person takes a test with false-positive rate (.+?) and false-negative rate (.+?)\. prior probabilities of the condition and no condition are (.+?) and (.+?)\. find p\(condition\s*\|\s*positive\)$").captures(s) {
return Some((|| {
let false_positive = model.probability(&c[1])?;
let false_negative = model.probability(&c[2])?;
let priors = model.priors(&[&c[3], &c[4]])?;
Ok(literal(model.posterior(&priors,&[1.0-false_negative,false_positive])?[0]))
})());
}
if let Some(c) = re!(r"(?i)^a screening program has exhaustive prevalence priors: (.+?) affected, (.+?) unaffected\. sensitivity is (.+?) and specificity (.+?)\. given a (positive|negative) result, what is p\(affected\)$").captures(s) {
return Some((|| {
let priors = model.priors(&[&c[1], &c[2]])?;
let sensitivity = model.probability(&c[3])?;
let specificity = model.probability(&c[4])?;
let likelihoods = if c[5].eq_ignore_ascii_case("negative") { [1.0-sensitivity,specificity] }
else { [sensitivity,1.0-specificity] };
Ok(literal(model.posterior(&priors,&likelihoods)?[0]))
})());
}
if let Some(c) = re!(r"(?i)^a box comes from one of (.+?) exhaustive suppliers with prior probabilities (.+?)\. their defect probabilities are (.+?)\. given a defective item, calculate the posterior probability of each supplier$").captures(s) {
return Some((|| {
let suppliers = model.count(&c[1], "invalid_population")?;
let priors = model.priors(&c[2].split(',').collect::<Vec<_>>())?;
let likelihoods = model.probabilities(&c[3])?;
if suppliers < 1 || suppliers as usize != priors.len() { return Err(error("invalid_probability_model")); }
let posteriors = model.posterior(&priors,&likelihoods)?;
Ok(report(&posteriors.into_iter().enumerate().map(|(i,p)| (format!("supplier {} given defective", i+1),p)).collect::<Vec<_>>()))
})());
}
if let Some(c) = re!(r"(?i)^for exhaustive mutually exclusive outcomes (.+?) with priors (.+?) and likelihoods of evidence (\w+) equal to (.+?), find p\((\w+)\|(\w+)\)$").captures(s) {
return Some((|| {
let names: Vec<_> = c[1].split(',').map(str::trim).collect();
if names.iter().enumerate().any(|(i,n)| n.is_empty() || !re!(r"^\w+$").is_match(n) || names[..i].iter().any(|prior| prior.eq_ignore_ascii_case(n))) || !c[3].eq_ignore_ascii_case(&c[6]) {
return Err(error("invalid_probability_model"));
}
let priors = model.priors(&c[2].split(',').collect::<Vec<_>>())?;
let likelihoods = model.probabilities(&c[4])?;
if names.len() != priors.len() { return Err(error("invalid_probability_model")); }
if let Some(source) = names.iter().position(|name| name.eq_ignore_ascii_case(&c[3])) {
model.evidence_identity(source, &c[4])?;
}
let chosen = names.iter().position(|name| name.eq_ignore_ascii_case(&c[5])).ok_or_else(|| error("invalid_probability_model"))?;
Ok(literal(model.posterior(&priors,&likelihoods)?[chosen]))
})());
}
None
}
fn same(name: &str, labels: &[&str]) -> bool {
labels.iter().all(|label| name.eq_ignore_ascii_case(label))
}
fn coin_event(model: &Model<'_>, distribution: &Distribution, event: &str) -> Result<f64, Error> {
let c = re!(r"(?i)^(?:(exactly|at least) (.+)|(.+) or fewer)$")
.captures(event)
.ok_or_else(|| error("invalid_probability_model"))?;
let (raw, operation) = if let Some(raw) = c.get(3) {
(raw.as_str(), Event::Cdf)
} else {
(
&c[2],
if c[1].eq_ignore_ascii_case("exactly") {
Event::Exact
} else {
Event::Tail
},
)
};
Ok(distribution.event(model.count(raw, "invalid_success_count")?, operation))
}
fn probability_expression(input: &str) -> String {
let input = input.trim();
if let Some(percent) = input.strip_suffix('%') {
format!("({percent})/100")
} else {
input.to_string()
}
}
fn literal(value: f64) -> String {
format!("real({value:e})")
}
fn report(fields: &[(String, f64)]) -> String {
let fields = fields
.iter()
.map(|(label, value)| format!("{label}: {}", number(*value)))
.collect::<Vec<_>>()
.join("; ");
format!("probability_report({fields})")
}
struct Model<'a> {
context: &'a Context,
}
impl Model<'_> {
fn calculate(&self, expression: &str) -> Result<f64, Error> {
scalar(expression, self.context)
}
fn count(&self, input: &str, code: &str) -> Result<i64, Error> {
let input = match input.to_ascii_lowercase().as_str() {
"zero" => "0",
"one" => "1",
"two" => "2",
"three" => "3",
"four" => "4",
"five" => "5",
"six" => "6",
"seven" => "7",
"eight" => "8",
"nine" => "9",
"ten" => "10",
_ => input,
};
if let Some((numerator, denominator)) = self.exact(input)? {
if denominator != BigInt::from(1) {
return Err(error(code));
}
if numerator.abs() > BigInt::from(9_007_199_254_740_991_i64) {
return Err(error("probability_limit"));
}
return numerator.to_i64().ok_or_else(|| error("probability_limit"));
}
let count = self.calculate(input)?;
if count.fract() != 0.0 {
return Err(error(code));
}
if count.abs() > 9_007_199_254_740_991.0 {
return Err(error("probability_limit"));
}
Ok(count as i64)
}
fn population(&self, input: &str) -> Result<i64, Error> {
let count = self.count(input, "invalid_population")?;
if count < 0 {
return Err(error("invalid_population"));
}
Ok(count)
}
fn probability(&self, input: &str) -> Result<f64, Error> {
let expression = probability_expression(input);
if let Some((numerator, denominator)) = self.exact(&expression)?
&& (numerator.is_negative() || numerator > denominator)
{
return Err(error("invalid_probability"));
}
let probability = self.calculate(&expression)?;
if !(0.0..=1.0).contains(&probability) {
return Err(error("invalid_probability"));
}
Ok(probability)
}
fn binomial(&self, trials: &str, probability: &str) -> Result<Distribution, Error> {
let n = self.count(trials, "invalid_trial_count")?;
if n < 0 {
return Err(error("invalid_trial_count"));
}
if n > 10_000 {
return Err(error("probability_limit"));
}
let p = self.probability(probability)?;
Ok(Distribution {
weights: binomial(n as usize, p),
p,
})
}
fn probabilities(&self, input: &str) -> Result<Vec<f64>, Error> {
input
.split(',')
.map(|part| self.probability(part.trim()))
.collect()
}
fn exact(&self, expression: &str) -> Result<Option<(BigInt, BigInt)>, Error> {
match super::super::integer_queries::ratio_value(expression) {
Ok(value) => Ok(Some(value)),
Err(e)
if matches!(
e.0.as_str(),
"invalid_integer_expression" | "non_rational_expression"
) =>
{
Ok(None)
}
Err(e) => Err(e),
}
}
fn priors(&self, inputs: &[&str]) -> Result<Vec<f64>, Error> {
let priors = inputs
.iter()
.map(|input| self.probability(input))
.collect::<Result<Vec<_>, _>>()?;
let sum = inputs
.iter()
.map(|input| format!("({})", probability_expression(input)))
.collect::<Vec<_>>()
.join("+");
if let Some((numerator, denominator)) = self.exact(&sum)?
&& numerator != denominator
{
return Err(error("invalid_probability_model"));
}
if priors.is_empty() || (priors.iter().sum::<f64>() - 1.0).abs() > 4.0 * f64::EPSILON {
return Err(error("invalid_probability_model"));
}
Ok(priors)
}
fn joint(&self, a: &str, b: &str, joint: &str) -> Result<(f64, f64, f64), Error> {
let values = (
self.probability(a)?,
self.probability(b)?,
self.probability(joint)?,
);
let (a, b, joint) = (
probability_expression(a),
probability_expression(b),
probability_expression(joint),
);
for difference in [
format!("({a})-({joint})"),
format!("({b})-({joint})"),
format!("1-({a})-({b})+({joint})"),
] {
if let Some((numerator, _)) = self.exact(&difference)?
&& numerator.is_negative()
{
return Err(error("invalid_probability_model"));
}
}
let (a, b, joint) = values;
let tolerance = 4.0 * f64::EPSILON;
if ((a == 0.0 || b == 0.0) && joint != 0.0)
|| joint - tolerance > a.min(b)
|| joint + tolerance < (a + b - 1.0).max(0.0)
{
return Err(error("invalid_probability_model"));
}
Ok(values)
}
fn evidence_identity(&self, source: usize, input: &str) -> Result<(), Error> {
for (index, raw) in input.split(',').enumerate() {
let expected = usize::from(index == source);
let expression = probability_expression(raw);
let valid = if let Some((numerator, denominator)) = self.exact(&expression)? {
numerator == denominator * expected
} else {
self.probability(raw)? == expected as f64
};
if !valid {
return Err(error("invalid_probability_model"));
}
}
Ok(())
}
fn posterior(&self, priors: &[f64], likelihoods: &[f64]) -> Result<Vec<f64>, Error> {
if priors.is_empty()
|| priors.len() != likelihoods.len()
|| (priors.iter().sum::<f64>() - 1.0).abs() > 4.0 * f64::EPSILON
{
return Err(error("invalid_probability_model"));
}
if priors
.iter()
.chain(likelihoods)
.any(|p| !(0.0..=1.0).contains(p))
{
return Err(error("invalid_probability"));
}
let joints = priors
.iter()
.zip(likelihoods)
.map(|(p, l)| self.calculate(&format!("({p:e})*({l:e})")))
.collect::<Result<Vec<_>, _>>()?;
let total = joints.iter().sum();
joints
.into_iter()
.map(|joint| self.conditional(joint, total))
.collect()
}
fn hypergeometric_tail(
&self,
total: i64,
category: i64,
draws: i64,
successes: i64,
) -> Result<f64, Error> {
self.sample_domain(total, category, draws)?;
if draws > 10_000 {
return Err(error("probability_limit"));
}
let start = successes.max(0).max(draws - (total - category));
let end = draws.min(category);
let choose =
|n, k| super::super::integer_queries::choose(&BigInt::from(n), &BigInt::from(k), false);
let mut numerator = BigInt::zero();
for k in start..=end {
numerator += choose(category, k)? * choose(total - category, draws - k)?;
}
let denominator = choose(total, draws)?;
let gcd = numerator.gcd(&denominator);
self.integer_ratio(numerator / &gcd, denominator / gcd)
}
fn sample_domain(&self, total: i64, category: i64, draws: i64) -> Result<(), Error> {
if total < 0 || category < 0 || category > total {
return Err(error("invalid_population"));
}
if draws < 0 || draws > total {
return Err(error("invalid_sample_count"));
}
Ok(())
}
fn conditional(&self, joint: f64, condition: f64) -> Result<f64, Error> {
if condition == 0.0 {
return Err(error("undefined_conditional_probability"));
}
self.calculate(&format!("({joint:e})/({condition:e})"))
}
fn hypergeometric(
&self,
total: i64,
category: i64,
draws: i64,
successes: i64,
) -> Result<f64, Error> {
self.sample_domain(total, category, draws)?;
if successes < 0
|| successes > category
|| successes > draws
|| draws - successes > total - category
{
return Ok(0.0);
}
let choose =
|n, k| super::super::integer_queries::choose(&BigInt::from(n), &BigInt::from(k), false);
let numerator = choose(category, successes)? * choose(total - category, draws - successes)?;
let denominator = choose(total, draws)?;
let gcd = numerator.gcd(&denominator);
self.integer_ratio(numerator / &gcd, denominator / gcd)
}
fn integer_ratio(&self, numerator: BigInt, denominator: BigInt) -> Result<f64, Error> {
if numerator.is_zero() {
return Ok(0.0);
}
let coordinate = |value: BigInt| {
let shift = value.bits().saturating_sub(64) as usize;
((value >> shift).to_f64().unwrap(), shift)
};
let (n, ne) = coordinate(numerator);
let (d, de) = coordinate(denominator);
let exponent = ne as i64 - de as i64;
self.calculate(&format!("({n:e})/({d:e})*2^({exponent})"))
}
}
enum Event {
Exact,
Tail,
Cdf,
}
struct Distribution {
weights: Vec<f64>,
p: f64,
}
impl Distribution {
fn event(&self, successes: i64, event: Event) -> f64 {
self.weights
.iter()
.enumerate()
.filter(|(index, _)| match event {
Event::Exact => *index as i64 == successes,
Event::Tail => *index as i64 >= successes,
Event::Cdf => *index as i64 <= successes,
})
.map(|(_, value)| value)
.sum::<f64>()
.clamp(0.0, 1.0)
}
fn interval(&self, low: i64, high: i64) -> f64 {
self.weights
.iter()
.enumerate()
.filter(|(index, _)| (*index as i64 >= low) && (*index as i64 <= high))
.map(|(_, value)| value)
.sum::<f64>()
.clamp(0.0, 1.0)
}
}
fn finite_categories(input: &str, model: &Model<'_>) -> Result<(Vec<(String, i64)>, i64), Error> {
let supplied = input.replace(", and ", ", ").replace(" and ", ", ");
let parts = super::split_arguments(&supplied)?;
if parts.is_empty() || parts.len() > 64 {
return Err(error("probability_limit"));
}
let mut categories = Vec::new();
let mut total = 0_i64;
for part in parts {
let pair = re!(r"(?i)^(.+?) ([a-z]+)$")
.captures(part)
.ok_or_else(|| error("invalid_probability_model"))?;
let count = model.population(&pair[1])?;
let label = pair[2].to_ascii_lowercase();
if categories
.iter()
.any(|(prior, _): &(String, i64)| prior == &label)
{
return Err(error("invalid_probability_model"));
}
total = total
.checked_add(count)
.filter(|n| *n <= 9_007_199_254_740_991)
.ok_or_else(|| error("probability_limit"))?;
categories.push((label, count));
}
Ok((categories, total))
}
fn exact_probability(numerator: BigInt, denominator: BigInt, reduced: bool) -> String {
let value = BigRational::new(numerator, denominator);
format!(
"rational({},{}){}",
value.numer(),
value.denom(),
if reduced { " in reduced fraction" } else { "" }
)
}
fn two_spin_product(
sectors: i64,
first: i64,
last: i64,
spins: i64,
divisor: i64,
reduced: bool,
) -> Result<String, Error> {
if sectors <= 0 || first != 1 || last != sectors {
return Err(error("invalid_population"));
}
if spins != 2 {
return Err(error("invalid_trial_count"));
}
if divisor <= 0 {
return Err(error("invalid_probability_model"));
}
let denominator = BigInt::from(sectors) * BigInt::from(sectors);
if divisor == 1 {
return Ok(exact_probability(denominator.clone(), denominator, reduced));
}
if BigInt::from(divisor) > denominator {
return Ok(exact_probability(BigInt::zero(), denominator, reduced));
}
let work = sectors.min(divisor);
if work > 100_000 {
return Err(error("probability_limit"));
}
let (whole, remainder) = (sectors / divisor, sectors % divisor);
let mut numerator = BigInt::zero();
for residue in 1..=work {
let multiplicity = whole + i64::from(residue <= remainder);
let partners = sectors / (divisor / residue.gcd(&divisor));
numerator += BigInt::from(multiplicity) * BigInt::from(partners);
}
Ok(exact_probability(numerator, denominator, reduced))
}
fn uniform_exclusion(c: ®ex::Captures<'_>, model: &Model<'_>) -> Result<String, Error> {
let lower = BigInt::from(model.count(&c[1], "invalid_population")?);
let upper = BigInt::from(model.count(&c[2], "invalid_population")?);
let divisors = [3, 4, 5]
.map(|index| model.count(&c[index], "invalid_probability_model"))
.into_iter()
.collect::<Result<Vec<_>, _>>()?;
if lower > upper {
return Err(error("invalid_population"));
}
if divisors.iter().any(|divisor| *divisor <= 0) {
return Err(error("invalid_probability_model"));
}
let (a, b, excluded) = (
BigInt::from(divisors[0]),
BigInt::from(divisors[1]),
BigInt::from(divisors[2]),
);
let ab = a.lcm(&b);
let multiples = |divisor: &BigInt| upper.div_floor(divisor) - (&lower - 1u8).div_floor(divisor);
let numerator = multiples(&a) + multiples(&b)
- multiples(&ab)
- multiples(&a.lcm(&excluded))
- multiples(&b.lcm(&excluded))
+ multiples(&ab.lcm(&excluded));
Ok(exact_probability(
numerator,
upper - lower + 1u8,
c.get(6).is_some(),
))
}
fn finite_wording(input: &str, model: &Model<'_>) -> Outcome {
if let Some(c) = re!(r"(?i)^for a uniformly selected integer from (.+?) through (.+?)(?: inclusive)?, (?:what is|give|calculate) (?:the )?(?:exact )?probability (?:that )?it is divisible by (.+?) or (.+?),? but not by (.+?)(\?\s*(?:give|return|report) (?:a |the )?reduced fraction|,? as a reduced fraction)?$").captures(input) {
return Some(if input.len() > 4096 { Err(error("probability_limit")) } else { uniform_exclusion(&c, model) });
}
if let Some(c) = re!(r"(?i)^a fair spinner has equally likely integer outcomes (.+?) through (.+?); (.+?) independent spins are made, and what is the exact probability that their product is divisible by (.+)$").captures(input) {
return Some((|| {
if input.len() > 4096 { return Err(error("probability_limit")); }
let first = model.count(&c[1], "invalid_population")?;
let last = model.population(&c[2])?;
let spins = model.count(&c[3], "invalid_trial_count")?;
let divisor = model.count(&c[4], "invalid_probability_model")?;
two_spin_product(last, first, last, spins, divisor, false)
})());
}
if let Some(c) = re!(r"(?i)^for independent uniform integers ([a-z]) and ([a-z]) chosen from (.+?) through (.+?) inclusive, give the exact probability that ([a-z])\s*\*?\s*([a-z]) is divisible by (.+)$").captures(input) {
return Some((|| {
if input.len() > 4096 { return Err(error("probability_limit")); }
let first = model.count(&c[3], "invalid_population")?;
let last = model.population(&c[4])?;
let divisor = model.count(&c[7], "invalid_probability_model")?;
let vars = [&c[1], &c[2]];
if vars[0].eq_ignore_ascii_case(vars[1]) || c[5].eq_ignore_ascii_case(&c[6])
|| ![&c[5], &c[6]].iter().all(|name| vars.iter().any(|var| var.eq_ignore_ascii_case(name)))
{
return Err(error("invalid_probability_model"));
}
two_spin_product(last, first, last, 2, divisor, false)
})());
}
if let Some(c) = re!(r"(?i)^a (?:circular )?spinner has (.+?) equal sectors numbered (.+?) through (.+?)\. it is spun (?:independently )?(.+?); (?:find|calculate|give) (?:the )?probability that the product is divisible by (.+?), (?:reduced(?: to lowest terms)?|as a reduced fraction)$").captures(input) {
return Some((|| {
if input.len() > 4096 { return Err(error("probability_limit")); }
let sectors = model.population(&c[1])?;
let first = model.count(&c[2], "invalid_population")?;
let last = model.count(&c[3], "invalid_population")?;
let spins = match c[4].to_ascii_lowercase().as_str() {
"once" => 1,
"twice" => 2,
"thrice" => 3,
_ => {
let times = re!(r"(?i)^(.+) times$").captures(&c[4])
.ok_or_else(|| error("invalid_trial_count"))?;
model.count(×[1], "invalid_trial_count")?
},
};
let divisor = model.count(&c[5], "invalid_probability_model")?;
two_spin_product(sectors, first, last, spins, divisor, true)
})());
}
if let Some(c) = re!(r"(?i)^a box has (.+?) balls; find the probability of drawing (?:two|2) ([a-z]+) balls in a row without replacement$").captures(input) {
return finite_wording(&format!("a bag contains {} tokens; what is the probability of drawing a {} token, then a {} token without replacement", &c[1], &c[2], &c[2]), model);
}
if let Some(c) = re!(r"(?i)^a box contains (.+?) tokens; two are drawn without replacement\. find the probability they have different colors$").captures(input) {
return Some((|| {
let (categories, total) = finite_categories(&c[1], model)?;
if total < 2 { return Err(error("invalid_sample_count")); }
let denominator = BigInt::from(total) * BigInt::from(total - 1);
let same = categories.iter().map(|(_, count)| BigInt::from(*count) * BigInt::from(*count - 1)).sum::<BigInt>();
let numerator = &denominator - same;
let gcd = numerator.gcd(&denominator);
Ok(format!("rational({},{})", numerator / &gcd, denominator / gcd))
})());
}
if let Some(c) = re!(r"(?i)^a bag contains (.+?) tokens; what is the probability of drawing (.+?) without replacement$").captures(input) {
return Some((|| {
let (mut categories, total) = finite_categories(&c[1], model)?;
let mut draws = Vec::new();
for event in re!(r"(?i),?\s+then\s+").split(&c[2]) {
let event = re!(r"(?i)^(?:a |an |one )?([a-z]+) token$").captures(event.trim()).ok_or_else(|| error("invalid_probability_model"))?;
let index = categories.iter().position(|(name, _)| name.eq_ignore_ascii_case(&event[1])).ok_or_else(|| error("invalid_probability_model"))?;
draws.push(index);
}
if draws.is_empty() || draws.len() > 64 { return Err(error("probability_limit")); }
if draws.len() as i64 > total { return Err(error("invalid_sample_count")); }
let mut numerator = BigInt::from(1); let mut denominator = BigInt::from(1);
for (draw, index) in draws.into_iter().enumerate() {
let count = &mut categories[index].1;
numerator *= (*count).max(0);
denominator *= total - draw as i64;
*count = count.saturating_sub(1);
}
let gcd = numerator.gcd(&denominator);
Ok(format!("rational({},{})", numerator / &gcd, denominator / gcd))
})());
}
if let Some(c) = re!(r"(?i)^a fair (.+?)-sided die is rolled (.+?); (?:find|calculate) the probability that the total is (at least|at most|exactly) (.+)$").captures(input) {
return Some((|| {
let sides = model.population(&c[1])?;
if sides == 0 { return Err(error("invalid_population")); }
let rolls = match c[2].to_ascii_lowercase().as_str() {
"once" => 1,
"twice" => 2,
"thrice" => 3,
_ => {
let times = re!(r"(?i)^(.+) times$").captures(&c[2]).ok_or_else(|| error("invalid_trial_count"))?;
model.count(×[1], "invalid_trial_count")?
},
};
if rolls < 0 { return Err(error("invalid_trial_count")); }
let threshold = model.count(&c[4], "invalid_success_count")?;
let maximum = sides.checked_mul(rolls).ok_or_else(|| error("probability_limit"))?;
if sides > 1000 || rolls > 1000 || maximum > 100_000 || maximum.checked_mul(rolls).is_none_or(|work| work > 1_000_000) { return Err(error("probability_limit")); }
let (sides, rolls) = (sides as usize, rolls as usize);
let mut counts = vec![BigInt::from(1)];
for roll in 1..=rolls {
let mut next = vec![BigInt::zero(); roll*sides+1];
let mut window = BigInt::zero();
for (sum, value) in next.iter_mut().enumerate() {
if sum > 0 && sum-1 < counts.len() { window += &counts[sum-1]; }
if sum > sides && sum-sides-1 < counts.len() { window -= &counts[sum-sides-1]; }
*value = window.clone();
}
counts = next;
}
let numerator: BigInt = counts.into_iter().enumerate().filter(|(sum, _)| {
let sum = *sum as i64;
if c[3].eq_ignore_ascii_case("at least") { sum >= threshold }
else if c[3].eq_ignore_ascii_case("at most") { sum <= threshold }
else { sum == threshold }
}).map(|(_, count)| count).sum();
let denominator = BigInt::from(sides).pow(rolls as u32);
let gcd = numerator.gcd(&denominator);
Ok(format!("rational({},{})", numerator / &gcd, denominator / gcd))
})());
}
None
}