#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<string> V; // words from wordlist05.txt

// Global variables for bfs distance, bfs predecessor, and neighboring nodes
// Should be unordered_map type
unordered_map<string, bool> visited;
unordered_map<string, string> pred;
unordered_map<string, int> dist;
unordered_map<string, vector<string>> nbrs;

// Function that creates a path from the source word to the target word 
// and returns the number of steps in-between
int getNumSteps(string source, string target, vector<string> &path) {

  int numSteps = 0;

  // Check to make sure the target word has a predecessor
  if (pred.end() != pred.find(target)) {

    // If the source and target words are the same, the path is just the word
    if (source.compare(target) == 0) {

      path.push_back(target);

      // If the source and target words are not the same, recursively call 
      // getNumSteps to find the path and number of steps between the source 
      // word and the target word's predecessor
    } else {

      numSteps = getNumSteps(source, pred[target], path) + 1;

      path.push_back(target);

    }

  }

  return numSteps;

}

// Implement breadth-first search, refer to Lab 10
void wordLadder(string s, string t, int &steps, vector<string> &p) {
  
  // Open input file wordlist05.txt
  ifstream inFile("wordlist05.txt");

  // Read a word from the input file until there are none left, and add each 
  // word to the words vector V
  string currentWord;
  while (inFile >> currentWord) {

    V.push_back(currentWord);

  }

  // Loop through each string in words vector V
  for (string word : V) {

    // Loop through each character in the current word
    for (int pos = 0; pos < word.size(); pos++) {

      // Loop through every lowercase letter from a to z
      for (char letter = 'a'; letter <= 'z'; letter++) {

        // If the current letter being tested is not already at the current 
        // position in the current word, create a neighbor word and 
        // add it to nbrs
        if (word.at(pos) != letter) {

          string neighbor = word;
          neighbor.at(pos) = letter;
          nbrs[word].push_back(neighbor);

        }

      }

    }

  }

  // Create a queue for words to be visited
  queue<string> toVisit;

  // Add the source word to the queue, set the status of visited for the 
  // source word to true, and set the distance to the source word to 0
  toVisit.push(s);
  visited[s] = true;
  dist[s] = 0;

  // Loop until there are no more words left to visit
  while (!toVisit.empty()) {

    // Get the first word from the queue
    string currentNode = toVisit.front();
    toVisit.pop();

    // Loop through each neighbor that exists for the current word
    for (string neighbor : nbrs[currentNode]) {

      // If the current neighbor hasn't been visited, set the current word 
      // as the predecessor for the current neighbor, set a distance of 1, 
      // set the status of visited for the neighbor to true, and add the 
      // neighbor to the queue
      if (!visited[neighbor]) {

        pred[neighbor] = currentNode;
        dist[neighbor] = dist[currentNode] + 1;
        visited[neighbor] = true;
        toVisit.push(neighbor);

      }

    }

  }

  // Call helper function getNumSteps to determine the number of steps 
  // from the source word to the target word
  steps = getNumSteps(s, t, p);

}

// int main(void) {
  
//   int steps = 0;
//   string s, t;
//   vector<string> path;
  
//   cout << "Source: ";
//   cin >> s;

//   cout << "Target: ";
//   cin >> t;

//   wordLadder(s, t, steps, path);

//   if (steps == 0) {
    
//     cout << "No path!\n";
  
//   } else {
    
//     cout << "Steps: " << steps << "\n\n";
//     for (int i = 0; i < path.size(); i++) {
      
//       cout << path[i] << endl;
    
//     }
  
//   }
  
//   return 0;

// }