diff options
Diffstat (limited to 'prison_cells_n_days.py')
-rw-r--r-- | prison_cells_n_days.py | 36 |
1 files changed, 36 insertions, 0 deletions
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)) |