Last active
November 23, 2025 00:35
-
-
Save stelleg/8c8d1e9998b2c84108110cf67d709eb5 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment