summaryrefslogtreecommitdiff
path: root/bonusaufgabe/src
diff options
context:
space:
mode:
Diffstat (limited to 'bonusaufgabe/src')
-rw-r--r--bonusaufgabe/src/main.rs165
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(())
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-21 17:40:57 +0000