Question

Проблема: Я пытаюсь извлечь действительный режим игры для Защиты Древних (DotA) из названия игры, используя C ++.

Детали:

Имена игр могут содержать не более 31 символа
Существует три категории игровых режимов: основной, дополнительный и разный.
- Может быть выбран только 1 основной режим игры
- Некоторые основные режимы игры несовместимы с некоторыми дополнительными режимами игры
- Некоторые дополнительные режимы игры несовместимы с другими дополнительными режимами игры
- Различные режимы игры можно комбинировать со всеми другими режимами игры

Вот список различных игровых режимов с диаграммой, показывающей, с какими дополнительными режимами совместим каждый режим (X означает несовместимый):

// Only 1 primary allowed
static char *Primary[] = {
          // Compatible with > | dm | rv | mm | du | sh | aa | ai | as | id | em | np | sc | om | nt | nm | nb | ro | mo | sp | 
    "ap", // All Pick          |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "ar", // All Random        |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "tr", // Team Random       | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "mr", // Mode Random       | X  | X  |    |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "lm", // League Mode       | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |    |
    "rd", // Random Draft      | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "vr", // Vote Random       | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "el", // Extended League   | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |    |
    "sd", // Single Draft      | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "cm", // Captains Mode     | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  | X  |
    "cd"  // Captains Draft    | X  | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
};

static char *Secondary[] = {
          // Compatible with > | dm | rv | mm | du | sh | aa | ai | as | id | em | np | sc | om | nt | nm | nb | ro | mo | sp | 
    "dm", // Death Match       |    | X  | X  |    | X  | X  | X  | X  |    |    |    |    |    |    |    |    | X  | X  |    |
    "rv", // Reverse Mode      | X  |    |    |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "mm", // Mirror Match      | X  |    |    |    | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "du", // Duplicate Mode    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "sh", // Same Hero         | X  | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "aa", // All Agility       | X  |    |    |    |    |    | X  | X  |    |    |    |    |    |    |    |    |    |    |    |
    "ai", // All Intelligence  | X  |    |    |    |    | X  |    | X  |    |    |    |    |    |    |    |    |    |    |    |
    "as", // All Strength      | X  |    |    |    |    | X  | X  |    |    |    |    |    |    |    |    |    |    |    |    |
    "id", // Item Drop         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "em", // Easy Mode         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "np", // No Powerups       |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "sc", // Super Creeps      |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | 
    "om", // Only Mid          |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nt", // No Top            |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nm", // No Middle         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    "nb", // No Bottom         |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | 
    "ro", // Range Only        | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | X  |    | 
    "mo", // Melee Only        | X  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    | X  |    |    | 
    "sp"  // Shuffle Players   |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
};

// These options are always available
static char *Misc[] = {
    "ns", // No Swap
    "nr", // No Repick
    "ts", // Terrain Snow
    "pm", // Pooling Mode
    "oi", // Observer Info
    "mi", // Mini Heroes
    "fr", // Fast Respawn
    "so"  // Switch On
};

Примеры: Вот несколько примеров ввода с желаемым выводом:

"DotA v6.60 -RDSOSP USA / CA LC!" -> "rdsosp"

"DOTA AREMDM USA LC" -> "aremdm"

"DotA v6.60 -ApEmDuSpId USA BL" -> "apemduspid"

Примечания: Решение не обязательно должно содержать фактический код, псевдокод и даже просто объяснение того, как вы будете обращаться с ним, является приемлемым и предпочтительным. Кроме того, решение должно быть достаточно гибким, чтобы можно было легко добавить другой режим игры. Также можно предположить, что в названии игры режим игры всегда будет начинаться с основного режима игры.

Результат:

#include <cstdarg>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <vector>

std::map<std::string, std::vector<std::string> > ModeCompatibilityMap;

static const unsigned int PrimaryModesCount = 11;
static char *PrimaryModes[] = { 
    "ap", "ar", "tr", "mr", "lm", "rd", "vr", "el", "sd", "cm", "cd"
};

static const unsigned int SecondaryModesCounts = 19;
static char *SecondaryModes[] = {
    "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np",
    "sc", "om", "nt", "nm", "nb", "ro", "mo", "sp"
};

static const unsigned int MiscModesCount = 8;
static char *MiscModes[] = {
    "ns", "nr", "ts", "pm", "oi", "mi", "fr", "so" 
};

std::vector<std::string> Vectorize( int count, ... ) {
    std::vector<std::string> result;

    va_list vl;
    va_start( vl, count );

    for ( int i = 0; i < count; ++i ) {
        char *buffer = va_arg( vl, char * );
        result.push_back( buffer );
    }

    va_end( vl );

    return result;
}

