path: root/einreichung/Bonusaufgabe/Quelltext/src/main.rs

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

type Card = BitVec;

// Typ, der eine zu lösende Aufgabe beschreibt.
struct Task {
    cards: Vec<Card>,
    num_pass_cards: usize,
}

// Die Lösung enthält die von Zara stammenden echten Karten.
struct Solution {
    real_cards: Vec<Card>,
    // Der Anschaulichkeit halber werden ein paar weitere Randinformationen
    // mit ausgegeben.
    num_cards: usize,
    num_real_cards: usize,
    bits_per_card: usize,
    num_free_vars: usize,
    p: usize,
}

// `solve_task` löst eine gegebene Aufgabe und beinhaltet 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,
        }
    }
}

// Parameter für den Lee-Brickell-Algorithmus.
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> {
    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));

    // `basic_vars` und `free_vars` enthalten jeweils die Spaltenindizes der
    // Basisvariablen bzw. freien Variablen von `ppcm`.
    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 Zeile des Pivotelements 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);

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

    // Im letzten Schritt wird versucht, aus der Kontrollmatrix `ppcm` ein
    // Codewort mit Hamming-Gewicht `num_real_cards` zu extrahieren, indem
    // angenommen wird, dass in der Lösung genau `p` der freien Variablen
    // den Wert 1 haben. Ob diese Annahme stimmt, hängt davon ab, ob im ersten
    // Schritt eine glückliche Permutation gewählt wurde.

    // In einigen Fällen muss der Parameter `P` des Lee-Brickell-Algorithmus
    // an die Eingabe angepasst werden, z.B. bei sehr leicht lösbaren Aufgaben
    // mit nur einer freien Variable. Details sind in der Dokumentation,
    // Abschnitt 1.2, Schritt 4 zu finden.
    let p = ((P as isize).clamp(
        -(num_cards as isize) + num_free_vars as isize + num_real_cards as isize,
        num_real_cards.min(num_free_vars) as isize,
    )) as usize;

    // Zunächst wird die Matrix transponiert, damit die Bits der Spalten
    // jeweils zusammenhängend im Speicher liegen und somit die Spalten
    // schneller miteinander XOR gerechnet werden können.
    let transposed_ppcm = transpose_and_optionally_permute_columns(&ppcm, None);

    // Um die `p` freien Variablen mit dem Wert 1 zu finden, wird über alle
    // möglichen `p`-Untermengen der freien Variablen iteriert und jeweils
    // angenommen, dass von den freien Variablen nur die in der Untermenge den
    // Wert 1 haben.
    let mut subset_iter = SubsetIterator::new(num_free_vars, p);
    while let Some(subset) = subset_iter.next() {
        // Zunächst wird das exklusive Oder der `p` Spalten in der Untermenge
        // errechnet. Aus der Struktur der reduzierten Stufenform folgt, dass
        // in jeder Zeile, in der `subset_xor` den Wert 1 hat, auch die
        // Basisvariable dieser Zeile den Wert 1 haben muss, damit die Zeile
        // insgesamt den Wert 0 hat (es handelt sich um eine Zeile der
        // Kontrollmatrix!)
        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]];
        }

        // Damit insgesamt `num_real_cards` Elemente des Lösungsvektors den
        // Wert 1 haben, müssen genau `num_real_cards - p` Basisvariablen den
        // Wert 1 haben, da oben angenommen wurde, dass von den freien
        // Variablen genau `p` den Wert 1 haben.
        if subset_xor.count_ones() == num_real_cards - p {
            // Ist dies der Fall, ist die Lösung gefunden. Die echten Karten
            // werden in `real_cards` gesammelt. Dabei wird die
            // Spaltenpermutation mittels `inverse_permutation` rückgängig
            // gemacht.
            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());
            }
            // Der Benutzerfreundlichkeit gegenüber Zara halber werden die
            // echten Karten vor der Ausgabe aufsteigend sortiert.
            real_cards.sort();

            return Some(Solution {
                real_cards,
                num_cards,
                num_real_cards,
                bits_per_card,
                num_free_vars,
                p,
            });
        }
    }

    // Von den freien Variablen hatten nicht genau `p` den Wert 1. Diese
    // Iteration ist fehlgeschlagen, und in der nächten Iteration wird eine
    // andere Spaltenpermutation und somit auch eine andere Auswahl freier
    // Variablen probiert.
    None
}

