diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/corpus.rs | 204 | ||||
| -rw-r--r-- | src/layout.rs | 363 | ||||
| -rw-r--r-- | src/main.rs | 118 |
3 files changed, 0 insertions, 685 deletions
diff --git a/src/corpus.rs b/src/corpus.rs deleted file mode 100644 index e1c903b..0000000 --- a/src/corpus.rs +++ /dev/null @@ -1,204 +0,0 @@ -use std::fmt; -use std::fs; - -use crate::layout::*; - -const fn build_lookup_table() -> [usize; 128] { - let mut result = [0; 128]; - let mut i = 0; - - while i < NUM_KEYS { - result[KEY_CHARS[i] as usize] = i; - i += 1; - } - return result; -} -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], - character_count: [u32; 256], - total_count: u32, - index_threshold: u32, -} - -fn pair_to_index(x: char, y: char) -> usize { - let xi = CHAR_TO_INDEX[x as usize]; - let yi = CHAR_TO_INDEX[y as usize]; - xi + NUM_KEYS * yi -} - -impl Corpus { - pub fn get_character_count(&self, c: char) -> u32 { - self.character_count[c as usize] - } - - 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 character_count = [0; 256]; - let mut total_count = 0; - - let mut last_char = None; - for c in contents.chars() { - if let Some(c) = canonicalise(c) { - if let Some(lc) = last_char { - // We don't count these anyway - if lc != c { - bigram_count[pair_to_index(c, lc)] += 1; - bigram_count[pair_to_index(lc, c)] += 1; - } - } - last_char = Some(c); - character_count[c as usize] += 1; - total_count += 1; - } else { - last_char = None; - } - } - - let index_threshold = (total_count as f32 * 0.15) as u32; - - return Ok(Corpus { - bigram_count, - character_count, - total_count, - index_threshold, - }); - } - - pub fn prelayout_fitness(&self, layout: &Prelayout) -> u32 { - let mut score: u32 = 0; - - for i in 0..6 { - let keys = layout.get_standard_column(i); - let k1 = keys[0]; - let k2 = keys[1]; - let k3 = keys[2]; - - score += self.bigram_count[pair_to_index(k1, k2)] - + self.bigram_count[pair_to_index(k1, k3)] - + self.bigram_count[pair_to_index(k2, k3)]; - } - - for i in 0..2 { - let keys = layout.get_index_column(i); - let k1 = keys[0]; - let k2 = keys[1]; - let k3 = keys[2]; - let k4 = keys[3]; - let k5 = keys[4]; - let k6 = keys[5]; - - // We want index usage! - let index_count: u32 = keys.iter().map(|&k| self.character_count[k as usize]).sum(); - score += (self.index_threshold as i64 - index_count as i64).abs() as u32 / 32; - - score += self.bigram_count[pair_to_index(k1, k2)] - + self.bigram_count[pair_to_index(k1, k3)] - + self.bigram_count[pair_to_index(k2, k3)] - + self.bigram_count[pair_to_index(k4, k5)] - + self.bigram_count[pair_to_index(k4, k6)] - + self.bigram_count[pair_to_index(k5, k6)] - + self.bigram_count[pair_to_index(k1, k4)] - + self.bigram_count[pair_to_index(k1, k5)] - + self.bigram_count[pair_to_index(k1, k6)] - + self.bigram_count[pair_to_index(k2, k4)] - + self.bigram_count[pair_to_index(k2, k5)] - + self.bigram_count[pair_to_index(k2, k6)] - + self.bigram_count[pair_to_index(k3, k4)] - + self.bigram_count[pair_to_index(k3, k5)] - + self.bigram_count[pair_to_index(k3, k6)]; - } - - score - } - - pub fn evaluate_layout(&self, layout: &Layout) -> Evaluation { - let mut keypress: [u32; NUM_KEYS] = [0; NUM_KEYS]; - let mut sfb: [u32; 8] = [0; 8]; - - for (i, &c) in self.character_count.iter().enumerate() { - if c > 0 { - keypress[layout.get_index((i as u8) as char)] = c; - } - } - - // TODO: We make assumptions about NUM_KEYS here - for i in 0..8 { - let ind = if i < 4 { i } else { i + 2 }; - - let k1 = layout.get_key(ind + 10 * 0); - let k2 = layout.get_key(ind + 10 * 1); - let k3 = layout.get_key(ind + 10 * 2); - - sfb[i] = self.bigram_count[pair_to_index(k1, k2)] - + self.bigram_count[pair_to_index(k1, k3)] - + self.bigram_count[pair_to_index(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] += self.bigram_count[pair_to_index(k4, k5)] - + self.bigram_count[pair_to_index(k4, k6)] - + self.bigram_count[pair_to_index(k5, k6)] - + self.bigram_count[pair_to_index(k1, k4)] - + self.bigram_count[pair_to_index(k1, k5)] - + self.bigram_count[pair_to_index(k1, k6)] - + self.bigram_count[pair_to_index(k2, k4)] - + self.bigram_count[pair_to_index(k2, k5)] - + self.bigram_count[pair_to_index(k2, k6)] - + self.bigram_count[pair_to_index(k3, k4)] - + self.bigram_count[pair_to_index(k3, k5)] - + self.bigram_count[pair_to_index(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] += self.bigram_count[pair_to_index(k4, k5)] - + self.bigram_count[pair_to_index(k5, k6)] - + self.bigram_count[pair_to_index(k4, k6)] - + self.bigram_count[pair_to_index(k1, k4)] - + self.bigram_count[pair_to_index(k1, k5)] - + self.bigram_count[pair_to_index(k1, k6)] - + self.bigram_count[pair_to_index(k2, k4)] - + self.bigram_count[pair_to_index(k2, k5)] - + self.bigram_count[pair_to_index(k2, k6)] - + self.bigram_count[pair_to_index(k3, k4)] - + self.bigram_count[pair_to_index(k3, k5)] - + self.bigram_count[pair_to_index(k3, k6)]; - } - } - - return Evaluation::new(keypress, self.total_count, sfb); - } -} - -fn dump_bigrams(corpus: &Corpus) -> Vec<(String, u32)> { - let mut result: Vec<(String, u32)> = 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, y)])); - } - } - - result.sort_by(|(_, c1), (_, c2)| c1.cmp(c2).reverse()); - - return result; -} - -impl fmt::Display for Corpus { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - formatter.write_str(&format!( - "Counted {} characters, top 5 bigrams {:?}", - self.total_count, - &dump_bigrams(self)[0..5] - )) - } -} diff --git a/src/layout.rs b/src/layout.rs deleted file mode 100644 index 9662b84..0000000 --- a/src/layout.rs +++ /dev/null @@ -1,363 +0,0 @@ -use crate::corpus::*; - -use rand::prelude::*; -use std::fmt; - -pub const NUM_KEYS: usize = 30; -pub const ROW_LENGTH: usize = 10; - -pub const KEY_CHARS: [char; NUM_KEYS] = [ - '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', '/', '.', ',', '\'', -]; - -pub fn canonicalise(inp: char) -> Option<char> { - if inp.is_ascii_alphabetic() { - return Some(inp.to_ascii_uppercase()); - } else { - match inp { - '.' => Some('.'), - '>' => Some('.'), - ',' => Some(','), - '<' => Some(','), - '/' => Some('/'), - '?' => Some('/'), - '\'' => Some('\''), - '"' => Some('\''), - _ => None, - } - } -} - -#[derive(Copy, Clone)] -pub struct Prelayout { - standard_columns: [[char; 3]; 6], - index_columns: [[char; 6]; 2], -} - -impl Prelayout { - pub fn get_standard_column(&self, index: usize) -> &[char; 3] { - &self.standard_columns[index] - } - - pub fn get_index_column(&self, index: usize) -> &[char; 6] { - &self.index_columns[index] - } - - pub fn new_random_from<R: RngCore>(pl: &Prelayout, rng: &mut R) -> Prelayout { - let mut standard_columns = pl.standard_columns.clone(); - let mut index_columns = pl.index_columns.clone(); - - let mut count = rng.gen_range(1..NUM_KEYS); - while count > 0 { - let source_index: bool = rng.gen(); - let target_index: bool = rng.gen(); - - let saved; - let target_col: usize; - let target_idx: usize; - if target_index { - target_col = rng.gen_range(0..2); - target_idx = rng.gen_range(0..6); - saved = index_columns[target_col][target_idx]; - } else { - target_col = rng.gen_range(0..6); - target_idx = rng.gen_range(0..3); - saved = standard_columns[target_col][target_idx]; - } - - let source_col: usize; - let source_idx: usize; - if source_index { - source_col = rng.gen_range(0..2); - source_idx = rng.gen_range(0..6); - if target_index { - index_columns[target_col][target_idx] = index_columns[source_col][source_idx]; - } else { - standard_columns[target_col][target_idx] = - index_columns[source_col][source_idx]; - } - index_columns[source_col][source_idx] = saved; - } else { - source_col = rng.gen_range(0..6); - source_idx = rng.gen_range(0..3); - if target_index { - index_columns[target_col][target_idx] = - standard_columns[source_col][source_idx]; - } else { - standard_columns[target_col][target_idx] = - standard_columns[source_col][source_idx]; - } - standard_columns[source_col][source_idx] = saved; - } - count -= 1; - } - Prelayout { - standard_columns, - index_columns, - } - } - - fn from_char_array(ca: &[char; NUM_KEYS]) -> Prelayout { - let mut standard_columns = [['x'; 3]; 6]; - let mut index_columns = [['x'; 6]; 2]; - - for i in 0..6 { - let ind = if i < 3 { i } else { i + 4 }; - for j in 0..3 { - standard_columns[i][j] = ca[ind + j * ROW_LENGTH]; - } - } - - for j in 0..3 { - index_columns[0][j] = ca[3 + j * ROW_LENGTH]; - index_columns[1][j] = ca[6 + j * ROW_LENGTH]; - index_columns[0][j + 3] = ca[4 + j * ROW_LENGTH]; - index_columns[1][j + 3] = ca[5 + j * ROW_LENGTH]; - } - - Prelayout { - standard_columns, - index_columns, - } - } -} - -const KEY_TO_FINGER: [usize; NUM_KEYS] = [ - 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, -]; - -#[derive(Copy, Clone)] -pub struct Layout { - keys: [char; NUM_KEYS], -} - -impl Layout { - pub fn as_prelayout(&self) -> Prelayout { - Prelayout::from_char_array(&self.keys) - } - - pub fn from_prelayout(pl: &Prelayout, corpus: &Corpus) -> Layout { - fn weight_function<const N: usize, const M: usize>( - columns: &[[char; N]; M], - corpus: &Corpus, - ) -> Vec<(Vec<char>, u32)> { - let mut result = columns - .iter() - .map(|col| { - let mut weight = 0; - let mut wcol: Vec<(char, u32)> = col - .iter() - .map(|&c| { - let w = corpus.get_character_count(c); - weight += w; - (c, w) - }) - .collect(); - wcol.sort_by(|(_, l), (_, r)| r.cmp(l)); - wcol.swap(0, 1); - if N == 6 { - wcol.swap(3, 4); - } - (wcol.into_iter().map(|(k, _)| k).collect(), weight) - }) - .collect::<Vec<(Vec<char>, u32)>>(); - result.sort_by(|(_, l), (_, r)| r.cmp(l)); - result - } - - let mut balance: i64 = 0; - let mut left_col: usize = 0; - let mut right_col: usize = 9; - let mut keys = ['x'; NUM_KEYS]; - - let mut w_standard_columns = weight_function(&pl.standard_columns, corpus); - while let Some((col, weight)) = w_standard_columns.pop() { - let left: bool = ((balance >= 0) && (left_col <= 2)) || (right_col <= 6); - let ind = if left { left_col } else { right_col }; - for i in 0..3 { - keys[ind + i * ROW_LENGTH] = col[i]; - } - if left { - left_col += 1; - } else { - right_col -= 1; - } - balance += if left { - -(weight as i64) - } else { - weight as i64 - }; - } - - let w_index_columns = weight_function(&pl.index_columns, corpus); - let (left_ind, right_ind) = if balance >= 0 { (0, 1) } else { (1, 0) }; - for j in 0..3 { - keys[3 + j * ROW_LENGTH] = w_index_columns[left_ind].0[j]; - keys[6 + j * ROW_LENGTH] = w_index_columns[right_ind].0[j]; - keys[4 + j * ROW_LENGTH] = w_index_columns[left_ind].0[j + 3]; - keys[5 + j * ROW_LENGTH] = w_index_columns[right_ind].0[j + 3]; - } - - Layout { keys } - } - - pub fn get_index(&self, c: char) -> usize { - let mut found_key = 0; - while self.keys[found_key] != c { - found_key += 1 - } - found_key - } - - fn char_array_to_layout(keys: [char; NUM_KEYS]) -> Layout { - return Layout { keys }; - } - - pub fn get_key(&self, index: usize) -> char { - self.keys[index] - } - - pub fn from_verbose(inp: &str) -> Option<Layout> { - let mut layout: [char; NUM_KEYS] = ['x'; NUM_KEYS]; - - 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; - k += 1; - } - if k > NUM_KEYS { - return None; - } - } - - return Some(Layout::char_array_to_layout(layout)); - } -} - -impl fmt::Display for Layout { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - formatter.write_str(&format_block_output(self.keys.into_iter())) - } -} - -#[derive(Copy, Clone)] -pub struct Evaluation { - keypress: [u32; NUM_KEYS], - total_keypress: u32, - sfb: [u32; 8], -} - -impl Evaluation { - pub fn new(keypress: [u32; NUM_KEYS], total_keypress: u32, sfb: [u32; 8]) -> Evaluation { - Evaluation { - keypress, - sfb, - total_keypress, - } - } - - fn output_eval(&self) -> String { - let mut result = String::new(); - let tot = self.total_keypress as f32; - - result += &"Percent per key:\n"; - result += &format_block_output(self.keypress.into_iter().map(|k| 100.0 * k as f32 / tot)); - - let mut finger_usages = [0; 8]; - for (i, &c) in self.keypress.iter().enumerate() { - finger_usages[KEY_TO_FINGER[i]] += c; - } - - result += "\nFinger usage: "; - let mut lh: f32 = 0.0; - let mut rh: f32 = 0.0; - for (i, &u) in finger_usages.iter().enumerate() { - let f = u as f32 / tot * 100.0; - result += &format!("{:>5.2}%{}", f, if i < 7 { ", " } else { "" }); - if i % 10 < 4 { - lh += f; - } else { - rh += f; - } - } - - result += &format!("\nHand usage: {:.2}% vs {:.2}%", lh, rh); - - result += "\nSame finger bigrams: "; - for (i, &u) in self.sfb.iter().enumerate() { - result += &format!( - "{:>6.3}%{}", - u as f32 / tot * 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); - - return result; - } -} - -impl fmt::Display for Evaluation { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - formatter.write_str(&self.output_eval()) - } -} - -// This is a silly amount of work to genericise the below... -trait ToMyString { - const BLANK_STRING: &'static str; - fn to_my_string(&self) -> String; -} - -impl ToMyString for char { - const BLANK_STRING: &'static str = " "; - fn to_my_string(&self) -> String { - self.to_string() - } -} - -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) - } -} - -fn format_block_output<T: Iterator<Item = S>, S: ToMyString>(things: T) -> String { - let mut result = String::new(); - for (i, t) in things.enumerate() { - result += &t.to_my_string(); - if i < NUM_KEYS - 1 { - result.push(' '); - } - if (i + 1) % 10 == 0 { - result.push('\n'); - if NUM_KEYS < 30 && i == 19 { - result += S::BLANK_STRING; - result.push(' ') - } - } else if (i < 20 && (i + 1) % 5 == 0) || (i == (NUM_KEYS - 20) / 2 + 19) { - result.push(' '); - } - if i + 1 >= NUM_KEYS { - break; - } - } - return result; -} diff --git a/src/main.rs b/src/main.rs deleted file mode 100644 index 4294484..0000000 --- a/src/main.rs +++ /dev/null @@ -1,118 +0,0 @@ -mod corpus; -mod layout; - -use rayon::prelude::*; - -use rand::prelude::*; -use rand_pcg::*; - -use corpus::*; -use layout::*; - -use std::time::Instant; - -const NUM_CONTESTANTS: usize = 128; -const NUM_PERSIST: usize = 8; - -// TODO: command line arguments to start at a given layout string, maybe read -// from file? Might as well make num_contestants and survive_threshold -// configurable, and number of swaps when generating new layout, and index -// finger threshold. - -struct Tournament<'a> { - rngs: Vec<Pcg64>, - top_prelayouts: Vec<(Prelayout, u32)>, - corpus: &'a Corpus, -} - -impl<'a> Tournament<'a> { - fn new_from_seed_prelayout(seed_prelayout: &Prelayout, corpus: &'a Corpus) -> Tournament<'a> { - let mut rngs: Vec<Pcg64> = Vec::new(); - for _ in 0..NUM_CONTESTANTS { - rngs.push(Pcg64::from_entropy()); - } - - let mut top_prelayouts: Vec<(Prelayout, u32)> = Vec::new(); - let score = corpus.prelayout_fitness(&seed_prelayout); - for _ in 0..NUM_PERSIST { - top_prelayouts.push((seed_prelayout.clone(), score)); - } - - Tournament { - rngs, - top_prelayouts, - corpus, - } - } - - fn run_round(&mut self) -> Option<Prelayout> { - let rngs = &mut self.rngs; - - let mut tournament = rngs - .into_par_iter() - .map(|mut rng| { - let layout = Prelayout::new_random_from( - &self.top_prelayouts[rng.gen_range(0..NUM_PERSIST)].0, - &mut rng, - ); - return (layout, self.corpus.prelayout_fitness(&layout)); - }) - .collect::<Vec<(Prelayout, u32)>>(); - - let best = self.top_prelayouts[0].1; - tournament.append(&mut self.top_prelayouts); - tournament.sort_by(|(_, lscore), (_, rscore)| lscore.cmp(rscore)); - - let result; - if tournament[0].1 < best { - result = Some(tournament[0].0); - } else { - result = None; - } - - for i in 0..NUM_PERSIST { - self.top_prelayouts.push(tournament[i]); - } - - result - } -} - -fn main() { - let corpus = Corpus::load("new.txt").unwrap(); - println!("{}", corpus); - - let seed_prelayout = Layout::from_verbose("QWERTYUIOPASDFGHJKL'ZXCVBNM,./") - .unwrap() - .as_prelayout(); - - let mut tournament = Tournament::new_from_seed_prelayout(&seed_prelayout, &corpus); - - let mut count: usize = 0; - let mut current = Instant::now(); - loop { - let improvement = tournament.run_round(); - - if let Some(prelayout) = improvement { - let layout = Layout::from_prelayout(&prelayout, &corpus); - let evl = corpus.evaluate_layout(&layout); - println!(""); - println!("================================================================================\n\n{}", - layout - ); - - println!("{}", evl); - } - - count += 1; - if count > 65535 { - let duration = current.elapsed(); - eprint!( - "\u{001b}[2K\u{001b}[1000D{} layouts/s", - (count * NUM_CONTESTANTS) as f32 / duration.as_millis() as f32 * 1000.0 - ); - current = Instant::now(); - count = 0; - } - } -} |