Skip to content

Instantly share code, notes, and snippets.

@andrewljohnson
Created July 5, 2022 22:14
Show Gist options
  • Save andrewljohnson/dda1eb62306b31112bd05ee5df6f1c5f to your computer and use it in GitHub Desktop.
Save andrewljohnson/dda1eb62306b31112bd05ee5df6f1c5f to your computer and use it in GitHub Desktop.
/*
This method prints all possible blocks, recursively.
For example, if you have blockers A & B, and attacker C, there are three posible blocks.
No blockers:
A:
B:
C blocks A:
A: C
B:
C blocks B
A:
B: C
defenders is a vector of possible defender IDs (ints)
indexOfDefender is which ID in defenders is being grouped into a block on this iteration
blockAssignments is a vector of int vectors, where each vector represents an attacker than can have 0 or more blockers
FIRST ITERATION:
The first time this method is called, blockAssignments is a vector of empty vectors.
This is a valid move and the empty vector of vectors gets printed - this means none of the attackers is blocked.
NEXT ITERATION:
->If defenders is length 0, there are no other possible blocks and it returns, having printed the only valid move (i.e. no blocks).
->If defenders is greater than length 0, the defenders[indexOfDefender] is pushed into a vector in blockAssignments.
Then the function calls itself, this time with blockAssignments not empty, and indexOfDefender incremented.
On this recursive call, it prints blockAssignments which now has one int in one of the vectors.
If there is only one possible blocker, then it returns. Then in the outer call, the defender gets popped out of blockAssignment, then pushed into the next blockAssignment vector, and recurses.
If there is more than one blockers, it now loops within the inner call to add the other defenders into blockAsssignments.
*/
void groupDefenders(vector<vector<int>> blockAssignments, vector<int> defenders, int indexOfDefender) {
int x = 0;
for (vector<int> attackerBucket:blockAssignments) {
cout << x << ": ";
for (int defender:attackerBucket) {
cout << defender << " ";
}
cout << "\n";
x+= 1;
}
if(indexOfDefender == defenders.size()) {
return;
}
for(int v=0; v<blockAssignments.size();++v) {
vector<int> attacker = blockAssignments[v];
attacker.push_back(defenders[indexOfDefender]);
blockAssignments[v] = attacker;
groupDefenders(blockAssignments, defenders, indexOfDefender+1);
attacker.pop_back();
blockAssignments[v] = attacker;
}
}
@lacker
Copy link

lacker commented Jul 6, 2022

Yeah exactly - the line vector<int> attacker = blockAssignments[v] is doing a copy. Any time you just assign a vector to another vector it makes a copy. So you don't want to do that, you want to use one of the other two formulations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment