Palindrome, Ambigram và Anagram - Toán học của trò chơi chữ sinh ra từ số ký tự

Đọc "racecar" ngược lại vẫn là "racecar." Đằng sau trò chơi đơn giản này ẩn chứa toán học sâu sắc liên quan đến lý thuyết tổ hợp, lý thuyết độ phức tạp tính toán và cấu trúc ngôn ngữ. Palindrome, anagram, pangram, lipogram. Những trò chơi chữ sinh ra từ các ràng buộc về thứ tự sắp xếp và số lượng ký tự này vừa là đề bài kinh điển trong các cuộc thi lập trình, vừa là nền tảng của mật mã học, và trên hết là trò chơi trí tuệ thách thức giới hạn năng lực ngôn ngữ của con người.

Palindrome - Đọc xuôi hay ngược đều giống nhau

Palindrome là văn bản đọc từ trước ra sau hay từ sau ra trước đều giống nhau. Trong tiếng Nhật, các ví dụ nổi tiếng bao gồm "shinbunshi" (báo), "tomato" và "shinbunshi" (giấy báo). Trong tiếng Anh, "racecar," "madam" và "A man, a plan, a canal: Panama!" là những ví dụ kinh điển.

Palindrome tiếng Nhật có những quy tắc đặc biệt không có trong tiếng Anh. Có quy ước bỏ qua dấu dakuten (dấu thanh) và handakuten (dấu bán thanh). Sự "linh hoạt" này làm phong phú thêm palindrome tiếng Nhật, nhưng từ góc độ quy tắc cơ bản của văn bản tiếng Nhật, nó cũng khiến tiêu chí phát hiện palindrome trở nên mơ hồ.

Tác phẩm palindrome dài nhất được biết đến là tiểu thuyết palindrome tiếng Anh do Lawrence Levine xuất bản năm 2002, dài khoảng 17.826 từ (khoảng 58.000 ký tự). Trong tiếng Nhật, bộ sưu tập palindrome của Koichi Tsuchiya nổi tiếng với các palindrome dài hàng trăm ký tự.

Thuật toán phát hiện Palindrome - Sự thanh lịch của O(n)

Trong lập trình, thuật toán xác định xem một chuỗi có phải palindrome hay không là đề tài nhập môn lý tưởng cho lý thuyết độ phức tạp tính toán. Phương pháp đơn giản nhất là đảo ngược chuỗi và so sánh với chuỗi gốc, đạt độ phức tạp thời gian O(n) và không gian O(n).

Phương pháp hiệu quả hơn đặt hai con trỏ ở hai đầu chuỗi và so sánh từng ký tự hướng vào giữa. Phương pháp này đạt độ phức tạp thời gian O(n) với không gian O(1).

Thuật toán Manacher có thể phát hiện tất cả các chuỗi con palindrome trong thời gian O(n). Được Glenn Manacher công bố năm 1975, thuật toán này tính toán hiệu quả bán kính palindrome dài nhất tại mỗi vị trí. Ý tưởng cốt lõi là giảm phương pháp ngây thơ O(n²) xuống O(n) bằng cách tận dụng tính đối xứng của các palindrome đã tính trước đó.

Trong các cuộc thi lập trình (AtCoder, LeetCode, v.v.), bài toán palindrome xuất hiện thường xuyên. "Longest Palindromic Substring" của LeetCode là câu hỏi phỏng vấn kinh điển. Kiến thức về khớp mẫu trong số ký tự và thiết kế biểu thức chính quy cũng có thể áp dụng cho phát hiện palindrome.

Phát hiện palindrome tiếng Nhật cần tiền xử lý bổ sung: chuẩn hóa dakuten và handakuten, xử lý dấu trường âm "ー", và quyết định xem âm rút gọn (như "kyo") được tính là 1 hay 2 ký tự. Các quy tắc này khác nhau giữa các cộng đồng palindrome và không có tiêu chuẩn thống nhất.

Anagram - Sự bùng nổ tổ hợp từ việc sắp xếp lại ký tự

Anagram là trò chơi chữ sắp xếp lại các ký tự của một từ hoặc câu để tạo thành từ hoặc câu có nghĩa khác. Ví dụ nổi tiếng trong tiếng Anh bao gồm "listen" và "silent", "astronomer" và "moon starer".

Số tổ hợp anagram lý thuyết từ một từ n ký tự là n! (n giai thừa). Tuy nhiên, cần loại bỏ trùng lặp khi cùng một ký tự xuất hiện nhiều lần.

Khi số ký tự tăng, số tổ hợp bùng nổ nhưng xác suất tạo thành từ có nghĩa giảm mạnh. Tìm anagram có nghĩa từ 10 ký tự trở lên cực kỳ khó ngay cả trong tiếng Anh.