void InitializeModeCompatibilityMap() {
    // Primary
    ModeCompatibilityMap["ar"] = Vectorize( 1, "rv" );
    ModeCompatibilityMap["tr"] = Vectorize( 2, "dm", "rv" );
    ModeCompatibilityMap["mr"] = Vectorize( 8, "dm", "rv", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["lm"] = Vectorize( 18, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo" );
    ModeCompatibilityMap["rd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["vr"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["el"] = Vectorize( 18, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo" );
    ModeCompatibilityMap["sd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["cm"] = Vectorize( 19, "dm", "rv", "mm", "du", "sh", "aa", "ai", "as", "id", "em", "np", "sc", "om", "nt", "nm", "nb", "ro", "mo", "sp" );
    ModeCompatibilityMap["cd"] = Vectorize( 9, "dm", "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );   
    // Secondary
    ModeCompatibilityMap["dm"] = Vectorize( 8, "rv", "mm", "sh", "aa", "ai", "as", "ro", "mo" );
    ModeCompatibilityMap["rv"] = Vectorize( 2, "dm", "sh" );
    ModeCompatibilityMap["mm"] = Vectorize( 2, "dm", "sh" );
    ModeCompatibilityMap["sh"] = Vectorize( 3, "dm", "rv", "mm" );
    ModeCompatibilityMap["aa"] = Vectorize( 3, "dm", "ai", "as" );
    ModeCompatibilityMap["ai"] = Vectorize( 3, "dm", "aa", "as" );
    ModeCompatibilityMap["as"] = Vectorize( 3, "dm", "aa", "ai" );
    ModeCompatibilityMap["ro"] = Vectorize( 2, "dm", "mo" );
    ModeCompatibilityMap["mo"] = Vectorize( 2, "dm", "ro" );
}

std::vector<std::string> Tokenize( const std::string &string ) {
    std::vector<std::string> tokens;
    std::string token;
    std::stringstream ss( string );

    while ( ss >> token ) {
        tokens.push_back( token );
    }

    return tokens;
}

void SanitizeString( std::string &in ) {
    std::transform( in.begin(), in.end(), in.begin(), tolower );

    for ( size_t i = 0; i < in.size(); ++i ) {
        if ( in[i] < 'a' || in[i] > 'z' ) {
            in.erase( i--, 1 );
        }
    }
}

std::vector<std::string> SplitString( const std::string &in, int count ) {
    std::vector<std::string> result;

    if ( in.length() % count != 0 ) {
        return result;
    }

    for ( std::string::const_iterator i = in.begin(); i != in.end(); i += count ) {
        result.push_back( std::string( i, i + count ) );
    }

    return result;
}

bool IsPrimaryGameMode( const std::string &in ) {
    for ( int i = 0; i < PrimaryModesCount; ++i ) {
        if ( strcmp( PrimaryModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsSecondaryGameMode( const std::string &in ) {
    for ( int i = 0; i < SecondaryModesCounts; ++i ) {
        if ( strcmp( SecondaryModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsMiscGameMode( const std::string &in ) {
    for ( int i = 0; i < MiscModesCount; ++i ) {
        if ( strcmp( MiscModes[i], in.c_str() ) == 0 ) {
            return true;
        }
    }

    return false;
}

bool IsValidGameMode( std::string in, std::string &out ) {
    // 1. Strip all non-letters from the string and convert it to lower-case
    SanitizeString( in );

    // 2. Confirm that it is a multiple of 2
    if ( in.length() == 0 || in.length() % 2 != 0 ) {
        return false;
    }

    // 3. Split the string further into strings of 2 characters
    std::vector<std::string> modes = SplitString( in, 2 );

    // 4. Verify that each game mode is a valid game mode and is compatible with the others
    bool primaryModeSet = false;

    for ( size_t i = 0; i < modes.size(); ++i ) {
        if ( IsPrimaryGameMode( modes[i] ) || IsSecondaryGameMode( modes[i] ) ) {
            if ( IsPrimaryGameMode( modes[i] ) ) {
                if ( primaryModeSet ) {
                    return false;
                }

                primaryModeSet = true;
            }

            if ( ModeCompatibilityMap.count( modes[i] ) > 0 ) {
                std::vector<std::string> badModes = ModeCompatibilityMap[modes[i]];

                for ( size_t j = 0; j < badModes.size(); ++j ) {
                    for ( size_t k = 0; k < modes.size(); ++k ) {
                        if ( badModes[j] == modes[k] ) {
                            return false;
                        }
                    }
                }
            }
        } else if ( !IsMiscGameMode( modes[i] ) ) {
            return false;
        }
    }

    // 5. Assign the output variable with the game mode and return true
    out = in;

    return true;
}

std::string ExtractGameMode( const std::string &gameName ) {
    std::vector<std::string> tokens = Tokenize( gameName );

    std::string gameMode;

    for ( size_t i = 0; i < tokens.size(); ++i ) {
        if ( IsValidGameMode( tokens[i], gameMode ) ) {
            return gameMode;
        }
    }

    return "";
}

int main( int argc, char *argv[] ) {
    InitializeModeCompatibilityMap();

    std::string gameName = "DotA v6.60 -RDEM USA/CA LC";
    std::string gameMode = ExtractGameMode( gameName );

    std::cout << "Name: " << gameName << std::endl;
    std::cout << "Mode: " << gameMode << std::endl;

    return 0;
}

Выход:

Название: DotA v6.60 -RDEM USA / CA LC

Режим: rdem

Если кто-то захочет просмотреть этот код и сообщить мне, что он изменит, это будет оценено.

Спасибо.

Doug T. · Answer 1 · 12 июня 2009

Создайте массивы bool, которые повторяют таблицы, которые вы добавили в комментарии. За исключением случаев, когда вместо «X» или пробела ставится «true» или «false» (поэтому «true» означает, что комбинация режимов действительна, а «false» означает недействительный).

Используйте эту таблицу, чтобы узнать, является ли комбинация допустимой:

 bool IsSecondaryValidWithPrimary(unsigned int primaryIndex, unsigned int secondaryIndex)
 {
     static bool secondaryValidWithPrimary[numPrimaryModes][numSecondaryModes] = {...}

     if (primaryIndex < numPrimaryModes && secondaryIndex < numSecondaryModes)
     {
         return secondaryValidWithPrimary[primaryIndex][secondaryIndex]
     }
     else
     {
         //... this should never happen, throw your favorite exception
     }
 }

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

Сделайте то же самое для другой проверки достоверности (вторичная с другой вторичной) или для любой другой комбинации режимов, для которых у вас есть правила совместимости.

Game_Overture · Answer 2 · 13 июня 2009

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

ToLower () вся строка с названием игры.
Разделите название игры, используя пробел ''.
Проанализируйте каждое слово, сделайте следующее. Если что-то не получается, переходите к следующему слову.

взяв [0] и определив, имеет ли оно значение ascii 97-122 (убедившись, что это буква). Если это не в этих значениях, переходите к следующему символу и так далее до тех пор, пока это не произойдет (очевидно, без превышения границ массива). Это удаляет любое пользовательское форматирование, например дефис -apem.
strcmp () следующие 2 персонажа с каждым из основных типов игр, пока вы не достигнете совпадения. В противном случае провал и переход к следующему слову.
С остальными персонажами, strcmp каждой следующей пары символов с каждым второстепенным или разным типом игры. Если какое-либо из них не соответствует, происходит сбой при переходе к следующему слову или если остается только 1 символ, при переходе к следующему слову

Это должно извлечь тип игры, или вы можете обвинить пользователя в использовании неверного названия игры.

Теперь самое сложное - проверить, совместимы ли типы игр друг с другом. Я предлагаю вам создать структуру, которая содержит структуру данных с логическими значениями, представляющими каждый из вторичных типов игр. Std :: map или единственный логический массив, доступ к которому можно получить с помощью enum.

Теперь вам понадобится объект данных для представления каждого основного типа игры , а также как каждого дополнительного типа игры.

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

map<const char*, bool> mapSecondaryCompatibility;

struct tGameType
{
    char szName[3];
    mapSecondaryCompatibility m_compat;
}

Как вы видите, технически нет разницы между вашими основными и дополнительными типами игр, у них обоих есть одно и то же ограничение ... может быть несовместимо с другим типом дополнительной игры.

С этим я уверен, что вы можете выяснить все остальное. Надеюсь, это поможет, я должен вернуться к работе:)

О, и я большой поклонник DotA ... продолжайте в том же духе!

Dolphin · Answer 3 · 12 июня 2009

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

Режимы misc, вероятно, не входят в белый список (потому что они есть в каждом белом списке).

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

Kieveli · Answer 4 · 12 июня 2009

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

Внутренне я бы создал std :: map > для хранения списка совместимых режимов. Как только введена командная строка, я бы преобразовал две строки символов в значение перечисления. Затем я посмотрел бы в сопоставимом режиме сопоставления, чтобы увидеть, является ли это разрешенным режимом.

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

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

C ++ - Как я могу извлечь допустимую строку в строке?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 4 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

C ++ - Как я могу извлечь допустимую строку в строке?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 4 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы