path: root/bonusaufgabe/src/main.rs

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(())
    }
}