use super::poly::{Mono, Poly};
fn gcd(a: i128, b: i128) -> i128 {
let (mut a, mut b) = (a.abs(), b.abs());
while b != 0 {
(a, b) = (b, a % b);
}
a
}
fn coef(p: &Poly, m: &Mono) -> i128 {
p.0.get(m).copied().unwrap_or(0)
}
fn konst(p: &Poly) -> i128 {
coef(p, &Vec::new())
}
fn unknowns(p: &Poly) -> impl Iterator<Item = (&Mono, &i128)> {
p.0.iter().filter(|(k, _)| !k.is_empty())
}
fn cancel(q: &Poly, p: &Poly, x: &Mono) -> Option<Poly> {
let c = coef(p, x);
let d = coef(q, x);
if d == 0 {
return Some(q.clone());
}
q.scale(c.abs())?.sub(&p.scale(c.signum() * d)?)
}
fn tighten(p: &Poly) -> Option<Poly> {
let g = unknowns(p).fold(0, |g, (_, c)| gcd(g, *c));
if g == 0 {
return None;
}
let mut out = Poly::default();
for (k, v) in &p.0 {
let nv = if k.is_empty() { v.div_euclid(g) } else { v / g };
if nv != 0 {
out.0.insert(k.clone(), nv);
}
}
Some(out)
}
pub fn eliminate(mut eqs: Vec<Poly>, mut ges: Vec<Poly>, max_rows: usize) -> Option<bool> {
while let Some(p) = eqs.pop() {
let g = unknowns(&p).fold(0, |g, (_, c)| gcd(g, *c));
if g == 0 {
if konst(&p) != 0 {
return Some(true);
}
continue;
}
if konst(&p) % g != 0 {
return Some(true);
}
let x = unknowns(&p).next().map(|(k, _)| k.clone())?;
for q in eqs.iter_mut().chain(ges.iter_mut()) {
*q = cancel(q, &p, &x)?;
}
}
loop {
let mut rows: Vec<Poly> = Vec::new();
for p in ges.drain(..) {
match tighten(&p) {
None => {
if konst(&p) < 0 {
return Some(true);
}
}
Some(t) => rows.push(t),
}
}
rows.sort();
rows.dedup();
if rows.is_empty() {
return Some(false);
}
if rows.len() > max_rows {
return None;
}
let mut best: Option<(usize, Mono)> = None;
for r in &rows {
for (k, _) in unknowns(r) {
let pos = rows.iter().filter(|q| coef(q, k) > 0).count();
let neg = rows.iter().filter(|q| coef(q, k) < 0).count();
let cost = pos * neg;
if best.as_ref().map(|b| cost < b.0) != Some(false) {
best = Some((cost, k.clone()));
}
}
}
let x = best?.1;
let (mut pos, mut neg) = (Vec::new(), Vec::new());
for r in rows {
match coef(&r, &x) {
0 => ges.push(r),
c if c > 0 => pos.push(r),
_ => neg.push(r),
}
}
for p in &pos {
for n in &neg {
let a = coef(p, &x);
let b = coef(n, &x);
ges.push(p.scale(-b)?.add(&n.scale(a)?)?);
}
}
if ges.len() > max_rows {
return None;
}
}
}