From d0c70ad88b11f412c9d8c6735b74cce1b1ff015b Mon Sep 17 00:00:00 2001
From: Malte Voos <git@mal.tc>
Date: Sat, 20 Aug 2022 14:12:11 +0200
Subject: cleanup

---
 bonusaufgabe/src/main.rs | 103 ++++++++++++++++++++++-------------------------
 1 file changed, 48 insertions(+), 55 deletions(-)

(limited to 'bonusaufgabe/src/main.rs')

diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs
index f5983bc..f3245d2 100644
--- a/bonusaufgabe/src/main.rs
+++ b/bonusaufgabe/src/main.rs
@@ -1,14 +1,21 @@
+#![feature(test)]
+
+extern crate test;
+
+#[cfg(test)]
+mod benchmark;
+
 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.
-#[derive(Clone)] // TODO remove
 struct Task {
     cards: Vec<Card>,
     num_pass_cards: usize,
@@ -17,11 +24,18 @@ struct Task {
 // 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 {
+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;
@@ -76,28 +90,20 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // `ppcm` ist eine solche Kontrollmatrix (repräsentiert als Iliffe-Vektor),
     // auf dessen Spalten zusätzlich noch die Permutation `permutation`
     // angewandt wurde.
-    //
-    // O(bits_per_card num_cards)
     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`. Die Indizes der
-    // Basisvariablen bilden das "information set" (siehe Dokumentation)
-    // dieser Iteration.
+    // 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.
-    //
-    // O(bits_per_card^2 num_cards)
     let mut current_row = 0;
     let mut current_col = 0;
     while current_row < bits_per_card && current_col < num_cards {
-        // O(bits_per_card)
         // 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]) {
-            // O(bits_per_card) worst-case
             Some(row) => row,
             None => {
                 // Wurde kein Pivotelement gefunden, gehört diese Spalte zu
@@ -118,10 +124,9 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
         // indem die entsprechenden Zeilen mit der Zeile des Pivotelements XOR
         // gerechnet (addiert) werden.
         for lower_row in (current_row + 1)..bits_per_card {
-            // O(bits_per_card)
             if ppcm[lower_row][current_col] {
                 let current_row_cloned = ppcm[current_row].clone();
-                ppcm[lower_row] ^= current_row_cloned; // O(num_cards)
+                ppcm[lower_row] ^= current_row_cloned;
             }
         }
         // Es kann zur nächsten Zeile und Spalte übergegangen werden.
@@ -145,15 +150,11 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // 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.
-    //
-    // O(bits_per_card^2 num_cards)
     for (pivot_row, pivot_col) in basic_vars.iter().enumerate().rev() {
-        // O(bits_per_card)
         for upper_row in 0..pivot_row {
-            // O(bits_per_card)
             if ppcm[upper_row][*pivot_col] {
                 let pivot_row_cloned = ppcm[pivot_row].clone();
-                ppcm[upper_row] ^= pivot_row_cloned; // O(num_cards)
+                ppcm[upper_row] ^= pivot_row_cloned;
             }
         }
     }
@@ -164,25 +165,24 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // den Wert 1 haben. Ob diese Annahme stimmt, hängt davon ab, ob im ersten
     // Schritt eine glückliche Permutation gewählt wurde.
 
-    // Bei sehr einfachen Aufgabenstellungen kann es vorkommen, das die Anzahl
-    // der freien Variablen noch kleiner als Parameter `P` des Lee-Brickell-
-    // Algorithmus ist (z.B. bei nur einer freien Variable). In diesem Fall
-    // muss der Parameter natürlich entsprechend nach unten korrigiert werden.
-    let p = P.min(num_free_vars);
+    // 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.
-    //
-    // O(bits_per_card num_cards)
     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.
-    //
-    // O(k choose p)
     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
@@ -216,7 +216,14 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
             // echten Karten vor der Ausgabe aufsteigend sortiert.
             real_cards.sort();
 
-            return Some(Solution { real_cards });
+            return Some(Solution {
+                real_cards,
+                num_cards,
+                num_real_cards,
+                bits_per_card,
+                num_free_vars,
+                p,
+            });
         }
     }
 
@@ -334,33 +341,12 @@ fn main() {
     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);
-
-    let mut task = task;
+    let start = time::Instant::now();
+    let solution = solve_task(&task);
+    let elapsed = start.elapsed();
 
-    loop {
-        use rand::prelude::*;
-        let solution = solve_task(task.clone());
-        print!("{}", solution);
-
-        let num_rand_cards = task.cards.len() - task.num_pass_cards - 1;
-        let bits_per_card = task.cards[0].len();
-        let mut new_rand_cards = (0..num_rand_cards)
-            .map(|_| {
-                rand::thread_rng()
-                    .sample_iter::<bool, rand::distributions::Standard>(
-                        rand::distributions::Standard,
-                    )
-                    .take(bits_per_card)
-                    .collect::<BitVec>()
-            })
-            .collect::<Vec<BitVec>>();
-        let mut new_cards = solution.real_cards;
-        new_cards.append(&mut new_rand_cards);
-        new_cards.shuffle(&mut rand::thread_rng());
-        task.cards = new_cards
-    }
+    println!("{}", solution);
+    println!("Laufzeit ohne I/O: {:?}", elapsed);
 }
 
 // Liest eine Aufgabe im Format der Beispielaufgaben ein.
@@ -386,7 +372,7 @@ impl TryFrom<&str> for Task {
                         '1' => Some(true),
                         _ => None,
                     })
-                    .collect::<BitVec>()
+                    .collect::<Card>()
             })
             .collect::<Vec<Card>>();
 
@@ -404,6 +390,13 @@ impl TryFrom<&str> for Task {
 // 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 {
-- 
cgit 1.4.1