Chopping words, une solution

I will solve your problem and you will pay me.

— Paul Rand à Steve Jobs lorsque ce dernier lui demanda de designer le logo de NeXT.

Un problème croisé au hasard des internets: Chopping Words. L'idée est de former une chaîne de mots où chaque entrée est obtenue en retirant une lettre du mot précédent — appelons cela une chaîne de dérivation. Par exemple, une chaîne de dérivation possible du mot poisse est: poisse → poise → pois → pis → pi.

L'objectif est évidemment d'écrire un programme qui détermine, pour un mot donné, quel est l'ensemble des chaînes de dérivation possibles. La solution ne fait que quelques lignes réparties dans deux fonctions.

La première fonction, chops, est toute simple. Elle génère toutes les déclinaisons possibles pour un mot. Par exemple, pour le mot plant, avec un dictionnaire anglais, les déclinaisons retournées seraient lant et pant.

vector<string> chops(const string& word, const Dict& dict) {
    vector<string> words;

    for (string::size_type i = 0; i < word.size(); ++i) {
        string subword(word);
        subword.erase(i, 1);
        if (dict.contains(subword)) {
            words.push_back(subword);
        }
    }

    return words;
}

La seconde fonction, chains, est plus subtile. Pour chaque déclinaison du mot d'entrée, celle-ci génère récursivement les sous-chaînes de dérivation; la chaîne de dérivation d'un mot de 2 lettres ou moins ne contenant que ce mot.

vector<list<string>> chains(const string& word, const Dict& dict) {
    if (word.size() <= 2) {
        return { { word } };
    }

    vector<list<string>> results;

    for (string subword : chops(word, dict)) {
        for (list<string> chain : chains(subword, dict)) {
            chain.push_front(word);
            results.push_back(chain);
        }
    }

    return results;
}

Voici les chaînes de dérivation obtenues pour le mot planet avec un dictionnaire anglais.

Le problème d'origine sur Programming Praxis: Chopping Words.