fix: improve minimization algorithm

1 files changed, 39 insertions, 5 deletions

diff --git a/src/main.rs b/src/main.rs
index 0577814..a1ee3c1 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -150,7 +150,10 @@ fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -
         for (a, b) in implicants.iter().sorted().tuple_combinations() {
             let a_set = &covered_by_implicants[a];
             let b_set = &covered_by_implicants[b];
-            let eq = a_set == b_set;
+
+            let a_is_subset = a_set.difference(b_set).count() == 0;
+            let b_is_subset = b_set.difference(a_set).count() == 0;
+            let eq = a_is_subset && b_is_subset;
 
             let a_cost = prime_implicants[*a].cost();
             let b_cost = prime_implicants[*b].cost();
@@ -161,6 +164,12 @@ fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -
             } else if eq {
                 implicants_to_remove[*b] = true;
                 removed = true;
+            } else if a_is_subset && a_cost >= b_cost {
+                implicants_to_remove[*a] = true;
+                removed = true;
+            } else if b_is_subset && b_cost >= a_cost {
+                implicants_to_remove[*b] = true;
+                removed = true;
             }
         }
 
@@ -173,9 +182,35 @@ fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -
             table = new_table;
         } else {
             // We can't remove implicants by cost, have to choose by ourselves.
-            // NOTE: this leads to non-minimal solution
-            // NOTE: this SHOULD NOT happen, as we are filtering equal implicant costs too
-            todo!()
+            // NOTE: this can lead to non-minimal solution!!!!!!!!!
+            // NOTE: this happens when there's no essential implicants
+
+            // Calculating minterm coverage
+            let mut minterms_freq = vec![0; minterms.len()];
+            table.iter().for_each(|&(_, j)| minterms_freq[j] += 1);
+
+            // Searching minterm that has the least coverage
+            let costless_minterm = minterms_freq
+                .into_iter()
+                .enumerate()
+                .filter(|&(_, v)| v >= 2)
+                .min_by_key(|&(_, v)| v)
+                .map(|(i, _)| i)
+                .unwrap();
+
+            // Selecting first implicant that contains this minterm
+            let selected_implicant = (0..prime_implicants.len())
+                .find(|&i| table.contains(&(i, costless_minterm)))
+                .unwrap();
+            selected_implicants[selected_implicant] = true;
+
+            // Updating table to remove this implicant from calculation
+            let new_table: HashSet<_> = table
+                .iter()
+                .filter(|&&(i, _)| i != selected_implicant)
+                .cloned()
+                .collect();
+            table = new_table;
         }
     }
 
@@ -190,7 +225,6 @@ fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -
 
 fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
     let prime_implicants = minimize_prime_implicants(n, minterms, maxterms);
-    // print_prime_implicants_table(n, minterms, &prime_implicants);
     solve_prime_implicants_table(minterms, &prime_implicants)
 }