// Diese Funktion transponiert eine Bit-Matrix und wendet anschließend, falls
// gefordert, auf die transponierte Matrix die gegebene Spaltenpermutation an.
// Durch die Vereinigung dieser beiden Operationen kann unnötiges Herumkopieren
// von Bits vermieden werden.
fn transpose_and_optionally_permute_columns(
    matrix: &[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
}

// Iterator, der über alle "n über k" k-Untermengen einer Menge von n Elementen
// iteriert. Die Elemente der Menge sind die natürlichen Zahlen von 0 bis n-1.
// Die Untermengen werden durch ein aufsteigend sortiertes Array repräsentiert.
struct SubsetIterator {
    n: usize,
    k: usize,
    fresh: bool,
    subset: Vec<usize>,
}

impl SubsetIterator {
    fn new(n: usize, k: usize) -> Self {
        Self {
            n,
            k,
            fresh: true,
            // Zu Anfang enthält die Untermenge die niedrigsten k Zahlen.
            subset: (0..k).into_iter().collect(),
        }
    }

    fn next(&mut self) -> Option<&[usize]> {
        // Falls dies die erste Iteration ist, geben wir einfach die in "new()"
        // (s.o.) definierte Anfangs-Untermenge zurück.
        if self.fresh {
            self.fresh = false;
            Some(&self.subset)
        } else {
            // `last_index` ist der Index des letzten Elements der Untermenge.
            let last_index = self.k - 1;
            // `index_to_increase` ist der Index des Elements der Untermenge,
            // das durch die nächstgrößere Zahl ersetzt wird.
            // Wir durchsuchen die Untermenge von links nach rechts nach einem
            // erhöhbaren Element, sodass immer das niedrigste Element zuerst
            // erhöht wird.
            let index_to_increase = self
                .subset
                .iter()
                .enumerate()
                .find(|(index, val)| {
                    if *index == last_index {
                        // Falls dies das letzte Element der Untermenge ist,
                        // kann es nurnoch erhöht werden, wenn die
                        // nächtsgrößere Zahl noch Teil der Gesamtmenge ist.
                        self.subset[*index] != self.n - 1
                    } else {
                        // Ansonsten kann das Element erhöht werden, wenn die
                        // nächstgrößere Zahl nicht schon durch ein anderes
                        // Element in der Untermenge repräsentiert ist.
                        self.subset[*index + 1] != **val + 1
                    }
                })? // das '?' gibt sofort `None` zurück, wenn kein erhöhbares
                // Element gefunden wurde und somit schon über alle Untermengen
                // iteriert wurde.
                .0;

            // Das im vorherigen Schritt gefundene Element wird um 1 erhöht,
            // und alle kleineren Elemente werden analog zum "normalen Zählen"
            // auf die kleinstmöglichen Werte gesetzt.
            self.subset[index_to_increase] += 1;
            for lower_idx in 0..index_to_increase {
                self.subset[lower_idx] = lower_idx;
            }

            // Die neu errechnete Untermenge wird zurückgegeben.
            Some(&self.subset)
        }
    }
}

// Einstiegspunkt für das Programm.
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 start = time::Instant::now();
    let solution = solve_task(&task);
    let elapsed = start.elapsed();

    println!("{}", solution);
    println!("Laufzeit ohne I/O: {:?}", elapsed);
}

// Liest eine Aufgabe im Format der Beispielaufgaben ein.
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::<Card>()
            })
            .collect::<Vec<Card>>();

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

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

// Formatiert die Lösung zur Ausgabe.
impl fmt::Display for Solution {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(
            f,
            "Randinformationen (siehe Dokumentation):\nn = {}; w = {}; b = {}; k = {}; p = {}",
            self.num_cards, self.num_real_cards, self.bits_per_card, self.num_free_vars, self.p
        )?;
        writeln!(f)?;
        writeln!(f, "Echte Karten:")?;
        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(())
    }
}