From 6331b2c6e9d0422c31863ba342c0abdbdb81efa7 Mon Sep 17 00:00:00 2001
From: Malte Voos <malte@malvo.org>
Date: Wed, 30 Mar 2022 17:59:01 +0200
Subject: bonusaufgabe: cleanup and comments

---
 bonusaufgabe/src/main.rs | 165 +++++++++++++++++++++++++----------------------
 1 file changed, 89 insertions(+), 76 deletions(-)

(limited to 'bonusaufgabe/src')

diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs
index 468d922..3c9255d 100644
--- a/bonusaufgabe/src/main.rs
+++ b/bonusaufgabe/src/main.rs
@@ -1,6 +1,5 @@
 use bitvec::prelude::*;
 use rand::seq::SliceRandom;
-use std::borrow::Borrow;
 use std::env;
 use std::fmt;
 use std::fs;
@@ -8,16 +7,18 @@ use std::process;
 
 type Card = BitVec;
 
+// Typ, der eine zu lösende Aufgabe beschreibt.
 struct Task {
     cards: Vec<Card>,
     num_pass_cards: usize,
 }
 
+// Die Lösung enthält die von Zara stammenden echten Karten.
 struct Solution {
     real_cards: Vec<Card>,
 }
 
-// `solve_task` löst eine gegebene Aufgabe und beinhaltet somit den
+// `solve_task` löst eine gegebene Aufgabe und beinhaltet den
 // eigentlichen Algorithmus.
 fn solve_task(task: Task) -> Solution {
     // `num_real_cards` Karten im Stapel stammen von Zara Zackig, nämlich
@@ -35,15 +36,13 @@ fn solve_task(task: Task) -> Solution {
     }
 }
 
+// Parameter für den Lee-Brickell-Algorithmus.
 const P: usize = 2;
 
 // `lee_brickell_iteration` beinhaltet eine Iteration des
 // Lee-Brickell-Algorithmus. Die Funktion liefert nur mit einer gewissen
 // Wahrscheinlichkeit eine Lösung, und gibt anderenfalls `None` zurück.
 fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solution> {
-    // Zunächst wird eine Arbeitskopie der Karten erstellt.
-    let cards = cards.to_vec();
-
     let num_cards = cards.len();
     let bits_per_card = cards[0].len();
 
@@ -76,19 +75,12 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // `ppcm` ist eine solche Kontrollmatrix (repräsentiert als Iliffe-Vektor),
     // auf dessen Spalten zusätzlich noch die Permutation `permutation`
     // angewandt wurde.
-    // let mut ppcm = transpose_and_optionally_permute_columns(&cards, Some(&permutation));
-
-    let mut ppcm  = vec![BitVec::<usize, Lsb0>::repeat(false, num_cards); bits_per_card];
-    for card_idx in 0..num_cards {
-        let new_card_idx = permutation[card_idx];
-        for bit_idx in 0..bits_per_card {
-            ppcm[bit_idx].set(new_card_idx, cards[card_idx][bit_idx]);
-        }
-    }
+    let mut ppcm = transpose_and_optionally_permute_columns(cards, Some(&permutation));
 
     // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der
-    // Basisvariablen bzw. freien Variablen. Die Indizes der Basisvariablen
-    // bilden das "information set" (siehe Dokumentation) dieser Iteration.
+    // Basisvariablen bzw. freien Variablen von `ppcm`. Die Indizes der
+    // Basisvariablen bilden das "information set" (siehe Dokumentation)
+    // dieser Iteration.
     let mut basic_vars = Vec::new();
     let mut free_vars = Vec::new();
 
@@ -116,7 +108,7 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
         // mit der derzeitigen Zeile getauscht wird.
         ppcm.swap(current_row, pivot_row);
         // Alle weiter unten liegenden Einsen dieser Spalte werden eliminiert,
-        // indem die entsprechenden Zeilen mit der derzeitigen Zeile XOR
+        // indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR
         // gerechnet (addiert) werden.
         for lower_row in (current_row + 1)..bits_per_card {
             if ppcm[lower_row][current_col] {
@@ -132,10 +124,6 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // letzte Zeile der Matrix erreicht wurde, gehören zu freien Variablen.
     free_vars.extend(current_col..num_cards);
 
-    // println!("n = {}", num_cards);
-    // println!("k = {}", free_vars.len());
-    // println!("w = {}", num_real_cards);
-
     let num_free_vars = free_vars.len();
     let num_basic_vars = basic_vars.len();
 
@@ -158,26 +146,49 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
         }
     }
 
-    // print_matrix(&ppcm);
+    // Im letzten Schritt wird versucht, aus der Kontrollmatrix `ppcm` ein
+    // Codewort mit Hamming-Gewicht `num_real_cards` zu extrahieren, indem
+    // angenommen wird, dass in der Lösung genau `p` der freien Variablen
+    // den Wert 1 haben. Ob diese Annahme stimmt, hängt davon ab, ob im ersten
+    // Schritt eine glückliche Permutation gewählt wurde.
 
+    // Bei sehr einfachen Aufgabenstellungen kann es vorkommen, das die Anzahl
+    // der freien Variablen noch kleiner als Parameter `P` des Lee-Brickell-
+    // Algorithmus ist (z.B. bei nur einer freien Variable). In diesem Fall
+    // muss der Parameter natürlich entsprechend nach unten korrigiert werden.
     let p = P.min(num_free_vars);
+
+    // Zunächst wird die Matrix transponiert, damit die Bits der Spalten
+    // jeweils zusammenhängend im Speicher liegen und somit die Spalten
+    // schneller miteinander XOR gerechnet werden können.
     let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None);
 
