KnightDialler_SequenceMapper

knightSequenceCalculator.cpp

/***********************************************************************************************
        Anshul Yadav
        [email protected]
        yadav26@github
        This is for reference, acacia system knight sequncer
************************************************************************************************
Compile and run :
g++ -std=c++17 -Wpedantic -O3 source.cpp -o knightSequence.out && ./knightSequence.out
g++ -std=c++17 -Wpedantic -O3 source.cpp -o knightSequence.out && ./knightSequence.out -c{8} -p [10]
*/

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <sstream>
#include <chrono>
#include <thread>

#define ll long long

using namespace std;
using VVINT = vector<vector<int>>;

constexpr int isAEIOU[] = { /*a*/1,0,0,0,/*e*/1,0,0,0,/*i*/1,0,0,0,0,0,/*o*/1,0,0,0,0,0,/*u*/1, 0, 0, 0, 0, 0 };
constexpr int MAX_SEQUENCE_LEN = 10;


class KeyBoardSequenceFinder {
    
    //currently its hard coded, but should be dynamically generated
    ll dp[100][18][3]; // 100 - max key length (currently only 10 used), 18 - keybord keys , 3 max vowels possible 0,1 and 2

	const std::map<char, int> keyIdentity = {
	    { 'A',0 },  { 'B', 1 }, { 'C', 2 }, { 'D', 3 }, { 'E',4 },
	    { 'F',5 },  { 'G', 6 }, { 'H', 7 }, { 'I', 8 }, { 'J',9 },
	    { 'K',10 }, { 'L',11 }, { 'M',12 }, { 'N',13 }, { 'O',14 },
				    { '1',15 }, { '2',16 }, { '3',17 }
	};
    VVINT kbLayout = {
        /*A:0 */{11,7},    /*B:1 */{10,8,12},     /*C:2 */{13,5,11,9},       /*D:3 */{14,6,12,},    /*E:4 */{7,13},
        /*F:5 */{12,2,15}, /*G:6 */{13,3,16},     /*H:7 */{4,10,0,17,15,14}, /*I:8 */{1,11,16},     /*J:9 */{2,12,17},
        /*K:10*/{7,1,16},  /*L:11*/{0,2,8,17},    /*M:12*/{3,1,5,9},         /*N:13*/{2,4,6,15},    /*O:14*/{3,7,16},
        /*1:15*/{5,7,13},      /*2:16*/{6,8,10,14},       /*3:17*/{7,9,11}
    };

public:
    int max_vow = 2;
    int start_key_len = 1;
    int final_key_len = MAX_SEQUENCE_LEN;
    static inline int use_cpu_cores = std::thread::hardware_concurrency();
    bool profile_enabled = false;
    bool do_range_run = false;
    std::vector<int> keys;

    KeyBoardSequenceFinder(int argc, char*argv[]){
        memset(dp, -1, sizeof(dp));
        std::transform(keyIdentity.begin(), keyIdentity.end(), std::back_inserter(keys),
            [](const auto& pair) { return pair.second; });

        UsageGuide();

        std::string arg;
        stringstream ss;
        for (int i = 1; i < argc; ++i) {
            ss << argv[i];
            ss << " ";
        }

        handleInputs(argc, ss.str());
        //reset max_vow here currently hardcoded to 2

    }

    VVINT build_keyboard_layout() {
        VVINT knightMoves = {
            /*A:0 */{11,7},    /*B:1 */{10,8,12},     /*C:2 */{13,5,11,9},       /*D:3 */{14,6,12,},    /*E:4 */{7,13},
            /*F:5 */{12,2,15}, /*G:6 */{13,3,16},     /*H:7 */{4,10,0,17,15,14}, /*I:8 */{1,11,16},     /*J:9 */{2,12,17},
            /*K:10*/{7,1,16},  /*L:11*/{0,2,8,17},    /*M:12*/{3,1,5,9},         /*N:13*/{2,4,6,15},    /*O:14*/{3,7,16},
            /*1:15*/{5,7,13},      /*2:16*/{6,8,10,14},       /*3:17*/{7,9,11}
        };
        return std::move(knightMoves);
    }
    //debug purpose only
    void printArr(const vector<int>& v) {
        cout << "[";
        for (int i = 0; i < v.size(); ++i) {
            cout << v[i] << (i == v.size() - 1 ? "" : ", ");
        }
        cout << "] ";
    }
    //flibility for user inputs
    void UsageGuide() {
        cout << "\n --------------------------------------------------------------------------------------------------- ";
        cout << "\n -Binary Flags ------------------------------------------------------------------------------------- ";
        cout << "\n --------------------------------------------------------------------------------------------------- ";
        cout << "\n 1. Default key length of 10 (./a.out) --------------------------------------------------------------";
        cout << "\n 2. To calculate valid paths of keys len 15 pass argument (./a.out 15) ";
        cout << "\n 3. To calculate range of inputs varying length from 1 to 10(./a.out [1-10]).";
        cout << "\n 4. To force run on limited cpu core use flag \"-c{1}\" e.g.(./a.out -c{N} ) will force using N cores.";
        cout << "\n 5. To profile the binary and print running time use flag \"-p\" e.g.(./a.out -p ) .";
        cout << "\n 6. To profile the binary results flag \"-p\" e.g.(./a.out -p ) will print time of execution.";
        cout << "\n ---------------------------------------------------------------------------------------------------- ";
        cout << "\n -----------------------------------THANKS----------------------------------------------------------- ";
        cout << "\n -------------------------------ANSHUL YADAV--------------------------------------------------------- ";
        cout << "\n ---------------------------------------------------------------------------------------------------- ";

    }
    void handleInputs(int c, string in) {
        size_t pos = in.find("-p");
        if (pos != std::string::npos) {
            profile_enabled = true;
            in.erase(pos, 2);
        }
        pos = in.find("-c");
        if (pos != std::string::npos) {
            int ipos = 2;
            if (in[pos + 2] == '{') {
                ipos = in.find('}', pos + 3);
                if (ipos != std::string::npos)
                {
                    string s = in.substr(pos + 3, ipos - 1 - (pos + 2));
                    use_cpu_cores = atoi(s.c_str());
                }

            }
            in.erase(pos, ipos - pos + 1);
        }

        pos = in.find("[");
        if (pos != std::string::npos) {
            int epos = in.find(']', pos + 1);
            do_range_run = true;
            //running in range
            int mp = in.find('-', pos + 1);
            if (mp == -1) {
                start_key_len = 1;

                string s = in.substr(pos + 1, epos - 1 - (pos));
                final_key_len = atoi(s.c_str());
            }
            else {
                string s = in.substr(pos + 1, mp - 1);
                start_key_len = atoi(s.c_str());
                string e = in.substr(mp + 1, epos - 1 - (mp));
                final_key_len = atoi(e.c_str());
                if (start_key_len > final_key_len)
                    swap(final_key_len, start_key_len);
            }
        }
        else {
            try {
                start_key_len = final_key_len = std::stoi(in);
            }
            catch (...)
            {
                cout << "\n HandleInput - Exception (stoi) invalid numeric params(" << in << ")\n";
                start_key_len = final_key_len = 10;
            }
        }
    }

    //no meorization
    //ll Solution1(const vector<int>& keys, uint32_t left_moves, uint32_t va) {
    ll Solution1(const vector<int>&keys, int cellid, uint32_t left_moves, uint32_t vowels_left) {

        if (!left_moves)
            return 1;// we got a valid path

        left_moves = left_moves - 1;

        ll total_paths = 0;
        for (const auto keyIdx : keys) {
            if (vowels_left > 0 || !isAEIOU[keyIdx]) {
                auto lessOneVa = vowels_left - isAEIOU[keyIdx];
                total_paths += Solution1(kbLayout[keyIdx], keyIdx, left_moves, lessOneVa);
            }
        }
        return total_paths;
    }

    //solution 2 faster with memorization
    ll Solution2(const vector<int>& keys, int cellid, uint32_t left_moves, uint32_t vowels_left) {

        if (!left_moves)
            return 1;// we got a valid path

        if (-1 != dp[left_moves][cellid][vowels_left]) {
            return dp[left_moves][cellid][vowels_left];//we already have this calculated
        }

        ll total_paths = 0;
        for (const auto keyIdx : keys) {
            if (vowels_left > 0 || !isAEIOU[keyIdx]) {
                total_paths += Solution2(kbLayout[keyIdx], keyIdx, left_moves - 1, vowels_left - isAEIOU[keyIdx]);
            }
        }
        return dp[left_moves][cellid][vowels_left] = total_paths;
    }


