সমস্যা বিবরণ
একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে (১ = জীবিত সেল, ০ = মৃত সেল)। প্রতিটি সেলের ৮টি পড়োসি (horizontal, vertical, diagonal) আছে। নেক্সট স্টেটের নিয়ম:
- জীবিত সেল যുടെ ২ বা ৩টি জীবিত পড়োসি → জীবিত থাকে
- মৃত সেল যude ৩টি জীবিত পড়োসি → জীবিত হয়
- অন্য সব → মৃত হয়
উদাহরণ
Input:
[[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 1],
[1, 1, 0, 1]]
Output:
[[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]]
পাইথন কোড (ইন-প্লেস অপ্টিমাইজড)
class Solution:
def solve(self, board):
if not board:
return board
n, m = len(board), len(board[0])
# ডিরেকশন ভেক্টর (৮ পড়োসি)
dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
# ফেজ ১: স্টেট এনকোড (ইন-প্লেস)
# 0: dead→dead, 1: live→live, 2: dead→live, 3: live→dead
for i in range(n):
for j in range(m):
live_neighbors = 0
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < m and board[ni][nj] in (1, 3):
live_neighbors += 1
if board[i][j] == 1: # জীবিত
if live_neighbors not in (2, 3):
board[i][j] = 3 # live→dead
else: # মৃত
if live_neighbors == 3:
board[i][j] = 2 # dead→live
# ফেজ ২: ডিকোড
for i in range(n):
for j in range(m):
if board[i][j] == 2:
board[i][j] = 1
elif board[i][j] == 3:
board[i][j] = 0
return board
ob = Solution()
matrix = [
[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 1],
[1, 1, 0, 1]
]
print(ob.solve(matrix))
প্রদত্ত কোড রিভিউ
প্রদত্ত কোড নতুন res ম্যাট্রিক্স বানায় (O(n×m) এক্সট্রা স্পেস)। ইন-প্লেস এনকোডিং (স্টেট ২, ৩) ব্যবহার করলে O(1) এক্সট্রা স্পেস।
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(n × m) — প্রতিটি সেল ৮ পড়োসি চেক
- স্থান জটিলতা: O(1) এক্সট্রা (ইন-প্লেস) বা O(n×m) (নতুন ম্যাট্রিক্স)
অপ্টিমাইজেশন টিপস
- বড় গ্রিডের জন্য নাম্পাই (NumPy) কনভলিউশন ব্যবহার করুন
- SPARSE গ্রিডের জন্য শুধু লাইভ সেল ট্র্যাক করুন (HashSet)
- প্যারালেল প্রসেসিং: রো-wise ইনডিপেনডেন্ট
উপসংহার
- Game of Life — সেলুলার অটোমাটা ক্লাসিক
- ইন-প্লেস স্টেট এনকোডিং (২, ৩) স্পেস সেভ করে
- নাম্পাই/সাইপাই দিয়ে বড় সিমুলেশন দ্রুত