+    // Um die `p` freien Variablen mit dem Wert 1 zu finden, wird über alle
+    // möglichen `p`-Untermengen der freien Variablen iteriert und jeweils
+    // angenommen, dass von den freien Variablen nur die in der Untermenge den
+    // Wert 1 haben.
     let mut subset_iter = SubsetIterator::new(num_free_vars, p);
     while let Some(subset) = subset_iter.next() {
-        // println!("---");
-        // println!("subset: {:?}", subset);
-
+        // Zunächst wird das exklusive Oder der `p` Spalten in der Untermenge
+        // errechnet. Aus der Struktur der reduzierten Stufenform folgt, dass
+        // in jeder Zeile, in der `subset_xor` den Wert 1 hat, auch die
+        // Basisvariable dieser Zeile den Wert 1 haben muss, damit die Zeile
+        // insgesamt den Wert 0 hat (es handelt sich um eine Zeile der
+        // Kontrollmatrix!)
         let mut subset_xor = BitVec::<usize, Lsb0>::repeat(false, bits_per_card);
         for free_var_idx in subset {
             subset_xor ^= &transposed_ppcm[free_vars[*free_var_idx]];
         }
 
-        // println!("subset_xor: {:?}", subset_xor);
-
+        // Damit insgesamt `num_real_cards` Elemente des Lösungsvektors den
+        // Wert 1 haben, müssen genau `num_real_cards - p` Basisvariablen den
+        // Wert 1 haben, da oben angenommen wurde, dass von den freien
+        // Variablen genau `p` den Wert 1 haben.
         if subset_xor.count_ones() == num_real_cards - p {
-            // println!("found it");
-
+            // Ist dies der Fall, ist die Lösung gefunden. Die echten Karten
+            // werden in `real_cards` gesammelt. Dabei wird die
+            // Spaltenpermutation mittels `inverse_permutation` rückgängig
+            // gemacht.
             let mut real_cards = Vec::new();
             for free_var_idx in subset {
                 real_cards.push(cards[inverse_permutation[free_vars[*free_var_idx]]].clone());
@@ -185,43 +196,27 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
             for basic_var_row in subset_xor.iter_ones() {
                 real_cards.push(cards[inverse_permutation[basic_vars[basic_var_row]]].clone());
             }
+            // Der Benutzerfreundlichkeit gegenüber Zara halber werden die
+            // echten Karten vor der Ausgabe aufsteigend sortiert.
             real_cards.sort();
 
             return Some(Solution { real_cards });
         }
     }
 
+    // Von den freien Variablen hatten nicht genau `p` den Wert 1. Die
+    // Iteration ist fehlgeschlagen, und in der nächten Iteration wird eine
+    // andere Spaltenpermutation und somit auch eine andere Auswahl freier
+    // Variablen probiert.
     None
-
-    // let free_one = *free_vars
-    //     .iter()
-    //     .find(|free_var| ppcm.iter().filter(|row| row[**free_var]).count() == num_real_cards - 1)?;
-    // let original_free_one = inverse_permutation[free_one];
-
-    // let original_basic_ones =
-    //     ppcm.iter()
-    //         .map(|row| row[free_one])
-    //         .enumerate()
-    //         .filter_map(|(row_idx, val)| {
-    //             if val {
-    //                 Some(inverse_permutation[basic_vars[row_idx]])
-    //             } else {
-    //                 None
-    //             }
-    //         });
-
-    // let mut real_cards = Vec::new();
-    // real_cards.push(cards[original_free_one].clone());
-    // for original_basic_one in original_basic_ones {
-    //     real_cards.push(cards[original_basic_one].clone());
-    // }
-    // real_cards.sort();
-
-    // Some(Solution { real_cards })
 }
 
