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

Have you tried iterating through the entire alphabet and trying every combination to see if it's 'ugly' or not?

Try substituting each question mark with a letter then check the validity, this is the easiest, least-optimal way. For example:

EEF?D??

I would start off filling in the ? with these combinations:

AAA AAB AAC AAD

etc.

EDIT: No you do not have to iterate over the entire alphabet, just A and B are enough. Or really, just any vowel and any consonant.

Answer 2

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. :-)

Answer 3

What you can do is iterate over each question mark, and test every possible combination of either inserting a vowel or a question mark.

For example (V => vowel, C => consonant)

1. "EE?FFFF"
   VVVCCCC
   VVCCCCC
   are the two possibilities, and as you know already, they are both ugly.

Answer 4

There is a regex pattern that will match the ugly:

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

Now, if a ? happens inside a sequence of vowels, you can turn it into a consonant. If it happens inside a sequence of consonants, you can turn it into a vowel. The problem happens if the question mark appears on a boundary:

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

In each of these cases, there is no solution. Now, if there are two question marks, one after the other, the problem happens if the sequences are:

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

These also have no solution. If there is more than two question marks, then you can solve it.

So, search for those for patterns, plus the "pure" ugly patterns. If any of them happens, you can't transform. Otherwise, it's ok.

Answer 5

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 6

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 7

As has been pointed out, there is a brute-force, grossly inefficient approach that will work. The fun is in adding efficiencies that trim the 2**n list of possibilities.

1. First, do a quick "ugly regex" match against the original string, before any ? substitution. If you get a match, the string obviously cannot be made nice.

2. Next look for single ? opportunities, those ? that are flanked on both sides by no other ? for four positions. See if any of these must be fixed as either V or C, or whether they disqualify the string entirely (as in OP's example 1). If they must be fixed V or C, do so and continue.

3. Subsequent strategies get more involved: double ? segments involve checking both left and right ? for a V/C requirement based on their respective left/right flanking characters, etc.

Answer 8

Here's a solution in C# that seems to work from a handful of test cases that I threw at it. [Parts of the regex expression were borrowed from a previous answerer.]

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;
}

This first tests the given word as-is to see if it's ugly (including question marks, if any). Then it loops through the word, replacing the first "?" with both a vowel and a consonant, and calls itself using the new word. If both the vowel and consonant replacement fail to make it nice, then that branch returns false (ugly).