How do i make a faster C algorithm [closed]

Question

i want to make an algorithm that filters some numbers like 101010101010101. numbers that have some patterns in them. but they are very large and i need 4 or 5 secounds to reach 100.000.000. and about 99.500.000 numbers are filtered out. the question is ,how can i reach 1.000.000.000.000.000 without waiting for months. i want the code to reach 100.000.000 in 0.4 secounds or less. i hope someone can help me. this is my code:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <windows.h>

#define NUM_THREADS 8
#define MAX_NUM 100000ULL  

typedef struct {
    unsigned long long int start;
    unsigned long long int end;
    unsigned long long int count;
} ThreadData;

// Funktion zur Überprüfung auf aufeinanderfolgende Ziffern
bool has_consecutive_digits(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool increasing = true, decreasing = true;
        for (int j = 0; j < length; j++) {
            if (password[i+j] != password[i] + j) increasing = false;
            if (password[i+j] != password[i] - j) decreasing = false;
        }
        if (increasing || decreasing) return true;
    }
    return false;
}

// Funktion zur Überprüfung auf zu viele Wiederholungen der gleichen Ziffer
bool has_repeated_digits(const char* password, int max_repeats) {
    int counts[10] = {0};
    int len = strlen(password);
    for (int i = 0; i < len; i++) {
        counts[password[i] - '0']++;
        if (counts[password[i] - '0'] > max_repeats) return true;
    }
    return false;
}

// Funktion zur Überprüfung auf palindromische Muster
bool has_palindromic_pattern(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool is_palindrome = true;
        for (int j = 0; j < length / 2; j++) {
            if (password[i+j] != password[i+length-1-j]) {
                is_palindrome = false;
                break;
            }
        }
        if (is_palindrome) return true;
    }
    return false;
}

// Funktion zur Überprüfung, ob das Passwort ein bekanntes Muster enthält
bool is_substring_of_common_patterns(const char* password) {
    const char* common_patterns[] = {
        "123456", "654321", "111111", "222222", "333333",
        "012345", "543210", "987654", "000000", "999999"
    };
    for (int i = 0; i < 10; i++) {
        if (strstr(password, common_patterns[i])) return true;
    }
    return false;
}

// Funktion zur Überprüfung auf abwechselnde Ziffern
bool has_alternating_digits(const char* password, int length) {
    int len = strlen(password);
    for (int i = 0; i <= len - length; i++) {
        bool valid = true;
        for (int j = 0; j < length; j++) {
            if ((j % 2 == 0 && password[i+j] != password[i]) ||
                (j % 2 == 1 && password[i+j] == password[i])) {
                valid = false;
                break;
            }
        }
        if (valid) return true;
    }
    return false;
}

// Funktion zur Überprüfung auf aufeinanderfolgende Blöcke von steigenden oder fallenden Ziffern
bool has_increasing_or_decreasing_blocks(const char* password, int block_size) {
    int len = strlen(password);
    for (int i = 0; i <= len - block_size; i += block_size) {
        if (has_consecutive_digits(password + i, block_size)) return true;
    }
    return false;
}

// Funktion zur Überprüfung auf spiegelbildliche Blöcke
bool has_mirrored_blocks(const char* password, int block_size) {
    int len = strlen(password);
    for (int i = 0; i <= len - 2 * block_size; i += block_size) {
        bool mirrored = true;
        for (int j = 0; j < block_size; j++) {
            if (password[i + j] != password[i + block_size * 2 - 1 - j]) {
                mirrored = false;
                break;
            }
        }
        if (mirrored) return true;
    }
    return false;
}

// Funktion zur Überprüfung, ob das Passwort ein zu einfaches Muster hat
bool is_pattern_too_simple(const char* password) {
    return has_consecutive_digits(password, 3) ||
           has_repeated_digits(password, 1) ||
           has_palindromic_pattern(password, 4) ||
           is_substring_of_common_patterns(password) ||
           has_alternating_digits(password, 4) ||
           has_increasing_or_decreasing_blocks(password, 2) ||
           has_mirrored_blocks(password, 4); // 3,1,3, ,4,2,4
}

// Funktion zur Überprüfung der Passwortgültigkeit
bool is_valid_password(const char* password) {
    return !is_pattern_too_simple(password);
}

DWORD WINAPI check_passwords(LPVOID arg) {
    ThreadData* data = (ThreadData*)arg;
    char password[7];  // Für Zahlen bis 999999 (6 Ziffern + Nullzeichen)
    data->count = 0;

    for (unsigned long long int i = data->start; i < data->end; i++) {
        sprintf(password, "%06llu", i);  // Erzeuge ein 6-stelliges Passwort
        if (is_valid_password(password)) {
            data->count++;
        }
    }

    return 0;
}

int main() {
    HANDLE threads[NUM_THREADS];
    ThreadData thread_data[NUM_THREADS];
    unsigned long long int range = MAX_NUM / NUM_THREADS;
    unsigned long long total_count = 0;

    // Starte die Threads
    for (int i = 0; i < NUM_THREADS; i++) {
        thread_data[i].start = i * range;
        thread_data[i].end = (i + 1) * range;
        threads[i] = CreateThread(NULL, 0, check_passwords, &thread_data[i], 0, NULL);
        if (threads[i] == NULL) {
            fprintf(stderr, "Error creating thread %d\n", i);
            return 1;
        }
    }

    // Warte auf Threads und sammle Ergebnisse
    for (int i = 0; i < NUM_THREADS; i++) {
        WaitForSingleObject(threads[i], INFINITE);
        DWORD exit_code;
        if (GetExitCodeThread(threads[i], &exit_code)) {
            total_count += thread_data[i].count;
        } else {
            fprintf(stderr, "Error getting thread exit code %d\n", i);
        }
        CloseHandle(threads[i]);
    }

    // Zeige die Gesamtanzahl der gültigen Passwörter an
    printf("Anzahl der gültigen Zahlen: %llu\n", total_count);

    return 0;
}

i tried to use multithreading and my code was about 10 times faster and an switched from int to unsigned long long int, that made my code a bit faster. i need at least a 10 times faster code than this one. i also tryed flags. i dont need to make this code in c ,if there is a faster language then please tell me.

Answer 1

For some of your individual checks, if a prefix of a password fails that check, then the full password will also fail that check.

For example, all passwords starting with "11" are invalid due to has_repeated_digits. So instead of checking all of them individually, you could skip the whole 110000-119999 range.

This will dramatically reduce a number of passwords that need to be considered -- as the passwords get longer, has_repeated_digits alone will exclude most of them from consideration.