diff options
-rw-r--r-- | prison_cells_n_days.c | 56 | ||||
-rw-r--r-- | prison_cells_n_days.py | 36 |
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)) |