diff options
author | Malte Voos <malte@malvo.org> | 2022-03-30 17:59:01 +0200 |
---|---|---|
committer | Malte Voos <malte@malvo.org> | 2022-03-30 17:59:01 +0200 |
commit | 6331b2c6e9d0422c31863ba342c0abdbdb81efa7 (patch) | |
tree | 1635a1786758918606a5ac41adeb6915d6d62919 /bonusaufgabe/src/main.rs | |
parent | eb86c31d74598a6ccf8d70a85695b4450622f351 (diff) | |
download | bwinf402-6331b2c6e9d0422c31863ba342c0abdbdb81efa7.tar.gz bwinf402-6331b2c6e9d0422c31863ba342c0abdbdb81efa7.zip |
bonusaufgabe: cleanup and comments
Diffstat (limited to 'bonusaufgabe/src/main.rs')
-rw-r--r-- | bonusaufgabe/src/main.rs | 165 |
1 files changed, 89 insertions, 76 deletions
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(()) } |