diff options
Diffstat (limited to 'einreichung/Bonusaufgabe/Quelltext/src/main.rs')
| -rw-r--r-- | einreichung/Bonusaufgabe/Quelltext/src/main.rs | 404 |
1 files changed, 404 insertions, 0 deletions
diff --git a/einreichung/Bonusaufgabe/Quelltext/src/main.rs b/einreichung/Bonusaufgabe/Quelltext/src/main.rs new file mode 100644 index 0000000..2ec4756 --- /dev/null +++ b/einreichung/Bonusaufgabe/Quelltext/src/main.rs @@ -0,0 +1,404 @@ +use bitvec::prelude::*; +use rand::seq::SliceRandom; +use std::env; +use std::fmt; +use std::fs; +use std::process; +use std::time; + +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>, + // Der Anschaulichkeit halber werden ein paar weitere Randinformationen + // mit ausgegeben. + num_cards: usize, + num_real_cards: usize, + bits_per_card: usize, + num_free_vars: usize, + p: usize, +} + +// `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 + // die `num_pass_cards` Öffnungskarten plus eine Sicherungkarte. + let num_real_cards = task.num_pass_cards + 1; + + // Der Lee-Brickell-Algorithmus erzeugt nur mit einer gewissen + // Wahrscheinlichkeit eine Lösung. Daher führen wir ihn wiederholt aus, + // bis eine Lösung gefunden wurde. + loop { + match lee_brickell_iteration(&task.cards, num_real_cards) { + None => continue, + Some(solution) => break 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> { + let num_cards = cards.len(); + let bits_per_card = cards[0].len(); + + // `permutation` ist eine zufällige Permutation der Karten, repräsentiert + // durch ein Array, in dem jeder Index in `cards` einmal vorkommt. + let mut permutation = (0..num_cards).into_iter().collect::<Vec<usize>>(); + permutation.shuffle(&mut rand::thread_rng()); + + let mut permutation_pairs = permutation + .iter() + .cloned() + .enumerate() + .map(|(from, to)| (to, from)) + .collect::<Vec<(usize, usize)>>(); + permutation_pairs.sort(); + + // `inverse_permutation` ist die zu `permutation` umgekehrte Permutation. + let inverse_permutation = permutation_pairs + .into_iter() + .map(|(_to, from)| from) + .collect::<Vec<usize>>(); + + // `ppcm` steht für "permuted parity-check matrix". Wie in der + // Dokumentation beschrieben, ist die Matrix, welche die gegebenen Karten + // als ihre Spalten enthält, Kontrollmatrix eines linearen Codes über den + // endlichen Körper GF(2). Die Codewörter dieses Codes repräsentieren + // jeweils eine Auswahl von Karten, die XOR einander null ergeben. Die + // Lösung des Problems ist gegeben durch ein Codewort dieses Codes mit + // Hamming-Gewicht `num_real_cards`. + // `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)); + + // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der + // Basisvariablen bzw. freien Variablen von `ppcm`. + let mut basic_vars = Vec::new(); + let mut free_vars = Vec::new(); + + // Zunächst wird `ppcm` mittels des Gaußschen Eliminierungsverfahrens + // in die reduzierte Stufenform gebracht. + let mut current_row = 0; + let mut current_col = 0; + while current_row < bits_per_card && current_col < num_cards { + // Wir suchen in der derzeitigen Spalte ein Pivotelement (eine 1). + let pivot_row = match (current_row..bits_per_card).find(|row| ppcm[*row][current_col]) { + Some(row) => row, + None => { + // Wurde kein Pivotelement gefunden, gehört diese Spalte zu + // einer freien Variable, und es kann zur nächsten Spalte + // übergegangen werden. + free_vars.push(current_col); + current_col += 1; + continue; + } + }; + // Wurde ein Pivotelement gefunden, gehört die Spalte zu einer + // Basisvariable. + basic_vars.push(current_col); + // Die Zeile mit dem Pivotelement wird nach oben gebracht, indem sie + // 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 Zeile des Pivotelements XOR + // gerechnet (addiert) werden. + for lower_row in (current_row + 1)..bits_per_card { + if ppcm[lower_row][current_col] { + let current_row_cloned = ppcm[current_row].clone(); + ppcm[lower_row] ^= current_row_cloned; + } + } + // Es kann zur nächsten Zeile und Spalte übergegangen werden. + current_row += 1; + current_col += 1; + } + // Übrig gebliebene Spalten, die nicht mehr betrachtet wurden, da die + // letzte Zeile der Matrix erreicht wurde, gehören zu freien Variablen. + free_vars.extend(current_col..num_cards); + + let num_free_vars = free_vars.len(); + let num_basic_vars = basic_vars.len(); + + // Sanity Check: Nach dem Rangsatz immer erfüllt + assert_eq!(num_basic_vars + num_free_vars, num_cards); + + // Hier ist `ppcm` in Stufenform. + + // Um die reduzierte Stufenform zu erreichen, wird noch einmal rückwärts + // über die Spalten mit Pivotelement iteriert. Die weiter oben liegenden + // Einsen werden eliminiert, indem die entsprechenden Zeilen mit der Zeile + // des Pivotelements XOR gerechnet (addiert) werden. Diese Erweiterung + // wird auch als Gauß-Jordan-Algorithmus bezeichnet. + for (pivot_row, pivot_col) in basic_vars.iter().enumerate().rev() { + for upper_row in 0..pivot_row { + if ppcm[upper_row][*pivot_col] { + let pivot_row_cloned = ppcm[pivot_row].clone(); + ppcm[upper_row] ^= pivot_row_cloned; + } + } + } + + // 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. + + // In einigen Fällen muss der Parameter `P` des Lee-Brickell-Algorithmus + // an die Eingabe angepasst werden, z.B. bei sehr leicht lösbaren Aufgaben + // mit nur einer freien Variable. Details sind in der Dokumentation, + // Abschnitt 1.2, Schritt 4 zu finden. + let p = ((P as isize).clamp( + -(num_cards as isize) + num_free_vars as isize + num_real_cards as isize, + num_real_cards.min(num_free_vars) as isize, + )) as usize; + + // 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() { + // 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]]; + } + + // 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 { + // 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()); + } + 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, + num_cards, + num_real_cards, + bits_per_card, + num_free_vars, + p, + }); + } + } + + // Von den freien Variablen hatten nicht genau `p` den Wert 1. Diese + // Iteration ist fehlgeschlagen, und in der nächten Iteration wird eine + // andere Spaltenpermutation und somit auch eine andere Auswahl freier + // Variablen probiert. + None +} + +// 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: &[BitVec], + permutation: Option<&[usize]>, +) -> Vec<BitVec> { + let orig_num_rows = matrix.len(); + let orig_num_cols = matrix[0].len(); + + let mut transposed = vec![BitVec::<usize, Lsb0>::repeat(false, orig_num_rows); orig_num_cols]; + for orig_row_idx in 0..orig_num_rows { + let new_col_idx = match permutation { + Some(permutation) => permutation[orig_row_idx], + None => orig_row_idx, + }; + for orig_col_idx in 0..orig_num_cols { + let new_row_idx = orig_col_idx; + transposed[new_row_idx].set(new_col_idx, matrix[orig_row_idx][orig_col_idx]); + } + } + 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, + subset: Vec<usize>, +} + +impl SubsetIterator { + fn new(n: usize, k: usize) -> Self { + Self { + n, + k, + fresh: true, + // 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.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 + .subset + .iter() + .enumerate() + .find(|(index, val)| { + if *index == last_index { + // 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 { + // 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; + + // 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.subset[lower_idx] = lower_idx; + } + + // Die neu errechnete Untermenge wird zurückgegeben. + Some(&self.subset) + } + } +} + +// Einstiegspunkt für das Programm. +fn main() { + let task_file_name = match env::args().nth(1) { + Some(x) => x, + None => { + eprintln!("Nutzung: bonusaufgabe <dateiname>"); + process::exit(1); + } + }; + let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden"); + let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe"); + + let start = time::Instant::now(); + let solution = solve_task(&task); + let elapsed = start.elapsed(); + + println!("{}", solution); + println!("Laufzeit ohne I/O: {:?}", elapsed); +} + +// Liest eine Aufgabe im Format der Beispielaufgaben ein. +impl TryFrom<&str> for Task { + type Error = (); + + fn try_from(value: &str) -> Result<Self, Self::Error> { + let mut lines = value.lines(); + let first_line = lines.next().ok_or(())?; + let mut first_line_words = first_line.split_ascii_whitespace(); + + let total_num_cards_str = first_line_words.next().ok_or(())?; + let total_num_cards = str::parse::<usize>(total_num_cards_str).map_err(|_| ())?; + let num_pass_cards_str = first_line_words.next().ok_or(())?; + let num_pass_cards = str::parse::<usize>(num_pass_cards_str).map_err(|_| ())?; + + let cards = lines + .into_iter() + .map(|line| { + line.chars() + .flat_map(|char| match char { + '0' => Some(false), + '1' => Some(true), + _ => None, + }) + .collect::<Card>() + }) + .collect::<Vec<Card>>(); + + if cards.len() != total_num_cards { + return Err(()); + } + + Ok(Task { + cards, + num_pass_cards, + }) + } +} + +// Formatiert die Lösung zur Ausgabe. +impl fmt::Display for Solution { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + writeln!( + f, + "Randinformationen (siehe Dokumentation):\nn = {}; w = {}; b = {}; k = {}; p = {}", + self.num_cards, self.num_real_cards, self.bits_per_card, self.num_free_vars, self.p + )?; + writeln!(f)?; + writeln!(f, "Echte Karten:")?; + for card in self.real_cards.iter() { + for bit in card.iter() { + match *bit { + true => write!(f, "1")?, + false => write!(f, "0")?, + }; + } + writeln!(f)?; + } + Ok(()) + } +} |