From a3925917e2da88cb243106ee2fb0a6c583ce613c Mon Sep 17 00:00:00 2001
From: Malte Voos <malte@malvo.org>
Date: Mon, 4 Apr 2022 20:07:26 +0200
Subject: bonusaufgabe: random testing

---
 bonusaufgabe/src/main.rs | 51 +++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 46 insertions(+), 5 deletions(-)

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

diff --git a/bonusaufgabe/src/main.rs b/bonusaufgabe/src/main.rs
index 3c9255d..f5983bc 100644
--- a/bonusaufgabe/src/main.rs
+++ b/bonusaufgabe/src/main.rs
@@ -8,6 +8,7 @@ use std::process;
 type Card = BitVec;
 
 // Typ, der eine zu lösende Aufgabe beschreibt.
+#[derive(Clone)] // TODO remove
 struct Task {
     cards: Vec<Card>,
     num_pass_cards: usize,
@@ -75,6 +76,8 @@ 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
@@ -86,11 +89,15 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
 
     // 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
@@ -111,9 +118,10 @@ 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;
+                ppcm[lower_row] ^= current_row_cloned; // O(num_cards)
             }
         }
         // Es kann zur nächsten Zeile und Spalte übergegangen werden.
@@ -137,11 +145,15 @@ 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;
+                ppcm[upper_row] ^= pivot_row_cloned; // O(num_cards)
             }
         }
     }
@@ -161,12 +173,16 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
     // 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
@@ -204,7 +220,7 @@ fn lee_brickell_iteration(cards: &[Card], num_real_cards: usize) -> Option<Solut
         }
     }
 
-    // Von den freien Variablen hatten nicht genau `p` den Wert 1. Die
+    // 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.
@@ -318,8 +334,33 @@ 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 solution = solve_task(task);
+    // print!("{}", solution);
+
+    let mut task = task;
+
+    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
+    }
 }
 
 // Liest eine Aufgabe im Format der Beispielaufgaben ein.
-- 
cgit 1.4.1