#include<optional>
#include<vector>
#include<iostream>

using namespace std;
enum opCode {
  start, // start loc
  send,  // send instrResult loc
  mix    // mix instrResult instrResult
};

struct instruction {
  opCode op;
  size_t x,y;
};

// If we specify that send and mix instructions consume their argument
// mixtures, we can verify in O(n). This is because we can never duplicate a
// chemical, so mixing the same chemical with itself is impossible by
// construction (sort of like linear types!). We can then replace the second
// check with a simple check that the value generated by an instruction hasn't
// been consumed already. 
bool verify(vector<instruction> &program){
  size_t n = program.size();
  // we now need to check if the mixture constructed by an instruction has been
  // consumed, so we use an optional, which if none means consumed
  vector<optional<size_t>> instrResultLoc(n);
  for(size_t i=0; i<n; i++){
    instruction &inst = program[i];
    switch(inst.op){
      case start:
        instrResultLoc[i] = inst.x;
        break;
      case send:
        // check that input hasn't been consumed already
        if(!instrResultLoc[inst.x]) return false;
        instrResultLoc[inst.x] = nullopt;  // consumes
        instrResultLoc[i] = inst.y;
        break;
      case mix:
        // if either input has been consumed already, fail
        if(!instrResultLoc[inst.x] || !instrResultLoc[inst.y]) return false;  
        // if the locations don't match, fail
        if(*instrResultLoc[inst.x] != *instrResultLoc[inst.y]) return false;
        // Also need to check we're not mixing an instructionResult with itself
        if(inst.x == inst.y) return false;
        instrResultLoc[i] = instrResultLoc[inst.x];
        // consumes input mixtures
        instrResultLoc[inst.x] = nullopt; 
        instrResultLoc[inst.y] = nullopt; 
        break;
    }
  }

  // We also can just store the size of the mixtures, summing with a mix
  // instruction, as we know they must be distinct. This lets us check the last
  // property that the final mixture contians all the chemicals in O(n) as
  // well.
  vector<size_t> numChemsAt(n);
  size_t numChems=0;
  for(size_t i=0; i<n; i++){
    instruction &inst = program[i];
    switch(inst.op){
      case start:
        numChems++;
        numChemsAt[i] = 1;
        break;
      case send:
        numChemsAt[i] = numChemsAt[inst.x];
        break;
      case mix:
        numChemsAt[i] = numChemsAt[inst.x] + numChemsAt[inst.y];
        break;
    }
  }
  if(numChemsAt[n-1] != numChems) return false;
  return true;
}
  

int main(){
  vector<instruction> exampleValidProgram = {{start, 0}, {start, 1}, {send, 0, 1}, {mix, 1, 2}};
  vector<instruction> exampleInvalidProgram = {{start, 0}, {start, 1}, {send, 0, 1}, {mix, 0, 2}};
  cout << "Example valid program " << (verify(exampleValidProgram) ? "is" : "is not") << " valid" << endl;
  cout << "Example invalid program " << (verify(exampleInvalidProgram) ? "is" : "is not") << " valid" << endl;
}