Longest shortest word ladder

Inspired by a statue in the Wellington botanic garden, I wanted to find the two words with the longest shortest path between them. For the dictionary I used, the here's the only path of length 13 for six letter words:

BUTLER
BUTTER
BETTER
LETTER
LATTER
MATTER
MASTER
FASTER
FOSTER
POSTER
POSTED
HOSTED
HOSTEL

A first version in python with networkx was too slow, so I had codex write it in rust and implement Floyd-Warshall directly.

Using a word list of the 10000 most common english words, the above was the only path length 13 for 6 letter words. For four letter words there are 50 paths of length 21, and for five letter words there are 13 paths of length 37.

Googling this afterwards, I found there's a pretty old game about this.

I then had codex write an implementation without any guidance from me. It implemented BFS from every word to find the furthest, which ran faster, presumably because it's sparse and there are many disconnected components.

use std::env;
use std::fs;
use std::process;

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() != 3 {
        eprintln!("Usage: {} <filename> <N>", args[0]);
        process::exit(1);
    }

    let filename = &args[1];
    let n: usize = match args[2].parse() {
        Ok(value) if value > 0 => value,
        _ => {
            eprintln!("N must be an integer greater than 0");
            process::exit(1);
        }
    };

    let contents = match fs::read_to_string(filename) {
        Ok(data) => data,
        Err(err) => {
            eprintln!("Failed to read {}: {}", filename, err);
            process::exit(1);
        }
    };

    let filtered: Vec<String> = contents
        .lines()
        .map(|line| line.trim().to_string())
        .filter(|word| word.chars().count() == n)
        .map(|word| word.to_uppercase())
        .collect();

    let sentinel = (2 * filtered.len()) as i32;
    let mut matrix = build_matrix(&filtered, sentinel);
    floyd_warshall(&mut matrix);

    if cfg!(debug_assertions) {
        print_words(&filtered);
        print_matrix(&matrix);
    }

    report_max_pairs(&filtered, &matrix, sentinel);
}

fn build_matrix(words: &[String], sentinel: i32) -> Vec<Vec<i32>> {
    let m = words.len();
    let mut matrix = vec![vec![sentinel; m]; m];

    for i in 0..m {
        matrix[i][i] = 0;
        for j in (i + 1)..m {
            if differ_by_one(&words[i], &words[j]) {
                matrix[i][j] = 1; // Connection weight for single-character difference.
                matrix[j][i] = 1;
            }
        }
    }

    matrix
}

fn differ_by_one(a: &str, b: &str) -> bool {
    a.chars().zip(b.chars()).filter(|(ca, cb)| ca != cb).count() == 1
}

fn floyd_warshall(matrix: &mut [Vec<i32>]) {
    let m = matrix.len();
    for k in 0..m {
        for i in 0..m {
            for j in 0..m {
                let through_k = matrix[i][k] + matrix[k][j];
                if matrix[i][j] > through_k {
                    matrix[i][j] = through_k;
                }
            }
        }
    }
}

fn report_max_pairs(words: &[String], matrix: &[Vec<i32>], sentinel: i32) {
    let m = words.len();
    if m < 2 {
        return;
    }

    let mut max_value: Option<i32> = None;
    for (i, row) in matrix.iter().enumerate().take(m) {
        for &dist in row.iter().skip(i + 1) {
            if dist != sentinel && dist >= 0 {
                max_value = match max_value {
                    Some(current) if dist <= current => Some(current),
                    _ => Some(dist),
                };
            }
        }
    }

    if let Some(max_value) = max_value {
        let mut pair_count = 0usize;
        let mut path_count = 0usize;

        for (i, row) in matrix.iter().enumerate().take(m) {
            for (j, &dist) in row.iter().enumerate().skip(i + 1) {
                if dist != max_value {
                    continue;
                }

                println!("{} {}", words[i], words[j]);
                let mut path = vec![i];
                let mut all_paths = Vec::new();
                collect_paths(i, j, words, matrix, sentinel, &mut path, &mut all_paths);
                pair_count += 1;
                path_count += all_paths.len();
                for route in all_paths {
                    let text = route
                        .iter()
                        .map(|&idx| words[idx].clone())
                        .collect::<Vec<_>>()
                        .join(" -> ");
                    println!("  {}", text);
                }
            }
        }

        println!("Pairs: {}", pair_count);
        println!("Paths: {}", path_count);
        println!("Path length: {}", max_value + 1);
    }
}

fn collect_paths(
    current: usize,
    target: usize,
    words: &[String],
    dist: &[Vec<i32>],
    sentinel: i32,
    path: &mut Vec<usize>,
    all_paths: &mut Vec<Vec<usize>>,
) {
    if current == target {
        all_paths.push(path.clone());
        return;
    }

    let remaining = dist[current][target];
    if remaining <= 0 || remaining >= sentinel {
        return;
    }

    for next in 0..words.len() {
        if next == current {
            continue;
        }
        if differ_by_one(&words[current], &words[next]) && dist[next][target] == remaining - 1 {
            path.push(next);
            collect_paths(next, target, words, dist, sentinel, path, all_paths);
            path.pop();
        }
    }
}

fn print_words(words: &[String]) {
    for word in words {
        println!("{}", word);
    }
}

fn print_matrix(matrix: &[Vec<i32>]) {
    for row in matrix {
        let line = row
            .iter()
            .map(|value| value.to_string())
            .collect::<Vec<_>>()
            .join(" ");
        println!("{}", line);
    }
}