Big overhaul, corrected sfb, added dsfb, lengthened corpus

6 files changed, 182 insertions, 129 deletions

diff --git a/srchr/src/config.rs b/srchr/src/config.rs
index 161922c..2633a71 100644
--- a/srchr/src/config.rs
+++ b/srchr/src/config.rs
@@ -1,38 +1,52 @@
-// With the below parameters and the supplied corpus searches seem to converge on the following
+// With the below parameters and the supplied corpus searches seem to converge on a few layouts, with one of the better ones being
 
-// J , H G Q  B C O U '
-// S A N T V  F D E I R
-// X . L M K  P W / Y Z
-//
+// V L O M Q  P F U H ,
+// S R A T K  Y C E N I
+// Z X / D J  G W ' B .
 // Percent per key:
-//  0.1  1.8  6.0  1.9  0.1   1.5  2.3  7.4  2.8  1.0
-//  6.0  7.7  6.6  8.6  0.9   2.1  4.3 11.9  6.6  5.5
-//  0.1  1.2  4.0  2.6  0.8   1.6  2.3  0.2  2.0  0.1
+//  0.92  3.96  7.42  2.57  0.10   1.62  2.10  2.77  5.94  1.78
+//  6.03  5.56  7.74  8.60  0.77   1.99  2.35 11.90  6.62  6.68
+//  0.06  0.15  0.14  4.25  0.15   1.93  2.27  1.00  1.50  1.14
 //
-// Finger usage:  6.29%, 10.70%, 16.56%, 14.88%, 14.05%, 19.47%, 11.45%,  6.60%
-// Hand usage: 48.43% vs 51.57%
-// Same finger bigrams:  0.000%,  0.029%,  0.092%,  0.032%,  0.042%,  0.096%,  0.113%,  0.031%
-// Total sfb: 0.43% (43414)
+// Finger usage:  7.02%,  9.66%, 15.30%, 16.44%, 12.25%, 15.67%, 14.06%,  9.61%
+// Hand usage: 48.42% vs 51.58%
+// SFB distribution :  0.001%,  0.087%,  0.089%,  0.047%,  0.104%,  0.197%,  0.044%,  0.024%
+// DSFB distribution:  0.147%,  0.431%,  0.615%,  0.999%,  0.208%,  0.997%,  1.102%,  0.408%
+// Total sfb: 0.594% (49972)
+// Total dsfb: 4.906% (412768)
 
-// Search parameters
-pub const CORPUS_FILE_NAME: &str = "corpus.txt";
+// -----------------------------------------------------------------------------
+//                                    Tweak
+// -----------------------------------------------------------------------------
 
+// Input parameters
+pub const CORPUS_FILE_NAME: &str = "corpus.txt";
 pub const STARTING_LAYOUT_STRING: &str = "
-Q W E R T  Y U I O P
-A S D F G  H J K L '
-Z X C V B  N M , . /
+A B C D E  F G H I J
+K L M N O  P Q R S T
+U V W X Y  Z . , / '
 ";
 
+// Tournament parameters
 pub const NUM_CONTESTANTS: usize = 256;
-pub const NUM_PERSIST: usize = 16;
+pub const NUM_PERSIST: usize = 8;
+pub const MAX_NUM_TRANSPOSITIONS: usize = 12;
 
