Phân tích

Tại Google Code Jam, chúng tôi luôn cố gắng khuyến khích nhiều ngôn ngữ lập trình khác nhau. Nhưng trong bài toán này, chúng tôi đã tiến xa hơn một chút bằng cách buộc bạn phải lập trình bằng ngôn ngữ khởi nguồn của tất cả — Máy Turing trừu tượng! Thật không may, Máy Turing trừu tượng khá cồng kềnh, và điều đó khiến ngay cả nhiệm vụ đơn giản ở đây cũng trở nên khá khó khăn.

Với rất ít quy tắc được cho phép, điều quan trọng là phải tận dụng các con số bạn có thể đánh dấu lên các cột đèn. Cách tiếp cận hiển nhiên là viết ra, có lẽ dưới dạng nhị phân, số bước bạn cần thực hiện, sau đó để robot đưa ra quyết định dựa trên đó. Tuy nhiên, cũng có một giới hạn khá chặt chẽ về số lượng bước di chuyển, điều đó có nghĩa là bạn không thể đủ khả năng quay lại điểm bắt đầu liên tục để kiểm tra số của mình. Bạn sẽ cần mang theo dữ liệu khi di chuyển.

Dưới đây là một cách hiệu quả để thực hiện việc này:

• Đầu tiên, viết khoảng cách bạn muốn đi về phía trước dưới dạng nhị phân, sử dụng các giá trị 1 và 2 để đại diện cho các chữ số nhị phân. Thông tin này bây giờ sẽ có sẵn trên các cột đèn bắt đầu.
• Sau đó lặp lại các bước sau:
  • Duyệt qua số đó từ phải sang trái và trừ đi 1 khi bạn đi qua.
  • Nếu số đó là 0, thì thả bánh ngay lập tức.
  • Nếu không, hãy duyệt qua số đó từ trái sang phải, sao chép mọi thứ sang bên phải một vị trí.

Khi bạn đã có thuật toán cấp cao, mỗi phần sẽ tương đối đơn giản để triển khai. Ví dụ, việc trừ đi 1 quy về việc hình thức hóa thuật toán trừ mà bạn đã học ở tiểu học:

• Bắt đầu ở trạng thái 1, trạng thái mà chúng ta sẽ sử dụng để chỉ ra rằng bạn chưa thực hiện phép trừ. Nếu chữ số cuối cùng là 1, bạn có thể thay thế nó bằng 0 và phép trừ hoàn tất, vì vậy hãy chuyển sang trạng thái 2. Nếu chữ số cuối cùng là 0, hãy thay thế nó bằng 1 nhưng bây giờ bạn cần mượn 1 từ chữ số trước đó, vì vậy hãy ở lại trạng thái 1. Dù thế nào đi nữa, hãy di chuyển đến chữ số trước đó.
• Khi bạn ở trạng thái 2, bạn chỉ đang di chuyển sang trái qua số đó mà không thay đổi bất cứ điều gì.
• Nếu bạn chạm đến đầu bên trái của số ở trạng thái 1, thì số đó chắc chắn đã là 0, vì vậy bạn nên thả bánh. Nếu không, bạn nên chuyển sang giai đoạn sao chép.

Giai đoạn sao chép cũng tương tự nhưng về mặt khái niệm thì đơn giản hơn.

Hầu như bất kỳ cách triển khai nào của thuật toán này cũng đủ tốt để giải bài toán, nhưng vẫn còn chỗ để tối ưu hóa hơn nữa nếu bạn muốn thử thách! Với giới hạn 30 quy tắc, chúng tôi đã có thể giảm số bước xuống còn khoảng 95,000. Dưới đây là chương trình đầy đủ để di chuyển 5,000 cột đèn:

0 0 -> E 1 1
1 0 -> E 2 3
2 0 -> E 3 1
3 0 -> E 4 3
4 0 -> E 5 2
5 0 -> E 6 3
6 0 -> E 7 1
7 0 -> E 8 3
8 0 -> W 9 3
9 0 -> R
10 0 -> E 11 0
9 1 -> W 9 3
10 1 -> W 10 1
9 2 -> W 10 1
10 2 -> W 10 2
9 3 -> W 10 2
10 3 -> W 10 3
11 1 -> E 12 0
12 0 -> W 9 3
12 1 -> E 12 1
12 2 -> E 13 1
12 3 -> E 14 1
13 0 -> W 10 1
13 1 -> E 12 2
13 2 -> E 13 2
13 3 -> E 14 2
14 0 -> W 10 2
14 1 -> E 12 3
14 2 -> E 13 3
14 3 -> E 14 3

Dựa trên phân tích chính thức của Google Code Jam.