summaryrefslogtreecommitdiff
path: root/einreichung/Bonusaufgabe/Quelltext
diff options
context:
space:
mode:
Diffstat (limited to 'einreichung/Bonusaufgabe/Quelltext')
-rw-r--r--einreichung/Bonusaufgabe/Quelltext/Cargo.lock115
-rw-r--r--einreichung/Bonusaufgabe/Quelltext/Cargo.toml8
-rw-r--r--einreichung/Bonusaufgabe/Quelltext/src/main.rs404
3 files changed, 527 insertions, 0 deletions
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<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(())
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-12 22:41:26 +0000