โปรแกรมหาสถานะห้องจำคุกหลัง k วันใน Python

มีรายการไบนารีแทนห้องจำคุก 1=มีคน 0=ว่าง ทุกวัน: ถ้าเพื่อนบ้านซ้ายขวาเหมือนกัน (ทั้งคู่ 1 หรือทั้งคู่ 0) กลายเป็น 1 มิฉะนั้น 0 ห้องแรกและสุดท้ายเป็น 0 ตลอด หาสถานะหลัง k วัน

เช่น nums=[1,0,1,0,0,0,0,0], k=1 ให้ [0,1,1,0,1,1,1,0]

ขั้นตอนการแก้ปัญหา

• ฟังก์ชัน next_day_state: สร้าง new_cells, เซ็ทหัวท้าย=0, กลางเช็คเพื่อนบ้าน
• ใช้ seen dict ตรวจจับ cycle
• พบ cycle: N = N % len(seen) แล้วจำลองต่อ

ตัวอย่างโค้ด

import copy
class Solution:
    def next_day_state(self, cells):
        new_cells = copy.copy(cells)
        new_cells[0] = 0; new_cells[7] = 0
        for j in range(1,7):
            new_cells[j] = 1 if cells[j-1] == cells[j+1] else 0
        return new_cells
    def solve(self, cells, N):
        seen = {}; flag, i = False, 0
        while i < N:
            ns = self.next_day_state(cells)
            if tuple(ns) not in seen: seen[tuple(ns)] = True
            else: flag = True; break
            cells = ns; i += 1
        if flag:
            N = N % len(seen); i = 0
            while i < N:
                ns = self.next_day_state(cells); i += 1; cells = ns
        return cells

ob = Solution()
nums = [1,0,1,0,0,0,0,0]; k = 1
print(ob.solve(nums, k))

อินพุต

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

เอาต์พุต

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