Today we have, in my opinion, a really interesting problem to work on! I would describe this problem as a highly restricted game of life variation. The general idea is that we are given a list of cells, here of fixed length eight, where each cell is in a binary state, 1 or 0. We are then given an integer, $n$, which indicates the target number of iterations which the cell list should undergo. Each iteration is performed by applying a provided set of rules:

  • If a cell has two adjacent neighbors that are either both occupied or both unoccupied, the cell becomes occupied.
  • Otherwise, the cell becomes unoccupied. For example:

[1,0,1,1,0,0,0,1]

$n = 1$

[0,1,0,0,0,1,0,0]

The problem has a simple, naive approach where we simply simulate $n$ permutations on the given cell list. While this method is valid, we are given, as an input space constraint, that $1 \leq n \leq 10^9$. Looking at that upper bound of $1,000,000,000$, and taking into account each iteration in simulation will again iterate over eight cell elements, it’s safe to assume we should seek a more efficient solution.

The key here is to look at the cell-line as essentially an eight bit value. From that fact, we can deduce that no matter what the rules, there are only 256 possible permutations of the cell-line. Expanding on this point, because the rule set applies uniformly, any idential permutation will result in a permutation cycle identical to any other permutation of the same identity. With these two ideas, we have everything needed to build a more efficient algorithm. The idea is to store each iteration of the cell-line in a map with its corresponding iteration number. Once a cell-line permutation repitition is detected, we mark both the cycle’s starting iteration and the length of the cycle. These two number allow us to calculate the remaining iterations needed from the cycle start point as an invariant, $(n - cyclestart) \% cyclelength$. With these steps, we can take the algorithm from a brute force asymptotic complexity of O(n) to what I would arguably describe as a constant time, O(1), algorithm that has an upper bound of $256 \cdot log(256)$, given that the upper bound of iterations for cycle detection is 256, and each iteration requires the traversal of a C++ map–internally represented as a binary tree, which brings up an additional point. This efficiency of this algorithm could likely be further improved by either providing a custom vector hash function, or using the boost library’s VectorHash function, which would all the use of a std::unordered map, with its attending benefits for this use case.

Overall, another really fun problem! Check out the code below and let me know if you have any comments!

vector<int> prisonAfterNDays(vector<int>& cells, int N) {
   // Would be better as an unordered map, but it would require a
   //  a custom vector hashing function.
   map<vector<int>,int> permutationMap;

   int cycleStart, cycleLength = 0;
   for(int i=0;i<N;i++) {
	  permutationMap[cells] = i;
	  int prev = cells[0];
	  for(int i=1;i<7;i++) {
		 int temp = cells[i];
		 if(prev == cells[i+1]) cells[i] = 1;
		 else cells[i] = 0;
		 prev = temp;
	  }
	  cells[0] = 0;
	  cells[7] = 0;

	  if(permutationMap.count(cells)) {
		 cycleStart = permutationMap[cells];
		 cycleLength = i - permutationMap[cells] + 1;
		 break;
	  }
   }
   if(cycleLength == 0) return cells;

   for(int i=0;i < (N-cycleStart) % cycleLength;i++) {
	  int prev = cells[0];
	  for(int i=1;i<7;i++) {
		 int temp = cells[i];
		 if(prev == cells[i+1]) cells[i] = 1;
		 else cells[i] = 0;
		 prev = temp;
	  }
	  cells[0] = 0;
	  cells[7] = 0;
   }
   return cells;
}