lock_wrapper.cpp

// Author : Gourang Pathak
// Including required libraries
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <stdio.h>
#include <conio.h>
#include <iomanip>
#include <stdlib.h>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;
#define endl "\n"

class PrimeGenerator {
protected:
    int primeCount;
    vector<int> primeList;

public:
    PrimeGenerator() : primeCount(0) {}

    void generatePrimes(int limit) {
        primeList.clear();
        primeCount = 0;
        for (int num = 2; num <= limit; ++num) {
            bool isPrime = true;
            for (int i = 2; i * i <= num; ++i) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primeList.push_back(num);
                ++primeCount;
            }
        }
    }

    int modularMultiplicativeInverse(int a, int m) {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;
        if (m == 1) return 0;
        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }
        if (x1 < 0) x1 += m0;
        return x1;
    }

    virtual void displayPrimes() {
        for (int prime : primeList) {
            cout << prime << " ";
        }
        cout << endl;
    }
};

class CRTCalculator : public PrimeGenerator {
private:
    int mod;
    int rem;

public:
    CRTCalculator() : mod(0), rem(0) {}

    void applyChineseRemainderTheorem(const vector<int>& nums, const vector<int>& rems) {
        int k = nums.size();
        int prod = 1;
        for (int i = 0; i < k; i++) prod *= nums[i];
        int result = 0;
        for (int i = 0; i < k; i++) {
            int pp = prod / nums[i];
            result += rems[i] * modularMultiplicativeInverse(pp, nums[i]) * pp;
        }
        rem = result % prod;
        mod = prod;
    }

    void displayResult() {
        cout << "Result: " << rem << " Modulus: " << mod << endl;
    }

    void displayPrimes() override {
        cout << "Displaying primes from CRTCalculator:" << endl;
        PrimeGenerator::displayPrimes();
    }
};


// A simple function to check if a number is prime or not.
bool checkPrime(long long int num)
{
    // A number less than or equal to 1 isn't prime
    if (num <= 1)
    {
        return false;
    }
    // 2 and 3 are prime
    if (num <= 3)
    {
        return true;
    }
    // Any number that is divisible by 2 or 3 isn't prime
    if (num % 2 == 0 || num % 3 == 0)
    {
        return false;
    }
    // All other primes are of the form 6n + 1 or 6n - 1
    for (long long int i = 5; i * i <= num; i = i + 6)
    {
        if (num % i == 0 || num % (i + 2) == 0)
        {
            return false;
        }
    }
    return true;
}

// This function would return me the next prime number for a given number.
long long int next_prime(long long int num)
{
    if (num <= 1)
    {
        return 2;
    }
    long long int prime = num;
    bool found_prime = false;

    // Look for the next prime number ahead of current number.
    while (!found_prime)
    {
        prime++;
        if (checkPrime(prime))
        {
            found_prime = true;
        }
    }
    return prime;
}

// This function would generate the primary keys
void fillprimes(vector<long long int> &primary_keys, long long int x)
{
    int i = 1;
    primary_keys[0] = next_prime(x);
    while (i < primary_keys.size())
    {
        // Each of the next primary key is generated by using previous primary key's value.
        primary_keys[i] = next_prime(primary_keys[i - 1]);
        i++;
    }
}

/*
This function takes in an ID and checks if its present in the
config file or not, returns 1 if present, 0 otherwise
*/
int checkID(string id)
{
    int flag = 0;
    vector<string> vecOfStrs;
    fstream in("config.txt");
    string str;

    while (getline(in, str))
    {
        if (str.size() > 0)
        {
            vecOfStrs.push_back(str);
        }
    }

    for (string &s : vecOfStrs)
    {
        string temp = s.substr(0, s.find(' '));
        if (temp == id)
        {
            flag = 1;
        }
    }

    return flag;
}

