Created
April 14, 2020 10:53
-
-
Save ritesh/34923c123e1f791e50a9e1285e2450c4 to your computer and use it in GitHub Desktop.
Brute force anagram
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::fs::File; | |
use std::io::{self, BufRead}; | |
use std::path::Path; | |
use rand::{thread_rng, Rng}; | |
use std::collections::HashSet; | |
use trie_rs::TrieBuilder; | |
// A silly program that finds words in a single word anagram using brute-force | |
// We use a data structure called a Trie: https://en.wikipedia.org/wiki/Trie | |
// to store a dictionary of words | |
// We take the jumbled up word and repeatedly shuffle it until we can find it in the dictionary | |
// We only try about 10000 times but that seems to work well enough for childish anagrams | |
// A clever-er solution would be to use n-grams to whittle down the search space | |
fn main() { | |
let mut builder = TrieBuilder::new(); | |
if let Ok(lines) = read_lines("/usr/share/dict/words") { | |
for line in lines { | |
if let Ok(word) = line { | |
builder.push(word); | |
} | |
} | |
} | |
let trie = builder.build(); | |
let mut rng = thread_rng(); | |
let mut word = "noolbal".to_string(); | |
let mut found_words:HashSet<String> = HashSet::new(); | |
for _i in 0..10000 { | |
let mut wordbytes = word.clone().into_bytes(); | |
if trie.exact_match(&word) { | |
found_words.insert(word); | |
} | |
rng.shuffle(&mut wordbytes); | |
word = String::from_utf8(wordbytes).unwrap(); | |
} | |
println!("Found: {:?}", found_words); | |
} | |
//via : https://doc.rust-lang.org/stable/rust-by-example/std_misc/file/read_lines.html | |
fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<File>>> | |
where P: AsRef<Path>, { | |
let file = File::open(filename)?; | |
Ok(io::BufReader::new(file).lines()) | |
} |
Author
ritesh
commented
Apr 14, 2020
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment