Algorithme pour rendre une chaîne de caractères belle ou moche

Question

J'ai du mal à trouver un algorithme pour l'énigme suivante Une chaîne est dite laide si elle comporte 3 voyelles à la suite, ou 5 consonnes à la suite, ou les deux. Une chaîne est dite belle si elle n'est pas laide. On vous donne une chaîne s, composée de lettres majuscules ('A'-'Z') et de points d'interrogation ('?'). Pouvez-vous trouver un algorithme qui indique si la chaîne peut être rendue agréable en remplaçant les points d'interrogation par des alphabets ?

Exemple -

1. "EE?FFFF" - On ne peut pas être gentil. Insérer une consonne ou une voyelle le rendrait laid.

2. "H??LOWOR ??" - On peut le rendre agréable.

P.S. - Pas un devoir, mais une partie d'un puzzle de programmation sur Internet.

Answer 1

Avez-vous essayé d'itérer à travers tout l'alphabet et d'essayer toutes les combinaisons pour voir si c'est "laid" ou non ?

Essayez de remplacer chaque point d'interrogation par une lettre puis vérifiez la validité, c'est la méthode la plus simple et la moins optimale. Par exemple :

EEF?D ??

Je commencerais par remplir les ? avec ces combinaisons :

AAA AAB AAC AAD

etc.

EDIT : Non, vous n'avez pas besoin d'itérer sur tout l'alphabet, juste A et B sont suffisants. Ou vraiment, juste n'importe quelle voyelle et n'importe quelle consonne.

Answer 2

Comme cela a été souligné, il existe une approche brutale et très inefficace qui fonctionnera. Le plaisir est d'ajouter des efficacités qui réduisent la 2**nième liste de possibilités.

1. Tout d'abord, effectuez une rapide correspondance "regex laide" avec la chaîne originale, avant toute substitution ? Si vous obtenez une correspondance, il est évident que la chaîne ne peut pas être rendue agréable.

2. Ensuite, recherchez les opportunités uniques, celles qui ne sont flanquées d'aucune autre position des deux côtés. Voyez si l'une d'entre elles doit être fixée en V ou en C, ou si elle disqualifie entièrement la corde (comme dans l'exemple 1 du PO). Si elles doivent être fixées en V ou en C, faites-le et continuez.

3. Les stratégies suivantes sont plus complexes : les segments double ? impliquent la vérification des deux ? gauche et droite pour une exigence de V/C basée sur leurs caractères de flanc gauche/droite respectifs, etc.

Answer 3

Voici une solution en C# qui semble fonctionner à partir d'une poignée de cas de test que je lui ai soumis. [Certaines parties de l'expression regex ont été empruntées à un répondeur précédent].

public static bool IsWordNiceable(string word, int maxVowels, int maxConsonants)
{
    if (IsUgly(word, maxVowels, maxConsonants)) return false;

    int i = 0;
    while ((i = word.IndexOf('?', i)) != -1)
    {
        string newWord = word.Substring(0, i) + "a" + word.Substring(i+1);
        bool vowelMakesNice = IsWordNiceable(newWord, maxVowels, maxConsonants);

        newWord = word.Substring(0, i) + "b" + word.Substring(i + 1);
        bool consonantMakesNice = IsWordNiceable(newWord, maxVowels, maxConsonants);

        if (!(vowelMakesNice || consonantMakesNice)) return false;
        i++;
    }

    return true;
}

private static bool IsUgly(string word, int maxVowels, int maxConsonants)
{
    string consonants = "bcdfghjklmnpqrstvwxyz";
    string vowels = "aeiou";
    string uglyRegex = string.Format("([{0}]{{{1},{1}}})|([{2}]{{{3},{3}}})", vowels, maxVowels, consonants, maxConsonants);

    Match match = Regex.Match(word.ToLower(), uglyRegex);
    return match.Success;
}

Elle teste d'abord le mot donné tel quel pour voir s'il est laid (y compris les points d'interrogation, le cas échéant). Puis elle boucle sur le mot, en remplaçant le premier " ?" par une voyelle et une consonne, et s'appelle en utilisant le nouveau mot. Si le remplacement des voyelles et des consonnes ne parvient pas à rendre le mot agréable, alors cette branche renvoie false (laid).