// The Config Routine
void CONFIGURE(int key)
{
    // if Key == 1 we do the add operation
    if (key == 1)
    {
        int check;
        long long int k;
        long long int L;
        string id;
        FILE *fp1;
        fp1 = fopen("config.txt", "a");
        cout << "Enter LockerId: ";
        cin >> id;
        check = checkID(id);
        if (check == 1)
        {
            cout << "A Locker with given ID Already Exists, Use a differnt Locker ID please";
            return;
        }
        cout << "Enter No of Users: ";
        cin >> k;
        cout << "Enter 10 digit Locker Key L: ";
        cin >> L;
        /*
        Key Idea Used to generate the primary keys is

        L < p1*p2*p3*....*pk

        So, let p1 = p2 = p3 = ... = pk = p

        then L < p^k

        So, p > L^(1/k)

        Now we fill our primary keys so that each primary key is strictly more than L^(1/k)

        This ensures our overall product is more than L.
        */
        vector<long long int> primary_keys(k);
        vector<long long int> secondary_keys(k);

        double K_inv = double(1) / double(k);
        long long int x = pow(L, K_inv); // Finding x = L^(1/k)
        fillprimes(primary_keys, x);     // populate the primary keys

        for (int i = 0; i < primary_keys.size(); i++)
        {
            secondary_keys[i] = L % primary_keys[i]; // generate the secondary keys
        }

        // Outputting the Secondary Keys to the user.
        for (int i = 0; i < secondary_keys.size(); i++)
        {
            cout << "u" << i + 1 << " = " << setfill('0') << setw(4) << secondary_keys[i] << " ";
        }

        // File Handling Routine
        fprintf(fp1, "%s %d ", id.c_str(), k);
        for (auto &it : primary_keys)
        {
            fprintf(fp1, "%d ", it);
        }
        fprintf(fp1, "%s", "\n");
        fclose(fp1);
    }
    else if (key == 2)
    {
        // if Key == 2 we do the deletion operation
        string line, id;
        cout << "Enter LockerId: ";
        cin >> id;
        ifstream myfile;
        myfile.open("config.txt");
        ofstream temp;
        temp.open("temp.txt");
        while (getline(myfile, line))
        {
            if (line.substr(0, line.find(' ')) != id)
                temp << line << endl;
        }
        myfile.close();
        temp.close();
        remove("config.txt");
        rename("temp.txt", "config.txt");
    }
}

// Returns the modular multiplicative inverse of num1 w.r.t. num2
long long int modular_inverse(long long int num1, long long int num2)
{
    long long int second_num = num2, temp, quotient;
    long long int a = 0, b = 1;

    if (num2 == 1)
    {
        return 0;
    }

    /*
    ax + by = gcd(a, b) put b = m
    ax + my = gcd(a, m) = 1
    taking mod m both sides
    ax + my = 1 (mod m)
    since my (mod m) = 0
    ax  = 1 mod (m)

    Normal GCD
    int gcd(int num1, int num2)
    {
        if (num1 == 0)
            return num2;
        return gcd(num2 % num1, num1);
    }

    Extended GCD Updation 

    a = a1 - ⌊num2/num1⌋ * a1
    b = b1    

    As seen above, a and b are results for inputs num1 and num2,
    num1.a + num2.b = gcd                      ----(1)  

    And a1 and b1 are results for inputs num2%num1 and num1
    (num2%num1).a1 + num1.b1 = gcd   
                        
    When we put num2%num1 = (num2 - (⌊num2/num1⌋).num1) in above, 
    we get following. Note that ⌊num2/num1⌋ is floor(num2/num1)

    (num2 - (⌊num2/num1⌋).num1).a1 + num1.b1  = gcd

    Above equation can also be written as below
    num2.a1 + num1.(b1 - (⌊num2/num1⌋).a1) = gcd      ---(2)

    After comparing coefficients of 'num1' and 'num2' in (1) and 
    (2), we get following
    a = b1 - (⌊num2/num1⌋).a1
    b = a1

    35,2

    num1 = 35 num2 = 2
    iter1 num1 = 2 num2 = 1 a = 1 b = 0
    iter2 num1 = 1 num2 = 0 a = -2 b = 1
    end
    so (35 % 1) = 2 
    
    MI of 3 , 17 so
    17 = 3x5 + 2
    3 = 2x1 + 1
    2 = 17- 3x5
    1 = 3-2x1
    1 = 3 - (17 - 3x5)x1
    1 = 3x6 - 17x1
    so MI of 3 w.r.t 17 = 6
    (3*6) % 17 = 1
    */

    while (num1 > 1)
    {
        quotient = num1 / num2;
        temp = num2;

        num2 = num1 % num2, num1 = temp;

        temp = a;

        a = b - quotient * a;

        b = temp;
    }

    if (b < 0)
    {
        b += second_num;
    }
    return b;
}

