diff options
Diffstat (limited to 'bonusaufgabe/src')
| -rw-r--r-- | bonusaufgabe/src/main.rs | 304 |
1 files changed, 304 insertions, 0 deletions
diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs new file mode 100644 index 0000000..f3a0301 --- /dev/null +++ b/bonusaufgabe/src/main.rs @@ -0,0 +1,304 @@ +use bitvec::prelude::*; +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>); + +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; + let num_cards = cards.len(); + let num_real_cards = num_pass_cards + 1; + + 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); + } + } + + let mut free_vars = Vec::new(); + let mut basic_vars = Vec::new(); + + 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]) { + Some(row) => row, + None => { + free_vars.push(current_col); + current_col += 1; + continue; + } + }; + matrix.swap(current_row, pivot_row); + basic_vars.push((current_row, current_col)); + 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; + } + } + current_row += 1; + current_col += 1; + } + free_vars.extend(current_col..num_cards); + + let num_basic_vars = basic_vars.len(); + let num_free_vars = free_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; + } + } + } + + print_matrix(&matrix); + + 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; + } + } + } + + solution +} + +struct BitSubsetIterator { + fresh: bool, + state: BitVec<usize, Lsb0>, +} + +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); + + Self { + fresh: true, + state: initial_state, + } + } + + fn next(&mut self) -> Option<&BitSlice> { + if self.fresh { + self.fresh = false; + Some(self.state.borrow()) + } else { + self.state + .iter_ones() + .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() + }) + } + } +} + +fn print_matrix(matrix: &[BitVec]) { + for row in matrix { + for col in row { + if *col { + print!("1"); + } else { + print!("0"); + } + } + println!(""); + } +} + +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 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>>(), + ) + }) + .collect::<Vec<Card>>(); + + if cards.len() != total_num_cards { + return Err(()); + } + + Ok(Task { + cards, + num_pass_cards, + bits_per_card, + }) + } +} + +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 { + true => write!(f, "1")?, + false => write!(f, "0")?, + }; + } + writeln!(f, "")?; + } + Ok(()) + } +} |