use super::Program;
use crate::linear::search::Reason;
use crate::linear::search::memory::{Account, Charged};
const AFFINE_ENTRIES_PER_UNIT: u64 = 16;
const LINEAR_ENTRIES_PER_UNIT: u64 = 4;
const EPSILON: f64 = 1e-9;
const MOST_DENOMINATOR: i64 = 1 << 20;
const MOST_COMMON_DENOMINATOR: i64 = 1 << 40;
pub(super) struct Equation<'a> {
affine: bool,
state: State,
spent: u64,
charged: Charged<'a>,
certificate: Option<Vec<(u32, i64)>>,
}
enum State {
Waiting,
Solving(Tableau),
Yielded,
Done,
}
impl<'a> Equation<'a> {
pub(super) fn new(affine: bool, account: &'a Account) -> Self {
Self {
affine,
state: State::Waiting,
spent: 0,
charged: Charged::new(account),
certificate: None,
}
}
pub(super) fn budget(&self, work: u64) -> u64 {
let per_unit = if self.affine {
AFFINE_ENTRIES_PER_UNIT
} else {
LINEAR_ENTRIES_PER_UNIT
};
work.saturating_mul(per_unit)
}
pub(super) fn wants(&self, budget: u64) -> bool {
!matches!(self.state, State::Done | State::Yielded) && self.spent < budget
}
pub(super) fn release(&mut self) -> bool {
if !matches!(self.state, State::Solving(_)) {
return false;
}
self.state = State::Yielded;
self.charged = Charged::new(self.charged.account());
true
}
pub(super) fn finish(
&mut self,
program: &Program,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<bool, Reason> {
if let State::Yielded = self.state {
self.state = State::Waiting;
}
self.run(program, u64::MAX, stop)
}
pub(super) fn run(
&mut self,
program: &Program,
budget: u64,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<bool, Reason> {
if let State::Waiting = self.state {
let places = program.places as u64;
let set_up = places
.saturating_mul(places)
.saturating_mul(3)
.saturating_add(program.arcs.len() as u64);
if budget < set_up {
return Ok(false);
}
self.state = match Tableau::new(program, self.affine, &mut self.charged) {
Some(tableau) => {
self.spent = self.spent.saturating_add(tableau.entries());
State::Solving(tableau)
}
None => State::Yielded,
};
}
let State::Solving(tableau) = &mut self.state else {
return Ok(false);
};
let weights = loop {
if self.spent.saturating_add(tableau.entries()) > budget {
return Ok(false);
}
if stop(1) {
return Err(Reason::Stopped);
}
match tableau.pivot() {
Step::Pivoted => self.spent = self.spent.saturating_add(tableau.entries()),
Step::Optimal => break tableau.weights(),
Step::GiveUp => break None,
}
};
self.state = State::Done;
self.charged = Charged::new(self.charged.account());
self.certificate = weights
.and_then(|weights| integers(&weights))
.filter(|weights| certify(program, self.affine, weights));
Ok(self.certificate.is_some())
}
pub(super) fn certificate(&self) -> Option<&[(u32, i64)]> {
self.certificate.as_deref()
}
}
enum Step {
Pivoted,
Optimal,
GiveUp,
}
struct Tableau {
columns: Vec<Vec<(u32, f64)>>,
places: Vec<(u32, f64)>,
surplus: bool,
inverse: Vec<f64>,
values: Vec<f64>,
basis: Vec<usize>,
prices: Vec<f64>,
column: Vec<f64>,
pivots: u64,
most_pivots: u64,
stalled: u32,
}
const STALLED: u32 = 64;
impl Tableau {
fn new(program: &Program, affine: bool, charged: &mut Charged<'_>) -> Option<Self> {
let places = program.places;
let mut effects: Vec<Vec<(u32, i64)>> = Vec::new();
let mut seen = crate::hash::HashSet::default();
let mut touched = vec![false; places];
for transition in &program.transitions {
let inputs = program.inputs(transition);
let outputs = program.outputs(transition);
let mut effect: Vec<(u32, i64)> = Vec::with_capacity(inputs.len() + outputs.len());
let (mut i, mut o) = (0, 0);
while i < inputs.len() || o < outputs.len() {
let (p, e) = match (inputs.get(i), outputs.get(o)) {
(Some(&(a, w)), Some(&(b, v))) if a == b => {
(i, o) = (i + 1, o + 1);
(a, i64::from(v) - i64::from(w))
}
(Some(&(a, w)), Some(&(b, _))) if a < b => {
i += 1;
(a, -i64::from(w))
}
(Some(&(a, w)), None) => {
i += 1;
(a, -i64::from(w))
}
(_, Some(&(b, v))) => {
o += 1;
(b, i64::from(v))
}
(None, None) => unreachable!("the loop's condition"),
};
if e != 0 {
effect.push((p, e));
}
}
if !effect.is_empty() && seen.insert(effect.clone()) {
for &(p, _) in &effect {
touched[p as usize] = true;
}
effects.push(effect);
}
}
let goal = |p: usize| i64::from(program.target[p]) - i64::from(program.initial[p]);
let rows: Vec<u32> = (0..places)
.filter(|&p| touched[p] || goal(p) != 0)
.map(|p| p as u32)
.collect();
let mut row_of = vec![u32::MAX; places];
for (r, &p) in rows.iter().enumerate() {
row_of[p as usize] = r as u32;
}
let height = rows.len();
let entries: usize = effects.iter().map(Vec::len).sum();
let bytes = height
.checked_mul(height)?
.checked_add(height.checked_mul(4)?)?
.checked_mul(size_of::<f64>())?
.checked_add(entries.checked_mul(size_of::<(u32, f64)>())?)?;
if !charged.account().fits(bytes) {
return None;
}
charged.charge(bytes);
let places: Vec<(u32, f64)> = rows
.iter()
.map(|&p| (p, if goal(p as usize) < 0 { -1.0 } else { 1.0 }))
.collect();
let columns = effects
.into_iter()
.map(|effect| {
effect
.into_iter()
.map(|(p, e)| {
let r = row_of[p as usize];
(r, places[r as usize].1 * e as f64)
})
.collect()
})
.collect::<Vec<Vec<(u32, f64)>>>();
let mut inverse = vec![0.0; height * height];
for r in 0..height {
inverse[r * height + r] = 1.0;
}
let structural = columns.len() + if affine { height } else { 0 };
Some(Self {
values: places
.iter()
.map(|&(p, sign)| sign * goal(p as usize) as f64)
.collect(),
basis: (0..height).map(|r| structural + r).collect(),
prices: vec![1.0; height],
column: vec![0.0; height],
most_pivots: 64 * (structural as u64 + 2 * height as u64),
columns,
places,
surplus: affine,
inverse,
pivots: 0,
stalled: 0,
})
}
fn entries(&self) -> u64 {
let height = self.places.len() as u64;
let priced: usize = self.columns.iter().map(Vec::len).sum();
2 * height * height + priced as u64 + height
}
fn structural(&self) -> usize {
self.columns.len() + if self.surplus { self.places.len() } else { 0 }
}
fn reduced(&self, j: usize) -> f64 {
let (n, structural) = (self.columns.len(), self.structural());
if j < n {
-self.columns[j]
.iter()
.map(|&(r, a)| self.prices[r as usize] * a)
.sum::<f64>()
} else if j < structural {
let r = j - n;
self.prices[r] * self.places[r].1
} else {
1.0 - self.prices[j - structural]
}
}
fn pivot(&mut self) -> Step {
let height = self.places.len();
let columns = self.structural() + height;
let entering = if self.stalled < STALLED {
(0..columns)
.map(|j| (j, self.reduced(j)))
.filter(|&(_, d)| d < -EPSILON)
.min_by(|a, b| a.1.total_cmp(&b.1))
.map(|(j, _)| j)
} else {
(0..columns).find(|&j| self.reduced(j) < -EPSILON)
};
let Some(q) = entering else {
return Step::Optimal;
};
if self.pivots >= self.most_pivots {
return Step::GiveUp;
}
let (n, structural) = (self.columns.len(), self.structural());
for (i, x) in self.column.iter_mut().enumerate() {
let row = &self.inverse[i * height..(i + 1) * height];
*x = if q < n {
self.columns[q]
.iter()
.map(|&(r, a)| row[r as usize] * a)
.sum()
} else if q < structural {
let r = q - n;
-row[r] * self.places[r].1
} else {
row[q - structural]
};
}
let mut leaving: Option<(usize, f64)> = None;
for i in 0..height {
let a = self.column[i];
if a > EPSILON {
let ratio = self.values[i] / a;
let better = match leaving {
None => true,
Some((best, least)) => {
ratio < least - EPSILON
|| (ratio <= least + EPSILON && self.basis[i] < self.basis[best])
}
};
if better {
leaving = Some((i, ratio));
}
}
}
let Some((p, ratio)) = leaving else {
return Step::GiveUp;
};
self.pivots += 1;
self.stalled = if ratio > EPSILON { 0 } else { self.stalled + 1 };
let pivot = self.column[p];
for x in &mut self.inverse[p * height..(p + 1) * height] {
*x /= pivot;
}
self.values[p] /= pivot;
let (before, rest) = self.inverse.split_at_mut(p * height);
let (pivot_row, after) = rest.split_at_mut(height);
let value = self.values[p];
for (i, row) in before
.chunks_exact_mut(height)
.chain(after.chunks_exact_mut(height))
.enumerate()
{
let i = if i < p { i } else { i + 1 };
let factor = self.column[i];
if factor != 0.0 {
for (x, &y) in row.iter_mut().zip(pivot_row.iter()) {
*x -= factor * y;
}
self.values[i] -= factor * value;
}
}
self.basis[p] = q;
self.prices.fill(0.0);
for i in 0..height {
if self.basis[i] >= structural {
let row = &self.inverse[i * height..(i + 1) * height];
for (y, &x) in self.prices.iter_mut().zip(row) {
*y += x;
}
}
}
Step::Pivoted
}
fn weights(&self) -> Option<Vec<(u32, f64)>> {
let structural = self.structural();
let objective: f64 = (0..self.places.len())
.filter(|&i| self.basis[i] >= structural)
.map(|i| self.values[i])
.sum();
if objective <= 1e3 * EPSILON {
return None;
}
Some(
self.places
.iter()
.zip(&self.prices)
.map(|(&(p, sign), &y)| (p, sign * y))
.collect(),
)
}
}
fn integers(weights: &[(u32, f64)]) -> Option<Vec<(u32, i64)>> {
if weights.iter().any(|&(_, w)| !w.is_finite()) {
return None;
}
let largest = weights.iter().map(|&(_, w)| w.abs()).fold(0.0, f64::max);
if largest <= EPSILON {
return None;
}
let fractions: Vec<(u32, i64, i64)> = weights
.iter()
.map(|&(p, w)| {
let (n, d) = fraction(w / largest);
(p, n, d)
})
.collect();
let mut common = 1i64;
for &(_, _, d) in &fractions {
common = common
.checked_mul(d / gcd(common, d))
.filter(|&c| c <= MOST_COMMON_DENOMINATOR)?;
}
let mut integers: Vec<(u32, i64)> = fractions
.into_iter()
.map(|(p, n, d)| (p, n * (common / d)))
.collect();
let divisor = integers.iter().fold(0, |g, &(_, w)| gcd(g, w));
if divisor > 1 {
for (_, w) in &mut integers {
*w /= divisor;
}
}
Some(integers)
}
fn fraction(x: f64) -> (i64, i64) {
if x.abs() <= EPSILON {
return (0, 1);
}
let (sign, x) = if x < 0.0 { (-1, -x) } else { (1, x) };
let (mut h, mut h_before, mut k, mut k_before) = (1i64, 0i64, 0i64, 1i64);
let mut rest = x;
loop {
let a = rest.floor();
let a = a as i64;
let (h_next, k_next) = (a * h + h_before, a * k + k_before);
if k_next > MOST_DENOMINATOR {
break;
}
(h_before, h, k_before, k) = (h, h_next, k, k_next);
let part = rest - a as f64;
if part <= EPSILON || (x - h as f64 / k as f64).abs() <= EPSILON {
break;
}
rest = 1.0 / part;
if rest > 1.0 / EPSILON {
break;
}
}
if k == 0 { (0, 1) } else { (sign * h, k) }
}
fn gcd(a: i64, b: i64) -> i64 {
let (mut a, mut b) = (a.unsigned_abs(), b.unsigned_abs());
while b != 0 {
(a, b) = (b, a % b);
}
a as i64
}
pub(super) fn certify(program: &Program, affine: bool, weights: &[(u32, i64)]) -> bool {
let mut y = vec![0i64; program.places];
for &(p, w) in weights {
y[p as usize] = w;
}
if affine && y.iter().any(|&w| w < 0) {
return false;
}
let weighted = |arcs: &[(u32, u32)]| {
arcs.iter().try_fold(0i128, |sum, &(p, w)| {
i128::from(y[p as usize])
.checked_mul(i128::from(w))
.and_then(|term| sum.checked_add(term))
})
};
for transition in &program.transitions {
let inputs = program.inputs(transition);
let outputs = program.outputs(transition);
let raised = weighted(outputs)
.zip(weighted(inputs))
.and_then(|(o, i)| o.checked_sub(i));
if !raised.is_some_and(|r| r <= 0) {
return false;
}
}
let asked = (0..program.places).try_fold(0i128, |sum, p| {
let change = i128::from(program.target[p]) - i128::from(program.initial[p]);
i128::from(y[p])
.checked_mul(change)
.and_then(|term| sum.checked_add(term))
});
asked.is_some_and(|a| a > 0)
}