Pragmatic Programmer – Topic 46: Solving Impossible Puzzles — Phá bẫy | Blog

Mở đầu

Hồi còn đi học, mình có một buổi tối ngồi với bài puzzle kinh điển: nối 9 chấm xếp thành hình vuông bằng đúng 4 đường thẳng, không nhấc bút. Mình vẽ tới vẽ lui cả tiếng, kẹt cứng. Tới khi thầy phóng bút vẽ vượt ra ngoài cái ô vuông tưởng tượng, mình mới vỡ lẽ: từ đầu tới cuối chẳng ai cấm vẽ ra ngoài — tự mình cấm mình thôi. Topic 46 của Pragmatic Programmer tên là Solving Impossible Puzzles, và thông điệp chính của nó cũng y hệt: đa số bài toán "bất khả thi" trong code, bất khả thi vì chính ta tự đặt ràng buộc.

Những mảnh ghép puzzle đầy màu sắc nằm rải rác Ảnh: DS stories — Pexels

Ràng buộc nào thật, ràng buộc nào tự đặt?

Sách gọi thứ này là degrees of freedom — độ tự do của bài toán. Cách làm được đề nghị: viết hết các ràng buộc ra giấy, rồi chất vấn từng cái một. Cái nào đến từ yêu cầu thật (hạ tầng, pháp lý, budget), cái nào chỉ là thói quen, là "từ xưa giờ vẫn vậy"?

Mình nhớ có lần kẹt cả tuần với chuyện "không thể thêm cột sort mới vì database production đang chạy, ALTER TABLE sẽ lock cả bảng". Nghe thì có vẻ bất khả thi thiệt. Nhưng ràng buộc thật chỉ là "không được downtime", còn "phải sửa ngay trên bảng chính" là do mình tự áp đặt. Đổi qua migration kiểu expand-contract — thêm cột mới, ghi song song, rồi mới chuyển — xong trong một buổi chiều.

Ngay cả những "chân lý" trong lập trình cũng có thể là ràng buộc tự đặt. Ai cũng thuộc lòng "không thể sort nhanh hơn O(n log n)" — nhưng câu đó chỉ đúng với comparison sort, khi ràng buộc là "so sánh từng cặp". Đổi ràng buộc một chút, bài toán đổi luôn:

# "Sort không thể nhanh hơn O(n log n)" — chỉ đúng khi so sánh từng cặp
def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result  # O(n + max_val) — vượt "giới hạn" vì đổi góc nhìn

Kẹt thì đổi góc nhìn, hoặc gọi người khác vô

Một cách phá bẫy khác sách nhắc: đổi góc nhìn. Khi mắc kẹt quá lâu, bước ra ngoài một lúc, hoặc nhờ đồng nghiệp nhìn dùm. Người ngoài cuộc không mang theo đống giả định của mình — họ thấy cái cửa sổ mà mình tưởng là bức tường. Mình nghiệm ra cái này đúng ghê: nhiều bug "không thể sửa" chỉ vì mình đã nhìn đoạn code đó đủ lâu để tin nó phải như vậy.

Cũng đáng hỏi ngược một câu: mình có đang giải đúng bài toán không? Nhiều khi "impossible" chỉ vì đang giải bài toán sai — xài cái metric không cần thiết, tối ưu chỗ không ai ngó tới. Đổi câu hỏi, tự nhiên thấy đường.

Mê cung trừu tượng với lối đi chằng chịt Ảnh: Steve A Johnson — Pexels

Nhưng có thật sự có bài bất khả thi

Sách cũng thẳng thắn, không phải puzzle nào cũng có lời giải. Có những bài toán chứng minh được là không giải được — halting problem chẳng hạn, hay lớp NP-complete. Gặp loại này mà cắm đầu giải là phí đời. Cách pragmatic: nhận diện sớm, rồi xài giải pháp xấp xỉ, heuristic, hoặc đổi bài toán thành thứ giải được. Thay vì đòi kết quả chính xác tuyệt đối, chấp nhận "đủ tốt" và đo lường được.

Quân tốt cờ vua đứng trước hai quân cờ mờ phía sau Ảnh: George Becker — Pexels

Kết bài

Trước khi kết luận "impossible", thử làm ba việc: kê ràng buộc ra giấy, chất vấn từng cái xem thật hay tự đặt, rồi đổi góc nhìn hoặc nhờ người khác soi giúp. Phân biệt "khó" với "thật sự không làm được" — phần lớn thứ ta gọi là bất khả thi trong code, thiệt ra chỉ là cái hộp do chính mình vẽ lên. Đập cái hộp đó xuống là xong.

Mấy bạn có bao giờ kẹt một bài toán tưởng bế tắc, rồi một ngày nhận ra ràng buộc tự mình đặt ra không? Hồi đó cái gì giúp bạn thoát — đi cà phê, hỏi đồng nghiệp, hay ngủ một giấc rồi sáng ra thấy đường?