use super::{affine_value, bounded, choose, decimal, err, factorial, ratio_value, value, wording};
use crate::{Error, re};
use num_bigint::BigInt;
use num_integer::Integer;
use num_rational::BigRational;
use num_traits::{One, Signed, Zero};
#[derive(Clone, Copy)]
enum Family {
LinearBlock,
FiniteConjunctionReport,
FiniteIntervalReport,
ConstrainedDigitCodes,
LetterWords,
Committees,
LabeledGraphs,
SubgroupCommittees,
DigitCodes,
RollOutcomes,
ExclusiveMultiples,
GrowingDifferences,
DivideSequence,
AffineSequence,
OddDifferences,
IndexedSequence,
IndexedAffineList,
DivisionReport,
Congruences,
BoundedDivisibility,
BoundedAbsoluteInequality,
ChainedInequality,
AbsoluteIntersection,
ConjunctionReport,
BoundedConjunctionReport,
}
fn patterns() -> [(Family, &'static regex::Regex); 25] {
[
(
Family::FiniteIntervalReport,
re!(
r"^for ([a-z]) in the integer interval \[([^\[\]]+)\], (?:solve|find solutions satisfying) (.+?); (?:provide|give|list|report) (?:every|all) solutions? in order,? (?:plus|\+|and) (.+)$"
),
),
(
Family::FiniteConjunctionReport,
re!(
r"^(?:(?:find|list|give) )?(?:all|every) integers? ([a-z]) (?:satisfying|that satisfy|such that) (.+?),? (?:then|and) (?:report|give|state|return) (?:their |the )?(.+)$"
),
),
(
Family::LinearBlock,
re!(
r"^there are (.+?) distinct ([a-z]+),? and (.+?) specified ([a-z]+) must (?:be adjacent|stay together) (?:on a shelf|in a linear arrangement)\. (?:count|find the number of) (?:the )?linear arrangements,? treating the specified (group|block|subset|pair|trio|quartet) as a single block whose internal order (?:can|may) vary$"
),
),
(
Family::ConstrainedDigitCodes,
re!(
r"^how many (.+?)-digit codes can be made using digits (.+?) through (.+?) without repetition if the first digit cannot be zero and the code must end in an even digit\? count valid codes$"
),
),
(
Family::LetterWords,
re!(
r"^how many distinct (.+?)-letter arrangements can be made from the letters (.+?), with each letter used at most as often as supplied$"
),
),
(
Family::Committees,
re!(
r"^from (.+?) people, how many different committees of (.+?) can be formed if two specified people may not both serve on the committee$"
),
),
(
Family::LabeledGraphs,
re!(
r"^in a simple undirected graph on (.+?) labeled vertices, exactly (.+?) edges are chosen; how many such graphs are possible$"
),
),
(
Family::SubgroupCommittees,
re!(
r"^from (.+?) (?:applicants|people), how many committees of (.+?) include exactly (.+?) of the (.+?) designated [a-z]+$"
),
),
(
Family::DigitCodes,
re!(
r"^an? (.+?)-digit code uses digits (.+?) through (.+?), permits repetition, and may begin with zero; how many codes have exactly (.+?) digits equal to (.+)$"
),
),
(
Family::RollOutcomes,
re!(
r"^a fair (.+?)-sided die is rolled (.+?) times; how many ordered outcomes contain exactly (.+?) rolls of (.+)$"
),
),
(
Family::ExclusiveMultiples,
re!(
r"^how many integers from (.+?) through (.+?) inclusive are divisible by (.+?) or (.+?),? but not by both$"
),
),
(
Family::GrowingDifferences,
re!(
r"^using the supplied sequence (.+?), what are the next (.+?) terms if the successive increments continue increasing by (.+?) each time$"
),
),
(
Family::DivideSequence,
re!(
r"^given the sequence (.+?), what is the next term if each term is obtained by dividing the previous term by (.+)$"
),
),
(
Family::AffineSequence,
re!(
r#"^for the supplied sequence (.+?), continue the rule "?double the previous term and add ([^"]+?)"? for (.+?) more terms$"#
),
),
(
Family::OddDifferences,
re!(
r"^a sequence begins (.+?); what are the next (.+?) terms if its successive differences continue as consecutive odd numbers starting at (.+)$"
),
),
(
Family::IndexedSequence,
re!(
r"^a sequence is defined by a_1\s*=\s*(.+?) and a_n\s*=\s*a_\(n-1\)\s*\+\s*(.+?)n for n at least 2; what are a_(\d+) and the sum of a_1 through a_(\d+)$"
),
),
(
Family::IndexedAffineList,
re!(
r"^for the recurrence ([a-z])₀=(.+?) and ([a-z])ₙ₊₁=(.+?), report ([a-z])₀ through ([a-z])([₀₁₂₃₄₅₆₇₈₉]+) as an ordered list$"
),
),
(
Family::DivisionReport,
re!(r"^(.+?) / (.+?) and report the quotient and remainder$"),
),
(
Family::Congruences,
re!(
r"^least positive integer that is congruent to (.+?) modulo (.+?) and (.+?) modulo (.+)$"
),
),
(
Family::BoundedDivisibility,
re!(
r"^every integer x from (.+?) through (.+?) inclusive for which (.+?) is divisible by (.+)$"
),
),
(
Family::ChainedInequality,
re!(
r"^how many integers? ([a-z]) (?:obey|satisfy) (.+?)\s*(<=|>=|≤|≥|<|>)\s*(.+?)\s*(<=|>=|≤|≥|<|>)\s*(.+?)\?\s*give (the count and the least such ([a-z])|the least such ([a-z]) and the count)$"
),
),
(
Family::AbsoluteIntersection,
re!(
r"^how many integers? ([a-z]) in \[\s*(.+?),\s*(.+?)\s*\] (?:meet|satisfy) both \|([^|]+)\|\s*(<=|>=|≤|≥|<|>)\s*(.+?) and \|([^|]+)\|\s*(<=|>=|≤|≥|<|>)\s*(.+)$"
),
),
(
Family::ConjunctionReport,
re!(
r"^(?:find )?every integer ([a-z]) satisfying (.+?); report (how many such integers there are and the least one|the least one and how many such integers there are)$"
),
),
(
Family::BoundedConjunctionReport,
re!(
r"^count the integers ([a-z]) in \[\s*(.+?),\s*(.+?)\s*\] such that (.+?), and state the least such ([a-z])$"
),
),
(
Family::BoundedAbsoluteInequality,
re!(
r"^for integer ([a-z]) in \[(.+?),\s*(.+?)\], list every solution to \|(.+?)\|\s*(<=|≥|>=|≤|<|>)\s*(.+?) and give their count$"
),
),
]
}
fn subset_request() -> &'static regex::Regex {
re!(
r"^how many subsets of \{\s*1\s*,\s*2\s*,\s*(?:\.\.\.|…)\s*,\s*(.+?)\s*\} have exactly (.+?) elements and contain no two consecutive integers\? (?:give|report) the count,? and (?:give|report) the count when the subset must also contain (.+)$"
)
}
struct RequiredSubset<'a> {
selected: &'a str,
lower: &'a str,
second: Option<&'a str>,
upper: &'a str,
required: &'a str,
location: Option<&'a str>,
}
fn required_subset(input: &str) -> Option<RequiredSubset<'_>> {
let c = re!(r"^(?:(?:how many|count(?: the)?|(?:find the |determine the )?number of) |among )(.+?)-(?:element|member) subsets of \{\s*(.+?)\s*\} (.+)$").captures(input)?;
let selected = c.get(1)?.as_str();
let set = re!(r"^(.+?)\s*,\s*(?:(.+?)\s*,\s*)?(?:\.\.\.|…)\s*,\s*(.+?)$")
.captures(c.get(2)?.as_str())?;
let clause = re!(r"^(?:contain|have|having|with|that have) (?:no (?:two )?(?:consecutive|adjacent) (?:integers|numbers|members|elements)|neither consecutive integers|pairwise nonadjacent members)(.+)$").captures(c.get(3)?.as_str())?;
let tail = clause.get(1)?.as_str();
let member = re!(r"^(?: and (?:must )?(?:include|contain)| that (?:must )?(?:include|contain)|, how many (?:include|contain)) (?:the )?(?:(endpoint|interior)(?: member| value)? )?(.+)$").captures(tail)
.or_else(|| re!(r"^ and (?:with )?(?:(endpoint|interior)(?: member| value)? )?(.+?) required$").captures(tail))
.or_else(|| re!(r"^ and required (?:(endpoint|interior)(?: member| value)? )?(.+)$").captures(tail))?;
Some(RequiredSubset {
selected,
lower: set.get(1)?.as_str().trim(),
second: set.get(2).map(|v| v.as_str().trim()),
upper: set.get(3)?.as_str().trim(),
required: member.get(2)?.as_str().trim(),
location: member.get(1).map(|v| v.as_str()),
})
}
pub(super) fn recognizes(input: &str) -> bool {
let input = crate::plugins::syntax::ungroup(input)
.trim_end_matches(['?', '.'])
.trim();
finite_request(input).is_some()
|| subset_request().is_match(input)
|| required_subset(input).is_some()
|| natural_request(input).is_some()
|| named_block_parts(input).is_some()
|| patterns()
.iter()
.any(|(_, pattern)| pattern.is_match(input))
}
pub(super) fn count(input: &str) -> Result<BigInt, Error> {
Ok(match input {
"zero" => 0.into(),
"one" => 1.into(),
"two" => 2.into(),
"three" => 3.into(),
"four" => 4.into(),
"five" => 5.into(),
"six" => 6.into(),
"seven" => 7.into(),
"eight" => 8.into(),
"nine" => 9.into(),
"ten" => 10.into(),
"eleven" => 11.into(),
"twelve" => 12.into(),
_ => value(input)?,
})
}
pub(super) fn nonadjacent_count(
length: &BigInt,
selected: &BigInt,
work: &mut u64,
) -> Result<BigInt, Error> {
if length.is_negative() || selected.is_negative() {
return err("invalid_integer_argument");
}
let positions = length - selected + 1u8;
if selected > &positions {
return Ok(BigInt::zero());
}
let factors = selected.min(&(&positions - selected)).clone();
let cost = bounded(&factors, *work)?;
*work -= cost;
choose(&positions, selected, false)
}
fn validate_subset_roles(
population: &BigInt,
selected: &BigInt,
required: &BigInt,
) -> Result<(), Error> {
if !population.is_positive()
|| selected.is_negative()
|| !required.is_positive()
|| required > population
{
return err("invalid_integer_argument");
}
Ok(())
}
fn subset_including(
population: &BigInt,
selected: &BigInt,
required: &BigInt,
work: &mut u64,
) -> Result<BigInt, Error> {
validate_subset_roles(population, selected, required)?;
let mut including = BigInt::zero();
if !selected.is_zero() && selected <= &((population + 1u8) / 2u8) {
let left = (required - 2u8).max(BigInt::zero());
let right = (population - required - 1u8).max(BigInt::zero());
let remaining = selected - 1u8;
let left_capacity = (&left + 1u8) / 2u8;
let right_capacity = (&right + 1u8) / 2u8;
let first = (&remaining - right_capacity).max(BigInt::zero());
let last = remaining.clone().min(left_capacity);
if first <= last {
let terms = bounded(&(&last - &first + 1u8), *work)?;
let mut left_selected = first;
for _ in 0..terms {
if *work == 0 {
return err("integer_limit");
}
*work -= 1;
let left_count = nonadjacent_count(&left, &left_selected, work)?;
let right_count = nonadjacent_count(&right, &(&remaining - &left_selected), work)?;
including = checked(including + checked(left_count * right_count)?)?;
left_selected += 1u8;
}
}
}
Ok(including)
}
fn subset_report(population: &str, selected: &str, required: &str) -> Result<String, Error> {
let (population, selected, required) = (count(population)?, count(selected)?, count(required)?);
validate_subset_roles(&population, &selected, &required)?;
let mut work = 100_000;
let total = nonadjacent_count(&population, &selected, &mut work)?;
let including = subset_including(&population, &selected, &required, &mut work)?;
bounded_report(format!(
"count: {}; count including {}: {}",
decimal(&total),
decimal(&required),
decimal(&including)
))
}
fn required_subset_count(parts: RequiredSubset<'_>) -> Result<String, Error> {
let lower = count(parts.lower)?;
let second = parts.second.map(count).transpose()?;
let upper = count(parts.upper)?;
let selected = count(parts.selected)?;
let required = count(parts.required)?;
if lower > upper
|| second.is_some_and(|second| second != &lower + 1u8)
|| required < lower
|| required > upper
|| selected.is_negative()
|| parts.location == Some("endpoint") && required != lower && required != upper
|| parts.location == Some("interior") && (required == lower || required == upper)
{
return err("invalid_integer_argument");
}
let population = checked(&upper - &lower + 1u8)?;
let required = checked(required - lower + 1u8)?;
let including = subset_including(&population, &selected, &required, &mut 100_000)?;
bounded_report(decimal(&including))
}
fn checked(value: BigInt) -> Result<BigInt, Error> {
if value.bits() > 1_000_000 {
return err("integer_limit");
}
Ok(value)
}
fn terms(input: &str) -> Result<Vec<BigRational>, Error> {
let fields = input.split(',').collect::<Vec<_>>();
if fields.len() < 2 {
return err("invalid_integer_argument");
}
if fields.len() > 256 {
return err("integer_limit");
}
fields
.into_iter()
.map(|field| ratio_value(field.trim()).map(|(n, d)| BigRational::new(n, d)))
.collect()
}
fn scalar(input: &str) -> Result<BigRational, Error> {
let (n, d) = ratio_value(input)?;
Ok(BigRational::new(n, d))
}
fn rational_display(value: &BigRational) -> String {
if value.is_integer() {
decimal(value.numer())
} else {
format!("{}/{}", decimal(value.numer()), decimal(value.denom()))
}
}
#[derive(Clone)]
struct IntegerRange {
lower: Option<BigInt>,
upper: Option<BigInt>,
}
impl IntegerRange {
fn finite(lower: BigInt, upper: BigInt) -> Self {
Self {
lower: Some(lower),
upper: Some(upper),
}
}
fn intersect(self, other: &Self) -> Option<Self> {
let lower = match (self.lower, &other.lower) {
(Some(a), Some(b)) => Some(a.max(b.clone())),
(a, b) => a.or_else(|| b.clone()),
};
let upper = match (self.upper, &other.upper) {
(Some(a), Some(b)) => Some(a.min(b.clone())),
(a, b) => a.or_else(|| b.clone()),
};
if lower
.as_ref()
.zip(upper.as_ref())
.is_some_and(|(a, b)| a > b)
{
None
} else {
Some(Self { lower, upper })
}
}
}
fn relation(input: &str) -> &str {
match input {
"≤" => "<=",
"≥" => ">=",
other => other,
}
}
fn reversed_relation(input: &str) -> &str {
match relation(input) {
"<" => ">",
"<=" => ">=",
">" => "<",
">=" => "<=",
_ => "",
}
}
fn affine_halfspace(
bounds: IntegerRange,
constant: &BigRational,
coefficient: &BigRational,
threshold: &BigRational,
comparison: &str,
) -> Result<Option<IntegerRange>, Error> {
let comparison = relation(comparison);
if coefficient.is_zero() {
let holds = match comparison {
"<" => constant < threshold,
"<=" => constant <= threshold,
">" => constant > threshold,
">=" => constant >= threshold,
_ => return err("invalid_integer_expression"),
};
return Ok(holds.then_some(bounds));
}
let crossing = (threshold - constant) / coefficient;
if crossing.numer().bits().max(crossing.denom().bits()) > 1_000_000 {
return err("integer_limit");
}
let floor = crossing.numer().div_floor(crossing.denom());
let ceil = -(-crossing.numer()).div_floor(crossing.denom());
let mut constraint = IntegerRange {
lower: None,
upper: None,
};
match (coefficient.is_positive(), comparison) {
(true, "<") | (false, ">") => constraint.upper = Some(ceil - 1u8),
(true, "<=") | (false, ">=") => constraint.upper = Some(floor),
(true, ">") | (false, "<") => constraint.lower = Some(floor + 1u8),
(true, ">=") | (false, "<=") => constraint.lower = Some(ceil),
_ => return err("invalid_integer_expression"),
}
Ok(bounds.intersect(&constraint))
}
fn absolute_ranges(
bounds: IntegerRange,
expression: &str,
variable: &str,
comparison: &str,
threshold: &str,
) -> Result<Vec<IntegerRange>, Error> {
let (constant, coefficients) = affine_value(expression, &[variable])?;
let threshold = scalar(threshold)?;
absolute_affine_ranges(bounds, &constant, &coefficients[0], comparison, &threshold)
}
fn absolute_affine_ranges(
bounds: IntegerRange,
constant: &BigRational,
coefficient: &BigRational,
comparison: &str,
threshold: &BigRational,
) -> Result<Vec<IntegerRange>, Error> {
let comparison = relation(comparison);
let negative_threshold = -threshold;
let mut ranges = Vec::new();
if comparison == "==" {
if !threshold.is_negative() {
for target in [&negative_threshold, threshold] {
if let Some(range) =
affine_halfspace(bounds.clone(), constant, coefficient, target, "<=")?
&& let Some(range) =
affine_halfspace(range, constant, coefficient, target, ">=")?
{
ranges.push(range);
}
}
}
} else if comparison == "<" || comparison == "<=" {
if !threshold.is_negative() {
let first = if comparison == "<" { ">" } else { ">=" };
if let Some(range) =
affine_halfspace(bounds, constant, coefficient, &negative_threshold, first)?
&& let Some(range) =
affine_halfspace(range, constant, coefficient, threshold, comparison)?
{
ranges.push(range);
}
}
} else if threshold.is_negative() {
ranges.push(bounds);
} else {
let first = if comparison == ">" { "<" } else { "<=" };
if let Some(range) = affine_halfspace(
bounds.clone(),
constant,
coefficient,
&negative_threshold,
first,
)? {
ranges.push(range);
}
if let Some(range) = affine_halfspace(bounds, constant, coefficient, threshold, comparison)?
{
ranges.push(range);
}
}
Ok(ranges)
}
fn absolute_sum_ranges(
bounds: IntegerRange,
first: &str,
second: &str,
variable: &str,
comparison: &str,
threshold: &str,
) -> Result<Vec<IntegerRange>, Error> {
let (a, ac) = affine_value(first, &[variable])?;
let (b, bc) = affine_value(second, &[variable])?;
let threshold = scalar(threshold)?;
let mut result = Vec::new();
for first_sign in [-1i32, 1] {
for second_sign in [-1i32, 1] {
let mut region = Some(bounds.clone());
for (constant, coefficient, sign) in
[(&a, &ac[0], first_sign), (&b, &bc[0], second_sign)]
{
if let Some(bounds) = region.take() {
region = affine_halfspace(
bounds,
constant,
coefficient,
&BigRational::zero(),
if sign < 0 { "<=" } else { ">=" },
)?;
}
}
if let Some(bounds) = region {
let first_sign = BigRational::from_integer(first_sign.into());
let second_sign = BigRational::from_integer(second_sign.into());
let terms = [
&a * &first_sign + &b * &second_sign - &threshold,
&ac[0] * first_sign + &bc[0] * second_sign,
BigRational::zero(),
];
result.extend(polynomial_ranges(bounds, terms, relation(comparison))?);
}
}
}
Ok(merged_ranges(result))
}
fn polynomial_ranges(
bounds: IntegerRange,
terms: [BigRational; 3],
comparison: &str,
) -> Result<Vec<IntegerRange>, Error> {
if comparison == "==" {
let below = polynomial_ranges(bounds.clone(), terms.clone(), "<=")?;
let above = polynomial_ranges(bounds, terms, ">=")?;
return Ok(intersect_ranges(below, &above));
}
let [constant, coefficient, quadratic] = terms;
if quadratic.is_zero() {
return Ok(affine_halfspace(
bounds,
&constant,
&coefficient,
&BigRational::zero(),
comparison,
)?
.into_iter()
.collect());
}
let denominator = checked(
constant
.denom()
.lcm(coefficient.denom())
.lcm(quadratic.denom()),
)?;
let integer = |value: &BigRational| checked(value.numer() * (&denominator / value.denom()));
let (mut c, mut b, mut a) = (
integer(&constant)?,
integer(&coefficient)?,
integer(&quadratic)?,
);
let comparison = if a.is_negative() {
a = -a;
b = -b;
c = -c;
reversed_relation(comparison)
} else {
comparison
};
let discriminant = checked(&b * &b - BigInt::from(4) * &a * c)?;
if discriminant.is_negative() {
return Ok(affine_halfspace(
bounds,
&BigRational::one(),
&BigRational::zero(),
&BigRational::zero(),
comparison,
)?
.into_iter()
.collect());
}
let floor = discriminant.sqrt();
let ceil = &floor
+ if &floor * &floor == discriminant {
BigInt::zero()
} else {
BigInt::one()
};
let (threshold, relation) = match comparison {
"<" => (ceil - 1u8, "<="),
"<=" => (floor, "<="),
">" => (floor + 1u8, ">="),
">=" => (ceil, ">="),
_ => return err("invalid_integer_expression"),
};
absolute_affine_ranges(
bounds,
&BigRational::from_integer(b),
&BigRational::from_integer(checked(a * 2u8)?),
relation,
&BigRational::from_integer(threshold),
)
}
fn merged_ranges(mut ranges: Vec<IntegerRange>) -> Vec<IntegerRange> {
ranges.sort_by(|a, b| a.lower.cmp(&b.lower));
let mut merged: Vec<IntegerRange> = Vec::new();
for range in ranges {
if let Some(previous) = merged.last_mut()
&& previous
.upper
.as_ref()
.zip(range.lower.as_ref())
.is_none_or(|(upper, lower)| lower <= &(upper + 1u8))
{
previous.upper = match (&previous.upper, range.upper) {
(Some(a), Some(b)) => Some(a.max(&b).clone()),
_ => None,
};
} else {
merged.push(range);
}
}
merged
}
fn intersect_ranges(left: Vec<IntegerRange>, right: &[IntegerRange]) -> Vec<IntegerRange> {
merged_ranges(
left.into_iter()
.flat_map(|range| {
right
.iter()
.filter_map(move |other| range.clone().intersect(other))
})
.collect(),
)
}
fn merged_finite_ranges(ranges: Vec<IntegerRange>) -> Result<Vec<(BigInt, BigInt)>, Error> {
merged_ranges(ranges)
.into_iter()
.map(|range| {
range
.lower
.zip(range.upper)
.ok_or_else(|| Error("invalid_integer_argument".into()))
})
.collect()
}
fn range_count(ranges: &[(BigInt, BigInt)]) -> Result<BigInt, Error> {
checked(ranges.iter().fold(BigInt::zero(), |sum, (lower, upper)| {
sum + upper - lower + 1u8
}))
}
fn bounded_report(output: String) -> Result<String, Error> {
if output.len() > 4096 {
err("integer_limit")
} else {
Ok(output)
}
}
fn supplied_bounds(lower: &str, upper: &str) -> Result<IntegerRange, Error> {
let (lower, upper) = (value(lower)?, value(upper)?);
if lower > upper {
return err("invalid_integer_argument");
}
Ok(IntegerRange::finite(lower, upper))
}
fn bounded_absolute_inequality(c: ®ex::Captures<'_>) -> Result<String, Error> {
let ranges = merged_finite_ranges(absolute_ranges(
supplied_bounds(&c[2], &c[3])?,
&c[4],
&c[1],
&c[5],
&c[6],
)?)?;
let count = bounded(&range_count(&ranges)?, 256)? as usize;
let mut solutions = Vec::with_capacity(count);
for (mut integer, upper) in ranges {
while integer <= upper {
solutions.push(decimal(&integer));
integer += 1u8;
}
}
bounded_report(format!(
"solutions: {}; count: {count}",
if solutions.is_empty() {
"none".into()
} else {
solutions.join(", ")
}
))
}
fn absolute_intersection(c: ®ex::Captures<'_>) -> Result<String, Error> {
let bounds = supplied_bounds(&c[2], &c[3])?;
let first = absolute_ranges(bounds.clone(), &c[4], &c[1], &c[5], &c[6])?;
let second = absolute_ranges(bounds, &c[7], &c[1], &c[8], &c[9])?;
let intersections = intersect_ranges(first, &second);
bounded_report(decimal(&range_count(&merged_finite_ranges(
intersections,
)?)?))
}
fn chained_inequality(c: ®ex::Captures<'_>) -> Result<String, Error> {
let name = &c[1];
if c.get(8)
.or_else(|| c.get(9))
.is_none_or(|goal| goal.as_str() != name)
{
return err("invalid_integer_expression");
}
let left = scalar(&c[2])?;
let right = scalar(&c[6])?;
let (constant, coefficients) = affine_value(&c[4], &[name])?;
let bounds = affine_halfspace(
IntegerRange {
lower: None,
upper: None,
},
&constant,
&coefficients[0],
&left,
reversed_relation(&c[3]),
)?;
let result = match bounds {
Some(bounds) => affine_halfspace(bounds, &constant, &coefficients[0], &right, &c[5])?,
None => None,
};
count_least_report(result.into_iter().collect(), name, c.get(8).is_some())
}
fn count_least_report(
ranges: Vec<IntegerRange>,
name: &str,
count_first: bool,
) -> Result<String, Error> {
let ranges = merged_ranges(ranges);
let least = ranges
.first()
.and_then(|range| range.lower.as_ref())
.map(decimal)
.unwrap_or_else(|| "none".into());
let count = if ranges
.iter()
.any(|range| range.lower.is_none() || range.upper.is_none())
{
"infinite".into()
} else {
decimal(&range_count(&merged_finite_ranges(ranges)?)?)
};
let count = format!("count: {count}");
let least = format!("least {name}: {least}");
bounded_report(if count_first {
format!("{count}; {least}")
} else {
format!("{least}; {count}")
})
}
fn condition_ranges(input: &str, name: &str) -> Result<Vec<IntegerRange>, Error> {
let unbounded = IntegerRange {
lower: None,
upper: None,
};
if let Some(c) =
re!(r"^\|([^|]+)\|\s*\+\s*\|([^|]+)\|\s*(<=|>=|≤|≥|==|=|<|>)\s*(.+)$").captures(input)
{
return absolute_sum_ranges(
unbounded,
&c[1],
&c[2],
name,
if &c[3] == "=" { "==" } else { &c[3] },
&c[4],
);
}
if let Some(c) = re!(r"^\|([^|]+)\|\s*(<=|>=|≤|≥|==|=|<|>)\s*(.+)$").captures(input) {
return absolute_ranges(
unbounded,
&c[1],
name,
if &c[2] == "=" { "==" } else { &c[2] },
&c[3],
);
}
let input = input.replace('≤', "<=").replace('≥', ">=");
let groups = crate::plugins::syntax::groups(&input)
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
let mut normalized = String::with_capacity(input.len());
for (at, character) in input.char_indices() {
if character == '='
&& !groups.iter().any(|group| group.contains(&at))
&& !at
.checked_sub(1)
.and_then(|before| input.as_bytes().get(before))
.is_some_and(|before| matches!(before, b'<' | b'>' | b'!' | b'='))
&& input.as_bytes().get(at + 1) != Some(&b'=')
{
normalized.push('=');
}
normalized.push(character);
}
let input = normalized;
let comparisons = crate::plugins::statistics::comparison_operators(&input)?;
if !(1..=2).contains(&comparisons.len())
|| comparisons
.iter()
.any(|(_, op)| !matches!(*op, "<" | "<=" | ">" | ">=" | "=="))
{
return err("invalid_integer_expression");
}
let mut start = 0;
let mut operands = Vec::new();
for (at, op) in &comparisons {
operands.push(input[start..*at].trim());
start = at + op.len();
}
operands.push(input[start..].trim());
if comparisons.len() == 2 && operands[1] == name {
let left = scalar(operands[0])?;
let right = scalar(operands[2])?;
let reversed = match (comparisons[0].1, comparisons[1].1) {
("<" | "<=", "<" | "<=") => left > right,
(">" | ">=", ">" | ">=") => left < right,
_ => false,
};
if reversed {
return err("invalid_integer_argument");
}
}
let mut constraints = Vec::new();
for (pair, (_, op)) in operands.windows(2).zip(comparisons) {
let expression = format!("({})-({})", pair[0], pair[1]).replace('²', "^2");
constraints.push(polynomial_ranges(
unbounded.clone(),
super::quadratic_value(&expression, name)?,
op,
)?);
}
let mut result = vec![unbounded];
for constraint in constraints {
result = intersect_ranges(result, &constraint);
}
Ok(result)
}
fn condition_comma(input: &str, at: usize, name: &str) -> bool {
let bytes = input.as_bytes();
if at == 0
|| !bytes[at - 1].is_ascii_digit()
|| !bytes.get(at + 1).is_some_and(u8::is_ascii_digit)
{
return true;
}
let mut start = at;
while start > 0 && (bytes[start - 1].is_ascii_digit() || bytes[start - 1] == b',') {
start -= 1;
}
let mut end = at + 1;
while bytes.get(end).is_some_and(u8::is_ascii_digit) {
end += 1;
}
if scalar(&input[start..end]).is_ok() {
return false;
}
input[end..].starts_with(name)
}
fn split_condition<'a>(input: &'a str, name: &str) -> Result<Option<(&'a str, &'a str)>, Error> {
let groups = crate::plugins::syntax::groups(input)
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
let mut separator = None;
for (at, character) in input.char_indices() {
if groups.iter().any(|group| group.contains(&at)) {
continue;
}
if character == ',' && condition_comma(input, at, name) {
separator = Some((at, 1));
} else if input[at..].starts_with(" and ") {
separator = Some((at, 5));
}
}
Ok(separator.map(|(at, width)| (&input[..at], &input[at + width..])))
}
fn conjunction_ranges(
input: &str,
name: &str,
bounds: Option<IntegerRange>,
) -> Result<Vec<IntegerRange>, Error> {
let mut rest = input;
let mut clauses = Vec::new();
while let Some((left, right)) = split_condition(rest, name)? {
if right.trim().is_empty() {
return err("invalid_integer_expression");
}
clauses.push(right.trim());
let separator = &rest[left.len()..rest.len() - right.len()];
rest = if separator == " and " {
left.trim_end().strip_suffix(',').unwrap_or(left).trim_end()
} else {
left
};
}
clauses.push(rest.trim());
if clauses.len() > 32 || clauses.iter().any(|clause| clause.is_empty()) {
return err("integer_limit");
}
let constraints = clauses
.into_iter()
.rev()
.map(|clause| condition_ranges(clause, name))
.collect::<Result<Vec<_>, _>>()?;
let mut ranges = bounds.into_iter().collect();
for constraint in constraints {
ranges = intersect_ranges(ranges, &constraint);
}
Ok(ranges)
}
fn conjunction_report(
input: &str,
name: &str,
bounds: Option<IntegerRange>,
count_first: bool,
) -> Result<String, Error> {
count_least_report(conjunction_ranges(input, name, bounds)?, name, count_first)
}
fn finite_goals(goals: &str) -> Result<Vec<&'static str>, Error> {
let mut roles = Vec::new();
for goal in re!(r",?\s+and\s+|,\s*").split(goals) {
let goal = goal.trim().strip_prefix("the ").unwrap_or(goal.trim());
let role = match goal {
"count" | "solution count" | "number of solutions" => "count",
"sum" | "sum of solutions" => "sum",
"minimum" | "smallest" => "minimum",
"maximum" | "largest" => "maximum",
"mean" | "average" => "mean",
_ => return err("invalid_integer_expression"),
};
if roles.contains(&role) {
return err("invalid_integer_expression");
}
roles.push(role);
}
Ok(roles)
}
fn finite_conjunction_report(
conditions: &str,
name: &str,
bounds: Option<IntegerRange>,
goals: &str,
) -> Result<String, Error> {
let roles = finite_goals(goals)?;
let ranges = conjunction_ranges(
conditions,
name,
Some(bounds.unwrap_or(IntegerRange {
lower: None,
upper: None,
})),
)?;
if ranges
.iter()
.any(|range| range.lower.is_none() || range.upper.is_none())
{
return err("integer_limit");
}
let ranges = merged_finite_ranges(ranges)?;
let count = range_count(&ranges)?;
let length = bounded(&count, 256)? as usize;
let mut values = Vec::with_capacity(length);
let mut sum = BigInt::zero();
for (lower, upper) in &ranges {
let cardinality = upper - lower + 1u8;
sum = checked(sum + checked((lower + upper) * cardinality)? / 2u8)?;
let mut next = lower.clone();
while &next <= upper {
let value = decimal(&next);
if values.iter().map(String::len).sum::<usize>() + value.len() > 4096 {
return err("integer_limit");
}
values.push(value);
next += 1u8;
}
}
let mut output = vec![format!(
"solutions: {}",
if values.is_empty() {
"none".into()
} else {
values.join(", ")
}
)];
for role in roles {
let value = match role {
"count" => decimal(&count),
"sum" => decimal(&sum),
"minimum" => ranges
.first()
.map(|(lower, _)| decimal(lower))
.unwrap_or_else(|| "none".into()),
"maximum" => ranges
.last()
.map(|(_, upper)| decimal(upper))
.unwrap_or_else(|| "none".into()),
"mean" => {
if count.is_zero() {
"none".into()
} else {
rational_display(&BigRational::new(sum.clone(), count.clone()))
}
}
_ => unreachable!(),
};
output.push(format!("{role}: {value}"));
}
bounded_report(output.join("; "))
}
struct FiniteRequest<'a> {
name: Option<&'a str>,
lower: &'a str,
upper: &'a str,
conditions: &'a str,
goals: &'a str,
}
fn finite_request(input: &str) -> Option<FiniteRequest<'_>> {
if let Some(c) = re!(r"^solve (.+?) over integers ([a-z]) in (.+?) (?:through|to) (.+?) inclusive, listing (?:every|all) solutions? and reporting (.+)$").captures(input) {
return Some(FiniteRequest {
name: Some(c.get(2)?.as_str()), lower: c.get(3)?.as_str(),
upper: c.get(4)?.as_str(), conditions: c.get(1)?.as_str(), goals: c.get(5)?.as_str(),
});
}
let (name, lower, upper, body) = if let Some(c) = re!(r"^(?:list (?:every|all)|(?:find )?all|for all) integers? ([a-z]) (?:from|in(?: the inclusive range)?) (.+?) (?:through|to) (.+?)(?: inclusive)?,? (?:satisfying|for which|list the solutions to) (.+)$").captures(input) {
(Some(c.get(1)?.as_str()), c.get(2)?.as_str(), c.get(3)?.as_str(), c.get(4)?.as_str())
} else {
let c = re!(r"^among integers (.+?) (?:through|to) (.+?) inclusive, solve (.+)$").captures(input)?;
(None, c.get(1)?.as_str(), c.get(2)?.as_str(), c.get(3)?.as_str())
};
let (conditions, goals) = crate::plugins::syntax::split_last(
body,
&[
", then report ",
"; return every solution and ",
" and give the complete solution list with its ",
" and summarize them by ",
],
)?;
Some(FiniteRequest {
name,
lower,
upper,
conditions,
goals,
})
}
pub(super) fn finite_report_request(input: &str) -> bool {
let input = crate::plugins::syntax::ungroup(input)
.trim_end_matches(['?', '.'])
.trim();
finite_request(input).is_some_and(|parts| finite_goals(parts.goals).is_ok())
}
fn finite_variable(conditions: &str) -> Result<String, Error> {
let c = re!(r"^\|([^|]+)\|")
.captures(conditions)
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
super::quadratic_variable(&c[1])
}
fn finite_natural_report(parts: FiniteRequest<'_>) -> Result<String, Error> {
let inferred;
let name = match parts.name {
Some(name) => name,
None => {
inferred = finite_variable(parts.conditions)?;
&inferred
}
};
finite_conjunction_report(
parts.conditions,
name,
Some(supplied_bounds(parts.lower, parts.upper)?),
parts.goals,
)
}
enum NaturalBounds<'a> {
Pair(&'a str, &'a str),
Bracket(&'a str),
Chain(&'a str),
}
struct NaturalRequest<'a> {
name: &'a str,
bounds: NaturalBounds<'a>,
request: &'a str,
prefix_goals: &'a str,
whole: bool,
empty: bool,
}
fn natural_request(input: &str) -> Option<NaturalRequest<'_>> {
let request = natural_request_parts(input)?;
let goals = format!("{} {}", request.prefix_goals, request.request);
let least = re!(r"\b(?:minimum|smallest|least|lowest)\b").is_match(&goals);
let count = re!(r"\b(?:how many|count|number)\b").is_match(&goals);
(least && count).then_some(request)
}
fn natural_prefix<'a>(input: &'a str, name: &str) -> Option<&'a str> {
match input {
"for" | "for each" | "among" | "considering every" | "check" | "check all" | "on"
| "take all" => Some(""),
"count" | "count the" | "report the number of" => Some("count"),
"how many" => Some("how many"),
_ => {
let goals = input
.strip_suffix(" of")
.or_else(|| input.strip_suffix(" among"))
.unwrap_or(input);
natural_goals(goals, name).ok().map(|_| goals)
}
}
}
fn natural_request_parts(input: &str) -> Option<NaturalRequest<'_>> {
if let Some(c) =
re!(r"^(.+?) (integers?|whole[- ]numbers?) ([a-z])(?: values)? (.+)$").captures(input)
&& let Some(prefix_goals) = natural_prefix(c.get(1)?.as_str(), c.get(3)?.as_str())
{
let name = c.get(3)?.as_str();
let mut rest = c.get(4)?.as_str();
let empty = rest.starts_with("in the empty interval ");
for prefix in [
"in the empty interval ",
"in the closed interval ",
"in the closed range ",
"in the inclusive interval ",
"in the range ",
"in ",
] {
if let Some(tail) = rest.strip_prefix(prefix) {
rest = tail;
break;
}
}
let (bounds, request) = if let Some(range) =
re!(r"^\[(.+)\]\s*[,;:]?\s*(.+)$").captures(rest)
{
(
NaturalBounds::Bracket(range.get(1)?.as_str()),
range.get(2)?.as_str(),
)
} else {
let range = re!(r"^(?:from |between )?(.+?) (?:through|to|and) (.+?)(?:,? inclusive)?(?:\s*[,.;:]\s*|\s+)((?:find|how many|report|count|determine|give|state|apply|that|for which|such that|satisfying|satisfy|meet|obey|pass|subject to)\b.+)$").captures(rest)?;
(
NaturalBounds::Pair(range.get(1)?.as_str(), range.get(2)?.as_str()),
range.get(3)?.as_str(),
)
};
return Some(NaturalRequest {
name,
bounds,
request,
prefix_goals,
whole: c[2].starts_with("whole"),
empty,
});
}
if let Some(c) =
re!(r"^within the inclusive range (.+?) for integer ([a-z]), (.+)$").captures(input)
{
return Some(NaturalRequest {
name: c.get(2)?.as_str(),
bounds: NaturalBounds::Chain(c.get(1)?.as_str()),
request: c.get(3)?.as_str(),
prefix_goals: "",
whole: false,
empty: false,
});
}
if let Some(c) = re!(r"^(?:within|using the thousands-grouped inclusive bounds) \[(.+)\](?: inclusive)?, count integers? ([a-z]) (.+)$").captures(input) {
return Some(NaturalRequest {name: c.get(2)?.as_str(), bounds: NaturalBounds::Bracket(c.get(1)?.as_str()), request: c.get(3)?.as_str(), prefix_goals: "count", whole: false, empty: false});
}
let c = re!(r"^on the inclusive integer interval \[(.+)\], (.+)$").captures(input)?;
let request = c.get(2)?.as_str();
let variable = re!(r"\b(?:minimum|least|smallest|lowest) ([a-z])\b").captures(request)?;
Some(NaturalRequest {
name: variable.get(1)?.as_str(),
bounds: NaturalBounds::Bracket(c.get(1)?.as_str()),
request,
prefix_goals: "",
whole: false,
empty: false,
})
}
fn natural_bounds(
bounds: NaturalBounds<'_>,
name: &str,
empty: bool,
) -> Result<Option<IntegerRange>, Error> {
let pair = |lower: &str, upper: &str| {
if empty {
let (lower, upper) = (value(lower)?, value(upper)?);
if lower <= upper {
return err("invalid_integer_argument");
}
Ok(None)
} else {
supplied_bounds(lower, upper).map(Some)
}
};
match bounds {
NaturalBounds::Pair(lower, upper) => pair(lower, upper),
NaturalBounds::Bracket(input) => {
let groups = crate::plugins::syntax::groups(input)
.ok_or_else(|| Error("invalid_integer_argument".into()))?;
for (at, _) in input.match_indices(',') {
if !groups.iter().any(|group| group.contains(&at))
&& value(input[..at].trim()).is_ok()
&& value(input[at + 1..].trim()).is_ok()
{
return pair(input[..at].trim(), input[at + 1..].trim());
}
}
err("invalid_integer_argument")
}
NaturalBounds::Chain(input) => {
let ranges = condition_ranges(input, name)?;
let [range] = ranges.as_slice() else {
return err("invalid_integer_argument");
};
if empty || range.lower.is_none() || range.upper.is_none() {
return err("invalid_integer_argument");
}
Ok(Some(range.clone()))
}
}
}
fn natural_goal_patterns() -> (&'static regex::Regex, &'static regex::Regex) {
(
re!(
r"\b(?:how many|(?:total )?count|(?:total )?number(?: of matches| satisfying all conditions)?)\b"
),
re!(
r"\b(?:minimum|smallest|least|lowest)(?: (?:qualifying|admissible|passing|satisfying|counted|matching|eligible|such))?(?: (?:value|solution|one|match))?(?: ([a-z]))?\b"
),
)
}
fn natural_goals(input: &str, name: &str) -> Result<bool, Error> {
let input = input
.strip_suffix(", or say no minimum exists if there are none")
.or_else(|| input.strip_suffix(", including zero matches if applicable"))
.unwrap_or(input);
let input = input.replace(
"use count zero and minimum \"none\" when there are no eligible integers",
"count and minimum",
);
let mut goals = Vec::new();
let (count, least) = natural_goal_patterns();
for found in count.find_iter(&input) {
goals.push((found.start(), true));
}
for c in least.captures_iter(&input) {
if c.get(1).is_some_and(|variable| variable.as_str() != name) {
return err("invalid_integer_expression");
}
goals.push((c.get(0).unwrap().start(), false));
}
if !(2..=4).contains(&goals.len())
|| !goals.iter().any(|(_, count)| *count)
|| !goals.iter().any(|(_, count)| !*count)
{
return err("invalid_integer_expression");
}
goals.sort_by_key(|(at, _)| *at);
let remainder = count.replace_all(&input, " ");
let remainder = least.replace_all(&remainder, " ");
for word in remainder.split(|character: char| {
character.is_whitespace() || matches!(character, ',' | ';' | '?' | '.')
}) {
if !word.is_empty()
&& !matches!(
word,
"report"
| "find"
| "determine"
| "give"
| "state"
| "include"
| "return"
| "also"
| "identify"
| "the"
| "and"
| "their"
| "what"
| "too"
| "values"
| "those"
| "provide"
| "answer"
| "as"
| "list"
| "before"
| "followed"
| "by"
| "then"
| "in"
| "that"
| "order"
| "first"
| "second"
| "requested"
| "fields"
| "are"
)
{
return err("invalid_integer_expression");
}
}
Ok(goals[0].1)
}
struct NaturalClauses<'a> {
leading_goals: &'a str,
conditions: &'a str,
trailing_goals: &'a str,
}
fn natural_clauses(input: &str) -> Result<NaturalClauses<'_>, Error> {
let footer = re!(r"(?:;\s*|[?.]\s*|,\s*(?:and|then)\s+)((?:also )?(?:give|state|include|return|report|identify|provide|answer|list|use|explicitly treat|the square condition|the requested fields) .+)$").captures(input);
let (request, mut trailing_goal) = footer.as_ref().map_or((input, ""), |c| {
let all = c.get(0).unwrap();
(&input[..all.start()], c.get(1).unwrap().as_str())
});
for prefix in [
"explicitly treat the square condition as nonlinear and outside affine intent, and ",
"the square condition is intentionally nonlinear, and the requested fields are ",
] {
if let Some(goal) = trailing_goal.strip_prefix(prefix) {
trailing_goal = goal;
break;
}
}
let c = re!(r"^(.*?)\b(?:that satisfy|that obey|for which|such that|satisfying|satisfy|obey|meet|meeting|pass|with|when|where|apply|for|subject to)\s+(.+)$").captures(request)
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
Ok(NaturalClauses {
leading_goals: c.get(1).unwrap().as_str(),
conditions: c.get(2).unwrap().as_str(),
trailing_goals: trailing_goal,
})
}
pub(super) fn quantity_diagnostic_input(input: &str) -> std::borrow::Cow<'_, str> {
use std::borrow::Cow;
let Some(parts) = natural_request(input) else {
return Cow::Borrowed(input);
};
let Ok(clauses) = natural_clauses(parts.request) else {
return Cow::Borrowed(input);
};
let goals = format!(
"{} {}; {}",
parts.prefix_goals, clauses.leading_goals, clauses.trailing_goals
);
if natural_goals(&goals, parts.name).is_err() {
return Cow::Borrowed(input);
}
let (count, least) = natural_goal_patterns();
let mut spans = Vec::new();
let mut segments = vec![
(input.len() - parts.request.len(), clauses.leading_goals),
(
input.len() - clauses.trailing_goals.len(),
clauses.trailing_goals,
),
];
if input.starts_with(parts.prefix_goals) {
segments.push((0, parts.prefix_goals));
}
for (offset, segment) in segments {
for pattern in [count, least] {
for goal in pattern.find_iter(segment) {
let tail = &segment[goal.end()..];
if tail.starts_with(" second")
&& tail
.as_bytes()
.get(7)
.is_none_or(|next| !next.is_ascii_alphanumeric() && *next != b'_')
{
spans.push(offset + goal.end() + 1..offset + goal.end() + 7);
}
}
}
}
if spans.is_empty() {
return Cow::Borrowed(input);
}
let mut output = input.to_owned();
for span in spans {
output.replace_range(span, " ");
}
Cow::Owned(output)
}
fn natural_conjunction(parts: NaturalRequest<'_>) -> Result<String, Error> {
let bounds = natural_bounds(parts.bounds, parts.name, parts.empty)?;
let clauses = natural_clauses(parts.request)?;
let goals = format!(
"{} {}; {}",
parts.prefix_goals, clauses.leading_goals, clauses.trailing_goals
);
let count_first = natural_goals(&goals, parts.name)?;
let conditions = if parts.whole {
format!("{}, {} >= 0", clauses.conditions, parts.name)
} else {
clauses.conditions.to_string()
};
conjunction_report(&conditions, parts.name, bounds, count_first)
}
fn following(
initial: BigRational,
amount: &str,
mut next: impl FnMut(&BigRational) -> BigRational,
) -> Result<String, Error> {
let amount = bounded(&count(amount)?, 256)?;
if amount == 0 {
return err("invalid_integer_argument");
}
let mut current = initial;
let mut result = Vec::new();
for _ in 0..amount {
current = next(¤t);
if current.numer().bits().max(current.denom().bits()) > 1_000_000 {
return err("integer_limit");
}
let display = rational_display(¤t);
if result.iter().map(String::len).sum::<usize>() + display.len() > 4096 {
return err("integer_limit");
}
result.push(display);
}
Ok(format!("next terms: {}", result.join("; ")))
}
fn increments(
sequence: &[BigRational],
initial: BigRational,
step: BigRational,
amount: &str,
) -> Result<String, Error> {
let mut difference = initial;
for pair in sequence.windows(2) {
if &pair[1] - &pair[0] != difference {
return err("invalid_integer_argument");
}
difference += &step;
}
following(sequence.last().unwrap().clone(), amount, |term| {
let result = term + &difference;
difference += &step;
result
})
}
struct NamedBlock<'a> {
population: &'a str,
noun: &'a str,
block_noun: &'a str,
names: &'a str,
stated_count: Option<&'a str>,
pair: bool,
}
fn named_block_parts(input: &str) -> Option<NamedBlock<'_>> {
if let Some(c) = re!(r"^how many ways can (.+?) distinct ([a-z]+) be arranged (?:on a shelf|in a row) if the (.+?) named ([a-z]+) (.+?) must occupy consecutive places in any internal order$").captures(input) {
return Some(NamedBlock { population: c.get(1)?.as_str(), noun: c.get(2)?.as_str(),
stated_count: Some(c.get(3)?.as_str()), block_noun: c.get(4)?.as_str(),
names: c.get(5)?.as_str(), pair: false });
}
let c = re!(r"^for (.+?) distinct ([a-z]+) in a row, count arrangements where the named ([a-z]+) (.+?) form one contiguous block with either internal order, and report the count$").captures(input)?;
Some(NamedBlock {
population: c.get(1)?.as_str(),
noun: c.get(2)?.as_str(),
stated_count: None,
block_noun: c.get(3)?.as_str(),
names: c.get(4)?.as_str(),
pair: true,
})
}
fn linear_block(population: BigInt, block: BigInt) -> Result<String, Error> {
if !population.is_positive() || !block.is_positive() || block > population {
return err("invalid_integer_argument");
}
let contracted = &population - &block + 1u8;
Ok(decimal(&checked(
factorial(&contracted)? * factorial(&block)?,
)?))
}
fn named_block(parts: NamedBlock<'_>) -> Result<String, Error> {
let mut names = Vec::new();
for name in re!(r",?\s+and\s+|,\s*").split(parts.names) {
let name = name.trim();
if !re!(r"^[a-z][a-z0-9_]*$").is_match(name) || names.contains(&name) {
return err("invalid_integer_argument");
}
names.push(name);
}
if names.len() > 256 {
return err("integer_limit");
}
let block = BigInt::from(names.len());
if parts.noun != parts.block_noun
|| parts.pair && names.len() != 2
|| parts
.stated_count
.map(count)
.transpose()?
.is_some_and(|count| count != block)
{
return err("invalid_integer_argument");
}
linear_block(count(parts.population)?, block)
}
pub(super) fn query(input: &str) -> Option<Result<String, Error>> {
let input = crate::plugins::syntax::ungroup(input)
.trim_end_matches(['?', '.'])
.trim();
if let Some(c) = subset_request().captures(input) {
return Some(if input.len() > 4096 {
err("integer_limit")
} else {
subset_report(&c[1], &c[2], &c[3])
});
}
if let Some(parts) = required_subset(input) {
return Some(if input.len() > 4096 {
err("integer_limit")
} else {
required_subset_count(parts)
});
}
if let Some(parts) = finite_request(input) {
return Some(if input.len() > 4096 {
err("integer_limit")
} else {
finite_natural_report(parts)
});
}
if let Some(parts) = named_block_parts(input) {
return Some(if input.len() > 4096 {
err("integer_limit")
} else {
named_block(parts)
});
}
if let Some(parts) = natural_request(input) {
return Some(if input.len() > 4096 {
err("integer_limit")
} else {
natural_conjunction(parts)
});
}
let patterns = patterns();
let (family, c) = patterns
.iter()
.find_map(|(family, pattern)| pattern.captures(input).map(|c| (*family, c)))?;
Some((|| {
if input.len() > 4096 {
return err("integer_limit");
}
match family {
Family::LinearBlock => {
let (population, block) = (count(&c[1])?, count(&c[3])?);
let noun = |input: &str| input.strip_suffix('s').unwrap_or(input).to_owned();
let stated_size = match &c[5] {
"pair" => Some(2u8),
"trio" => Some(3u8),
"quartet" => Some(4u8),
_ => None,
};
if !population.is_positive()
|| !block.is_positive()
|| block > population
|| noun(&c[2]) != noun(&c[4])
|| stated_size.is_some_and(|size| block != BigInt::from(size))
{
return err("invalid_integer_argument");
}
linear_block(population, block)
}
Family::FiniteConjunctionReport => finite_conjunction_report(&c[2], &c[1], None, &c[3]),
Family::FiniteIntervalReport => finite_conjunction_report(
&c[3],
&c[1],
natural_bounds(NaturalBounds::Bracket(&c[2]), &c[1], false)?,
&c[4],
),
Family::LetterWords => {
let positions = bounded(&count(&c[1])?, 256)? as usize;
let letters = c[2].split(',').map(str::trim).collect::<Vec<_>>();
if letters.len() > 256 {
return err("integer_limit");
}
let mut counts = [0usize; 26];
for letter in &letters {
if letter.len() != 1 || !letter.as_bytes()[0].is_ascii_lowercase() {
return err("invalid_integer_argument");
}
counts[(letter.as_bytes()[0] - b'a') as usize] += 1;
}
if positions > letters.len() {
return Ok("0".into());
}
let mut ways = vec![BigInt::zero(); positions + 1];
ways[0] = BigInt::one();
for available in counts.into_iter().filter(|n| *n > 0) {
let mut next = vec![BigInt::zero(); positions + 1];
for used in 0..=positions {
for added in 0..=available.min(positions - used) {
next[used + added] +=
&ways[used] * choose(&(used + added).into(), &added.into(), false)?;
}
}
ways = next;
}
Ok(decimal(&ways[positions]))
}
Family::Committees => {
let (population, size) = (count(&c[1])?, count(&c[2])?);
if population < BigInt::from(2) || size.is_negative() || size > population {
return err("invalid_integer_argument");
}
let all = choose(&population, &size, false)?;
let forbidden = if size < BigInt::from(2) {
BigInt::zero()
} else {
choose(&(&population - 2u8), &(&size - 2u8), false)?
};
Ok(decimal(&(all - forbidden)))
}
Family::LabeledGraphs => {
let vertices = count(&c[1])?;
let selected = count(&c[2])?;
bounded(&vertices, 100_000)?;
if selected.is_negative() {
return err("invalid_integer_argument");
}
let edges = &vertices * (&vertices - 1u8) / 2u8;
if selected > edges {
return Ok("0".into());
}
Ok(decimal(&choose(&edges, &selected, false)?))
}
Family::SubgroupCommittees => {
let (population, size, selected, subgroup) =
(count(&c[1])?, count(&c[2])?, count(&c[3])?, count(&c[4])?);
if [&population, &size, &selected, &subgroup]
.into_iter()
.any(Signed::is_negative)
|| subgroup > population
|| size > population
{
return err("invalid_integer_argument");
}
if selected > subgroup
|| selected > size
|| &size - &selected > &population - &subgroup
{
return Ok("0".into());
}
let designated = choose(&subgroup, &selected, false)?;
let remaining = choose(&(&population - subgroup), &(&size - selected), false)?;
Ok(decimal(&checked(designated * remaining)?))
}
Family::ConstrainedDigitCodes => {
let (length, first, last) = (count(&c[1])?, count(&c[2])?, count(&c[3])?);
if !length.is_positive()
|| first.is_negative()
|| first > last
|| last > BigInt::from(9)
{
return err("invalid_integer_argument");
}
let alphabet = &last - &first + 1u8;
if length > alphabet {
return Ok("0".into());
}
let even = &last / 2u8 - (&first + 1u8) / 2u8 + 1u8;
let zero = if first.is_zero() {
BigInt::one()
} else {
BigInt::zero()
};
if length.is_one() {
return Ok(decimal(&(even - zero)));
}
let leading = &alphabet - &zero;
let endpoints = &zero * &leading + (&even - &zero) * (&leading - 1u8);
let interior = choose(&(&alphabet - 2u8), &(&length - 2u8), true)?;
Ok(decimal(&checked(endpoints * interior)?))
}
Family::DigitCodes => {
let (positions, first, last, successes, digit) = (
count(&c[1])?,
count(&c[2])?,
count(&c[3])?,
count(&c[4])?,
count(&c[5])?,
);
if positions.is_negative()
|| successes.is_negative()
|| first.is_negative()
|| first > last
|| last > BigInt::from(9)
|| digit < first
|| digit > last
{
return err("invalid_integer_argument");
}
if successes > positions {
return Ok("0".into());
}
let choices = choose(&positions, &successes, false)?;
let others = bounded(&(&positions - successes), 100_000)? as u32;
let ways = value(&format!("({})^{others}", last - first))?;
Ok(decimal(&checked(choices * ways)?))
}
Family::RollOutcomes => {
let (sides, rolls, successes, face) =
(count(&c[1])?, count(&c[2])?, count(&c[3])?, count(&c[4])?);
if sides < BigInt::one() || face < BigInt::one() || face > sides {
return err("invalid_integer_argument");
}
let choices = choose(&rolls, &successes, false)?;
let others = bounded(&(&rolls - &successes), 100_000)? as u32;
let ways = value(&format!("({})^{others}", sides - 1u8))?;
Ok(decimal(&checked(choices * ways)?))
}
Family::ExclusiveMultiples => {
let (lower, upper, a, b) =
(value(&c[1])?, value(&c[2])?, value(&c[3])?, value(&c[4])?);
if lower > upper || a <= BigInt::zero() || b <= BigInt::zero() {
return err("invalid_integer_argument");
}
let period = checked(a.lcm(&b))?;
let multiples =
|divisor: &BigInt| upper.div_floor(divisor) - (&lower - 1u8).div_floor(divisor);
Ok(decimal(
&(multiples(&a) + multiples(&b) - multiples(&period) * 2u8),
))
}
Family::GrowingDifferences => {
let sequence = terms(&c[1])?;
let step = BigRational::from_integer(count(&c[3])?);
if step <= BigRational::zero() {
return err("invalid_integer_argument");
}
increments(&sequence, &sequence[1] - &sequence[0], step, &c[2])
}
Family::DivideSequence => {
let sequence = terms(&c[1])?;
let divisor = scalar(&c[2])?;
if divisor.is_zero() {
return err("division_by_zero");
}
if sequence
.windows(2)
.any(|pair| &pair[0] / &divisor != pair[1])
{
return err("invalid_integer_argument");
}
Ok(rational_display(&(sequence.last().unwrap() / divisor)))
}
Family::AffineSequence => {
let sequence = terms(&c[1])?;
let add = BigRational::from_integer(count(&c[2])?);
if sequence
.windows(2)
.any(|pair| &pair[0] * BigInt::from(2) + &add != pair[1])
{
return err("invalid_integer_argument");
}
following(sequence.last().unwrap().clone(), &c[3], |term| {
term * BigInt::from(2) + &add
})
}
Family::OddDifferences => {
let sequence = terms(&c[1])?;
let initial = count(&c[3])?;
if initial.is_even() {
return err("invalid_integer_argument");
}
increments(
&sequence,
BigRational::from_integer(initial),
BigRational::from_integer(2.into()),
&c[2],
)
}
Family::IndexedSequence => {
let (first, coefficient) = (value(&c[1])?, value(&c[2])?);
let (term, until) = (value(&c[3])?, value(&c[4])?);
if term <= BigInt::zero() || until <= BigInt::zero() {
return err("invalid_integer_argument");
}
bounded(&term, 1_000_000)?;
bounded(&until, 1_000_000)?;
let result = checked(&first + &coefficient * (&term * (&term + 1u8) / 2u8 - 1u8))?;
let sum = checked(
&until * &first
+ &coefficient * (&until * (&until + 1u8) * (&until + 2u8) / 6u8 - &until),
)?;
Ok(format!(
"a_{term}: {}; sum: {}",
decimal(&result),
decimal(&sum)
))
}
Family::IndexedAffineList => {
if c[1] != c[3] || c[1] != c[5] || c[1] != c[6] {
return err("invalid_integer_expression");
}
let endpoint = c[7]
.chars()
.map(|digit| {
"₀₁₂₃₄₅₆₇₈₉"
.chars()
.position(|item| item == digit)
.unwrap()
.to_string()
})
.collect::<String>();
let endpoint = bounded(&value(&endpoint)?, 255)?;
let expression = c[4].replace(format!("{}ₙ", &c[1]).as_str(), &c[1]);
let (constant, coefficients) = affine_value(&expression, &[&c[1]])?;
let mut term = BigRational::from_integer(value(&c[2])?);
let mut result = Vec::new();
for index in 0..=endpoint {
if term.numer().bits().max(term.denom().bits()) > 1_000_000 {
return err("integer_limit");
}
let display = rational_display(&term);
if result.iter().map(String::len).sum::<usize>() + display.len() > 4096 {
return err("integer_limit");
}
result.push(display);
if index < endpoint {
term = &coefficients[0] * term + &constant;
}
}
Ok(format!("terms: {}", result.join("; ")))
}
Family::DivisionReport => {
let (number, divisor) = (value(&c[1])?, value(&c[2])?);
if divisor.is_zero() {
return err("division_by_zero");
}
let (quotient, remainder) = number.div_mod_floor(&divisor.abs());
let quotient = if divisor.is_negative() {
-quotient
} else {
quotient
};
Ok(format!(
"quotient: {}; remainder: {}",
decimal("ient),
decimal(&remainder)
))
}
Family::Congruences => wording::special(&format!(
"least positive solution to x ≡ ({}) (mod ({})), x ≡ ({}) (mod ({}))",
&c[1], &c[2], &c[3], &c[4]
))
.ok_or_else(|| Error("invalid_integer_expression".into()))?,
Family::BoundedDivisibility => {
let (lower, upper, modulus) = (value(&c[1])?, value(&c[2])?, value(&c[4])?);
if lower > upper || modulus <= BigInt::zero() {
return err("invalid_integer_argument");
}
let width = bounded(&(&upper - &lower), 10_000)?;
let (constant, coefficients) = affine_value(&c[3], &["x"])?;
if !constant.is_integer() || !coefficients[0].is_integer() {
return err("integer_required");
}
let (constant, coefficient) = (constant.to_integer(), coefficients[0].to_integer());
let mut solutions = Vec::new();
for offset in 0..=width {
let x = &lower + offset;
if checked(&coefficient * &x + &constant)?
.mod_floor(&modulus)
.is_zero()
{
if solutions.len() == 256 {
return err("integer_limit");
}
solutions.push(decimal(&x));
}
}
Ok(format!(
"solutions: {}",
if solutions.is_empty() {
"none".into()
} else {
solutions.join("; ")
}
))
}
Family::BoundedAbsoluteInequality => bounded_absolute_inequality(&c),
Family::ChainedInequality => chained_inequality(&c),
Family::AbsoluteIntersection => absolute_intersection(&c),
Family::ConjunctionReport => conjunction_report(
&c[2],
&c[1],
Some(IntegerRange {
lower: None,
upper: None,
}),
c[3].starts_with("how many"),
),
Family::BoundedConjunctionReport => {
if c[1] != c[5] {
return err("invalid_integer_expression");
}
conjunction_report(&c[4], &c[1], Some(supplied_bounds(&c[2], &c[3])?), true)
}
}
})())
}