Алгоритм, чтобы сделать строку красивой или уродливой

Question

Мне трудно найти алгоритм для следующей загадки: Строка называется некрасивой, если в ней 3 гласных подряд, 5 согласных подряд или оба. Строка называется хорошей, если она не безобразна. Вам дана строка s, состоящая из заглавных букв ('A' - 'Z') и вопросительных знаков ('?'). Можете ли вы найти алгоритм, который говорит, можно ли сделать строку удобной, заменив знаки вопроса алфавитами?

Пример -

1. "EE? FFFF" - Не могу быть хорошим. Вставка согласного или гласного сделает его уродливым.

2. "H ?? LOWOR ??" - Можно сделать красиво.

P.S. Не домашнее задание, а часть головоломки в интернете.

Answer 1

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

• Для любого набора из двух вопросительных знаков сделайте левый вопросительный знак противоположным левому соседу, а правый вопросительный знак - противоположному правому соседу. Например. V ?? ​​C должен стать VCVC. Такая замена никогда не может превратить строку в некрасивую, если она еще не была некрасивой.
• Для любого набора из трех или более вопросительных знаков установите крайний левый и самый правый вопросительные знаки, как указано выше, а затем чередуйте средние вопросительные знаки между V и C. Это может привести к введению двух последовательных букв V или C, но не трех.

Итак, у нас осталось два простых случая.

• Проверка, является ли строка уже безобразной, является простым регулярным выражением.
• Единственный сценарий, в котором синглтон может превратить строку в некрасивую, - это если знак вопроса содержит две гласные на одной стороне и четыре согласных на другой стороне; но вы не можете просто проверить их, поскольку подстановка может привести к таким шаблонам (рассмотрим EE? FFF? EE). Но в этот момент вы можете проверить, работая слева направо, решая каждый вопросительный знак синглтона, вставляя противоположность правому соседу, если это не повлечет за собой уродливую строку, и останавливается, если присутствует шаблон с двумя гласными / четырьмя согласными.

Answer 2

Решение в 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. Если знак вопроса найден, делается два рекурсивных вызова, один считается знак вопроса как гласный, другой как согласный, проверяя, хорош ли любой из этих вариантов.

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

Например (V => гласный, C => согласный)

1. "EE? FFFF"
   VVVCCCC
   VVCCCCC
   это две возможности, и, как вы уже знаете, они оба безобразны.

Answer 6

Вот решение в 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;
}

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

Answer 7

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

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

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

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

Answer 8

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

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

КЭЭ? D ??

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

AAA AAB AAC AAD

и т.д.

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