Skip to content

Instantly share code, notes, and snippets.

@fizbin
Created September 26, 2022 12:12
Show Gist options
  • Save fizbin/905a219af86adb95a6e7fd4bd26a507e to your computer and use it in GitHub Desktop.
Save fizbin/905a219af86adb95a6e7fd4bd26a507e to your computer and use it in GitHub Desktop.
Rust language solution to an ancient "Perl Quiz of the Week" (qotw21)
/*
* This program solves the puzzle
* https://perl.plover.com/qotw/e/021
*
* (In case that link goes away, a brief summary of the problem
* is to consider the free non-abelian group with 26 generators
* 'a' through 'z', under the equivalence relation that any two
* words found in the dictionary that are anagrams of each other
* are equivalent. Now determine which letters commute with which
* other letters, and specifically which letters are in the center.)
*
* It does so by reading the dictionary to determine all anagram
* pairs and then applying two strategies over and over again
* to ever known pair of equivalent strings, manipulating the
* set of everything known until it can't any further at which
* point it prints out a table of the letters which are known
* to commute and the list of other equivalences that are known
* and not derivable from the commutativity table.
*
* It's a bit surprising that this relatively simple approach
* suffices to wring every piece of information out of the
* Web2 word list, but it does. Presumably, more advanced reasoning
* strategies could be required for different dictionaries; however,
* the list of "Leftover facts" printed at the end should be
* enough to know whether this simple approach was enough for a given
* dictionary.
*/
use std::{
cell::Cell,
collections::{HashMap, HashSet},
fs::File,
io::{prelude::*, BufReader},
path::Path,
};
#[derive(Hash, Eq, PartialEq, Debug)]
struct Fact {
lhs: String,
rhs: String,
}
impl Fact {
// store facts sorted, so that we know that
// abcd=bcda is the same fact as bcda=abcd
fn new(lhs: &str, rhs: &str) -> Fact {
if lhs <= rhs {
Fact {
lhs: lhs.to_string(),
rhs: rhs.to_string(),
}
} else {
Fact {
lhs: rhs.to_string(),
rhs: lhs.to_string(),
}
}
}
}
struct WorldState {
// In a WorldState, we store single-letter-commutes facts (e.g. on=no) in 'single_commutes'
// and only use 'facts' for facts about longer strings
single_commutes: HashMap<char, HashSet<char>>,
facts: HashSet<Fact>,
}
impl WorldState {
fn new() -> WorldState {
WorldState {
single_commutes: HashMap::new(),
facts: HashSet::new(),
}
}
fn new_with_singles(single_commutes: &HashMap<char, HashSet<char>>) -> WorldState {
let mut singles = HashMap::new();
for (c, nbhs) in single_commutes {
singles.insert(*c, nbhs.clone());
}
WorldState {
single_commutes: singles,
facts: HashSet::new(),
}
}
fn add_fact(&mut self, lhs: &str, rhs: &str) {
if lhs.ne(rhs) {
match lhs.len() {
0 => (),
1 => (),
2 => {
self.single_commutes
.entry(lhs.chars().next().unwrap())
.or_default()
.insert(rhs.chars().next().unwrap());
self.single_commutes
.entry(rhs.chars().next().unwrap())
.or_default()
.insert(lhs.chars().next().unwrap());
}
_ => {
self.facts.insert(Fact::new(lhs, rhs));
}
}
}
}
}
fn reduce(state: WorldState) -> (WorldState, bool) {
// Take each fact and remove common characters from front/back of both sides
let mut retval = WorldState::new_with_singles(&state.single_commutes);
let mut found_something = false;
for fact in state.facts {
let lhsbytes = fact.lhs.as_bytes();
let rhsbytes = fact.rhs.as_bytes();
let mut i1: usize = 0;
let mut i2 = fact.rhs.len();
while i1 + 1 < i2 && lhsbytes[i1] == rhsbytes[i1] {
i1 += 1;
found_something = true;
}
while i2 > i1 + 1 && lhsbytes[i2 - 1] == rhsbytes[i2 - 1] {
i2 -= 1;
found_something = true;
}
retval.add_fact(&fact.lhs[i1..i2], &fact.rhs[i1..i2])
}
(retval, found_something)
}
fn scramble(state: WorldState) -> (WorldState, bool) {
// adjust WorldState facts by moving stuff to the front or the back as may
// help with a later reduce operation
let mut retval = WorldState::new_with_singles(&state.single_commutes);
let mut found_something = false;
for fact in state.facts {
let ourletters: HashSet<char> = fact.lhs.chars().collect();
let mut lhscopy: Vec<char> = fact.lhs.chars().collect();
let mut rhscopy: Vec<char> = fact.rhs.chars().collect();
let mut local_found: bool = false;
for c in ourletters {
// So for each letter, we see whether we can move the letter all
// the way to the left, or all the way to the right, based on the
// letters that we know commute. We only move a letter if we can
// move it all the way left/right on both lhs & rhs of the fact.
if state.single_commutes.contains_key(&c) {
let commutes_with = &state.single_commutes[&c];
let can_swap = Cell::new(true);
let finder = |c2: &char| {
if c == *c2 {
true
} else {
if !commutes_with.contains(c2) {
can_swap.replace(false);
}
false
}
};
// Can we move c all the way left?
let idx1: Option<usize> = lhscopy.iter().position(finder);
let idx2: Option<usize> = rhscopy.iter().position(finder);
if can_swap.get() {
match (idx1, idx2) {
(Some(i1), Some(i2)) => {
local_found = true;
// vec[0], vec[1], .. vec[i1-1], vec[i1] -> vec[i1], vec[0], vec[1], .. vec[i1-1]
for i in (0..i1).rev() {
lhscopy.swap(i, i + 1);
}
for i in (0..i2).rev() {
rhscopy.swap(i, i + 1);
}
}
(_, _) => (), // shouldn't happen
}
} else {
// Can we move c all the way right?
can_swap.replace(true);
let ridx1: Option<usize> = lhscopy.iter().rposition(finder);
let ridx2: Option<usize> = rhscopy.iter().rposition(finder);
if can_swap.get() {
match (ridx1, ridx2) {
(Some(i1), Some(i2)) => {
local_found = true;
// vec[i1], ..., vec[len()-1] -> vec[i1+1], ..., vec[len()-1], vec[i1]
for i in i1..(lhscopy.len() - 1) {
lhscopy.swap(i, i + 1);
}
for i in i2..(rhscopy.len() - 1) {
rhscopy.swap(i, i + 1);
}
}
(_, _) => (), // shouldn't happen
}
}
}
}
}
if local_found {
let lhsnew: String = lhscopy.into_iter().collect();
let rhsnew: String = rhscopy.into_iter().collect();
retval.add_fact(lhsnew.as_str(), rhsnew.as_str());
found_something = true;
} else {
retval.add_fact(fact.lhs.as_str(), fact.rhs.as_str())
}
}
(retval, found_something)
}
fn lines_from_file(filename: impl AsRef<Path>) -> Vec<String> {
let file = File::open(filename).expect("no such file");
let buf = BufReader::new(file);
buf.lines()
.map(|l| l.expect("Could not parse line"))
// Comment out the next line to limit us to only words that are already all lowercase
// (i.e. disallow use of proper nouns)
.map(|s| s.to_ascii_lowercase())
.filter(|w| w.chars().all(|f| f.is_lowercase()))
.collect()
}
fn make_initial_facts(wordlist: &[String]) -> Vec<Fact> {
let mut anamap: HashMap<String, Vec<&str>> = HashMap::new();
for word in wordlist {
let mut cvec: Vec<char> = word.chars().collect();
cvec.sort();
let sorted: String = cvec.into_iter().collect();
anamap.entry(sorted).or_default().push(word.as_str());
}
let mut result = Vec::new();
for value in anamap.values() {
if value.len() > 1 {
for n in 1..value.len() {
result.push(Fact::new(value[n - 1], value[n]));
}
}
}
result
}
fn main() {
let mut state = WorldState::new();
{
// Web2 is from https://perl.plover.com/qotw/words/Web2.gz
let lines = lines_from_file("Web2");
for fact in make_initial_facts(lines.as_slice()) {
state.add_fact(fact.lhs.as_str(), fact.rhs.as_str());
}
}
let mut working = true;
while working {
//println!("Interesting fact size: {}", state.facts.len());
(state, _) = scramble(state);
(state, working) = reduce(state);
}
println!("Commute summary:");
println!(" abcdefghijklmnopqrstuvwxyz");
let empty: HashSet<char> = HashSet::new();
for a in 'a'..='z' {
print!("{}:", a);
let commset = state.single_commutes.get(&a).unwrap_or(&empty);
let mut in_center = true;
for b in 'a'..='z' {
if a == b {
print!("\\");
} else if commset.contains(&b) {
print!("#");
} else {
print!(" ");
in_center = false;
}
}
if in_center {
print!(" (*)");
}
println!();
}
println!();
println!("Leftover facts:");
for fact in state.facts {
println!(" {}={}", fact.lhs, fact.rhs);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment