grid generation

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <thread>
#include <mutex>
#include <chrono>
#include <ctime>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <filesystem>
#include <queue>
#include <set>

using namespace std;

namespace fs = std::filesystem;

const int GRID_SIZE = 5;
const int MAX_STATE_NAME_LENGTH = 13; // Maximum length of U.S. state names
const char MOST_FREQUENT_CHAR = 'A';  // The most frequent character in state names
const unsigned long long SAVE_INTERVAL = 1000000; // Save cache every 1,000,000 calculations
const int SCORE_THRESHOLD = 100000000; // Score threshold for highlighting

vector<string> states = {
    "ALABAMA", "ALASKA", "ARIZONA", "ARKANSAS", "CALIFORNIA", "COLORADO", "CONNECTICUT", "DELAWARE",
    "FLORIDA", "GEORGIA", "HAWAII", "IDAHO", "ILLINOIS", "INDIANA", "IOWA", "KANSAS", "KENTUCKY",
    "LOUISIANA", "MAINE", "MARYLAND", "MASSACHUSETTS", "MICHIGAN", "MINNESOTA", "MISSISSIPPI",
    "MISSOURI", "MONTANA", "NEBRASKA", "NEVADA", "NEWHAMPSHIRE", "NEWJERSEY", "NEWMEXICO",
    "NEWYORK", "NORTHCAROLINA", "NORTHDAKOTA", "OHIO", "OKLAHOMA", "OREGON", "PENNSYLVANIA",
    "RHODEISLAND", "SOUTHCAROLINA", "SOUTDAKOTA", "TENNESSEE", "TEXAS", "UTAH", "VERMONT",
    "VIRGINIA", "WASHINGTON", "WESTVIRGINIA", "WISCONSIN", "WYOMING"
};
unordered_map<string, int> population = {
    {"ALABAMA", 5024279}, {"ALASKA", 733391}, {"ARIZONA", 7151502}, {"ARKANSAS", 3011524},
    {"CALIFORNIA", 39538223}, {"COLORADO", 5773714}, {"CONNECTICUT", 3605944}, {"DELAWARE", 989948},
    {"FLORIDA", 21538187}, {"GEORGIA", 10711908}, {"HAWAII", 1455271}, {"IDAHO", 1839106},
    {"ILLINOIS", 12812508}, {"INDIANA", 6785528}, {"IOWA", 3190369}, {"KANSAS", 2937880},
    {"KENTUCKY", 4505836}, {"LOUISIANA", 4657757}, {"MAINE", 1362359}, {"MARYLAND", 6177224},
    {"MASSACHUSETTS", 7029917}, {"MICHIGAN", 10077331}, {"MINNESOTA", 5706494}, {"MISSISSIPPI", 2961279},
    {"MISSOURI", 6154913}, {"MONTANA", 1084225}, {"NEBRASKA", 1961504}, {"NEVADA", 3104614},
    {"NEWHAMPSHIRE", 1377529}, {"NEWJERSEY", 9288994}, {"NEWMEXICO", 2117522}, {"NEWYORK", 20201249},
    {"NORTHCAROLINA", 10439388}, {"NORTHDAKOTA", 779094}, {"OHIO", 11799448}, {"OKLAHOMA", 3959353},
    {"OREGON", 4237256}, {"PENNSYLVANIA", 13002700}, {"RHODEISLAND", 1097379}, {"SOUTHCAROLINA", 5118425},
    {"SOUTDAKOTA", 886667}, {"TENNESSEE", 6910840}, {"TEXAS", 29145505}, {"UTAH", 3271616},
    {"VERMONT", 643077}, {"VIRGINIA", 8631393}, {"WASHINGTON", 7705281}, {"WESTVIRGINIA", 1793716},
    {"WISCONSIN", 5893718}, {"WYOMING", 576851}
};