long long int solve(vector<long long int> &numbers, vector<long long int> &remainders)
{
    /*
    L%p1 = u1 => u1 = L(mod p1)
    L%p2 = u2 => u2 = L(mod p2)
    ....
    ....
    L%pk = uk => uk = L(mod pk)

    Also,
        m[i] = (p[0]*p[1]*p[2]*....*p[k-1]) / p[i]

    KEY IDEA USED :
    L = (∑ (u[i] * m[i] * (modular multiplicative inverse of m[i]'s w.r.t. p[i]'s))) % (product_of_p[i]'s)

    Dry Run


    Let, L = 17 ,p[] = {2, 5, 7} & u[] = {1, 2, 3}
    product => 2*5*7 = 70
    m[]  = {35, 14, 10}
    modular inverse = {1,  4,  5}   because (35*1) % 2 = 1, (14*4) % 5 = 1 & (10*5) % 7 = 1

    L = (u[0]*m[0]*modular_inverse(m[0],p[0]) + u[1]*m[1]*modular_inverse(m[1],p[1]) + u[2]*m[2]*modular_inverse(m[2],p[2])) % product
    = (1*35*1 + 2*14*4 + 3*10*5) % 70 => 287 % 70 = 17

    */

    // Calculate the product of all numbers
    long long int product = 1;
    for (int i = 0; i < numbers.size(); i++)
    {
        product = product * numbers[i];
    }

    long long int ans = 0;

    // Compute m array
    vector<long long int> m;
    for (int i = 0; i < numbers.size(); i++)
    {
        m.push_back(product / numbers[i]);
    }

    for (int i = 0; i < numbers.size(); i++)
    {
        ans += remainders[i] * modular_inverse(m[i], numbers[i]) * m[i];
    }

    return (ans % product);
}

int USE()
{
    int flag = 0;
    string id;

    // storing each of the lines in the config file into a vector of strings
    vector<string> vecOfStrs;
    fstream in("config.txt");
    string str;

    while (getline(in, str))
    {
        if (str.size() > 0)
        {
            vecOfStrs.push_back(str);
        }
    }

    cout << "Enter LockerId: ";
    cin >> id;

    vector<long long int> myNumbers;
    for (string &s : vecOfStrs)
    {
        string temp = s.substr(0, s.find(' '));
        if (temp == id)
        {
            stringstream iss(s.substr(temp.length(), s.length() - temp.length()));
            long long int number;
            while (iss >> number)
                myNumbers.push_back(number);
        }
    }

    // if myNumbers list is empty this means there isn't any Locker with given ID
    if (myNumbers.size() == 0)
    {
        flag = 1;
        return flag;
    }

    long long int n = myNumbers[0]; // Number of Users
    vector<long long int> primary_keys(n);
    vector<long long int> secondary_keys(n);

    for (int i = 1; i < myNumbers.size(); i++)
    {
        primary_keys[i - 1] = myNumbers[i];
    }

    for (int i = 0; i < n; i++)
    {
        cout << "Enter Userkey" << i + 1 << ": ";
        string temp;
        cin >> temp;
        temp.erase(0, min(temp.find_first_not_of('0'), temp.size() - 1));
        secondary_keys[i] = stoi(temp);
    }

    cout << "The Access Code is : " << solve(primary_keys, secondary_keys);
    return flag;
}

void Menu()
{
    int choice;
    int fg;
    do
    {
        cout << "\n\n1. CONFIGURE\n2. USE\n3. EXIT\nMention your preference (1/2/3): ";
        cin >> choice;
        switch (choice)
        {
        case 1:
            int subchoice;
            cout << "\n\n1. Add New Locker Entry\n2. Delete a locker entry\n3. Return\nMention your preference (1/2/3): ";
            cin >> subchoice;
            switch (subchoice)
            {
            case 1:
                CONFIGURE(1);
                break;
            case 2:
                CONFIGURE(2);
                cout << "Entry Successfully Deleted/Invalid Entry";
                break;
            case 3:
                cout << "Exiting configure...";
                break;
            default:
                cout << "Enter 1,2 or 3 only";
                break;
            }
            break;
        case 2:
            fg = USE();
            if (fg == 1)
                cout << "Locker Key doesn't exist";
            break;
        case 3:
            cout << "Exiting...";
            break;
        default:
            cout << "Enter 1,2 or 3 only";
            break;
        }
    } while (choice != 3);
}

int main()
{
    cout << "=================================== WELCOME TO SHARED LOCKER ===================================";
    Menu();
    return 0;
}