Подсчитайте количество действительных паролей на основе некоторых ограничений

Question

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

1. Минимум 10 символов и Максимум 14 символов.
2. Символы могут включать маленькие английские буквы ('a'-'z'), заглавные буквы ('A'-'Z'), цифры ('0'-'9') и специальные символы ('!','@','#','$','%','^','&','*','(',')')
3. Допустимые пароли должны содержатьпо крайней мере, одна из маленьких букв, заглавных букв, цифр и специальных символов.
4. Пароли не могут содержать собственный идентификатор студента. Студенческий билет состоит из 7 цифр. Первые две цифры обозначают год (00, 01, ... , 99), следующие две цифры обозначают код отдела (00, 01, ... 99), а последние три цифры обозначают свиток внутри отдела (000 - 180). Таким образом, идентификатор студента может быть таким: 1210142, где 12 обозначает, что он из партии 12, 10 - код отдела, а 142 - номер броска. Студент с идентификатором 1210142 не может иметь пароль типа Ti@s1210142mE, но может иметь пароль типа Ti@s121014m2E.
5. Студент может использовать идентификатор другого студента в своем собственном пароле.

Учитывая ограничения, сколько допустимых паролей может быть сгенерировано?

Я написал простую программу на C ++ для имитации этого. Но так как это просто наивная реализация, потребуется много времени (может быть, больше, чем моя жизнь), чтобы выложить ответ. Есть ли какой-нибудь умный способ выяснить ответ, используя код, возможно, используя регулярное выражение или что-то в этом роде?

Мои усилия до сих пор:

#include <iostream>
#include <algorithm>

inline bool is_valid_password(const std::string &generated_password, const std::string &student_id){
    bool small = false, captial = false, digit = false, special = false;
    for(const char &c : generated_password){
        if(c >= 'a' && c <= 'z') small = true;
        else if(c >= 'A' && c <= 'Z') captial = true;
        else if(c >= '0' && c <= '9') digit = true;
        else if(c == '!' || c == '@' || c == '#' || c == '$' || c == '%' || c == '^' || c == '&' || c == '*' || c == '(' || c == ')') special = true;
    }
    if(small && captial && digit && special){
        return generated_password.find(student_id) == std::string::npos;
    }
    return false;
}

char valid_character_set [] = {
        'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
        'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
        '0','1','2','3','4','5','6','7','8','9',
        '!','@','#','$','%','^','&','*','(',')'
};

long long comb(int N, int K, const std::string &student_id)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    long long counter = 0;

    // print integers and permute bitmask
    do {
        std::string generated_password = "";

        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]){
                generated_password += valid_character_set[i];
            }
        }

        if(is_valid_password(generated_password, student_id)) {
            //std::cout << "valid password found: " << generated_password << '\n';
            counter++;
        }

    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));

    return counter;
}

int main(int argc, char const *argv[])
{
    std::cout << "Enter your student id: ";
    std::string student_id; std::cin >> student_id;
    std::cout << "Your student id is: " << student_id << "\n";



    // all possible 10 character passwords

    std::cout << comb(72, 10, student_id) << '\n';

    return 0;
}

Answer 1

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

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

#include<regex>

И затем вы можете создать свой собственный объект регулярного выражения:

std::regex r = regex("yourRegexPattern");

С этим объектом вы можете вызывать некоторые полезные функции, такие как regex_match() (которые могут бытьодин для вашего случая использования), regex_search() или regex_replace().

Для получения дополнительной информации, я связал официальную ссылку выше, или вы можете просто google "c ++ regex"

Редактировать: фиксированные ссылки