summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bonusaufgabe/Cargo.lock66
-rw-r--r--bonusaufgabe/Cargo.toml3
-rw-r--r--bonusaufgabe/src/main.rs426
3 files changed, 310 insertions, 185 deletions
diff --git a/bonusaufgabe/Cargo.lock b/bonusaufgabe/Cargo.lock
index 1577f2b..d5f5406 100644
--- a/bonusaufgabe/Cargo.lock
+++ b/bonusaufgabe/Cargo.lock
@@ -19,27 +19,93 @@ 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"
diff --git a/bonusaufgabe/Cargo.toml b/bonusaufgabe/Cargo.toml
index dc82037..cc415c7 100644
--- a/bonusaufgabe/Cargo.toml
+++ b/bonusaufgabe/Cargo.toml
@@ -5,5 +5,4 @@ edition = "2021"
[dependencies]
bitvec = "1.0.0"
-
-[features]
+rand = "0.8.5"
diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs
index f3a0301..468d922 100644
--- a/bonusaufgabe/src/main.rs
+++ b/bonusaufgabe/src/main.rs
@@ -1,251 +1,316 @@
use bitvec::prelude::*;
+use rand::seq::SliceRandom;
use std::borrow::Borrow;
use std::env;
use std::fmt;
use std::fs;
-use std::marker::PhantomData;
-use std::mem;
-use std::ops::BitXor;
-use std::path::Display;
use std::process;
-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");
-
- match solve_task(task) {
- Some(solution) => println!("{}", solution),
- None => eprintln!("Keine Lösung gefunden"),
- }
-}
-
-#[derive(Clone)]
-struct Card(Vec<bool>);
+type Card = BitVec;
struct Task {
cards: Vec<Card>,
num_pass_cards: usize,
- bits_per_card: usize,
}
struct Solution {
real_cards: Vec<Card>,
}
-fn solve_task(task: Task) -> Option<Solution> {
- let Task {
- cards,
- num_pass_cards,
- bits_per_card,
- } = task;
+// `solve_task` löst eine gegebene Aufgabe und beinhaltet somit 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,
+ }
+ }
+}
+
+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 num_real_cards = num_pass_cards + 1;
+ let bits_per_card = cards[0].len();
- let mut matrix: Vec<BitVec> = vec![BitVec::with_capacity(num_cards); bits_per_card];
- for card in cards.iter() {
- for (bit_idx, bit) in card.0.iter().enumerate() {
- matrix[bit_idx].push(*bit);
+ // `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));
+
+ 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 free_vars = Vec::new();
+ // `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.
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 {
- let pivot_row = match (current_row..bits_per_card).find(|row| matrix[*row][current_col]) {
+ // 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;
}
};
- matrix.swap(current_row, pivot_row);
- basic_vars.push((current_row, current_col));
+ // 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 derzeitigen Zeile XOR
+ // gerechnet (addiert) werden.
for lower_row in (current_row + 1)..bits_per_card {
- if matrix[lower_row][current_col] {
- let current_row_cloned = matrix[current_row].clone();
- matrix[lower_row] ^= current_row_cloned;
+ 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_basic_vars = basic_vars.len();
+ // 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();
// Sanity Check: Nach dem Rangsatz immer erfüllt
assert_eq!(num_basic_vars + num_free_vars, num_cards);
- for (pivot_row, pivot_col) in basic_vars.iter().rev() {
- for upper_row in (0..*pivot_row).rev() {
- if matrix[upper_row][*pivot_col] {
- let pivot_row_cloned = matrix[*pivot_row].clone();
- matrix[upper_row] ^= pivot_row_cloned;
+ // 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;
}
}
}
- print_matrix(&matrix);
+ // print_matrix(&ppcm);
- let basic_vars_terms = basic_vars
- .iter()
- .map(|(basic_var_row, _basic_var_col)| {
- free_vars
- .iter()
- .map(|free_var| matrix[*basic_var_row][*free_var])
- .collect::<BitVec>()
- })
- .collect::<Vec<BitVec>>();
-
- println!("num_real_cards {}", num_real_cards);
- println!("num_cards {}", num_cards);
- println!("num_free_vars {}", num_free_vars);
- println!("num_basic_vars {}", num_basic_vars);
-
- // std::process::exit(0);
-
- let mut solution = None;
-
- 'outer: for num_ones_in_free_vars in 0..=(num_free_vars.min(num_real_cards)) {
- let mut iterator = BitSubsetIterator::new(num_free_vars, num_ones_in_free_vars);
- while let Some(free_var_values) = iterator.next() {
- // print!("trying ");
- // for b in free_var_values {
- // if *b {
- // print!("1");
- // } else {
- // print!("0");
- // }
- // }
- // println!("");
-
- let basic_var_values = basic_vars_terms
- .iter()
- .map(|basic_var_term| {
- let basic_var_solution_term = basic_var_term.clone() & free_var_values;
- let basic_var_solution = basic_var_solution_term
- .iter()
- .fold(false, |acc, bit| acc ^ *bit);
- basic_var_solution
- })
- .collect::<BitVec>();
- let num_ones_in_basic_vars = basic_var_values
- .iter()
- .filter(|solution_bit| **solution_bit)
- .count();
- let num_ones_in_solution = num_ones_in_free_vars + num_ones_in_basic_vars;
-
- if num_ones_in_solution == num_real_cards {
- let mut solution_vector = BitVec::<usize, Lsb0>::repeat(false, num_cards);
-
- for (free_var_idx, free_var_val) in free_vars.iter().zip(free_var_values.iter()) {
- solution_vector.set(*free_var_idx, *free_var_val);
- }
- for ((_, basic_var_idx), basic_var_val) in
- basic_vars.iter().zip(basic_var_values.iter())
- {
- solution_vector.set(*basic_var_idx, *basic_var_val);
- }
-
- assert_eq!(solution_vector.count_ones(), num_real_cards);
- //TODO: more sanity checks
-
- print!("solution free vars ");
- for b in free_var_values {
- if *b {
- print!("1");
- } else {
- print!("0");
- }
- }
- println!("");
-
- solution = Some(Solution {
- real_cards: solution_vector
- .into_iter()
- .enumerate()
- .filter(|(_card_idx, is_real)| *is_real)
- .map(|(real_card_idx, _)| (cards[real_card_idx]).clone())
- .collect(),
- });
-
- break 'outer;
+ let p = P.min(num_free_vars);
+ let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None);
+
+ let mut subset_iter = SubsetIterator::new(num_free_vars, p);
+ while let Some(subset) = subset_iter.next() {
+ // println!("---");
+ // println!("subset: {:?}", subset);
+
+ 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);
+
+ if subset_xor.count_ones() == num_real_cards - p {
+ // println!("found it");
+
+ 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());
}
+ real_cards.sort();
+
+ return Some(Solution { real_cards });
}
}
- solution
+ 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 })
}
-struct BitSubsetIterator {
- fresh: bool,
- state: BitVec<usize, Lsb0>,
+fn transpose_and_optionally_permute_columns(
+ matrix: &Vec<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
}
-impl BitSubsetIterator {
- fn new(set_size: usize, subset_size: usize) -> Self {
- let mut initial_state = BitVec::repeat(false, set_size);
- initial_state.get_mut(0..subset_size).unwrap().fill(true);
+struct SubsetIterator {
+ n: usize,
+ k: usize,
+ fresh: bool,
+ state: Vec<usize>,
+}
+impl SubsetIterator {
+ fn new(n: usize, k: usize) -> Self {
Self {
+ n,
+ k,
fresh: true,
- state: initial_state,
+ state: (0..k).into_iter().collect(),
}
}
- fn next(&mut self) -> Option<&BitSlice> {
+ fn next(&mut self) -> Option<&[usize]> {
if self.fresh {
self.fresh = false;
- Some(self.state.borrow())
+ Some(&self.state)
} else {
- self.state
- .iter_ones()
+ let last_index = self.k - 1;
+ let index_to_increase = self
+ .state
+ .iter()
.enumerate()
- .find(
- |(_num_prev_ones, one_idx)| match self.state.get(*one_idx + 1) {
- Some(bit) => !bit,
- None => false,
- },
- )
- .map(|(num_prev_ones, moveable_one_idx)| {
- self.state.set(moveable_one_idx, false);
- self.state.set(moveable_one_idx + 1, true);
- self.state.get_mut(0..num_prev_ones).unwrap().fill(true);
- self.state
- .get_mut(num_prev_ones..moveable_one_idx)
- .unwrap()
- .fill(false);
- self.state.borrow()
- })
+ .find(|(index, val)| {
+ if *index == last_index {
+ self.state[*index] != self.n - 1
+ } else {
+ self.state[*index + 1] != **val + 1
+ }
+ })?
+ .0;
+
+ self.state[index_to_increase] += 1;
+ for lower_idx in 0..index_to_increase {
+ self.state[lower_idx] = lower_idx;
+ }
+
+ Some(&self.state)
}
}
}
-fn print_matrix(matrix: &[BitVec]) {
+fn print_matrix(matrix: &Vec<BitVec>) {
for row in matrix {
- for col in row {
- if *col {
- print!("1");
- } else {
- print!("0");
- }
+ for bit in row {
+ print!("{}", if *bit { "1" } else { "0" });
}
- println!("");
+ println!();
}
}
+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 solution = solve_task(task);
+ print!("{}", solution);
+}
+
impl TryFrom<&str> for Task {
type Error = ();
@@ -258,21 +323,17 @@ impl TryFrom<&str> for Task {
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 bits_per_card_str = first_line_words.next().ok_or(())?;
- let bits_per_card = str::parse::<usize>(bits_per_card_str).map_err(|_| ())?;
let cards = lines
.into_iter()
.map(|line| {
- Card(
- line.chars()
- .flat_map(|char| match char {
- '0' => Some(false),
- '1' => Some(true),
- _ => None,
- })
- .collect::<Vec<bool>>(),
- )
+ line.chars()
+ .flat_map(|char| match char {
+ '0' => Some(false),
+ '1' => Some(true),
+ _ => None,
+ })
+ .collect::<BitVec>()
})
.collect::<Vec<Card>>();
@@ -283,7 +344,6 @@ impl TryFrom<&str> for Task {
Ok(Task {
cards,
num_pass_cards,
- bits_per_card,
})
}
}
@@ -291,8 +351,8 @@ impl TryFrom<&str> for Task {
impl fmt::Display for Solution {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for card in self.real_cards.iter() {
- for bit in card.0.iter() {
- match bit {
+ for bit in card.iter() {
+ match *bit {
true => write!(f, "1")?,
false => write!(f, "0")?,
};
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-21 12:54:02 +0000