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

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

• Pour tout ensemble de deux points d'interrogation, faites en sorte que le point d'interrogation de gauche soit l'opposé du voisin de gauche et le point d'interrogation de droite l'opposé du voisin de droite. Par exemple, V??C devrait devenir VCVC. Une telle substitution ne peut jamais enlaidir une chaîne de caractères si elle ne l'était pas déjà.
• Pour tout ensemble de trois points d'interrogation ou plus, placez les points d'interrogation les plus à gauche et les plus à droite comme ci-dessus, puis alternez les points d'interrogation du milieu entre V et C. Cela peut aboutir à l'introduction de deux V ou C consécutifs, mais jamais de trois.

Donc, il nous reste deux cas simples.

• Vérifier si une chaîne est déjà laide est une simple regex.
• Le seul scénario dans lequel un singleton peut enlaidir une chaîne de caractères est celui où le point d'interrogation comporte deux voyelles d'un côté et quatre consonnes de l'autre ; mais vous ne pouvez pas simplement vérifier cela, car la substitution pourrait introduire de tels motifs (pensez à EE?FFF?EE). Mais à ce stade, vous pouvez vérifier en travaillant de gauche à droite, en résolvant chaque point d'interrogation singleton en insérant l'opposé du voisin de droite, à moins que cela n'enlaidisse la chaîne, et en vous arrêtant si le modèle deux voyelles / quatre consonnes est présent.

Answer 2

Une solution en Haskell :

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

La fonction tient un compte du nombre de voyelles et de consonnes consécutives qui ont été vues jusqu'au point actuel. S'il y en a trop, elle renvoie False . Si un point d'interrogation est trouvé, deux appels récursifs sont effectués, l'un comptant le point d'interrogation comme une voyelle, l'autre comme une consonne, en vérifiant si l'une de ces variations est agréable.

Answer 3

Voici la clé : la possibilité de passer du laid au beau est conditionnée par une certaine longueur de consonnes ou de voyelles. Ainsi, si la transformation d'un bloc en un bloc agréable implique nécessairement la laideur d'un autre bloc, cela ne peut pas être fait.

La mise en œuvre est laissée comme un exercice pour les personnes trop paresseuses pour faire leurs propres devoirs :-)

Answer 4

Ce que vous pouvez faire, c'est itérer sur chaque point d'interrogation et tester toutes les combinaisons possibles d'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à, elles sont toutes les deux moches.

Answer 5

Il y a un motif regex qui correspondra à la laideur :

[aeiouAEIOU]{3}|[a-zA-Z&&[^aeiouAEIOU]]{5}

Maintenant, si un ? se produit à l'intérieur d'une séquence de voyelles, vous pouvez la transformer en consonne. S'il se trouve dans une séquence de consonnes, vous pouvez le transformer en voyelle. Le problème se pose si le point d'interrogation apparaît sur une frontière :

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

Dans chacun de ces cas, il n'y a pas de solution. Maintenant, s'il y a deux points d'interrogation, l'un après l'autre, le problème se pose si les séquences sont :

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

Ceux-ci n'ont pas non plus de solution. S'il y a plus de deux points d'interrogation, alors vous pouvez les résoudre.

Donc, cherchez ces motifs, plus les motifs laids "purs". Si l'un d'eux se produit, vous ne pouvez pas vous transformer. Sinon, c'est bon.