From d0c70ad88b11f412c9d8c6735b74cce1b1ff015b Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Sat, 20 Aug 2022 14:12:11 +0200 Subject: cleanup --- einreichung/Bonusaufgabe/Quelltext/Cargo.lock | 115 +++++++ einreichung/Bonusaufgabe/Quelltext/Cargo.toml | 8 + einreichung/Bonusaufgabe/Quelltext/src/main.rs | 404 +++++++++++++++++++++++++ 3 files changed, 527 insertions(+) create mode 100644 einreichung/Bonusaufgabe/Quelltext/Cargo.lock create mode 100644 einreichung/Bonusaufgabe/Quelltext/Cargo.toml create mode 100644 einreichung/Bonusaufgabe/Quelltext/src/main.rs (limited to 'einreichung/Bonusaufgabe/Quelltext') diff --git a/einreichung/Bonusaufgabe/Quelltext/Cargo.lock b/einreichung/Bonusaufgabe/Quelltext/Cargo.lock new file mode 100644 index 0000000..d5f5406 --- /dev/null +++ b/einreichung/Bonusaufgabe/Quelltext/Cargo.lock @@ -0,0 +1,115 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "bitvec" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1489fcb93a5bb47da0462ca93ad252ad6af2145cce58d10d46a83931ba9f016b" +dependencies = [ + "funty", + "radium", + "tap", + "wyz", +] + +[[package]] +name = "bonusaufgabe" +version = "0.1.0" +dependencies = [ + "bitvec", + "rand", +] + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "funty" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6d5a32815ae3f33302d95fdcb2ce17862f8c65363dcfd29360480ba1001fc9c" + +[[package]] +name = "getrandom" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d39cd93900197114fa1fcb7ae84ca742095eed9442088988ae74fa744e930e77" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "libc" +version = "0.2.121" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "efaa7b300f3b5fe8eb6bf21ce3895e1751d9665086af2d64b42f19701015ff4f" + +[[package]] +name = "ppv-lite86" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eb9f9e6e233e5c4a35559a617bf40a4ec447db2e84c20b55a6f83167b7e57872" + +[[package]] +name = "radium" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dc33ff2d4973d518d823d61aa239014831e521c75da58e3df4840d3f47749d09" + +[[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d34f1408f55294453790c48b2f1ebbb1c5b4b7563eb1f418bcfcfdbb06ebb4e7" +dependencies = [ + "getrandom", +] + +[[package]] +name = "tap" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "55937e1799185b12863d447f42597ed69d9928686b8d88a1df17376a097d8369" + +[[package]] +name = "wasi" +version = "0.10.2+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fd6fbd9a79829dd1ad0cc20627bf1ed606756a7f77edff7b66b7064f9cb327c6" + +[[package]] +name = "wyz" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30b31594f29d27036c383b53b59ed3476874d518f0efb151b27a4c275141390e" +dependencies = [ + "tap", +] diff --git a/einreichung/Bonusaufgabe/Quelltext/Cargo.toml b/einreichung/Bonusaufgabe/Quelltext/Cargo.toml new file mode 100644 index 0000000..cc415c7 --- /dev/null +++ b/einreichung/Bonusaufgabe/Quelltext/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "bonusaufgabe" +version = "0.1.0" +edition = "2021" + +[dependencies] +bitvec = "1.0.0" +rand = "0.8.5" 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, + num_pass_cards: usize, +} + +// Die Lösung enthält die von Zara stammenden echten Karten. +struct Solution { + real_cards: Vec, + // 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 { + 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::>(); + permutation.shuffle(&mut rand::thread_rng()); + + let mut permutation_pairs = permutation + .iter() + .cloned() + .enumerate() + .map(|(from, to)| (to, from)) + .collect::>(); + permutation_pairs.sort(); + + // `inverse_permutation` ist die zu `permutation` umgekehrte Permutation. + let inverse_permutation = permutation_pairs + .into_iter() + .map(|(_to, from)| from) + .collect::>(); + + // `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::::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 { + let orig_num_rows = matrix.len(); + let orig_num_cols = matrix[0].len(); + + let mut transposed = vec![BitVec::::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, +} + +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 "); + 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 { + 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::(total_num_cards_str).map_err(|_| ())?; + let num_pass_cards_str = first_line_words.next().ok_or(())?; + let num_pass_cards = str::parse::(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::() + }) + .collect::>(); + + 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(()) + } +} -- cgit 1.4.1