const vector<pair<int, int>> directions = {
    {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
};

bool isValid(int x, int y) {
    return x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE;
}

bool isValidPrefix(const string& word) {
    for (const auto& state : states) {
        if (word.length() > state.length()) continue;
        int mismatchCount = 0;
        for (int i = 0; i < word.length(); ++i) {
            if (word[i] != state[i]) {
                mismatchCount++;
                if (mismatchCount > 1) break;
            }
        }
        if (mismatchCount <= 1) return true;
    }
    return false;
}

void findStates(vector<vector<char>>& grid, int x, int y, string currentWord, unordered_set<string>& foundStates, unordered_map<string, unordered_set<string>>& cache) {
    currentWord += grid[x][y];
    if (currentWord.length() > MAX_STATE_NAME_LENGTH) return;

    // First check the cache
    auto it = cache.find(currentWord);
    if (it != cache.end()) {
        foundStates.insert(it->second.begin(), it->second.end());
        return;
    }

    if (!isValidPrefix(currentWord)) return;

    unordered_set<string> localFoundStates;
    for (const auto& state : states) {
        if (currentWord == state) {
            localFoundStates.insert(state);
            break;
        }
        int mismatchCount = 0;
        if (currentWord.length() == state.length()) {
            for (int i = 0; i < currentWord.length(); ++i) {
                if (currentWord[i] != state[i]) {
                    mismatchCount++;
                    if (mismatchCount > 1) break;
                }
            }
            if (mismatchCount == 1) {
                localFoundStates.insert(state);
                break;
            }
        }
    }

    for (const auto& dir : directions) {
        int newX = x + dir.first;
        int newY = y + dir.second;
        if (isValid(newX, newY)) {
            findStates(grid, newX, newY, currentWord, localFoundStates, cache);
        }
    }

    foundStates.insert(localFoundStates.begin(), localFoundStates.end());
    cache[currentWord] = localFoundStates;
}

void printGridAndStates(ostream& os, const vector<vector<char>>& grid, const unordered_set<string>& states) {
    for (const auto& row : grid) {
        for (char c : row) {
            os << c << " ";
        }
        os << endl;
    }
    for (const auto& state : states) {
        os << state << " ";
    }
    os << endl;
}

string getCurrentTimestamp() {
    auto now = chrono::system_clock::now();
    auto now_time_t = chrono::system_clock::to_time_t(now);
    stringstream ss;
    ss << put_time(localtime(&now_time_t), "%Y-%m-%d %H:%M:%S");
    return ss.str();
}

string getLogFileName() {
    auto now = chrono::system_clock::now();
    auto now_time_t = chrono::system_clock::to_time_t(now);
    stringstream ss;
    ss << "kingsmove_log_" << put_time(localtime(&now_time_t), "%Y%m%d_%H%M%S") << ".txt";
    return ss.str();
}

mutex logMutex;
ofstream logFile;

void logMessage(const string& message, bool highlight = false) {
    string formattedMessage = "[" + getCurrentTimestamp() + "] " + message;
    if (highlight) {
        formattedMessage = "\033[1;31m" + formattedMessage + "\033[0m"; // Highlight in red
    }
    lock_guard<mutex> guard(logMutex);
    cout << formattedMessage << endl;
    logFile << formattedMessage << endl;
}

void logNewMaxScore(int threadId, int maxScore, const vector<vector<char>>& grid, const unordered_set<string>& states, bool highlight) {
    string formattedMessage = "[" + getCurrentTimestamp() + "] Thread " + to_string(threadId) + " found new max score: " + to_string(maxScore);
    if (highlight) {
        formattedMessage = "\033[1;31m" + formattedMessage + "\033[0m"; // Highlight in red
    }
    lock_guard<mutex> guard(logMutex);
    cout << formattedMessage << endl;
    logFile << formattedMessage << endl;
    printGridAndStates(cout, grid, states); // Print to console
    printGridAndStates(logFile, grid, states); // Print to log file
}

void saveCache(int threadId, unsigned long long idx, int maxScore, const unordered_map<string, unordered_set<string>>& cache, const string& folderPath) {
    // Delete previous cache files for this thread
    for (const auto& entry : fs::directory_iterator(folderPath)) {
        if (entry.path().stem().string().find("thread_" + to_string(threadId) + "_cache_") == 0) {
            fs::remove(entry.path());
        }
    }

    // Save new cache file
    stringstream ss;
    ss << folderPath << "/thread_" << threadId << "_cache_" << idx / SAVE_INTERVAL << ".cache";
    ofstream cacheFile(ss.str());
    if (cacheFile.is_open()) {
        cacheFile << idx << " " << maxScore << endl;
        for (const auto& entry : cache) {
            cacheFile << entry.first << " ";
            for (const auto& state : entry.second) {
                cacheFile << state << " ";
            }
            cacheFile << "-" << endl; // Use '-' as a delimiter for the end of the state's list
        }
        cacheFile.close();
    }
}

bool loadLatestCache(int threadId, unsigned long long& idx, int& maxScore, unordered_map<string, unordered_set<string>>& cache, const string& folderPath) {
    vector<fs::path> cacheFiles;
    for (const auto& entry : fs::directory_iterator(folderPath)) {
        if (entry.path().stem().string().find("thread_" + to_string(threadId) + "_cache_") == 0) {
            cacheFiles.push_back(entry.path());
        }
    }
    if (cacheFiles.empty()) {
        return false;
    }

    sort(cacheFiles.begin(), cacheFiles.end(), [](const fs::path& a, const fs::path& b) {
        return a.stem().string() > b.stem().string();
    });

    string latestCacheFile = cacheFiles.front().string();
    ifstream cacheFile(latestCacheFile);
    if (cacheFile.is_open()) {
        cacheFile >> idx >> maxScore;
        string key, state;
        while (cacheFile >> key) {
            unordered_set<string> statesSet;
            while (cacheFile >> state && state != "-") {
                statesSet.insert(state);
            }
            cache[key] = statesSet;
        }
        cacheFile.close();
        logMessage("Thread " + to_string(threadId) + " loaded cache from " + latestCacheFile + " at index " + to_string(idx) + " with max score " + to_string(maxScore));
        return true;
    }
    return false;
}

void saveHighScore(int threadId, int score, const string& logFileName) {
    ofstream csvFile(logFileName + ".csv", ios::app);
    if (csvFile.is_open()) {
        csvFile << threadId << "," << score << "," << getCurrentTimestamp() << endl;
        csvFile.close();
    }
}

struct Grid {
    vector<vector<char>> grid;
    int heuristicScore;
    unsigned long long index;

    bool operator<(const Grid& other) const {
        return heuristicScore < other.heuristicScore;
    }
};

int calculateHeuristic(const vector<vector<char>>& grid) {
    unordered_map<char, int> charFrequency;
    for (const auto& row : grid) {
        for (char c : row) {
            charFrequency[c]++;
        }
    }

    int potentialScore = 0;
    for (const auto& entry : charFrequency) {
        if (population.count(string(1, entry.first))) {
            potentialScore += population[string(1, entry.first)] * entry.second;
        }
    }

    int charDiversity = charFrequency.size();

    return potentialScore + charDiversity * 1000000; // Adjust weight of diversity as needed
}

vector<vector<char>> generateGridVariation(const vector<vector<char>>& grid) {
    vector<vector<char>> newGrid = grid;
    int x1 = rand() % GRID_SIZE;
    int y1 = rand() % GRID_SIZE;
    int x2 = rand() % GRID_SIZE;
    int y2 = rand() % GRID_SIZE;
    swap(newGrid[x1][y1], newGrid[x2][y2]);
    return newGrid;
}

void generateGrids(priority_queue<Grid>& gridQueue, set<unsigned long long>& checkedGrids, unordered_set<string>& foundStates, int threadId, unsigned long long& counter, unsigned long long totalCalculations, unsigned long long start, unsigned long long end, unordered_map<string, unordered_set<string>>& cache, int& maxScore, const string& folderPath, const string& logFileName) {
    while (!gridQueue.empty()) {
        Grid current = gridQueue.top();
        gridQueue.pop();

        if (checkedGrids.count(current.index)) {
            continue;
        }
        checkedGrids.insert(current.index);

        unordered_set<string> localFoundStates;
        for (int x = 0; x < GRID_SIZE; ++x) {
            for (int y = 0; y < GRID_SIZE; ++y) {
                findStates(current.grid, x, y, "", localFoundStates, cache);
            }
        }
        unordered_set<string> combinedStates = foundStates;
        combinedStates.insert(localFoundStates.begin(), localFoundStates.end());

        int totalScore = 0;
        for (const auto& state : combinedStates) {
            totalScore += population.at(state);
        }

        if (totalScore > maxScore) {
            maxScore = totalScore;
            bool highlight = maxScore > SCORE_THRESHOLD;
            logNewMaxScore(threadId, maxScore, current.grid, combinedStates, highlight);
            saveHighScore(threadId, maxScore, logFileName);
        }
        counter++;

        if (counter % SAVE_INTERVAL == 0) {  // Save cache every SAVE_INTERVAL calculations
            saveCache(threadId, current.index, maxScore, cache, folderPath);
            double progress = static_cast<double>(counter - start) / (end - start) * 100.0;
            logMessage("Thread " + to_string(threadId) + " saved cache at counter " + to_string(counter) + " / " + to_string(end - start) + " (" + to_string(progress) + "%)");
        }

        for (int i = 0; i < 10; ++i) {
            vector<vector<char>> newGrid = generateGridVariation(current.grid);
            int heuristicScore = calculateHeuristic(newGrid);
            gridQueue.push({newGrid, heuristicScore, current.index});
        }
    }
}

void threadFunction(int threadId, unsigned long long start, unsigned long long end, int& maxScore, const string& folderPath, const string& logFileName) {
    vector<vector<char>> initialGrid(GRID_SIZE, vector<char>(GRID_SIZE, MOST_FREQUENT_CHAR)); // Initialize with the most common character
    unordered_set<string> foundStates;
    unordered_map<string, unordered_set<string>> cache;
    unsigned long long counter = start;
    priority_queue<Grid> gridQueue;
    set<unsigned long long> checkedGrids;

    // Load cache if exists
    if (loadLatestCache(threadId, counter, maxScore, cache, folderPath)) {
        logMessage("Thread " + to_string(threadId) + " continuing from cache at index " + to_string(counter) + " with max score " + to_string(maxScore));
    }

    // Initialize the priority queue with the initial grid
    int heuristicScore = calculateHeuristic(initialGrid);
    gridQueue.push({initialGrid, heuristicScore, start});

    generateGrids(gridQueue, checkedGrids, foundStates, threadId, counter, end - start, start, end, cache, maxScore, folderPath, logFileName);

    logMessage("Thread " + to_string(threadId) + " finished with max score: " + to_string(maxScore));
}

unsigned long long power(unsigned long long base, unsigned long long exp) {
    unsigned long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        cerr << "Usage: " << argv[0] << " <number_of_threads>" << endl;
        return 1;
    }

    int numThreads;
    try {
        numThreads = stoi(argv[1]);
        if (numThreads <= 0) throw invalid_argument("Number of threads must be a positive integer.");
    } catch (const invalid_argument& e) {
        cerr << "Invalid number of threads: " << argv[1] << endl;
        return 1;
    }

    // Create directory with number of threads as name
    string folderPath = to_string(numThreads);
    fs::create_directory(folderPath);

    // Initialize log file with a timestamp in the name
    string logFileName = getLogFileName();
    logFile.open(folderPath + "/" + logFileName);
    if (!logFile.is_open()) {
        cerr << "Failed to open log file: " << logFileName << endl;
        return 1;
    }
    logMessage("Program started with " + to_string(numThreads) + " threads.");

    unsigned long long totalCalculations = power(26, GRID_SIZE * GRID_SIZE);
    unsigned long long calculationsPerThread = totalCalculations / numThreads;
    vector<int> threadMaxScores(numThreads, 0);

    vector<thread> threads;
    for (int i = 0; i < numThreads; ++i) {
        unsigned long long start = i * calculationsPerThread;
        unsigned long long end = (i == numThreads - 1) ? totalCalculations : start + calculationsPerThread;
        threads.emplace_back(threadFunction, i + 1, start, end, ref(threadMaxScores[i]), folderPath, folderPath + "/" + logFileName);
    }

    for (auto& t : threads) {
        t.join();
    }

    // Combine results from all threads
    int maxScore = *max_element(threadMaxScores.begin(), threadMaxScores.end());
    logMessage("Max score found: " + to_string(maxScore));
    logFile.close();

    return 0;
}