extern crate fixedbitset;
extern crate num_traits;
extern crate ndarray;
use fixedbitset::FixedBitSet;
use num_traits::{PrimInt, NumAssign};
use ndarray::prelude::Array2;
macro_rules! get {
($m:expr, $i:expr, $j:expr) => (unsafe { *$m.uget(($i, $j)) })
}
macro_rules! set {
($m:expr, $i:expr, $j:expr, $v: expr) => (unsafe { *$m.uget_mut(($i, $j)) = $v; })
}
macro_rules! on {
($s:expr, $i:expr) => ($s.contains($i))
}
macro_rules! off {
($s:expr, $i:expr) => (!$s.contains($i))
}
pub fn minimize<N: NumAssign + PrimInt>(matrix: &[N], height: usize, width: usize) -> Vec<Option<usize>> {
if height == 0 || width == 0 { return Vec::new() }
let rotated = width < height;
let (w, h) = if rotated { (height, width) } else { (width, height) };
let mut m = Array2::zeros((h, w));
for i in 0..height {
for j in 0..width {
let cost = matrix[width * i + j];
if cost < N::zero() {
continue
} else if rotated {
set!(m, width - 1 - j, i, cost)
} else {
set!(m, i, j, cost)
}
}
}
let mut stars = Array2::from_elem((h, w), false);
let mut primes = Array2::from_elem((h, w), false);
let mut row_cover = FixedBitSet::with_capacity(h);
let mut col_cover = FixedBitSet::with_capacity(w);
for mut row in m.genrows_mut() {
let min = row.iter().min().unwrap().clone();
row.map_inplace(|v| *v -= min);
}
for i in 0..h {
for j in 0..w {
if on!(col_cover, j) { continue }
if get!(m, i, j).is_zero() {
set!(stars, i, j, true);
col_cover.insert(j);
break
}
}
}
col_cover.clear();
let mut verify = true;
loop {
if verify {
stars.gencolumns()
.into_iter()
.enumerate()
.for_each(|(j, col)| {
if col.iter().any(|&s| s) { col_cover.insert(j) }
});
if col_cover.count_ones(..) == h {
let assign = stars.genrows().into_iter().map(|r| {
r.iter().enumerate()
.find(|&(_, &v)| v)
.map(|(i, _)| i)
.unwrap()
});
if rotated {
let mut result = vec![None; w];
assign.enumerate().for_each(|(i, j)| result[j] = Some(h - i - 1));
return result
} else {
return assign.map(|j| Some(j)).collect()
}
}
}
let mut uncovered = None;
'outer : for i in 0..h {
if on!(row_cover, i) { continue }
for j in 0..w {
if on!(col_cover, j) { continue }
if get!(m, i, j).is_zero() {
uncovered = Some((i, j));
set!(primes, i, j, true);
break 'outer;
}
}
}
if let None = uncovered {
let mut min = N::max_value();
for i in 0..h {
if on!(row_cover, i) { continue }
for j in 0..w {
if on!(col_cover, j) { continue }
let value = get!(m, i, j);
min = if value < min { value } else { min };
}
}
for i in (0..h).filter(|&i| on!(row_cover, i)) {
m.row_mut(i).map_inplace(|c| *c += min)
}
for j in (0..w).filter(|&j| off!(col_cover, j)) {
m.column_mut(j).map_inplace(|c| *c -= min)
}
verify = false;
continue
}
let (i, j) = uncovered.unwrap();
if let Some(j) = (0..w).find(|&j| get!(stars, i, j)) {
row_cover.insert(i);
col_cover.set(j, false);
verify = false;
continue
}
let mut path = vec![(i, j)];
loop {
let (_, j) = path[path.len() - 1];
let next_star = (0..h).find(|&i| get!(stars, i, j));
if let None = next_star { break }
let i = next_star.unwrap();
path.push((i, j));
let j = (0..w).find(|&j| get!(primes, i, j)).unwrap();
path.push((i, j));
}
for (i, j) in path {
set!(stars, i, j, *primes.uget((i, j)));
}
row_cover.clear();
col_cover.clear();
primes.map_inplace(|p| *p = false);
verify = true;
}
}
#[cfg(test)]
mod tests {
macro_rules! index {
($w:expr, $i:expr, $j:expr) => (($w*$i) + $j)
}
use minimize;
#[test]
fn test_basic_0x0() {
let matrix: Vec<i32> = Vec::new();
assert_eq!(
minimize(&matrix, 0, 0),
Vec::new()
)
}
#[test]
fn test_basic_1x1() {
let matrix = vec![1];
assert_eq!(
minimize(&matrix, 1, 1),
vec![Some(0)]
);
}
#[test]
fn test_basic_1x2() {
let matrix = vec![
1, 2
];
assert_eq!(
minimize(&matrix, 1, 2),
vec![Some(0)]
);
}
#[test]
fn test_basic_2x1() {
let matrix = vec![
1,
2
];
assert_eq!(
minimize(&matrix, 2, 1),
vec![Some(0), None]
);
}
#[test]
fn test_basic_2x2() {
let matrix = vec![
1, 2,
2, 1,
];
assert_eq!(
minimize(&matrix, 2, 2),
vec![Some(0), Some(1)]
);
}
#[test]
fn test_sales_3x3() {
let matrix = vec![
250, 400, 350,
400, 600, 350,
200, 400, 250,
];
assert_eq!(
minimize(&matrix, 3, 3),
vec![Some(1), Some(2), Some(0)]
);
}
#[test]
fn test_party_3x3() {
let matrix = vec![
108, 125, 150,
150, 135, 175,
122, 148, 250,
];
assert_eq!(
minimize(&matrix, 3, 3),
vec![Some(2), Some(1), Some(0)]
);
}
#[test]
fn test_wikipedia_4x4() {
let matrix = vec![
0, 1, 2, 3,
4, 5, 6, 0,
0, 2, 4, 5,
3, 0, 0, 9,
];
assert_eq!(
minimize(&matrix, 4, 4),
vec![Some(1), Some(3), Some(0), Some(2)]
);
}
#[test]
fn test_wikihow_5x5() {
let matrix = vec![
10, 19, 8, 15, 19,
10, 18, 7, 17, 19,
13, 16, 9, 14, 19,
12, 19, 8, 18, 19,
14, 17, 10, 19, 19
];
assert_eq!(
minimize(&matrix, 5, 5),
vec![Some(0), Some(2), Some(3), Some(4), Some(1)]
);
}
#[test]
fn test_python_5x5() {
let matrix = vec![
12, 9, 27, 10, 23,
7, 13, 13, 30, 19,
25, 18, 26, 11, 26,
9, 28, 26, 23, 13,
16, 16, 24, 6, 9,
];
assert_eq!(
51,
minimize(&matrix, 5, 5)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(5, i, j)]))
.sum::<u64>()
);
}
#[test]
fn test_python_10x10() {
let matrix = vec![
37, 34, 29, 26, 19, 8, 9, 23, 19, 29,
9, 28, 20, 8, 18, 20, 14, 33, 23, 14,
15, 26, 12, 28, 6, 17, 9, 13, 21, 7,
2, 8, 38, 36, 39, 5, 36, 2, 38, 27,
30, 3, 33, 16, 21, 39, 7, 23, 28, 36,
7, 5, 19, 22, 36, 36, 24, 19, 30, 2,
34, 20, 13, 36, 12, 33, 9, 10, 23, 5,
7, 37, 22, 39, 33, 39, 10, 3, 13, 26,
21, 25, 23, 39, 31, 37, 32, 33, 38, 1,
17, 34, 40, 10, 29, 37, 40, 3, 25, 3,
];
assert_eq!(
66,
minimize(&matrix, 10, 10)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(10, i, j)]))
.sum::<u64>()
);
}
#[test]
fn test_python_20x20() {
let matrix = vec![
5, 4, 3, 9, 8, 9, 3, 5, 6, 9, 4, 10, 3, 5, 6, 6, 1, 8, 10, 2,
10, 9, 9, 2, 8, 3, 9, 9, 10, 1, 7, 10, 8, 4, 2, 1, 4, 8, 4, 8,
10, 4, 4, 3, 1, 3, 5, 10, 6, 8, 6, 8, 4, 10, 7, 2, 4, 5, 1, 8,
2, 1, 4, 2, 3, 9, 3, 4, 7, 3, 4, 1, 3, 2, 9, 8, 6, 5, 7, 8,
3, 4, 4, 1, 4, 10, 1, 2, 6, 4, 5, 10, 2, 2, 3, 9, 10, 9, 9, 10,
1, 10, 1, 8, 1, 3, 1, 7, 1, 1, 2, 1, 2, 6, 3, 3, 4, 4, 8, 6,
1, 8, 7, 10, 10, 3, 4, 6, 1, 6, 6, 4, 9, 6, 9, 6, 4, 5, 4, 7,
8, 10, 3, 9, 4, 9, 3, 3, 4, 6, 4, 2, 6, 7, 7, 4, 4, 3, 4, 7,
1, 3, 8, 2, 6, 9, 2, 7, 4, 8, 10, 8, 10, 5, 1, 3, 10, 10, 2, 9,
2, 4, 1, 9, 2, 9, 7, 8, 2, 1, 4, 10, 5, 2, 7, 6, 5, 7, 2, 6,
4, 5, 1, 4, 2, 3, 3, 4, 1, 8, 8, 2, 6, 9, 5, 9, 6, 3, 9, 3,
3, 1, 1, 8, 6, 8, 8, 7, 9, 3, 2, 1, 8, 2, 4, 7, 3, 1, 2, 4,
5, 9, 8, 6, 10, 4, 10, 3, 4, 10, 10, 10, 1, 7, 8, 8, 7, 7, 8, 8,
1, 4, 6, 1, 6, 1, 2, 10, 5, 10, 2, 6, 2, 4, 5, 5, 3, 5, 1, 5,
5, 6, 9, 10, 6, 6, 10, 6, 4, 1, 5, 3, 9, 5, 2, 10, 9, 9, 5, 1,
10, 9, 4, 6, 9, 5, 3, 7, 10, 1, 6, 8, 1, 1, 10, 9, 5, 7, 7, 5,
2, 6, 6, 6, 6, 2, 9, 4, 7, 5, 3, 2, 10, 3, 4, 5, 10, 9, 1, 7,
5, 2, 4, 9, 8, 4, 8, 2, 4, 1, 3, 7, 6, 8, 1, 6, 8, 8, 10, 10,
9, 6, 3, 1, 8, 5, 7, 8, 7, 2, 1, 8, 2, 8, 3, 7, 4, 8, 7, 7,
8, 4, 4, 9, 7, 10, 6, 2, 1, 5, 8, 5, 1, 1, 1, 9, 1, 3, 5, 3,
];
assert_eq!(
22,
minimize(&matrix, 20, 20)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(20, i, j)]))
.sum::<u64>()
);
}
#[test]
fn test_stack_overflow_4x4_zeros() {
let matrix = vec![
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 1, 2,
0, 0, 3, 4,
];
assert_eq!(
minimize(&matrix, 4, 4),
vec![Some(3), Some(2), Some(1), Some(0)]
);
}
#[test]
fn test_stack_overflow_4x4() {
let matrix = vec![
35, 0, 0, 0,
0 , 30, 0, 5,
55, 5, 0, 10,
0 , 45, 30, 45,
];
assert_eq!(
5,
minimize(&matrix, 4, 4)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(4, i, j)]))
.sum::<u64>()
);
assert_eq!(
minimize(&matrix, 4, 4),
vec![Some(1), Some(3), Some(2), Some(0)]
);
}
#[test]
fn test_stack_overflow_5x5() {
let matrix = vec![
0, 7, 0, 0, 0,
0, 8, 0, 0, 6,
5, 0, 7, 3, 4,
5, 0, 5, 9, 3,
0, 4, 0, 0, 9,
];
assert_eq!(
3,
minimize(&matrix, 5, 5)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(5, i, j)]))
.sum::<u64>()
);
assert_eq!(
minimize(&matrix, 5, 5),
vec![Some(4), Some(2), Some(3), Some(1), Some(0)]
);
}
#[test]
fn test_stack_overflow_6x6() {
let matrix = vec![
2, 1, 0, 0, 0, 3,
2, 0, 4, 5, 2, 7,
0, 7, 0, 0, 0, 5,
3, 2, 3, 1, 2, 0,
0, 0, 6, 3, 3, 5,
3, 4, 5, 2, 0, 3,
];
assert_eq!(
minimize(&matrix, 6, 6),
vec![Some(3), Some(1), Some(2), Some(5), Some(0), Some(4)]
);
}
#[test]
fn test_stack_overflow_14x11() {
let matrix = vec![
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
53, 207, 256, 207, 231, 348, 348, 348, 231, 244, 244,
240, 33, 67, 33, 56, 133, 133, 133, 56, 33, 33,
460, 107, 200, 107, 122, 324, 324, 324, 122, 33, 33,
167, 340, 396, 340, 422, 567, 567, 567, 422, 442, 442,
167, 367, 307, 367, 433, 336, 336, 336, 433, 158, 158,
160, 20, 37, 20, 31, 70, 70, 70, 31, 22, 22,
200, 307, 393, 307, 222, 364, 364, 364, 222, 286, 286,
33 , 153, 152, 153, 228, 252, 252, 252, 228, 78, 78,
93 , 140, 185, 140, 58, 118, 118, 118, 58, 44, 44,
0 , 7, 22, 7, 19, 58, 58, 58, 19, 0, 0,
67 , 153, 241, 153, 128, 297, 297, 297, 128, 39, 39,
73 , 253, 389, 253, 253, 539, 539, 539, 253, 36, 36,
173, 267, 270, 267, 322, 352, 352, 352, 322, 231, 231,
];
assert_eq!(
828,
minimize(&matrix, 14, 11)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(11, i, j)]))
.sum::<u64>()
);
}
#[test]
fn test_rectangle_3x4() {
let matrix = vec![
400, 150, 400, 1,
400, 450, 600, 2,
300, 225, 300, 3,
];
assert_eq!(
452,
minimize(&matrix, 3, 4)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(4, i, j)]))
.sum::<u64>()
);
assert_eq!(
minimize(&matrix, 3, 4),
vec![Some(1), Some(3), Some(0)]
);
}
#[test]
fn test_rectangle_4x5() {
let matrix = vec![
82, 83, 69, 92, 100,
77, 37, 49, 92, 195,
11, 69, 5, 86, 93,
8, 9, 98, 23, 106,
];
assert_eq!(
140,
minimize(&matrix, 4, 5)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(5, i, j)]))
.sum::<u64>()
);
assert_eq!(
minimize(&matrix, 4, 5),
vec![Some(2), Some(1), Some(0), Some(3)]
);
}
#[test]
fn test_rectangle_5x4() {
let matrix = vec![
34, 26, 17, 12,
43, 43, 36, 10,
97, 47, 66, 34,
52, 42, 19, 36,
15, 93, 55, 80
];
assert_eq!(
70,
minimize(&matrix, 5, 4)
.iter()
.enumerate()
.filter_map(|(i, &v)| v.map(|j| matrix[index!(4, i, j)]))
.sum::<u64>()
);
assert_eq!(
minimize(&matrix, 5, 4),
vec![Some(1), Some(3), None, Some(2), Some(0)]
);
}
#[test]
fn test_rectangle_nx1() {
let max = 100;
for n in 1..max {
let matrix = (0..n as u64).rev().collect::<Vec<_>>();
let mut expected = vec![None; n];
expected[n - 1] = Some(0);
assert_eq!(minimize(&matrix, n, 1), expected);
}
}
#[test]
fn test_rectangle_1xn() {
let max = 100;
for n in 1..max {
let matrix = (0..n as u64).rev().collect::<Vec<_>>();
let expected = vec![Some(n - 1)];
assert_eq!(minimize(&matrix, 1, n), expected);
}
}
#[test]
fn test_stress() {
for max in 1..100 {
let mut matrix = vec![0; max * max];
let mut n: u64 = 0;
for i in 0..max {
for j in 0..max {
matrix[index!(max, i, j)] = n;
n += 1;
}
}
let expected = (0..max).map(|i| Some(i)).rev().collect::<Vec<_>>();
assert_eq!(minimize(&matrix, max, max), expected);
}
}
#[test]
fn test_worst_case() {
for max in 1..50 {
let mut matrix = vec![0; max * max];
for i in 0..max {
for j in 0..max {
matrix[index!(max, i, j)] = ((i + 1)*(j + 1)) as u64;
}
}
let expected = (0..max).map(|i| Some(i)).rev().collect::<Vec<_>>();
assert_eq!(minimize(&matrix, max, max), expected);
}
}
#[test]
fn test_large() {
let max = 1000;
let mut matrix = vec![0; max * max];
let mut n: u64 = 0;
for i in 0..max {
for j in 0..max {
matrix[index!(max, i, j)] = n;
n += 1;
}
}
let expected = (0..max).map(|i| Some(i)).rev().collect::<Vec<_>>();
assert_eq!(minimize(&matrix, max, max), expected);
}
}