diff options
Diffstat (limited to 'bonusaufgabe/src/main.rs')
| -rw-r--r-- | bonusaufgabe/src/main.rs | 426 |
1 files changed, 243 insertions, 183 deletions
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")?, }; |