Алгоритм для создания Строки хорошей или ужасной

Решение на 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

Функция ведет подсчет количества последовательных гласных и согласных, которые были замечены до текущего момента. Если их слишком много, возвращается False . При обнаружении вопросительного знака выполняются два рекурсивных вызова: один считает вопросительный знак как гласный, второй - как согласный, проверяя, подходит ли какой-либо из этих вариантов.

Вот ключ: возможность преобразования от уродливого к красивому основывается на определенной длине согласных или гласных. Так что, если преобразование одного блока в хороший обязательно предопределит уродство другого блока, это невозможно.

Реализация оставлена ​​в качестве упражнения для человека, слишком ленивого, чтобы делать свою домашнюю работу. : -)

Что вы можете сделать, так это перебрать каждый вопросительный знак, VVVCCCC
VVCCCCC
это две возможности, и, как вы уже знаете, обе они уродливы.

Существует шаблон регулярного выражения, который будет соответствовать уродливому:

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

Теперь, если ? встречается внутри последовательности гласных, вы можете превратить его в согласный. Если это происходит внутри последовательности согласных, вы можете превратить ее в гласную. Проблема возникает, если на границе появляется вопросительный знак:

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

В каждом из этих случаев решения нет. Теперь, если есть два вопросительных знака, один за другим, проблема возникает, если последовательности следующие:

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

У них также нет решения. Если вопросительных знаков больше двух, то вы можете его решить.

Итак, ищите в них шаблоны, а также «чистые» уродливые шаблоны. Если что-то из них произойдет, вы не сможете трансформироваться. В противном случае ничего страшного.

Вы пробовали перебирать весь алфавит и пробовать каждую комбинацию, чтобы увидеть, «некрасиво» она или нет?

Попробуйте заменить каждый вопросительный знак буквой, затем проверьте правильность, это самый простой и наименее оптимальный способ. Например:

EEF? D ??

Я бы начал с заполнения? с этими комбинациями:

AAA AAB AAC AAD

и т. Д.

РЕДАКТИРОВАТЬ: Нет, вам не нужно перебирать весь алфавит, достаточно только A и B. На самом деле, любой гласный и любой согласный.

Как уже указывалось, есть грубый и крайне неэффективный подход, который будет работать. Самое интересное в добавлении эффективности, которая сокращает список возможностей 2 ** n.

1. Во-первых, выполнить быстрое сопоставление "уродливого регулярного выражения" с исходной строкой перед любым? подмена. Если вы найдете совпадение, очевидно, что строку невозможно сделать красивой.

2. А теперь искать сингл? возможности, те? которые с обеих сторон не окружены никем другим? на четыре позиции. Посмотрите, должны ли какие-либо из них быть зафиксированы как V или C, или они полностью дисквалифицируют строку (как в примере OP 1). Если они должны быть зафиксированы V или C, сделайте это и продолжайте.

3. Последующие стратегии становятся более вовлеченными: удвоение? сегменты предполагают проверку как слева, так и справа? для требования V / C на основе их соответствующих символов левого / правого фланга и т. д.

Вот решение на C #, которое, похоже, работает на нескольких тестовых примерах, которые я ему использовал. [Части выражения регулярного выражения были заимствованы у предыдущего ответчика.]

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

Сначала проверяется данное слово как есть, чтобы увидеть, некрасиво ли оно (включая вопросительные знаки, если они есть). Затем он перебирает слово, заменяя первое "?" как с гласной, так и с согласной, и называет себя, используя новое слово. Если замена гласного и согласного не может сделать его приятным, тогда эта ветвь вернет false (некрасиво).