Подтвердить что ты не робот

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

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

Пример -

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

  • "Н?? LOWOR??" - Можно сделать красивым.

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

Ответ 6

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

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

КЭЭ?: D??

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

AAA AAB AAC AAD

и др.

EDIT: Нет, вам не нужно перебирать весь алфавит, достаточно A и B. Или действительно, просто какой-нибудь гласный и любой согласный.

Ответ 7

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

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

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

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

Ответ 8

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

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 (уродливая).