Algorithm to make a String nice or ugly

Question

Im having difficulty finding an algorithm for the following puzzle- A string is called ugly if it has 3 vowels in a row, or 5 consonants in a row, or both. A string is called nice if it is not ugly. You are given a string s, consisting of uppercase letters ('A'-'Z') and question marks ('?'). Can you find an algorithm that tells if the string can be made nice by substituting the question marks with alphabets?

Example -

1. "EE?FFFF" - Cant be made nice. Inserting either a consonant or a vowel would make it ugly.

2. "H??LOWOR??" - Can be made nice.

P.S - Not homework, but a part of a programming puzzle on the internet.

Answer 1

Note that the only strings that might potentially be ugly are those that are already ugly by virtue of the given letters or those which contain only singleton question marks. Here's the sketch of the proof:

• For any set of two question marks, make the left question mark the opposite of the left neighbor and the right question mark the opposite of the right neighbor. E.g. V??C should become VCVC. Such a substitution can never turn a string ugly if it was not already ugly.
• For any set of three or more question marks, set the leftmost and rightmost question marks as above and then alternate the middle question marks between V and C. This might result in introducing two consecutive V's or C's, but never three.

So, we're left with two simple cases.

• Checking if a string is already ugly is a straightforward regex.
• The only scenario in which a singleton can turn a string ugly is if the question mark has two vowels to one side and four consonants to the other side; but you can't just check for those, as substitution might introduce such patterns (consider EE?FFF?EE). But at this point, you can check by working from left to right, resolving each singleton question mark by inserting the opposite of the right neighbor unless that would turn the string ugly and stopping if the two vowel / four consonant pattern is present.

Answer 2

A solution in 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

The function keeps a count of how many consecutive vowels and consonants have been seen up to the current point. If there are too many it returns False. If a question mark is found, two recursive calls are made, one counting the question mark as a vowel, one as a consonant, checking if any of these variations is nice.

Answer 3

Here's the key: the transformability from ugly to nice is predicated upon a certain length of either consonants or vowels. So if transforming one block to nice would necessarily predicate the ugliness of another block, it cannot be done.

The implementation is left as an exercise for the person too lazy to do their own homework. :-)