use super::{bounded, choose, decimal, err, factorial, numeral, value};
use crate::{Error, re};
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{One, Signed, Zero};
pub(super) fn normalize(input: &str) -> String {
let mut s = input
.to_lowercase()
.replace(['−', '–'], "-")
.replace(['×', '⋅'], "*")
.replace('÷', "/")
.replace(['’', '‘'], "'")
.replace(['“', '”'], "\"");
s = s.trim().trim_end_matches(['?', '.']).trim().to_string();
s = re!(r"\b([0-9][0-9a-f]*)([₀₁₂₃₄₅₆₇₈₉]+)")
.replace_all(&s, |c: ®ex::Captures| {
let base: String = c[2]
.chars()
.map(|c| {
"₀₁₂₃₄₅₆₇₈₉"
.chars()
.position(|n| n == c)
.unwrap()
.to_string()
})
.collect();
match base.as_str() {
"2" => format!("0b{}", &c[1]),
"8" => format!("0o{}", &c[1]),
"16" => format!("0x{}", &c[1]),
"10" => c[1].into(),
_ => c[0].into(),
}
})
.into_owned();
s = re!(r"^(?:what (?:is|are) |find (?:the )?|compute |calculate |evaluate |write |give the )")
.replace(&s, "")
.into_owned();
s = s
.replace(" multiplied by ", " * ")
.replace(" multiply ", " * ")
.replace(" plus ", " + ")
.replace(" minus ", " - ")
.replace(" divided by ", " / ");
if let Some(c) = re!(r"^multiply (.+) by (.+) and report the result in (binary|octal|hexadecimal|decimal|base \d+)$").captures(&s) {
s = format!("({}) * ({}) in {}", &c[1], &c[2], &c[3]);
}
s = s.split_whitespace().collect::<Vec<_>>().join(" ");
if let Some(c) =
re!(r"^how many distinct arrangements are there of the letters in ([a-z]+)$").captures(&s)
{
s = format!(
"how many distinct arrangements of the letters in {} are there",
&c[1]
);
}
if let Some(c) = re!(r"^a fair(?: (.+?)-sided)? die is rolled (.+?) times; give the number of ordered sequences containing exactly (.+?) sixes$").captures(&s) {
let sides = c.get(1).map_or("6", |value| value.as_str());
s = format!("a fair {sides}-sided die is rolled {} times; how many ordered outcomes contain exactly {} rolls of 6", &c[2], &c[3]);
}
s
}
pub(super) fn base(s: &str) -> Result<u32, Error> {
match s.trim() {
"binary" | "bin" => Ok(2),
"octal" | "oct" => Ok(8),
"decimal" => Ok(10),
"hex" | "hexadecimal" => Ok(16),
s => s
.strip_prefix("base ")
.and_then(|s| s.parse().ok())
.filter(|b| (2..=36).contains(b))
.ok_or_else(|| Error("invalid_base".into())),
}
}
fn hamming_count(first: BigInt, second: BigInt) -> Result<String, Error> {
if first.is_negative() || second.is_negative() {
return err("invalid_integer_argument");
}
let count: u64 = (first ^ second)
.to_biguint()
.unwrap()
.iter_u64_digits()
.map(|digit| u64::from(digit.count_ones()))
.sum();
Ok(decimal(&BigInt::from(count)))
}
pub(super) fn numeral_request(s: &str) -> bool {
if s.ends_with(" decimal") && s.contains(['.', '/']) {
return false;
}
re!(r"^(?:convert |multiply )?[-+()0-9a-fbox. */^]+ (?:from (?:decimal|binary|bin|octal|oct|hexadecimal|hex) )?(?:to|in|as) (?:binary|bin|octal|oct|hexadecimal|hex|decimal|base \d+|signed \d+-bit decimal)$").is_match(s)
}
pub(super) fn expression(s: &str) -> String {
let s = s.trim_start_matches("the ");
let mut result = s.to_string();
if let Some(c) = re!(r"^(?:the )?(gcd|gcf|greatest common divisor|greatest common factor|lcm|least common multiple|lowest common multiple) of (.+)$").captures(s) {
let name = if c[1].contains("multiple") || &c[1] == "lcm" { "lcm" } else { "gcd" };
result = format!("{name}({})", c[2].replace(", and ", ", ").replace(" and ", ", "));
} else if let Some(c) = re!(r"^(?:the )?(?:remainder when|remainder of) (.+?) (?:is /|when /|/) (.+)$").captures(s) {
result = format!("({}) mod ({})", &c[1], &c[2]);
} else if let Some(c) = re!(r"^(?:the )?least nonnegative residue of (.+)$").captures(s) { result = c[1].into(); }
if let Some(c) = re!(r"^(?:the )?remainder of (.+) (?:mod|modulo) (.+)$").captures(s) {
result = format!("({}) mod ({})", &c[1], &c[2]);
}
result = re!(r"\b(\d+) factorial\b")
.replace_all(&result, "$1!")
.into_owned();
result
}
pub(super) fn special(s: &str) -> Option<Result<String, Error>> {
macro_rules! run {
($body:expr) => {
return Some((|| -> Result<String, Error> { $body })());
};
}
if let Some(c) = re!(r"^a (0b[01]+) bit mask is anded with (0b[01]+); give the result in (\d+)-bit binary and decimal$").captures(s) {
run!({
let width = bounded(&value(&c[3])?, 1_000_000)? as usize;
if width == 0 {
return err("invalid_integer_argument");
}
let first = value(&c[1])?;
let second = value(&c[2])?;
if first.is_negative() || second.is_negative()
|| first.bits() > width as u64 || second.bits() > width as u64 {
return err("integer_limit");
}
let result = first & second;
Ok(format!("binary: {}; decimal: {}", numeral(&result, 2, width)?, decimal(&result)))
});
}
if let Some(c) = re!(r"^for byte x=(0x[0-9a-f]+), clear bits (\d+) and (\d+) using zero-based bit positions from the least significant bit; give the resulting byte in hexadecimal$").captures(s) {
run!({
let byte = value(&c[1])?;
if byte.is_negative() || byte.bits() > 8 {
return err("integer_limit");
}
let first = value(&c[2])?;
let second = value(&c[3])?;
if first.is_negative() || second.is_negative()
|| first >= BigInt::from(8) || second >= BigInt::from(8) {
return err("invalid_integer_argument");
}
let first = bounded(&first, 7)? as usize;
let second = bounded(&second, 7)? as usize;
let mask = (BigInt::one() << first) | (BigInt::one() << second);
numeral(&(byte & !mask), 16, 0)
});
}
if let Some(c) = re!(r"^(?:the )?hamming distance between ([01]+) and ([01]+), treating the strings as equal-length binary words$").captures(s) {
run!({
if c[1].len() != c[2].len() {
return err("invalid_integer_argument");
}
if c[1].len() > 1_000_000 {
return err("integer_limit");
}
let first = BigInt::parse_bytes(c[1].as_bytes(), 2).ok_or_else(|| Error("invalid_integer_expression".into()))?;
let second = BigInt::parse_bytes(c[2].as_bytes(), 2).ok_or_else(|| Error("invalid_integer_expression".into()))?;
hamming_count(first, second)
});
}
if let Some(c) = re!(r"^(.+) in (?:reduced|simplified) fraction$").captures(s) {
run!({
let (numerator, denominator) = super::ratio_value(&c[1])?;
Ok(format!("{}/{}", decimal(&numerator), decimal(&denominator)))
});
}
if let Some(c) = re!(r"^(?:convert |multiply )?(.+?) (?:from (decimal|binary|bin|octal|oct|hexadecimal|hex) )?(?:to|in|as) (binary|bin|octal|oct|hexadecimal|hex|decimal|base \d+|signed \d+-bit decimal)$").captures(s).filter(|c| re!(r"^[-+()0-9a-fbox. */^]+$").is_match(&c[1]) || super::expression::parse(&c[1]).is_ok()) {
run!({
let raw = c[1].replace(" by ", " * ");
let n = if let Some(source) = c.get(2) {
BigInt::parse_bytes(raw.as_bytes(), base(source.as_str())?).ok_or_else(|| Error("invalid_integer_expression".into()))?
} else { value(&raw)? };
if let Some(c) = re!(r"^signed (\d+)-bit decimal$").captures(&c[3]) {
let width = c[1].parse::<usize>().map_err(|_| Error("invalid_integer_argument".into()))?;
if width == 0 || width > 1_000_000 || n.is_negative() || n.bits() > width as u64 { return err("integer_limit"); }
let modulus = BigInt::one() << width;
return Ok(decimal(&if n >= (&modulus >> 1) { n - modulus } else { n }));
}
numeral(&n, base(&c[3])?, 0)
});
}
if let Some(c) = re!(r"^(?:convert )?(.+?) to (\d+)-bit two's-complement binary$").captures(s) {
run!({
let n = value(&c[1])?;
let width = bounded(&value(&c[2])?, 1_000_000)? as usize;
if width == 0 {
return err("invalid_integer_argument");
}
let modulus = BigInt::one() << width;
if n < -(&modulus >> 1usize) || n >= (&modulus >> 1usize) {
return err("integer_limit");
}
numeral(&n.mod_floor(&modulus), 2, width)
});
}
if let Some(c) =
re!(r"^interpret ([01]+) as an? (\d+)-bit two's-complement integer$").captures(s)
{
run!({
let width = bounded(&value(&c[2])?, 1_000_000)? as usize;
if width == 0 || c[1].len() != width {
return err("invalid_integer_argument");
}
let n = BigInt::parse_bytes(c[1].as_bytes(), 2).unwrap();
Ok(decimal(&if c[1].starts_with('1') {
n - (BigInt::one() << width)
} else {
n
}))
});
}
if let Some(c) =
re!(r"^(.+) (?:in (\d+)-bit unsigned arithmetic|and report the result in (.+))$")
.captures(s)
{
run!({
let n = value(&c[1].trim_start_matches("multiply ").replace(" by ", " * "))?;
if let Some(width) = c.get(2) {
let width = bounded(&value(width.as_str())?, 1_000_000)? as usize;
if width == 0 {
return err("invalid_integer_argument");
}
return Ok(decimal(&n.mod_floor(&(BigInt::one() << width))));
}
numeral(&n, base(&c[3])?, 0)
});
}
if let Some(c) = re!(r"^(?:the )?(\d+)-bit result of (.+)$").captures(s) {
run!({
let width = bounded(&value(&c[1])?, 1_000_000)? as usize;
if width == 0 {
return err("invalid_integer_argument");
}
let result = value(&c[2])?.mod_floor(&(BigInt::one() << width));
numeral(&result, if c[2].starts_with("0x") { 16 } else { 10 }, 0)
});
}
if let Some(c) =
re!(r"^how many (1 bits|bits) are (?:in (.+)|in the decimal number (.+))$").captures(s)
{
run!({
let n = value(
c.get(3)
.or_else(|| c.get(2))
.unwrap()
.as_str()
.trim_start_matches("the decimal number "),
)?;
if n.is_negative() {
return err("invalid_integer_argument");
}
let count = if &c[1] == "bits" {
n.bits()
} else {
n.to_biguint()
.unwrap()
.iter_u64_digits()
.map(|d| u64::from(d.count_ones()))
.sum()
};
Ok(decimal(&BigInt::from(count)))
});
}
if let Some(c) = re!(r"^hamming distance between (.+) and (.+)$").captures(s) {
run!({
let (a, b) = (value(&c[1])?, value(&c[2])?);
hamming_count(a, b)
});
}
if let Some(c) =
re!(r"^(set the least significant 1 bit of|clear bit (\d+) of) (.+)$").captures(s)
{
run!({
let n = value(&c[3])?;
if n.is_negative() {
return err("invalid_integer_argument");
}
let result = if let Some(bit) = c.get(2) {
let bit = bounded(&value(bit.as_str())?, 1_000_000)? as usize;
n & !(BigInt::one() << bit)
} else {
&n | BigInt::one()
};
numeral(
&result,
if c[3].starts_with("0b") {
2
} else if c[3].starts_with("0x") {
16
} else {
10
},
0,
)
});
}
if let Some(c) = re!(r"^reverse the order of the (\d+) bits in (.+)$").captures(s) {
run!({
let width = bounded(&value(&c[1])?, 1_000_000)? as usize;
let n = value(&c[2])?;
if n.is_negative() || n.bits() > width as u64 {
return err("integer_limit");
}
let raw = format!("{:0>width$}", n.to_str_radix(2));
let reversed: String = raw.chars().rev().collect();
numeral(
&BigInt::parse_bytes(reversed.as_bytes(), 2).unwrap(),
2,
width,
)
});
}
if let Some(c) = re!(r"^(.+) rotated (left|right) by (\d+) bits within (\d+) bits$").captures(s)
{
run!({
let n = value(&c[1])?;
let width = bounded(&value(&c[4])?, 1_000_000)? as usize;
if width == 0 || n.is_negative() || n.bits() > width as u64 {
return err("integer_limit");
}
let shift = (bounded(&value(&c[3])?, u64::MAX)? % width as u64) as usize;
let shift = if &c[2] == "right" {
(width - shift) % width
} else {
shift
};
let mask = (BigInt::one() << width) - 1u8;
let result = ((&n << shift) | (&n >> (width - shift))) & mask;
numeral(
&result,
if c[1].starts_with("0x") { 16 } else { 2 },
if c[1].starts_with("0x") { 0 } else { width },
)
});
}
if let Some(c) =
re!(r"^solve (.+)x ≡ (.+) \(mod (.+)\) for the least nonnegative x$").captures(s)
{
run!({
let (a, b, m) = (value(&c[1])?, value(&c[2])?, value(&c[3])?);
if m <= BigInt::zero() {
return err("invalid_integer_argument");
}
let eg = a.extended_gcd(&m);
if !(&b % &eg.gcd).is_zero() {
return err("no_integer_solution");
}
Ok(decimal(&((eg.x * (b / &eg.gcd)).mod_floor(&(m / eg.gcd)))))
});
}
if let Some(c) =
re!(r"^(?:the )?least positive solution to x ≡ (.+) \(mod (.+)\), x ≡ (.+) \(mod (.+)\)$")
.captures(s)
{
run!({
let (a, m, b, n) = (value(&c[1])?, value(&c[2])?, value(&c[3])?, value(&c[4])?);
if m <= BigInt::zero() || n <= BigInt::zero() {
return err("invalid_integer_argument");
}
let eg = m.extended_gcd(&n);
let difference = b - &a;
if !(&difference % &eg.gcd).is_zero() {
return err("no_integer_solution");
}
let modulus = m.lcm(&n);
let result = (a + &m * (difference / &eg.gcd * eg.x)).mod_floor(&modulus);
Ok(decimal(&if result.is_zero() { modulus } else { result }))
});
}
if let Some(c) = re!(r"^(?:the )?smallest positive integer divisible by (.+)$").captures(s) {
run!({
let args = c[1].replace(", and ", ", ").replace(" and ", ", ");
let result = value(&format!("lcm({args})"))?;
if result.is_zero() {
return err("invalid_integer_argument");
}
Ok(decimal(&result))
});
}
if let Some(c) = re!(r"^how many ways can (.+) items be chosen from (.+)$").captures(s) {
run!(Ok(decimal(&choose(&value(&c[2])?, &value(&c[1])?, false)?)));
}
if let Some(c) = re!(r"^(?:the )?coefficient of x\^(\d+) in \(1\+x\)\^(\d+)$").captures(s) {
run!(Ok(decimal(&choose(&value(&c[2])?, &value(&c[1])?, false)?)));
}
if let Some(c) =
re!(r"^how many distinct arrangements of the letters in ([a-z]+) are there$").captures(s)
{
run!({
let mut counts = [0usize; 26];
for letter in c[1].bytes() {
counts[(letter - b'a') as usize] += 1;
}
let mut result = factorial(&BigInt::from(c[1].len()))?;
for count in counts {
result /= factorial(&BigInt::from(count))?;
}
Ok(decimal(&result))
});
}
if let Some(c) = re!(r"^how many ways can (.+) people sit around a circular table if rotations count as the same seating and two specified people must sit next to each other$").captures(s)
{
run!({
let n = value(&c[1])?;
if n < BigInt::from(2) {
return err("invalid_integer_argument");
}
let result = if n == BigInt::from(2) {
BigInt::one()
} else {
2u8 * factorial(&(n - 2u8))?
};
Ok(decimal(&result))
});
}
if let Some(c) = re!(r"^how many ways can (.+) people sit around a circular table$").captures(s)
{
run!({
let n = value(&c[1])?;
if n < BigInt::one() {
return err("invalid_integer_argument");
}
Ok(decimal(&factorial(&(n - 1u8))?))
});
}
if let Some(c) = re!(r"^how many (\d+)-digit numbers can be made from digits (\d+) through (\d+) without repetition$").captures(s) {
run!({ let (k, a, b) = (value(&c[1])?, value(&c[2])?, value(&c[3])?);
if a < BigInt::zero() || a > b || b > BigInt::from(9) { return err("invalid_integer_argument"); }
let n = b - &a + 1u8; let mut result = choose(&n, &k, true)?;
if a.is_zero() && k > BigInt::zero() { result -= choose(&(n - 1u8), &(k - 1u8), true)?; } Ok(decimal(&result)) });
}
if let Some(c) =
re!(r"^how many subsets of a (\d+)-element set have an even number of elements$")
.captures(s)
{
run!({
let n = bounded(&value(&c[1])?, 1_000_000)?;
Ok(decimal(&if n == 0 {
BigInt::one()
} else {
BigInt::one() << (n - 1) as usize
}))
});
}
if let Some(c) =
re!(r"^count the (\d+)-card hands from a standard (\d+)-card deck$").captures(s)
{
run!(Ok(decimal(&choose(&value(&c[2])?, &value(&c[1])?, false)?)));
}
if let Some(c) =
re!(r"^how many ways to distribute (\d+) identical balls into (\d+) distinct boxes$")
.captures(s)
{
run!({
let (n, k) = (value(&c[1])?, value(&c[2])?);
if k.is_zero() {
return err("invalid_integer_argument");
}
Ok(decimal(&choose(&(n + &k - 1u8), &(k - 1u8), false)?))
});
}
if let Some(c) =
re!(r"^(?:the )?number of integer solutions to ([^=]+)=(\d+) with all xᵢ≥0$").captures(s)
{
run!({
let variables = c[1].split('+').collect::<Vec<_>>();
if !variables
.iter()
.all(|s| re!(r"^x[₀₁₂₃₄₅₆₇₈₉]+$").is_match(s))
{
return err("invalid_integer_expression");
}
let unique: std::collections::BTreeSet<_> = variables.iter().collect();
if unique.len() != variables.len() {
return err("unsupported_integer_equation");
}
let k = BigInt::from(variables.len());
Ok(decimal(&choose(
&(value(&c[2])? + &k - 1u8),
&(k - 1u8),
false,
)?))
});
}
if let Some(c) =
re!(r"^how many permutations of (\d+) objects have no fixed points$").captures(s)
{
run!({
let n = bounded(&value(&c[1])?, 10_000)?;
let (mut a, mut b) = (BigInt::one(), BigInt::zero());
if n == 0 {
return Ok("1".into());
}
for k in 2..=n {
(a, b) = (b.clone(), (k - 1) * (a + b));
}
Ok(decimal(&b))
});
}
if let Some(c) = re!(
r"^(?:(?:the )?number of ways to )?partition (\d+) distinct people into (\d+) unlabeled pairs$"
)
.captures(s)
{
run!({
let (n, k) = (value(&c[1])?, value(&c[2])?);
if n != &k * 2u8 {
return err("invalid_integer_argument");
}
let count = bounded(&k, 10_000)?;
let result = factorial(&n)? / (BigInt::from(2).pow(count as u32) * factorial(&k)?);
Ok(decimal(&result))
});
}
if let Some(c) =
re!(r"^convert (.+) to an? integer base-(\d+) numeral without specifying a rounding rule$")
.captures(s)
{
run!({
let n = value(&c[1])?;
numeral(
&n,
c[2].parse().map_err(|_| Error("invalid_base".into()))?,
0,
)
});
}
if let Some(c) =
re!(r"^how many binary strings of length (\d+) contain exactly (\d+) ones$").captures(s)
{
run!(Ok(decimal(&choose(&value(&c[1])?, &value(&c[2])?, false)?)));
}
if let Some(c) =
re!(r"^how many length-(.+?) binary strings contain exactly (.+?) 1s and no adjacent 1s$")
.captures(s)
{
run!({
let (length, ones) = (
super::discrete::count(&c[1])?,
super::discrete::count(&c[2])?,
);
let count = super::discrete::nonadjacent_count(&length, &ones, &mut 100_000)?;
Ok(decimal(&count))
});
}
if re!(r"^convert [-+]?(?:0[bxo][0-9a-f]+|[\d.]+) to [\d.]+$").is_match(s) {
return Some(err("invalid_base"));
}
None
}