use super::arithmetic::eval;
use crate::{Context, Error, Outcome, Plugin, number, re};
pub struct Integers;
fn scalar(s: &str) -> Option<f64> {
let s = s.trim().replace(',', "");
let (sign, s) = s.strip_prefix('-').map(|x| (-1.0, x)).unwrap_or((1.0, &s));
for (prefix, base) in [("0x", 16), ("0b", 2), ("0o", 8)] {
if let Some(v) = s.strip_prefix(prefix) {
return if v.chars().all(|c| c.is_digit(base)) {
Some(sign * u64::from_str_radix(v, base).unwrap_or(0) as f64)
} else {
None
};
}
}
s.parse::<f64>()
.ok()
.map(|n| n * sign)
.filter(|n| n.is_finite())
.or_else(|| eval(s).map(|n| n * sign))
}
fn uint(x: f64) -> u64 {
if x < 0.0 || x >= u64::MAX as f64 {
0
} else {
x.round() as u64
}
}
fn display(n: u64, base: u32) -> String {
match base {
2 => format!("0b{n:b}"),
8 => format!("0o{n:o}"),
16 => format!("0x{n:X}"),
_ => number(n as f64),
}
}
fn invalid() -> Outcome {
Some(Err(Error("invalid_expression".into())))
}
impl Plugin for Integers {
fn evaluate(&self, input: &str, _ctx: &Context) -> Outcome {
let s = input.trim();
let mut changed = false;
let reduced = re!(r"\(([^()]+ (?:choose|combination|permutation) [^()]+)\)").replace_all(
s,
|c: ®ex::Captures| {
if let Some(Ok(value)) = self.evaluate(&c[1], _ctx) {
changed = true;
format!("({value})")
} else {
c[0].to_string()
}
},
);
if changed {
return eval(&reduced).map(|n| Ok(number(n)));
}
if let Some(c) = re!(r"(?i)^(.+) (combinations?|permutations?) of (.+)$").captures(s) {
return self.evaluate(&format!("{} {} {}", &c[3], &c[2], &c[1]), _ctx);
}
let pattern = re!(
r"(?i)^(is prime [+-]?[\d.,]+|(?:gcd|gcf|greatest common divisor|greatest common factor|lcm|lowest common multiple) of [+-]?[\d.,]+ and [+-]?[\d.,]+|[+-]?[\d.,]+ (?:choose|combinations?|permutations?) [+-]?[\d.,]+)(\s*[+*/^−-].+)$"
);
if let Some(c) = pattern.captures(s) {
let value = self.evaluate(&c[1], _ctx)?.ok()?;
let value = match value.as_str() {
"true" => "1",
"false" => "0",
s => s,
};
return Some(Ok(number(eval(&format!("({value}){}", &c[2]))?)));
}
if let Some(c) =
re!(r"(?i)^(?:is (.+) (?:a prime number|prime)|is prime (.+))$").captures(s)
{
let raw = c.get(1).or_else(|| c.get(2))?.as_str();
if raw.starts_with('+')
|| (!raw.starts_with('(')
&& raw
.trim_start_matches('-')
.contains(['^', '+', '*', '/', '-']))
{
return invalid();
}
let n = scalar(raw)?;
return Some(Ok((n >= 2.0
&& n.fract() == 0.0
&& n < u64::MAX as f64
&& prime(n as u64))
.to_string()));
}
if let Some(c) =
re!(r"(?i)^(gcd|gcf|greatest common divisor|greatest common factor|lcm|lowest common multiple) of (.+) and (.+)$")
.captures(s)
{
if !c[2].trim_start().starts_with('(')
&& c[2]
.trim_start_matches('-')
.contains(['^', '+', '*', '/', '-'])
{
return None;
}
let (a, b) = (scalar(&c[2])?, scalar(&c[3])?);
let exact = integer(&c[2]).zip(integer(&c[3]));
let g = if let Some((a, b)) = exact {
let (mut x, mut y) = (a.unsigned_abs(), b.unsigned_abs());
while y != 0 {
(x, y) = (y, x % y);
}
x as f64
} else {
let (mut x, mut y) = (a.abs(), b.abs());
let mut steps = 0;
while y > 1e-12 && steps < 128 {
(x, y) = (y, x % y);
steps += 1;
}
x
};
let g = if a < 0.0 || b < 0.0 { -g } else { g };
let v = if c[1].eq_ignore_ascii_case("lcm")
|| c[1].eq_ignore_ascii_case("lowest common multiple")
{
if b == 0.0 {
a
} else if g == 0.0 {
0.0
} else {
a * b / g
}
} else {
g
};
return Some(Ok(number(v)));
}
if let Some(c) =
re!(r"(?i)^(.+) (choose|combination|combinations|permutation|permutations) (.+)$")
.captures(s)
{
if !c[1].trim_start().starts_with('(')
&& c[1]
.trim_start_matches('-')
.contains(['^', '+', '*', '/', '-'])
{
return None;
}
let (n, k) = (scalar(&c[1])?.round(), scalar(&c[3])?.round());
if n < 0.0 || k < 0.0 || k > n {
return invalid();
}
let n = n as u64;
let k = k as u64;
let mut result = 1.0;
let choose = !c[2].to_lowercase().starts_with("permutation");
let k = if choose { k.min(n - k) } else { k };
for i in 1..=k {
result *= (n - k + i) as f64 / if choose { i as f64 } else { 1.0 };
if !result.is_finite() {
return invalid();
}
}
return Some(Ok(number(result)));
}
if let Some(c) =
re!(r"(?i)^(.+) (?:to|in|as) (binary|bin|octal|oct|hex|hexadecimal|decimal|base \d+)$")
.captures(s)
{
let x = scalar(&c[1])?;
let target = c[2].to_lowercase();
let base = match target.as_str() {
"binary" | "bin" => 2,
"octal" | "oct" => 8,
"hex" | "hexadecimal" => 16,
"decimal" => 10,
_ => target.strip_prefix("base ")?.parse().ok()?,
};
if ![2, 8, 10, 16].contains(&base) {
return invalid();
}
return Some(Ok(if base == 10 {
number(x)
} else {
display(uint(x), base)
}));
}
if s.matches('|').count() > 1
&& let Some(values) = s.split('|').map(scalar).collect::<Option<Vec<_>>>()
{
let n = values.into_iter().map(uint).fold(0, |a, b| a | b);
return Some(Ok(number(n as f64)));
}
if let Some(c) = re!(r"(?i)^(.+?)\s*(XOR|<<|>>|&|\|)\s*(.+)$").captures(s) {
let (a, b) = (uint(scalar(&c[1])?), uint(scalar(&c[3])?));
let n = match c[2].to_lowercase().as_str() {
"xor" => a ^ b,
"&" => a & b,
"|" => a | b,
"<<" => {
if b >= 64 {
0
} else {
a << b
}
}
">>" => {
if b >= 64 {
0
} else {
a >> b
}
}
_ => return None,
};
return Some(Ok(display(
n,
if c[1].trim().starts_with("0x") {
16
} else if c[1].trim().starts_with("0b") {
2
} else {
10
},
)));
}
if let Some(c) = re!(r"(?i)^([+-]?[\d.]+)\s+(?:mod|%)\s+(\(?[+-]?[\d.]+\)?)$").captures(s) {
let (a, b) = (scalar(&c[1])?, scalar(&c[2])?);
if b == 0.0 {
return invalid();
}
return Some(Ok(number(((a % b) + b) % b)));
}
if let Some(c) = re!(r"(?i)^remainder of (.+) divided by (.+)$").captures(s) {
let (a, b) = (scalar(&c[1])?, scalar(&c[2])?);
if b == 0.0 {
return invalid();
}
return Some(Ok(number(((a % b) + b) % b)));
}
None
}
}
fn integer(s: &str) -> Option<i128> {
s.trim().replace(',', "").parse().ok()
}
fn powmod(mut a: u64, mut n: u64, m: u64) -> u64 {
let mut r = 1;
while n > 0 {
if n & 1 == 1 {
r = (r as u128 * a as u128 % m as u128) as u64;
}
a = (a as u128 * a as u128 % m as u128) as u64;
n >>= 1;
}
r
}
pub(crate) fn prime(n: u64) -> bool {
if n < 2 {
return false;
}
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
if n.is_multiple_of(p) {
return n == p;
}
}
let s = (n - 1).trailing_zeros();
let d = (n - 1) >> s;
'witness: for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022] {
if a % n == 0 {
continue;
}
let mut x = powmod(a % n, d, n);
if x == 1 || x == n - 1 {
continue;
}
for _ in 1..s {
x = (x as u128 * x as u128 % n as u128) as u64;
if x == n - 1 {
continue 'witness;
}
}
return false;
}
true
}