    void thCallBack(vector<int>v, int cellid, int chunkSize, int len, ll& res)
    {       
        for (int i = cellid; i < (cellid + chunkSize > kbLayout.size() ? kbLayout.size() : cellid + chunkSize); ++i)
            //To use memorization solution
            res += Solution2(kbLayout[i], i, len - 1, max_vow - isAEIOU[i]);
            //To use non memorization solution comment above line and uncomment below line
            //res += Solution1(kbLayout[i], i, len - 1, max_vow - isAEIOU[i]);
    }

    void NonThreadedSolution_X() {

        //ll ans1 = 0;
        //for(int i=0;i< kbLayout.size();++i)
        //    ans1 += Solution1(kbLayout[i], final_key_len-1, max_vow - isAEIOU[i]);
        //cout << "Solution 1(no memoization): " <<ans1;
        //cout << endl;

        memset(dp, -1, sizeof(dp));
        ll ans2 = 0;
        for (int i = 0; i < kbLayout.size(); ++i)
            ans2 += Solution2(kbLayout[i], i, final_key_len - 1, max_vow - isAEIOU[i]);

        cout << "\nSolution 2(memoization): " << ans2;
        cout << endl;
    }

    //Concurrent multithread solution
    void MultiThreadedSolution_X( )
    {
        auto start = std::chrono::steady_clock::now();

        const int tth = KeyBoardSequenceFinder::use_cpu_cores;// Get number of available cores
        int chunkSize = keys.size() / tth;
        int chunkCount = keys.size() % chunkSize == 0 ? keys.size() / chunkSize : (keys.size() / chunkSize) + 1;
        
        for (int run = start_key_len; run <= final_key_len; ++run) 
        {
            auto start_run = std::chrono::steady_clock::now();
            ll ans = 0;
            vector<thread> threads(chunkCount); // one threads per workload
            std::vector<ll> results(chunkCount);//gather output result per thread

            for (int tid = 0; tid < chunkCount; ++tid) {
                auto start = keys.begin() + (tid * chunkSize);
                auto endPos = start;
                if (tid == chunkCount - 1) {
                    //BugFix for the last work load
                    endPos = keys.end();
                }
                else
                    endPos = keys.begin() + ((tid + 1) * chunkSize);
                vector<int> vec = { start, endPos };
                std::thread th(&KeyBoardSequenceFinder::thCallBack, this, vec, (tid * chunkSize), chunkSize, run, std::ref(results[tid]));
                threads[tid] = std::move(th);
            }

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

            for (int r : results) {
                ans += r;
            }
            cout << "\nFor key len = " << run << ", Total Valid sequences = " << ans;
            threads.clear();
            results.clear();
            auto end_run = std::chrono::steady_clock::now();
            auto elapsed_run = end_run - start_run;
            double elapsed_seconds_run = std::chrono::duration<double>(elapsed_run).count();
            if (profile_enabled)std::cout << ", Elapsed time(sec): " << elapsed_seconds_run;
        }
        cout << "\nUsed cpu cores = " << tth;
        auto end = std::chrono::steady_clock::now();
        auto elapsed = end - start;
        double elapsed_seconds = std::chrono::duration<double>(elapsed).count();
        if (profile_enabled)std::cout << "\n Total Elapsed time: " << elapsed_seconds << " seconds" << std::endl;

    }

};


int main(int argc, char* argv[])
{
    KeyBoardSequenceFinder SeqCalculator(argc,argv);
    SeqCalculator.MultiThreadedSolution_X();

    //for simple non threaded solution 
    //SeqCalculator.NonThreadedSolution_X();
    return 0;
}

Solution2 function is what all you want. Rest code is harware concurrency I did to refresh my skills.

For key len = 1, Total Valid sequences = 18, Elapsed time(sec): 0.0015133
For key len = 2, Total Valid sequences = 60, Elapsed time(sec): 0.0005201
For key len = 3, Total Valid sequences = 214, Elapsed time(sec): 0.0004622
For key len = 4, Total Valid sequences = 732, Elapsed time(sec): 0.0003648
For key len = 5, Total Valid sequences = 2486, Elapsed time(sec): 0.0004601
For key len = 6, Total Valid sequences = 8392, Elapsed time(sec): 0.0004138
For key len = 7, Total Valid sequences = 27912, Elapsed time(sec): 0.0007859
For key len = 8, Total Valid sequences = 93204, Elapsed time(sec): 0.0017012
For key len = 9, Total Valid sequences = 306288, Elapsed time(sec): 0.00047
For key len = 10, Total Valid sequences = 1013398, Elapsed time(sec): 0.000532