use crate::game::Rational;
use num_traits::Zero;
#[derive(Debug, Clone, PartialEq)]
pub enum LinearSolution {
Unique(Vec<Rational>),
None,
Infinite,
}
pub fn solve_linear_system(mut a: Vec<Vec<Rational>>, mut b: Vec<Rational>) -> LinearSolution {
let rows = a.len();
assert_eq!(
rows,
b.len(),
"coefficient rows and constants must match: {rows} rows, {} constants",
b.len()
);
if rows == 0 {
return LinearSolution::Infinite;
}
let cols = a[0].len();
assert!(
a.iter().all(|row| row.len() == cols),
"coefficient matrix must be rectangular: expected {cols} columns in every row"
);
let mut pivot_row = 0usize;
let mut pivot_col_of_row: Vec<usize> = Vec::new();
for col in 0..cols {
let Some(swap) = (pivot_row..rows).find(|&r| !a[r][col].is_zero()) else {
continue;
};
a.swap(pivot_row, swap);
b.swap(pivot_row, swap);
let pivot = a[pivot_row][col].clone();
for entry in a[pivot_row].iter_mut() {
*entry /= &pivot;
}
b[pivot_row] /= &pivot;
let pivot_values = a[pivot_row].clone();
let pivot_constant = b[pivot_row].clone();
for r in 0..rows {
if r == pivot_row || a[r][col].is_zero() {
continue;
}
let factor = a[r][col].clone();
for (entry, pivot_entry) in a[r].iter_mut().zip(&pivot_values) {
*entry -= &factor * pivot_entry;
}
b[r] -= &factor * &pivot_constant;
}
pivot_col_of_row.push(col);
pivot_row += 1;
if pivot_row == rows {
break;
}
}
for r in 0..rows {
if a[r].iter().all(Zero::is_zero) && !b[r].is_zero() {
return LinearSolution::None;
}
}
if pivot_col_of_row.len() < cols {
return LinearSolution::Infinite;
}
let mut solution = vec![Rational::zero(); cols];
for (r, &col) in pivot_col_of_row.iter().enumerate() {
solution[col] = b[r].clone();
}
LinearSolution::Unique(solution)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::game::Rational;
fn r(n: i64, d: i64) -> Rational {
Rational::new(n.into(), d.into())
}
fn int(n: i64) -> Rational {
Rational::from_integer(n.into())
}
#[test]
fn solves_a_two_by_two_system() {
let a = vec![vec![int(2), int(1)], vec![int(1), int(-1)]];
let b = vec![int(5), int(1)];
match solve_linear_system(a, b) {
LinearSolution::Unique(x) => assert_eq!(x, vec![int(2), int(1)]),
other => panic!("expected a unique solution, got {other:?}"),
}
}
#[test]
fn produces_exact_fractions_not_approximations() {
let a = vec![vec![int(3)]];
let b = vec![int(1)];
match solve_linear_system(a, b) {
LinearSolution::Unique(x) => assert_eq!(x, vec![r(1, 3)]),
other => panic!("expected a unique solution, got {other:?}"),
}
}
#[test]
fn reports_an_inconsistent_system_as_none() {
let a = vec![vec![int(1), int(1)], vec![int(1), int(1)]];
let b = vec![int(1), int(2)];
assert!(matches!(solve_linear_system(a, b), LinearSolution::None));
}
#[test]
fn reports_an_underdetermined_system_as_infinite() {
let a = vec![vec![int(1), int(1)], vec![int(2), int(2)]];
let b = vec![int(1), int(2)];
assert!(matches!(
solve_linear_system(a, b),
LinearSolution::Infinite
));
}
#[test]
fn handles_a_zero_pivot_by_swapping_rows() {
let a = vec![vec![int(0), int(1)], vec![int(1), int(0)]];
let b = vec![int(2), int(3)];
match solve_linear_system(a, b) {
LinearSolution::Unique(x) => assert_eq!(x, vec![int(3), int(2)]),
other => panic!("expected a unique solution, got {other:?}"),
}
}
#[test]
fn a_non_square_system_is_rejected_rather_than_guessed() {
let a = vec![vec![int(1), int(1)]];
let b = vec![int(1)];
assert!(matches!(
solve_linear_system(a, b),
LinearSolution::Infinite
));
}
#[test]
#[should_panic(expected = "coefficient rows and constants must match")]
fn more_rows_than_constants_panics_naming_the_mismatch() {
let a = vec![vec![int(1)], vec![int(1)]];
let b = vec![int(1)];
let _ = solve_linear_system(a, b);
}
#[test]
#[should_panic(expected = "coefficient matrix must be rectangular")]
fn a_ragged_coefficient_matrix_panics() {
let a = vec![vec![int(1), int(1)], vec![int(1)]];
let b = vec![int(1), int(1)];
let _ = solve_linear_system(a, b);
}
}