aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--prison_cells_n_days.c56
-rw-r--r--prison_cells_n_days.py36
2 files changed, 92 insertions, 0 deletions
diff --git a/prison_cells_n_days.c b/prison_cells_n_days.c
new file mode 100644
index 0000000..a31988d
--- /dev/null
+++ b/prison_cells_n_days.c
@@ -0,0 +1,56 @@
+// 957. Prison Cells After N Days
+#include "leetcode.h"
+
+/*
+ * there are 8 prison cells in a row and each cell is either occupied or vacant.
+ * each day, whether the cell is occupied or vacant changes according to the
+ * following rules: if a cell has two adjacent neighbours that are both occupied
+ * or both vacant, then the cell becomes occupied, otherwise it becomes vacant.
+ * note that because the prison is a row, the first and the last cells in the
+ * row can't have two adjacent neighbours. you are given an integer array
+ * 'cells' where 'cells[i] == 1' if the i'th cell is occupied and 'cells[i] ==
+ * 0' if the i'th cell is vacant, and you are given an integer 'n'. return the
+ * state of the prison after 'n' days (ie. 'n' such changes desribed above)
+ */
+
+int *prisonAfterNDays(int *cells, int cellsSize, int n, int *returnSize) {
+ *returnSize = cellsSize;
+ int state = 0;
+ for (int i = 0; i < cellsSize; i++)
+ if (cells[i])
+ state |= 1 << (7 - i);
+ n = (n % 14) + 14;
+ for (int i = 0; i < n; i++) {
+ int clear = 0, set = 0;
+ for (int j = 1; j < 7; j++) {
+ int low = (1 << (8 - j)), high = (1 << (6 - j));
+ if (((low & state) == low && (high & state) == high) ||
+ (!(low & state) && !(high & state)))
+ set |= 1 << (7 - j);
+ else
+ clear |= 1 << (7 - j);
+ }
+ state &= ~0x81;
+ state &= ~clear;
+ state |= set;
+ }
+ int *ans = (int *)calloc(cellsSize, sizeof(int));
+ for (int i = 0; i < cellsSize; i++)
+ if (1 << (7 - i) & state)
+ ans[i] = 1;
+ return ans;
+}
+
+int main() {
+ int c1[] = {0, 1, 0, 1, 1, 0, 0, 1}, c2[] = {1, 0, 0, 1, 0, 0, 1, 0}, rs1,
+ rs2;
+ int *pand1 = prisonAfterNDays(c1, ARRAY_SIZE(c1), 7, &rs1);
+ int *pand2 = prisonAfterNDays(c2, ARRAY_SIZE(c2), 1000000000, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pand1[i]); // expect: [0,0,1,1,0,0,0,0]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pand2[i]); // expect: [0,0,1,1,1,1,1,0]
+ printf("\n");
+ free(pand1), free(pand2);
+}
diff --git a/prison_cells_n_days.py b/prison_cells_n_days.py
new file mode 100644
index 0000000..e8b7524
--- /dev/null
+++ b/prison_cells_n_days.py
@@ -0,0 +1,36 @@
+# 957. Prison Cells After N Days
+
+"""
+there are 8 prison cells in a row and each cell is either occupied or vacant.
+each day, whether the cell is occupied or vacant changes according to the
+following rules: if a cell has two adjacent neighbours that are both occupied
+or both vacant, then the cell becomes occupied, otherwise it becomes vacant.
+note that because the prison is a row, the first and the last cells in the
+row can't have two adjacent neighbours. you are given an integer array
+'cells' where 'cells[i] == 1' if the i'th cell is occupied and 'cells[i] ==
+0' if the i'th cell is vacant, and you are given an integer 'n'. return the
+state of the prison after 'n' days (ie. 'n' such changes desribed above)
+"""
+
+
+class Solution(object):
+ def prisonAfterNDays(self, cells, n):
+ """
+ :type cells: List[int]
+ :type n: int
+ :rtype: List[int]
+ """
+ vis = {str(cells): n}
+ while n:
+ vis.setdefault(str(cells), n)
+ n -= 1
+ cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
+ if str(cells) in vis:
+ n %= vis[str(cells)] - n
+ return cells
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.prisonAfterNDays(cells=[0, 1, 0, 1, 1, 0, 0, 1], n=7))
+ print(obj.prisonAfterNDays(cells=[1, 0, 0, 1, 0, 0, 1, 0], n=1000000000))