Algorithme pour faire une ficelle agréable ou laid

Avez-vous essayé d'itération à travers tout l'alphabet et essayez chaque combinaison de voir si c'est «laid» ou non?

Essayez de remplacer chaque point d'interrogation avec une lettre, vérifiez la validité, c'est la manière la plus simple, la moins optimale. Par exemple:

EEF? D ??

Je commencerais à remplir dans le? Avec ces combinaisons:

aaa Aab Aac AAD

etc.

Edit: Non, vous n'avez pas à itérer sur tout l'alphabet, juste A et B suffisent. Ou vraiment, n'importe quelle voyelle et toute consonne.

Voici la clé: la transformabilité de laid à Nice est fondée sur une certaine longueur de consonnes ou de voyelles. Donc, si transformer un bloc à Nice serait nécessairement prédire la laideur d'un autre bloc, on ne peut pas être fait.

La mise en œuvre est laissée comme un exercice pour la personne trop paresseuse pour faire leurs propres devoirs. : -)

Ce que vous pouvez faire est de se déplacer sur chaque point d'interrogation et testez toute combinaison possible de l'insertion d'une voyelle ou d'un point d'interrogation.

Par exemple (v => voyelle, c => consonne)

1. "ee? FFFF"
   VVVCCCC
   VVCCCCC
   sont les deux possibilités et comme vous le savez déjà, ils sont tous les deux laids.

Il y a un modèle de regex qui correspondra à la laide: xxx pré>

maintenant, si un ? code> se produit à l'intérieur d'une séquence de voyelles, vous pouvez le transformer en un consonne. Si cela se produit à l'intérieur d'une séquence de consonnes, vous pouvez la transformer en voyelle. Le problème se produit si le point d'interrogation apparaît sur une limite: p> xxx pré>

dans chacun de ces cas, il n'y a pas de solution. Maintenant, s'il y a deux marques d'interrogation, l'une après l'autre, le problème se produit si les séquences sont les suivantes: P>

[aeiouAEIOU]{2}\?\?[aeiouAEIOU]{2}
[a-zA-Z&&[^aeiouAEIOU]]{4}\?\?[a-zA-Z&&[^aeiouAEIOU]]{4}

Une solution dans HASKELLL:

import System (getArgs)

nicePart :: Int -> Int -> String -> Bool
nicePart 3 _ _  = False
nicePart _ 5 _  = False
nicePart _ _ "" = True
nicePart v c ('?':as) = nicePart (v+1) 0 as || nicePart 0 (c+1) as
nicePart v c (a:as)
   | a `elem` "AEIOU" = nicePart (v+1) 0 as
   | otherwise        = nicePart 0 (c+1) as

nice :: String -> Bool
nice as = nicePart 0 0 as

main = getArgs >>= print . nice . unwords

Notez que les seules chaînes qui pourraient potentiellement être laides sont celles qui sont déjà laides en vertu des lettres données ou celles qui ne contiennent que des marques d'interrogation singleton. Voici le croquis de la preuve:

• Pour tout ensemble de deux marques d'interrogation, rendez-vous à gauche sur l'opposé du voisin de gauche et la bonne question marque l'opposé du bon voisin. Par exemple. V ?? ​​c devrait devenir vcvc. Une telle substitution ne peut jamais transformer une corde laide si elle n'était pas déjà laide.
• Pour tout ensemble de trois marques d'interrogation ou plus, définissez les points d'interrogation les plus à gauche et les plus à droite comme ci-dessus, puis alternez les points d'interrogation moyens entre V et C. Cela pourrait entraîner une introduction de deux v ou C consécutifs, mais jamais trois. < / li>

  Alors, nous sommes partis avec deux cas simples.

  • Vérification Si une chaîne est déjà laid est une regex simple.
  • Le seul scénario dans lequel un singleton peut transformer une chaîne laids est si le point d'interrogation a deux voyelles d'un côté et de quatre consonnes de l'autre côté; Mais vous ne pouvez pas simplement vérifier ceux-ci, car la substitution pourrait introduire de tels modèles (considérer EE? FFF? EE). Mais à ce stade, vous pouvez vérifier en travaillant de gauche à droite, résolvant chaque point d'interrogation singleton en insérant le contraire du voisin droit, à moins que cela ne tournerait la chaîne laid et l'arrêt si le motif de la voyelle / quatre consonnes est présent.

Comme il a été souligné, il y a une approche brutale de force brute qui fonctionnera très inefficace. Le plaisir consiste à ajouter des gains d'efficacité qui éliminent la liste 2 ** n des possibilités.

1. Premièrement, faites une correspondance rapide "laid de regex" contre la chaîne d'origine, avant tout? substitution. Si vous obtenez un match, la chaîne ne peut évidemment pas être rendue belle.

2. Suivant look pour célibataire? opportunités, celles? qui sont flanqués des deux côtés par aucun autre? pour quatre positions. Voir si l'une d'entre elles doit être corrigée comme V ou C, ou si elles disqualifient entièrement la chaîne entièrement (comme dans l'exemple de OP). S'ils doivent être réparés V ou C, faites-le et continuez.

3. Les stratégies ultérieures sont plus impliquées: double? Les segments impliquent la vérification de gauche et non? Pour une exigence v / c basée sur leurs caractères flanques gauche / droite respectifs, etc.

Voici une solution en C # qui semble fonctionner d'une poignée de cas de test que j'ai jeté dessus. [Certaines parties de l'expression de 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;
}