74
Tên của hai thành phố Nhật Bản Tokyo và Kyoto là phép đảo chữ của nhau (khi viết bằng chữ Latinh). Có nước nào có 2 thành phố cũng có tên là phép đảo chữ không?
*Phép đảo chữ: Anagram, hay còn gọi là thuật đảo chữ là cách một từ hay cụm từ được tái sắp xếp thành các ký tự của 1 từ hay cụm từ khác, sử dụng các ký tự ban đầu chỉ 1 lần duy nhất.
Trả lời bởi Samuel Mackey
—
Úi chà, tôi hoàn toàn bị hấp dẫn bởi câu hỏi này đến mức quên hết mọi thứ.
Thuật toán kiểm tra xem 2 cụm từ có phải là anagram không thì rất đơn giản. Chỉ cần sắp xếp 2 cụm từ và kiểm tra độ bằng nhau sẽ đưa ra câu trả lời trong lần thứ O(Nlog(N)).
Để kiểm tra tất cả anagram trong một danh sách cố định, chỉ cần đối chiếu từng cụm từ với những cụm còn lại, và thế là sẽ có kết quả ở lần O(N^2). Không phải là cách nhanh nhất, nhưng rất dễ để code, và nó chạy mượt trên cấu hình máy tính của tôi.
Vấn đề bây giờ chỉ là tìm đâu được danh sách tất cả thành phố trên thế giới. May thay có mấy gã đã làm nè: https://datahub.io/core/world-cities#data
Danh sách này có các thành phố trên 15.000 dân, cũng khá ổn để bắt đầu. Cũng có dữ liệu khác cung cấp thông tin của các thành phố ít dân hơn, nhưng thế thì quá lớn để xử lý và cũng có thêm vấn đề (bị trùng lặp vân vân). Tôi dùng dữ liệu trên vì nó được trình bày đơn giản và Python dễ xử lý – khá ngon ăn để có câu trả lời nhanh chóng, đặc biệt là với coder thích đơn giản như tôi.
Tôi định nghĩa anagram theo các cách sau: ký tự không có trong hệ Latinh vẫn được tính. Viết hoa hay ký tự đặc biệt đều được tính như chữ thường. Hai địa danh trùng tên hoàn toàn trong cùng một quốc gia không được tính. Ví dụ:
-
Dorval và Val-d’Or là một cặp anagram, dù có dấu gạch ngang và dấu phẩy.
-
Telhāra và Lātehār là một cặp anagram, dù tên sau có tận 2 chữ ā đặc biệt.
-
Shikārpūr và Shikārpur không phải là một cặp anagram, dù đây là tên 2 thành phố khác nhau ở Ấn Độ.
Đoạn code sẽ được đính kèm cuối bài. Tôi biết là nó có thể không tốt lắm, nhưng tôi dùng phương pháp nhanh và đơn giản để có câu trả lời. Cứ xài tự nhiên cho mọi mục đích nhé, nhưng tôi sẽ không cải tiến gì đâu.
Vấn đề lớn với tôi là xử lý dữ liệu ban đầu. Xóa và thay thế các ký tự đặc biệt thì khá dễ, nhưng loại bỏ các tên giống hệt nhau thì phải làm thủ công. Một số thành phố (chẳng hạn như Zurich và Budapest) có các khu vực riêng lẻ được liệt kê là các trung tâm dân cư khác nhau và bản dịch của bảng chữ cái Kirin trong một số trường hợp – điều này gây khó khăn cho một số quốc gia ở Đông Âu, đặc biệt là khi các thành phố của họ được liệt kê bằng cả hai chữ cái Kirin (bảng chữ tiếng Đông Âu) và Latin. Nói chung, câu trả lời này gần như chắc chắn sẽ kém chính xác hơn đối với khu vực ngoài phương Tây, vì các dạng tên theo Latinh không phải lúc nào cùng hình thức. Tất cả các vấn đề trên có nghĩa là tôi phải sửa đổi dữ liệu theo cách thủ công, do đó, tại sao tôi không thật sự muốn làm việc với cơ sở dữ liệu lớn hơn.
Nói dông dài thì đây là 18 quốc gia có 2 thành phố là anagram của nhau.
-
Brazil (Piraí, Ipirá)
-
Canada (Dorval, Val-d’Or)
-
Bờ biển Ngà (Touba, Tabou)
-
Trung Quốc (Dongtai, Dingtao)
-
Đức (Gelsenkirchen,Engelskirchen)
-
Algeria (Rouiba, Bouïra)
-
Tây Ban Nha (Manacor, Carmona)
-
Indonesia (Surakarta, Kartasura)
-
Ấn Độ (Wardha, Dārwha)
-
Iran (Bahār, Abhar)
-
Italy (Palagonia, Palagiano)
-
Nhật Bản (Akashi, Hasaki)
-
Hà Lan (Rhoon, Hoorn)
-
Philippines (Plaridel, Del Pilar)
-
Pakistan (Okāra, Akora)
-
Nga (Rostov, Ostrov)
-
Mỹ (Altus, Tulsa)
-
Việt Nam (Hội An, Hà Nội)
Tôi chỉ liệt kê 1 cặp anagram cho mỗi quốc gia vì nếu không thì câu trả lời này sẽ chiếm quá nhiều dung lượng. Có thể có một số sai sót với danh sách này. Tôi đã liệt kê một số vấn đề mà tôi gặp phải khi đưa ra câu trả lời này, vì vậy bạn có thể tìm ra cách cải thiện vấn đề.
