Skip to content

Instantly share code, notes, and snippets.

@macournoyer
Last active March 20, 2019 01:37
Show Gist options
  • Save macournoyer/c891d3a9233c18778252c8a367ee68c6 to your computer and use it in GitHub Desktop.
Save macournoyer/c891d3a9233c18778252c8a367ee68c6 to your computer and use it in GitHub Desktop.
/// A solver for Ruzzle (https://www.maginteractive.com/games/ruzzle/)
/// Finds all the word combinations in a 4x4 grid of letters.
/// Requires a dictionnary (one word per line) in words.txt.
use std::collections::HashSet;
use std::fs::File;
use std::io::{self, BufReader};
use std::io::prelude::*;
const MIN_WORD_SIZE: usize = 5;
const MAX_WORD_SIZE: usize = 12;
// Possible moves from a given letter position
static MOVES : [[isize; 8]; 16] = [
[1,4,5,0,0,0,0,0],[-1,1,3,4,5,0,0,0],[-1,1,3,4,5,0,0,0],[-1,3,4,0,0,0,0,0],
[-4,-3,1,4,5,0,0,0],[-1,-3,-4,-5,1,3,4,5],[-1,-3,-4,-5,1,3,4,5],[-1,-4,-5,3,4,0,0,0],
[-4,-3,1,4,5,0,0,0],[-1,-3,-4,-5,1,3,4,5],[-1,-3,-4,-5,1,3,4,5],[-1,-4,-5,3,4,0,0,0],
[-3,-4,1,0,0,0,0,0],[-1,-3,-4,-5,1,0,0,0],[-1,-3,-4,-5,1,0,0,0],[-1,-4,-5,0,0,0,0,0]
];
struct Board {
dictionary: HashSet<String>,
letters: String,
}
impl Board {
pub fn letter_at(&self, i: usize) -> String {
self.letters.chars().nth(i).expect(&format!("No letter at {}", i)).to_string()
}
pub fn find_words(&self) -> HashSet<String> {
let mut found = HashSet::new();
for i in 0..16 {
found.extend(self.find_from_letter(i, self.letter_at(i), vec![i]));
}
found
}
pub fn find_from_letter(&self, i: usize, word: String, mut visited: Vec<usize>) -> HashSet<String> {
let mut found = HashSet::new();
for m in &MOVES[i] {
if *m == 0 { continue; }
let new_i = (i as isize + m) as usize;
if visited.contains(&new_i) { continue; }
visited.push(new_i);
let word = format!("{}{}", word, self.letter_at(new_i));
if word.len() >= MIN_WORD_SIZE && self.dictionary.contains(&word) {
found.insert(word.clone());
}
if word.len() <= MAX_WORD_SIZE {
found.extend(self.find_from_letter(new_i, word.clone(), visited.clone()));
}
}
found
}
}
fn main() {
println!("Loading dictionary ...");
let dictionary = load_dict("words.txt");
println!("{} words loaded", dictionary.len());
// let letters = "erpdoauirtgeeona".to_string();
let mut letters = String::new();
println!("Enter 16 letters: ");
io::stdin().read_to_string(&mut letters).unwrap();
letters.pop(); // Remove \n
let board = Board { dictionary, letters };
println!("Found words: {:?}", board.find_words());
}
fn load_dict(file: &str) -> HashSet<String> {
let mut words = HashSet::new();
let f = File::open(file).unwrap();
let reader = BufReader::new(f);
for line in reader.lines() {
words.insert(line.unwrap());
}
words
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment