path: root/bonusaufgabe/src/main.rs

use bitvec::prelude::*;
use rand::seq::SliceRandom;
use std::borrow::Borrow;
use std::env;
use std::fmt;
use std::fs;
use std::process;

type Card = BitVec;

struct Task {
    cards: Vec<Card>,
    num_pass_cards: usize,
}

struct Solution {
    real_cards: Vec<Card>,
}

// `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 bits_per_card = cards[0].len();

    // `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]);
        }
    }

    // `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 {
        // 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;
            }
        };
        // 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 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);

    // 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);

    // 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(&ppcm);

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

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

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
}

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: (0..k).into_iter().collect(),
        }
    }

    fn next(&mut self) -> Option<&[usize]> {
        if self.fresh {
            self.fresh = false;
            Some(&self.state)
        } else {
            let last_index = self.k - 1;
            let index_to_increase = self
                .state
                .iter()
                .enumerate()
                .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: &Vec<BitVec>) {
    for row in matrix {
        for bit in row {
            print!("{}", if *bit { "1" } else { "0" });
        }
        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 = ();

    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 cards = lines
            .into_iter()
            .map(|line| {
                line.chars()
                    .flat_map(|char| match char {
                        '0' => Some(false),
                        '1' => Some(true),
                        _ => None,
                    })
                    .collect::<BitVec>()
            })
            .collect::<Vec<Card>>();

        if cards.len() != total_num_cards {
            return Err(());
        }

        Ok(Task {
            cards,
            num_pass_cards,
        })
    }
}

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.iter() {
                match *bit {
                    true => write!(f, "1")?,
                    false => write!(f, "0")?,
                };
            }
            writeln!(f, "")?;
        }
        Ok(())
    }
}