-pub const MAX_NUM_TRANSPOSITIONS: usize = 8;
-pub const DESIRED_INDEX_USAGE_PERCENT: f32 = 0.15;
-pub const fn index_usage_fitness(index_threshold: u32, index_count: u32) -> u32 {
-    (index_threshold as i64 - index_count as i64).abs() as u32 / 64
+// Fitness parameters
+pub const DESIRED_INDEX_USAGE_PERCENT: f32 = 0.12;
+pub const STANDARD_DSFB_WEIGHT: f32 = 1.0 / 32.0;
+pub fn index_usage_fitness(total_count: u32, index_count: u32) -> f32 {
+    let index_perc = index_count as f32 / total_count as f32;
+    if index_perc < DESIRED_INDEX_USAGE_PERCENT {
+        DESIRED_INDEX_USAGE_PERCENT - index_perc
+    } else {
+        0.0
+    }
 }
 
-// Do not change, code makes assumptions about these
+// -----------------------------------------------------------------------------
+//     Do not change the following, the code makes assumptions about these
+// -----------------------------------------------------------------------------
 pub const NUM_KEYS: usize = 30;
 pub const ROW_LENGTH: usize = 10;
 
diff --git a/srchr/src/corpus.rs b/srchr/src/corpus.rs
index aa6e163..4428bc6 100644
--- a/srchr/src/corpus.rs
+++ b/srchr/src/corpus.rs
@@ -17,10 +17,11 @@ const CHAR_TO_INDEX: [usize; 128] = build_lookup_table();
 
 const NUM_BIGRAMS: usize = NUM_KEYS * NUM_KEYS;
 pub struct Corpus {
-    bigram_count: [u32; NUM_BIGRAMS],
+    bigram_percs: [f32; NUM_BIGRAMS],
+    skipgram_percs: [f32; NUM_BIGRAMS],
     character_count: [u32; 128],
     total_count: u32,
-    index_threshold: u32,
+    total_bigrams: u32,
 }
 
 fn pair_to_index(x: u8, y: u8) -> usize {
@@ -34,66 +35,94 @@ impl Corpus {
         self.character_count[c as usize]
     }
 
-    pub fn get_bigram_count(&self, x: u8, y: u8) -> u32 {
-        self.bigram_count[pair_to_index(x, y)]
+    pub fn get_bigram_perc(&self, x: u8, y: u8) -> f32 {
+        self.bigram_percs[pair_to_index(x, y)]
     }
 
-    pub fn get_index_threshold(&self) -> u32 {
-        self.index_threshold
+    pub fn get_skipgram_perc(&self, x: u8, y: u8) -> f32 {
+        self.skipgram_percs[pair_to_index(x, y)]
     }
 
     pub fn get_total_count(&self) -> u32 {
         self.total_count
     }
 
+    pub fn get_total_bigrams(&self) -> u32 {
+        self.total_bigrams
+    }
+
     pub fn load(path: &str) -> Result<Corpus, std::io::Error> {
         let contents = fs::read_to_string(path)?;
 
         let mut bigram_count = [0; NUM_BIGRAMS];
+        let mut skipgram_count = [0; NUM_BIGRAMS];
         let mut character_count = [0; 128];
         let mut total_count = 0;
+        let mut total_bigrams = 0;
+        let mut total_trigrams = 0;
 
         let mut last_char: Option<u8> = None;
+        let mut last_last_char: Option<u8> = None;
         for c in contents.chars() {
-            if let Some(c) = canonicalise(c) {
+            let current_char = canonicalise(c);
+            if let Some(c) = current_char {
                 if let Some(lc) = last_char {
-                    // We don't count these anyway
+                    if let Some(llc) = last_last_char {
+                        if llc != c {
+                            skipgram_count[pair_to_index(llc, c)] += 1;
+                            skipgram_count[pair_to_index(c, llc)] += 1;
+                        }
+                        total_trigrams += 1;
+                    }
                     if lc != c {
                         bigram_count[pair_to_index(c, lc)] += 1;
                         bigram_count[pair_to_index(lc, c)] += 1;
                     }
+                    total_bigrams += 1;
                 }
-                last_char = Some(c);
                 character_count[c as usize] += 1;
                 total_count += 1;
-            } else {
-                last_char = None;
             }
+            last_last_char = last_char;
+            last_char = current_char;
         }
 
-        let index_threshold = (total_count as f32 * DESIRED_INDEX_USAGE_PERCENT) as u32;
+        let mut bigram_percs = [0.0; NUM_BIGRAMS];
+        let mut skipgram_percs = [0.0; NUM_BIGRAMS];
+
+        for i in 0..NUM_BIGRAMS {
+            bigram_percs[i] = bigram_count[i] as f32 / total_bigrams as f32;
+            skipgram_percs[i] = skipgram_count[i] as f32 / total_trigrams as f32;
+        }
 
         return Ok(Corpus {
-            bigram_count,
+            skipgram_percs,
+            bigram_percs,
             character_count,
             total_count,
-            index_threshold,
+            total_bigrams,
         });
     }
 }
 
-fn dump_bigrams(corpus: &Corpus) -> Vec<(String, u32)> {
-    let mut result: Vec<(String, u32)> = Vec::new();
+fn dump_bigrams(corpus: &Corpus) -> Vec<(String, f32)> {
+    let mut result: Vec<(String, f32)> = Vec::new();
 
     for (i, &x) in KEY_CHARS.iter().enumerate() {
         for &y in &KEY_CHARS[i..] {
             let mut pair = String::from(x);
             pair.push(y);
-            result.push((pair, corpus.bigram_count[pair_to_index(x as u8, y as u8)]));
+            result.push((pair, corpus.bigram_percs[pair_to_index(x as u8, y as u8)]));
         }
     }
 
-    result.sort_by(|(_, c1), (_, c2)| c1.cmp(c2).reverse());
+    result.sort_by(|(_, c1), (_, c2)| {
+        if c2 < c1 {
+            std::cmp::Ordering::Less
+        } else {
+            std::cmp::Ordering::Greater
+        }
+    });
 
     return result;
 }
diff --git a/srchr/src/evaluation.rs b/srchr/src/evaluation.rs
index aba3501..a855d89 100644
--- a/srchr/src/evaluation.rs
+++ b/srchr/src/evaluation.rs
@@ -5,8 +5,8 @@ use crate::output::*;
 
 use std::fmt;
 
-pub fn prelayout_fitness(corpus: &Corpus, layout: &Prelayout) -> u32 {
-    let mut score: u32 = 0;
+pub fn prelayout_fitness(corpus: &Corpus, layout: &Prelayout) -> f32 {
+    let mut score: f32 = 0.0;
 
     for i in 0..6 {
         let keys = layout.get_standard_column(i);
@@ -14,9 +14,14 @@ pub fn prelayout_fitness(corpus: &Corpus, layout: &Prelayout) -> u32 {
         let k2 = keys[1];
         let k3 = keys[2];
 
-        score += corpus.get_bigram_count(k1, k2)
-            + corpus.get_bigram_count(k1, k3)
-            + corpus.get_bigram_count(k2, k3);
+        score += corpus.get_bigram_perc(k1, k2)
+            + corpus.get_bigram_perc(k1, k3)
+            + corpus.get_bigram_perc(k2, k3);
+
+        score += (corpus.get_skipgram_perc(k1, k2)
+            + corpus.get_skipgram_perc(k1, k3)
+            + corpus.get_skipgram_perc(k2, k3))
+            * STANDARD_DSFB_WEIGHT;
     }
 
     for i in 0..2 {
@@ -28,41 +33,42 @@ pub fn prelayout_fitness(corpus: &Corpus, layout: &Prelayout) -> u32 {
         let k5 = keys[4];
         let k6 = keys[5];
 
-        // We want index usage!
-        let index_count: u32 = keys.iter().map(|&k| corpus.get_character_count(k)).sum();
-        score += index_usage_fitness(corpus.get_index_threshold(), index_count);
+        let index_percs = keys.iter().map(|&k| corpus.get_character_count(k)).sum();
+        score += index_usage_fitness(corpus.get_total_count(), index_percs);
 
-        score += corpus.get_bigram_count(k1, k2)
-            + corpus.get_bigram_count(k1, k3)
-            + corpus.get_bigram_count(k2, k3)
-            + corpus.get_bigram_count(k4, k5)
-            + corpus.get_bigram_count(k4, k6)
-            + corpus.get_bigram_count(k5, k6)
-            + corpus.get_bigram_count(k1, k4)
-            + corpus.get_bigram_count(k1, k5)
-            + corpus.get_bigram_count(k1, k6)
-            + corpus.get_bigram_count(k2, k4)
-            + corpus.get_bigram_count(k2, k5)
-            + corpus.get_bigram_count(k2, k6)
-            + corpus.get_bigram_count(k3, k4)
-            + corpus.get_bigram_count(k3, k5)
-            + corpus.get_bigram_count(k3, k6);
+        score += corpus.get_bigram_perc(k1, k2)
+            + corpus.get_bigram_perc(k1, k3)
+            + corpus.get_bigram_perc(k2, k3)
+            + corpus.get_bigram_perc(k4, k5)
+            + corpus.get_bigram_perc(k4, k6)
+            + corpus.get_bigram_perc(k5, k6)
+            + corpus.get_bigram_perc(k1, k4)
+            + corpus.get_bigram_perc(k1, k5)
+            + corpus.get_bigram_perc(k1, k6)
+            + corpus.get_bigram_perc(k2, k4)
+            + corpus.get_bigram_perc(k2, k5)
+            + corpus.get_bigram_perc(k2, k6)
+            + corpus.get_bigram_perc(k3, k4)
+            + corpus.get_bigram_perc(k3, k5)
+            + corpus.get_bigram_perc(k3, k6);
     }
 
     score
 }
 
-#[derive(Copy, Clone)]
 pub struct Evaluation {
     keypress: [u32; NUM_KEYS],
     total_keypress: u32,
-    sfb: [u32; 8],
+    total_bigrams: u32,
+    sfb: [f32; 8],
+    dsfb: [f32; 8],
 }
 
 impl Evaluation {
     pub fn evaluate_layout(corpus: &Corpus, layout: &Layout) -> Evaluation {
         let mut keypress: [u32; NUM_KEYS] = [0; NUM_KEYS];
-        let mut sfb: [u32; 8] = [0; 8];
+        let mut sfb: [f32; 8] = [0.0; 8];
+        let mut dsfb: [f32; 8] = [0.0; 8];
 
         for (i, &c) in layout.get_keys().iter().enumerate() {
             keypress[i] = corpus.get_character_count(c as u8);
@@ -75,55 +81,63 @@ impl Evaluation {
             let k2 = layout.get_key(ind + 10 * 1);
             let k3 = layout.get_key(ind + 10 * 2);
 
-            sfb[i] = corpus.get_bigram_count(k1, k2)
-                + corpus.get_bigram_count(k1, k3)
-                + corpus.get_bigram_count(k2, k3);
+            sfb[i] = corpus.get_bigram_perc(k1, k2)
+                + corpus.get_bigram_perc(k1, k3)
+                + corpus.get_bigram_perc(k2, k3);
+
+            dsfb[i] = corpus.get_skipgram_perc(k1, k2)
+                + corpus.get_skipgram_perc(k1, k3)
+                + corpus.get_skipgram_perc(k2, k3);
 
             if i == 3 {
                 let k4 = layout.get_key(4 + 10 * 0);
                 let k5 = layout.get_key(4 + 10 * 1);
                 let k6 = layout.get_key(4 + 10 * 2);
-                sfb[i] += corpus.get_bigram_count(k4, k5)
-                    + corpus.get_bigram_count(k4, k6)
-                    + corpus.get_bigram_count(k5, k6)
-                    + corpus.get_bigram_count(k1, k4)
-                    + corpus.get_bigram_count(k1, k5)
-                    + corpus.get_bigram_count(k1, k6)
-                    + corpus.get_bigram_count(k2, k4)
-                    + corpus.get_bigram_count(k2, k5)
-                    + corpus.get_bigram_count(k2, k6)
-                    + corpus.get_bigram_count(k3, k4)
-                    + corpus.get_bigram_count(k3, k5)
-                    + corpus.get_bigram_count(k3, k6);
+                sfb[i] += corpus.get_bigram_perc(k4, k5)
+                    + corpus.get_bigram_perc(k4, k6)
+                    + corpus.get_bigram_perc(k5, k6)
+                    + corpus.get_bigram_perc(k1, k4)
+                    + corpus.get_bigram_perc(k1, k5)
+                    + corpus.get_bigram_perc(k1, k6)
+                    + corpus.get_bigram_perc(k2, k4)
+                    + corpus.get_bigram_perc(k2, k5)
+                    + corpus.get_bigram_perc(k2, k6)
+                    + corpus.get_bigram_perc(k3, k4)
+                    + corpus.get_bigram_perc(k3, k5)
+                    + corpus.get_bigram_perc(k3, k6);
             } else if i == 4 {
                 let k4 = layout.get_key(5 + 10 * 0);
                 let k5 = layout.get_key(5 + 10 * 1);
                 let k6 = layout.get_key(5 + 10 * 2);
-                sfb[i] += corpus.get_bigram_count(k4, k5)
-                    + corpus.get_bigram_count(k5, k6)
-                    + corpus.get_bigram_count(k4, k6)
-                    + corpus.get_bigram_count(k1, k4)
-                    + corpus.get_bigram_count(k1, k5)
-                    + corpus.get_bigram_count(k1, k6)
-                    + corpus.get_bigram_count(k2, k4)
-                    + corpus.get_bigram_count(k2, k5)
-                    + corpus.get_bigram_count(k2, k6)
-                    + corpus.get_bigram_count(k3, k4)
-                    + corpus.get_bigram_count(k3, k5)
-                    + corpus.get_bigram_count(k3, k6);
+                sfb[i] += corpus.get_bigram_perc(k4, k5)
+                    + corpus.get_bigram_perc(k5, k6)
+                    + corpus.get_bigram_perc(k4, k6)
+                    + corpus.get_bigram_perc(k1, k4)
+                    + corpus.get_bigram_perc(k1, k5)
+                    + corpus.get_bigram_perc(k1, k6)
+                    + corpus.get_bigram_perc(k2, k4)
+                    + corpus.get_bigram_perc(k2, k5)
+                    + corpus.get_bigram_perc(k2, k6)
+                    + corpus.get_bigram_perc(k3, k4)
+                    + corpus.get_bigram_perc(k3, k5)
+                    + corpus.get_bigram_perc(k3, k6);
             }
         }
 
         return Evaluation {
             keypress,
             total_keypress: corpus.get_total_count(),
+            total_bigrams: corpus.get_total_bigrams(),
             sfb,
+            dsfb,
         };
     }
 
     fn output_eval(&self) -> String {
         let mut result = String::new();
         let tot = self.total_keypress as f32;
+        let big = self.total_bigrams as f32;
+        let tig = self.total_bigrams as f32;
 
         result += &"Percent per key:\n";
         result += &format_block_output(self.keypress.into_iter().map(|k| 100.0 * k as f32 / tot));
@@ -148,17 +162,20 @@ impl Evaluation {
 
         result += &format!("\nHand usage: {:.2}% vs {:.2}%", lh, rh);
 
-        result += "\nSame finger bigrams: ";
+        result += "\nSFB distribution : ";
         for (i, &u) in self.sfb.iter().enumerate() {
-            result += &format!(
-                "{:>6.3}%{}",
-                u as f32 / tot * 100.0,
-                if i < 7 { ", " } else { "" }
-            );
+            result += &format!("{:>6.3}%{}", u * 100.0, if i < 7 { ", " } else { "" });
+        }
+
+        result += "\nDSFB distribution: ";
+        for (i, &u) in self.dsfb.iter().enumerate() {
+            result += &format!("{:>6.3}%{}", u * 100.0, if i < 7 { ", " } else { "" });
         }
 
-        let sfb = self.sfb.iter().sum::<u32>();
-        result += &format!("\nTotal sfb: {:.2}% ({})", sfb as f32 / tot * 100.0, sfb);
+        let sfb = self.sfb.iter().sum::<f32>();
+        let dsfb = self.dsfb.iter().sum::<f32>();
+        result += &format!("\nTotal sfb: {:.3}% ({:.0})", sfb * 100.0, sfb * big);
+        result += &format!("\nTotal dsfb: {:.3}% ({:.0})", dsfb * 100.0, dsfb * tig);
 
         return result;
     }
diff --git a/srchr/src/layout.rs b/srchr/src/layout.rs
index 0f89b9d..841c085 100644
--- a/srchr/src/layout.rs
+++ b/srchr/src/layout.rs
@@ -192,13 +192,8 @@ impl Layout {
 
         let mut k: usize = 0;
         for c in inp.chars() {
-            let valid = (c.is_uppercase() && c.is_alphabetic())
-                || c == '.'
-                || c == '/'
-                || c == ','
-                || c == '\'';
-            if valid {
-                layout[k] = c;
+            if let Some(c) = canonicalise(c) {
+                layout[k] = c as char;
                 k += 1;
             }
             if k > NUM_KEYS {
diff --git a/srchr/src/main.rs b/srchr/src/main.rs
index 7c0ede9..667b675 100644
--- a/srchr/src/main.rs
+++ b/srchr/src/main.rs
@@ -18,7 +18,7 @@ use std::time::Instant;
 
 struct Tournament<'a> {
     rngs: Vec<Pcg64>,
-    top_prelayouts: Vec<(Prelayout, u32)>,
+    top_prelayouts: Vec<(Prelayout, f32)>,
     corpus: &'a Corpus,
 }
 
@@ -29,7 +29,7 @@ impl<'a> Tournament<'a> {
             rngs.push(Pcg64::from_entropy());
         }
 
-        let mut top_prelayouts: Vec<(Prelayout, u32)> = Vec::new();
+        let mut top_prelayouts: Vec<(Prelayout, f32)> = Vec::new();
         let score = prelayout_fitness(&corpus, &seed_prelayout);
         for _ in 0..NUM_PERSIST {
             top_prelayouts.push((seed_prelayout.clone(), score));
@@ -54,11 +54,17 @@ impl<'a> Tournament<'a> {
                 );
                 return (layout, prelayout_fitness(&self.corpus, &layout));
             })
-            .collect::<Vec<(Prelayout, u32)>>();
+            .collect::<Vec<(Prelayout, f32)>>();
 
         let best = self.top_prelayouts[0].1;
         tournament.append(&mut self.top_prelayouts);
-        tournament.sort_by(|(_, lscore), (_, rscore)| lscore.cmp(rscore));
+        tournament.sort_by(|(_, lscore), (_, rscore)| {
+            if lscore < rscore {
+                std::cmp::Ordering::Less
+            } else {
+                std::cmp::Ordering::Greater
+            }
+        });
 
         let result;
         if tournament[0].1 < best {
@@ -79,9 +85,11 @@ fn main() {
     let corpus = Corpus::load(CORPUS_FILE_NAME).unwrap();
     println!("{}", corpus);
 
-    let seed_prelayout = Layout::from_verbose(STARTING_LAYOUT_STRING)
-        .unwrap()
-        .as_prelayout();
+    let seed_layout = Layout::from_verbose(STARTING_LAYOUT_STRING).unwrap();
+    let seed_evl = Evaluation::evaluate_layout(&corpus, &seed_layout);
+    println!("Starting with\n {}{}", seed_layout, seed_evl);
+
+    let seed_prelayout = seed_layout.as_prelayout();
 
     let mut tournament = Tournament::new_from_seed_prelayout(&seed_prelayout, &corpus);
 
@@ -93,12 +101,9 @@ fn main() {
         if let Some(prelayout) = improvement {
             let layout = Layout::from_prelayout(&prelayout, &corpus);
             let evl = Evaluation::evaluate_layout(&corpus, &layout);
-            println!("");
-            println!("================================================================================\n\n{}",
-                 layout
+            println!("\n================================================================================\n\n{}{}",
+                 layout, evl
             );
-
-            println!("{}", evl);
         }
 
         count += 1;
diff --git a/srchr/src/output.rs b/srchr/src/output.rs
index b5af9e7..dec079d 100644
--- a/srchr/src/output.rs
+++ b/srchr/src/output.rs
@@ -13,17 +13,10 @@ impl ToMyString for char {
     }
 }
 
-impl ToMyString for u32 {
-    const BLANK_STRING: &'static str = "     ";
-    fn to_my_string(&self) -> String {
-        format!("{:5}", *self)
-    }
-}
-
 impl ToMyString for f32 {
     const BLANK_STRING: &'static str = "    ";
     fn to_my_string(&self) -> String {
-        format!("{:>4.1}", *self)
+        format!("{:>5.2}", *self)
     }
 }