Cách hiệu quả nhất để phát hiện anagram trong lập trình là sắp xếp các ký tự của hai chuỗi rồi so sánh. Sắp xếp "listen" được "eilnst", sắp xếp "silent" cũng được "eilnst", xác nhận chúng là anagram. Phương pháp này có độ phức tạp O(n log n). Phương pháp nhanh hơn O(n) đếm tần suất mỗi ký tự rồi so sánh.

Anagram có mối liên hệ sâu sắc với lịch sử mật mã học. Vào thế kỷ 17, các nhà khoa học sử dụng anagram để khẳng định quyền ưu tiên cho phát hiện của mình. Galileo công bố phát hiện vành đai Sao Thổ dưới dạng anagram "smaismrmilmepoetaleumibunenugttauiras", sau đó tiết lộ đó là anagram của "Altissimum planetam tergeminum observavi" (Tôi đã quan sát hành tinh cao nhất là ba phần).

Pangram - Thách thức sử dụng mọi chữ cái

Pangram là câu sử dụng mỗi chữ cái trong bảng chữ cái ít nhất một lần. Pangram tiếng Anh nổi tiếng nhất là "The quick brown fox jumps over the lazy dog," chứa tất cả 26 chữ cái trong 35 ký tự (không tính dấu cách).

Pangram hoàn hảo (perfect pangram) sử dụng mỗi chữ cái đúng một lần. Pangram hoàn hảo tiếng Anh phải gồm đúng 26 ký tự, khiến việc tạo câu có nghĩa cực kỳ khó. "Mr Jock, TV quiz PhD, bags few lynx" (26 ký tự) là một ví dụ hơi gượng ép.

Tiếng Nhật có pangram có lẽ đẹp nhất thế giới: bài thơ Iroha.

"Iro ha nihoheto / chirinuru wo / waka yo tare so / tsune naramu / uwi no okuyama / kefu koete / asaki yume mishi / wehi mo sesu"

Bài thơ này sử dụng tất cả 47 ký tự kana thời đó, mỗi ký tự đúng một lần - một pangram hoàn hảo - đồng thời là bài waka có ý nghĩa thể hiện quan niệm vô thường của Phật giáo. Được cho là ra đời vào khoảng thế kỷ 10, bài thơ này là di sản trí tuệ của nhân loại đạt được cả ràng buộc toán học lẫn vẻ đẹp văn học.

Kana tiếng Nhật hiện đại gồm 46 ký tự ("wi" và "we" bị bãi bỏ, "n" được thêm vào), nhưng bài Iroha không chứa "n". Nhiều người đã thử tạo pangram hoàn hảo với 46 kana hiện đại nhưng chưa ai sánh được vẻ đẹp của bài Iroha. Ràng buộc càng nghiêm ngặt, giá trị của tác phẩm thỏa mãn nó càng cao.

Pangram tiếng Anh được sử dụng thực tế trong luyện gõ phím và xem trước phông chữ. Bản xem trước phông chữ macOS hiển thị "The quick brown fox jumps over the lazy dog," và danh sách phông chữ Windows cũng dùng câu này. Câu chứa tất cả 26 chữ cái này là công cụ không thể thiếu cho nhà thiết kế.

Lipogram - Ràng buộc tránh ký tự cụ thể

Lipogram ngược lại với pangram - viết văn bản hoàn toàn không sử dụng một ký tự cụ thể. Tác phẩm lipogram nổi tiếng nhất là tiểu thuyết "La Disparition" (Sự biến mất) của nhà văn Pháp Georges Perec xuất bản năm 1969. Cuốn tiểu thuyết khoảng 300 trang này được viết hoàn toàn không dùng chữ "e" - chữ cái được sử dụng nhiều nhất trong tiếng Pháp.

Trong tiếng Anh, "Gadsby" của Ernest Vincent Wright xuất bản năm 1939 rất nổi tiếng. Toàn bộ tiểu thuyết khoảng 50.000 từ không sử dụng chữ "e". Tần suất xuất hiện của "e" trong văn bản tiếng Anh khoảng 12,7% - chữ cái được dùng nhiều nhất - viết tiểu thuyết dài mà loại bỏ nó đòi hỏi năng lực ngôn ngữ phi thường.

Trong thế giới Unicode được thảo luận trong bài đếm ký tự emoji, với hơn 140.000 ký tự khả dụng, việc tránh một ký tự cụ thể rất dễ. Tuy nhiên, viết văn bản có nghĩa trong bộ ký tự hạn chế của ngôn ngữ tự nhiên mà loại trừ một ký tự cụ thể là thách thức trí tuệ ở chiều kích khác so với ràng buộc số ký tự.

