/*
 * Name: Owen Sullivan
 * Date Submitted: 12/5/2022
 * Lab Section: 006
 * Assignment Name: Lab 10: Using Breadth-First Search to Solve Puzzles
*/

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <bitset>
using namespace std;

// Reflects what each node represents...
// int with each bit == 0 left of river, bit == 1 right of river
typedef int state;

// Bit position representation for wolf/goat/cabbage/me
bool bit(int x, int i) { return (x>>i) & 1; }
const int wolf=0, goat=1, cabbage=2, me=3;

// GENERIC -- these shouldn't need to be changed...
map<state, bool> visited;         // have we queued up this state for visitation?
map<state, state> pred;           // predecessor state we came from
map<state, int> dist;             // distance (# of hops) from source node
map<state, vector<state>> nbrs;   // vector of neighboring states

map<pair<state,state>, string> edge_label;

// GENERIC (breadth-first search, outward from curnode)
void search(state source_node)
{
  queue<state> to_visit;
  to_visit.push(source_node);
  visited[source_node] = true;
  dist[source_node] = 0;
  
  while (!to_visit.empty()) {
    state curnode = to_visit.front();
    to_visit.pop();
    for (state n : nbrs[curnode])
      if (!visited[n]) {
	pred[n] = curnode;
	dist[n] = 1 + dist[curnode];
	visited[n] = true;
	to_visit.push(n);
      }
  }
}

string state_string(state s)
{
  string items[4] = { "wolf", "goat", "cabbage", "you" }, result = "";
  for (int i=0; i<4; i++)
    if (!bit(s, i)) result += items[i] + " ";
  result += " |river| ";
  for (int i=0; i<4; i++)
    if (bit(s, i)) result += items[i] + " ";
  return result;
}

// GENERIC
void print_path(state s, state t)
{
  if (s != t) {
    print_path(s, pred[t]);
    cout << edge_label[make_pair(pred[t], t)] << ": " << state_string(t) << "\n";
  } else {
    cout << "Initial state: " << state_string(s) << "\n";
  }
}

string neighbor_label(int s, int t)
{
  string items[3] = { "wolf", "goat", "cabbage" }, which_cross;
  if (bit(s,me) == bit(t,me)) return "";  // must cross river
  int cross_with = 0;
  for (int i=0; i<3; i++) {
    if (bit(s,i) != bit(t,i) && bit(s,i)==bit(s,me)) { cross_with++; which_cross = items[i]; }
    if (bit(s,i) != bit(t,i) && bit(s,i)!=bit(s,me)) return "";
  }
  if (cross_with > 1) return "";
  if (cross_with == 0) return "Cross alone";
  else return "Cross with " + which_cross;
}

// Function to determine whether or not a state is valid
// determined by constraints
bool validState(const bitset<4> &state) {

  // Wolf and goat cannot be left alone together
  if (state[wolf] == state[goat]) {

    // If person is present, state is valid
    if (state[wolf] == state[me]) {

      return true;

      // If person is not present, state is invalid
    } else {

      return false;

    }

    // Goat and cabbage cannot be left alone together
  } else if (state[goat] == state[cabbage]) {

    // If person is present, state is valid
    if (state[goat] == state[me]) {

      return true;

      // If person is not present, state is invalid
    } else {

      return false;

    }

    // All other combinations are valid
  } else {

    return true;

  }

}

// Function to return the integer evaluation of a bitset
int getIntState(const bitset<4> &state) {

  return (int)state.to_ulong();

}

void build_graph(void) {
  
  // Create bitset for current state, will initialize to all 0s
  bitset<4> currentState;
  // Create bitset for last possible state, 15 evaluates to "1111"
  bitset<4> lastState(15);

  // Loop through each possible state, determined by square of number of bits
  for (int i = 0; i < (lastState.size() * lastState.size()); i++) {

    // Loop through each bit in the current state
    for (int j = 0; j < lastState.size(); j++) {

      // The person can only cross the river with something if that thing 
      // is on the same side of the river as the person
      if (currentState[j] == currentState[me]) {

        // Create bitset for next state to be generated, assigning to 
        // the current state since we're building on the previous
        bitset<4> newState = currentState;

        // Flip the position of the person, which is equivalent to the person 
        // crossing the river
        newState[me].flip();
        // Make sure that the thing the person is trying to cross with isn't 
        // the person itself
        if (j != me) {

          // If not, have the thing cross
          newState[j].flip();

        }

        // Check that the new state doesn't violate safety constraints
        if (validState(newState)) {

          // Add the new state (integer form) to the neighbors map at the 
          // current state's key
          nbrs[getIntState(currentState)].push_back(getIntState(newState));
          
          // Generate the string matching the correct action to get from one 
          // state to the next, then add that string to the edge labels map 
          // at the pair of the current state and the new state
          edge_label[make_pair(getIntState(currentState), 
                               getIntState(newState))] = neighbor_label(getIntState(currentState), 
                                                                        getIntState(newState));
          
        }

      }

    }

    // Regardless of whether a new state was generated, increment the current 
    // state to move on to the next possible state
    currentState = getIntState(currentState) + 1;

  }

}

// int main(void)
// {
//   build_graph();

//   state start = 0, end = 15;
  
//   search(start);
//   if (visited[end])
//     print_path (start, end);
//   else
//     cout << "No path!\n";
  
//   return 0;
// }