#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Task 1: Populate board using user input
void populateBoard(char board[5][5]) {
    string userWord;

    for (int i = 0; i < 5; ++i) {
        cout << "Enter the input of 5 length of characters: " << endl;
        cin >> userWord;
        for (int k = 0; k < 5; ++k) {
            char letter = userWord.at(k);
            board[i][k] = letter;
        }
    }
}

// Task 2: Check if a word is in the dictionary using binary search
int binarySearchString(string searchWord, vector<string> dictionary) {
    int low = 0;
    int high = dictionary.size() - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int searchResult = searchWord.compare(dictionary[mid]);

        if (searchResult == 0) {
            return mid; // Word found in the dictionary
        } else if (searchResult < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1; // Word not found in the dictionary
}

void checkExists(char board[5][5], vector<string> dictionary) {
    for (int i = 0; i < 5; ++i) {
        string word = "";
        for (int j = 0; j < 5; ++j) {
            word += board[i][j];
        }
        int isWord = binarySearchString(word, dictionary);
        if (isWord == -1) {
            cout << "Row " << i << " word does not exist in dictionary" << endl;
        } else {
            cout << "Row " << i << " word does exist in dictionary" << endl;
        }
    }
}

// This function displays a board that is given through parameters
void displayBoard(char board[5][5]) {
    for (int row = 0; row < 5; row++) {
        cout << "-----------" << endl;
        cout << "|";
        for (int col = 0; col < 5; col++) {
            cout << board[row][col] << "|";
        }
        cout << endl;
    }
    cout << "-----------" << endl;
}

int main() {
    char board[5][5] = {
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' '}
    };

    vector<string> dictionary = {"enter", "hello", "mixed", "shift", "world"};

    int task;

    cout << "Enter the task you want to execute:" << endl
         << "1 for populate board " << endl
         << "2 for check word is existed in the dictionary " << endl
         << "3 for counting how many operations are needed for binary search " << endl
         << endl;
    cin >> task;
    if (task == 1) {
        populateBoard(board);
        displayBoard(board);
    } else if (task == 2) {
        populateBoard(board);
        displayBoard(board);
        checkExists(board, dictionary);
    } else if (task == 3) {
        // Uncomment below code block to test Extra Credit Task
        // string candidateWord;
        // cout << "Enter the word :";
        // cin >> candidateWord;
        // countingNumOfComparison(candidateWord, dictionary);
    }
}