Ambigram - Thiết kế chữ đọc được khi xoay

Ambigram là thiết kế mà văn bản có thể đọc được (cùng từ hoặc từ khác) khi xoay 180 độ hoặc soi gương. Chúng trở nên phổ biến qua tiểu thuyết "Thiên thần và Ác quỷ" của Dan Brown.

Ambigram không phải vấn đề thuần túy về số ký tự mà là thiết kế khai thác tính đối xứng thị giác của chữ cái. Trong chữ hoa tiếng Anh, "A," "H," "I," "M," "O," "T," "U," "V," "W," "X," "Y" đối xứng trái-phải, còn "H," "I," "N," "O," "S," "X," "Z" đối xứng xoay 180 độ. Các từ chỉ gồm những chữ cái đối xứng này (ví dụ: "NOON," "SOS," "SWIMS") tự nhiên trở thành ambigram.

"SWIMS" là ambigram đặc biệt nổi tiếng, xoay 180 độ vẫn đọc là "SWIMS". Nghệ sĩ ambigram John Langdon đã thiết lập kỹ thuật thư pháp để vẽ bất kỳ từ nào thành ambigram và thiết kế bìa tiểu thuyết của Dan Brown. Ít ký tự hơn thì thiết kế ambigram dễ hơn, nhưng tạo ambigram cho từ dài hoặc câu là thách thức nghệ thuật đòi hỏi kỹ năng thiết kế cao.

Palindrome số và Toán học - Bài toán 196

Palindrome cũng tồn tại trong thế giới số. Các số palindrome như 121, 1331, 12321 có tính chất toán học thú vị. Với bất kỳ số tự nhiên nào, lặp lại thao tác "cộng số đó với số đảo ngược các chữ số" thường dẫn đến số palindrome. Ví dụ: 59 → 59 + 95 = 154 → 154 + 451 = 605 → 605 + 506 = 1111 (số palindrome).

Tuy nhiên, khi thực hiện thao tác này với số 196, dù lặp lại hàng triệu lần vẫn không đạt được số palindrome. Đây là bài toán chưa giải được gọi là "bài toán 196" (196 conjecture). Tính đến năm 2023, phép tính đã được thực hiện đến hơn một tỷ chữ số nhưng vẫn chưa tìm thấy palindrome. Bài toán mà số ký tự (số chữ số) liên tục tăng này tượng trưng cho chiều sâu toán học mà khái niệm đơn giản palindrome sở hữu.

Semagram - Thông điệp ẩn trong các yếu tố phi văn bản

Là một dạng trò chơi chữ, semagram cũng đáng được đề cập. Semagram ẩn thông điệp không phải trong bản thân ký tự mà trong trang trí hoặc bố cục của ký tự. Ví dụ, làm đậm nhẹ một số ký tự cụ thể trong thư, hoặc thay đổi tinh tế khoảng cách giữa các từ nhất định để truyền thông điệp bí mật.

Trong thế giới kỹ thuật số, nghiên cứu đã được thực hiện về việc nhúng thông tin bit bằng cách thao tác kerning phông chữ (khoảng cách ký tự). Kerning bình thường đại diện cho "0" và kerning hơi rộng hơn đại diện cho "1", nhúng dữ liệu nhị phân xuyên suốt tài liệu. Kỹ thuật này ẩn thông điệp mà không thay đổi số ký tự, nên không thể phát hiện bằng đếm ký tự.

Lập trình và Trò chơi chữ - Ứng dụng thực tế của ràng buộc ký tự

Những trò chơi chữ này không chỉ là giải trí trí tuệ. Phát hiện palindrome là nền tảng của thuật toán chuỗi và được ứng dụng trong phân tích trình tự DNA (trình tự palindrome là vị trí nhận diện của enzyme cắt giới hạn). Phát hiện anagram liên quan đến thiết kế hàm băm, và pangram được dùng để hiển thị xem trước phông chữ.

Đếm độ dài chuỗi bằng công cụ đếm ký tự là điểm khởi đầu cho tất cả các trò chơi chữ này. Số ký tự palindrome là chẵn hay lẻ thay đổi cách xử lý ký tự giữa, tăng số ký tự anagram gây bùng nổ tổ hợp, và kích thước bộ ký tự trở thành ràng buộc cho pangram. Phía sau hành động đơn giản đếm ký tự là thế giới rộng lớn của lý thuyết tổ hợp và độ phức tạp tính toán.

Sách về trò chơi chữ và câu đố toán học cũng có thể tìm thấy trên Amazon.