+// Diese Funktion transponiert eine Bit-Matrix und wendet anschließend, falls
+// gefordert, auf die transponierte Matrix die gegebene Spaltenpermutation an.
+// Durch die Vereinigung dieser beiden Operationen kann unnötiges Herumkopieren
+// von Bits vermieden werden.
 fn transpose_and_optionally_permute_columns(
-    matrix: &Vec<BitVec>,
+    matrix: &[BitVec],
     permutation: Option<&[usize]>,
 ) -> Vec<BitVec> {
     let orig_num_rows = matrix.len();
@@ -241,11 +236,14 @@ fn transpose_and_optionally_permute_columns(
     transposed
 }
 
+// Iterator, der über alle "n über k" k-Untermengen einer Menge von n Elementen
+// iteriert. Die Elemente der Menge sind die natürlichen Zahlen von 0 bis n-1.
+// Die Untermengen werden durch ein aufsteigend sortiertes Array repräsentiert.
 struct SubsetIterator {
     n: usize,
     k: usize,
     fresh: bool,
-    state: Vec<usize>,
+    subset: Vec<usize>,
 }
 
 impl SubsetIterator {
@@ -254,48 +252,61 @@ impl SubsetIterator {
             n,
             k,
             fresh: true,
-            state: (0..k).into_iter().collect(),
+            // Zu Anfang enthält die Untermenge die niedrigsten k Zahlen.
+            subset: (0..k).into_iter().collect(),
         }
     }
 
     fn next(&mut self) -> Option<&[usize]> {
+        // Falls dies die erste Iteration ist, geben wir einfach die in "new()"
+        // (s.o.) definierte Anfangs-Untermenge zurück.
         if self.fresh {
             self.fresh = false;
-            Some(&self.state)
+            Some(&self.subset)
         } else {
+            // `last_index` ist der Index des letzten Elements der Untermenge.
             let last_index = self.k - 1;
+            // `index_to_increase` ist der Index des Elements der Untermenge,
+            // das durch die nächstgrößere Zahl ersetzt wird.
+            // Wir durchsuchen die Untermenge von links nach rechts nach einem
+            // erhöhbaren Element, sodass immer das niedrigste Element zuerst
+            // erhöht wird.
             let index_to_increase = self
-                .state
+                .subset
                 .iter()
                 .enumerate()
                 .find(|(index, val)| {
                     if *index == last_index {
-                        self.state[*index] != self.n - 1
+                        // Falls dies das letzte Element der Untermenge ist,
+                        // kann es nurnoch erhöht werden, wenn die
+                        // nächtsgrößere Zahl noch Teil der Gesamtmenge ist.
+                        self.subset[*index] != self.n - 1
                     } else {
-                        self.state[*index + 1] != **val + 1
+                        // Ansonsten kann das Element erhöht werden, wenn die
+                        // nächstgrößere Zahl nicht schon durch ein anderes
+                        // Element in der Untermenge repräsentiert ist.
+                        self.subset[*index + 1] != **val + 1
                     }
-                })?
+                })? // das '?' gibt sofort `None` zurück, wenn kein erhöhbares
+                // Element gefunden wurde und somit schon über alle Untermengen
+                // iteriert wurde.
                 .0;
 
-            self.state[index_to_increase] += 1;
+            // Das im vorherigen Schritt gefundene Element wird um 1 erhöht,
+            // und alle kleineren Elemente werden analog zum "normalen Zählen"
+            // auf die kleinstmöglichen Werte gesetzt.
+            self.subset[index_to_increase] += 1;
             for lower_idx in 0..index_to_increase {
-                self.state[lower_idx] = lower_idx;
+                self.subset[lower_idx] = lower_idx;
             }
 
-            Some(&self.state)
-        }
-    }
-}
-
-fn print_matrix(matrix: &Vec<BitVec>) {
-    for row in matrix {
-        for bit in row {
-            print!("{}", if *bit { "1" } else { "0" });
+            // Die neu errechnete Untermenge wird zurückgegeben.
+            Some(&self.subset)
         }
-        println!();
     }
 }
 
+// Einstiegspunkt für das Programm.
 fn main() {
     let task_file_name = match env::args().nth(1) {
         Some(x) => x,
@@ -311,6 +322,7 @@ fn main() {
     print!("{}", solution);
 }
 
+// Liest eine Aufgabe im Format der Beispielaufgaben ein.
 impl TryFrom<&str> for Task {
     type Error = ();
 
@@ -348,6 +360,7 @@ impl TryFrom<&str> for Task {
     }
 }
 
+// Formatiert die Lösung zur Ausgabe.
 impl fmt::Display for Solution {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         for card in self.real_cards.iter() {
@@ -357,7 +370,7 @@ impl fmt::Display for Solution {
                     false => write!(f, "0")?,
                 };
             }
-            writeln!(f, "")?;
+            writeln!(f)?;
         }
         Ok(())
     }
-- 
cgit 1.4.1