Chương 9: Nghiên cứu cụ thể: trò chơi chữ

Trở về Mục lục cuốn sách

9.1 Đọc danh sách các từ

Với những bài tập trong chương này, ta cần đến một danh sách các từ tiếng Anh. Trên mạng hiện nay có rất nhiều danh sách từ, nhưng danh sách thích hợp nhất được Grady Ward sưu tầm và đóng góp cho nguồn tài liệu công cộng, như một phần dự án từ vựng Moby¹. Nó là một danh sách gồm 113.809 từ chính thức được dùng trong các ô chữ; nghĩa là những từ có nghĩa trong trò chơi ô chữ và các trò đố chữ khác. Trong tuyển tập Moby, tên file danh sách từ là 113809of.fic; tôi có kèm theo một bản sao của file này với tên gọi đơn giản hơn words.txt, trong bộ Swampy.

File này chỉ chứa các kí tự thuần túy, vì vậy bạn có thể mở bằng một trình soạn thảo; nhưng bạn cũng có thể dùng Python để đọc. Hàm có sẵn open sẽ nhận vào tên file như một tham biến và trả lại một đối tượng file mà bạn dùng nó để đọc nội dung file.

>>> fin = open('words.txt')

>>> print fin
<open file 'words.txt', mode 'r' at 0xb7f4b380>

fin là một cái tên thông dụng để đặt cho đối tượng file nhập vào (input). Chế độ 'r' chỉ định rằng file này được mở để đọc (reading), khác với 'w' để ghi (writing).

Đối tượng file cung cấp một số phương thức để đọc, trong đó có readline, để đọc các kí tự từ một file cho đến hết dòng, sang đến đầu dòng mới, và trả trả lại kết quả dưới dạng một chuỗi:

>>> fin.readline()
'aa\r\n'

Từ đầu tiên trong danh mục là “aa”, có nghĩa là một loại dung nham. Chuỗi \r\n biểu thị hai kí tự trống, một kí tự về đầu dòng (carriage return) và một kí tự nhảy dòng mới (newline), để ngăn cách từ này với từ tiếp theo.

Đối tượng file có nhiệm vụ theo dõi vị trí hiện thời trong file, vì vậy nếu bạn gọi lại readline lần nữa, bạn sẽ được từ kế tiếp:

>>> fin.readline()
'aah\r\n'

Từ tiếp theo là “aah”, là một từ hoàn toàn có nghĩa, vì vậy bạn đừng nhìn tôi kiểu như vậy nữa nhé. À, nếu như các dấu trống làm bạn không hài lòng thì hãy dùng phương thức chuỗi có tên là strip:

>>> line = fin.readline()
>>> word = line.strip()

>>> print word
aahed

Bạn cũng có thể dùng một đối tượng file như một bộ phận trong vòng lặp for. Chương trình sau sẽ đọc words.txt và in ra các từ, mỗi từ trên một dòng:

fin = open('words.txt')
for line in fin:
    word = line.strip()
    print word

Bài tập 1

Hãy viết một chương trình đọc vào words.txt và chỉ in ra những từ dài hơn 20 kí tự (không kể dấu trống).

9.2 Bài tập

Trong mục tiếp theo sẽ có lời giải cho các bài tập dưới đây. Vì vậy, bạn cần phải ít ra là cố gắng thử giải chúng trước khi đọc đến đáp án.

Bài tập 2

Vào năm 1939, Ernest Vincent Wright đã xuất bản một cuốn tiểu thuyết gồm 50.000 từ có tên là Gadsby, mà trong đó không chứa một chữ cái “e” nào. Việc này thật chẳng dễ dàng vì trong tiếng Anh, “e” là chữ cái thường gặp nhất.

Thực ra khi không dùng chữ cái thông dụng nhất đó thì việc diễn đạt một ý tưởng đơn lẽ cũng là khó rồi. Ban đầu bạn phải thử làm rất chậm, nhưng dần sau này khi cẩn thận và đã có kinh nghiệm nhiều giờ thì bạn sẽ quen hơn.

Thôi, tôi sẽ không nói tiếp về điều đó nữa.

Yêu cầu của bài tập là viết một hàm tên là has_no_e nhằm trả lại True nếu từ đã cho không chứa chữ cái “e” trong đó.

Hãy chỉnh lại chương trình bạn đã viết trong mục trước để chỉ in ra những từ mà không chứa chữ “e” và tính tỉ lệ phần trăm của các từ trong danh sách mà không chứa chữ “e”.

Bài tập 3

Hãy viết một hàm có tên là avoids, trong đó nhận vào một từ và một chuỗi các chữ cái bị cấm dùng, sau đó trả lại True nếu từ đó không chứa bất kì chữ cái nào trong danh sách bị cấm.

Hãy sửa lại chương trình của bạn để người dùng nhập vào một chuỗi các chữ cái cấm dùng và sau đó in ra tổng số từ mà trong đó không chứa bất kì chữ cái cấm nào.

Bạn có thể tìm được tập hợp 5 chữ cái cấm mà chỉ loại ra số ít nhất các từ vi phạm những chữ cái cấm đó không?

Bài tập 4

Hãy viết một hàm có tên là uses_only, trong đó nhận vào một từ và một chuỗi các chữ cái, sau đó trả lại True nếu từ đó chỉ cấu thành từ những chữ có trong danh sách chữ cái. Bạn có thể đặt một câu trong đó chỉ dùng các chữ cái acefhlo không, ngoài câu “Hoe alfalfa?”

Bài tập 5

Hãy viết một hàm có tên là uses_all, trong đó nhận vào một từ và một chuỗi các chữ cái yêu cầu, sau đó trả lại True nếu từ đó dùng hết tất cả các chữ cái yêu cầu, mỗi chữ cái ít nhất là một lần. Có bao nhiêu từ dùng tất cả các nguyên âm aeiou? Dùng tất cả aeiouy?

Bài tập 6

Hãy viết một hàm có tên là is_abecedarian để trả lại True nếu các chữ cái trong từ xuất hiện xuôi theo thứ tự của bảng chữ cái (chấp nhận các chữ cái lặp lại hai lần). Có tất cả bao nhiêu từ như vậy?

9.3 Tìm kiếm

Tất cả các bài tập trong mục trước đều có điểm chung; chúng đều giải quyết được bằng dạng mẫu tìm kiếm ở Mục find. Ví dụ đơn giản nhất là:

def has_no_e(word):
    for letter in word:
        if letter == 'e':
            return False
    return True

Vòng lặp for duyệt các kí tự có trong word. Nếu ta thấy kí tự “e”, ta có thể lập tức trả về False; còn không thì tiếp tục đến với kí tự tiếp theo. Nếu ta thoát khỏi vòng lặp một cách bình thường, nghĩa là ta không tìm thấy chữ “e”, thì ta sẽ trả về True.

avoids là một dạng khái quát của has_no_e nhưng nó cũng có cấu trúc tương tự:

def avoids(word, forbidden):
    for letter in word:
        if letter in forbidden:
            return False
    return True

Chúng ta có thể trả về False ngay khi tìm thấy một chữ cái bị cấm; còn nếu chúng ta đến được cuối vòng lặp thì sẽ trả về True.

uses_only cũng tương tự, chỉ khác là điều kiện được đảo ngược lại:

def uses_only(word, available):
    for letter in word: 
        if letter not in available:
            return False
    return True

Thay vì một danh sách các chữ cái bị cấm, ta có một danh sách chữ cái được dùng. Nếu ta tìm thấy một chữ cái trong word mà không có trong available, ta có thể trả về giá trị False.

uses_all tương tự, nhưng ta đảo lại vai trò của từ và dẫy các chữ cái:

def uses_all(word, required):
    for letter in required: 
        if letter not in word:
            return False
    return True

Thay vì việc duyệt các chữ cái trong word, vòng lặp duyệt các chữ cái được yêu cầu. Nếu bất kì chữ cái yêu cần nào mà không có mặt trong từ thì ta có thể trả về giá trị False.

Nếu bạn có thể tư duy như một nhà khoa học máy tính thực thụ, bạn có thể nhận thấy rằng uses_all là một trường hợp của một bài toán mà trước đây ta đã giải quyết rồi, và bạn có thể đã viết:

def uses_all(word, required):
    return uses_only(required, word)

Đó là ví dụ cho một phương pháp xây dựng chương trình gọi là nhận diện bài toán, trong đó bạn nhân ra bài toán mà bạn đang giải quyết chính là một trường hợp của bài toán trước đây đã từng làm rồi, và chỉ cần áp dụng cách giải trước đây.

9.4 Lặp với các chỉ số

Tôi đã viết các hàm trong mục trước đây bằng vòng lệnh for vì tôi chỉ cần các kí tự có trong chuỗi; tôi không cần làm gì với các chỉ số (thứ tự) của từng kí tự.

Đối với is_abecedarian chúng ta phải so sánh các chữ cái liền kề nhau, điều này đòi hỏi phải có mẹo khi dùng một vòng lặp for:

def is_abecedarian(word):
    previous = word[0]
    for c in word:
        if c < previous:
            return False
        previous = c
    return True

Một cách làm khác là dùng đệ quy:

def is_abecedarian(word):
    if len(word) <= 1:
        return True
    if word[0] > word[1]:
        return False
    return is_abecedarian(word[1:])

hoặc dùng một vòng lặp while:

def is_abecedarian(word):
    i = 0
    while i < len(word)-1:
        if word[i+1] < word[i]:
            return False
        i = i+1
    return True

Vòng lặp bắt đầu tại i=0 và kết thúc khi i=len(word)-1. Mỗi lần duyệt qua vòng lặp, máy sẽ so sánh chữ cái thứ i (mà bạn có thể coi như chữ cái hiện hành) và chữ cái thứ i+1 (coi như chữ cái tiếp theo).

Nếu chữ cái tiếp theo mà nhỏ hơn (tức là đứng trước theo bản chữ cái) chữ cái hiện hành, thì ta sẽ phát hiện được sự phá vỡ quy luật sắp xếp, và sẽ trả lại giá trị False.

Nếu ta đến được cuối vòng lặp mà không gặp lỗi nào, thì từ đã cho đạt yêu cầu kiểm trả. Để tự tin khẳng định rằng vòng lặp đã kết thúc đúng, hãy xét một ví dụ như 'flossy'. Từ này có độ dài là 6, vì vậy vòng lặp kết thúc lần cuối khi i bằng 4, ứng với chỉ số của chữ cái áp chót. Ở vòng lặp cuối, máy sẽ so sánh chữ cái áp chót với chữ cái cuối; đây là điều chúng ta muốn.

Sau đây là một dạng khác của is_palindrome (xem lại Bài tập palindrome) trong đó có dùng hai biến chỉ số; một bắt đầu từ chữ cái đầu và tăng dần lên; biến kia bắt đầu từ chữ cái cuối và giảm dần xuống.

def is_palindrome(word):
    i = 0
    j = len(word)-1

    while i<j:
        if word[i] != word[j]:
            return False
        i = i+1
        j = j-1

    return True

Hoặc là, nếu bạn nhận thấy rằng đây chỉ là một trường hợp của bài toán đã giải trước đó, thì bạn có thể viết:

def is_palindrome(word):
    return is_reverse(word, word)

Với giả sử là bạn đã làm Bài tập 9.

9.5 Gỡ lỗi

Kiểm tra chương trình là một việc khó. Các hàm được viết trong chương này đều khá dễ kiểm tra vì bạn có thể kiểm tra kết quả bằng cách tính nhẩm. Tuy vậy, để chọn được toàn bộ tập hợp các từ nhằm kiểm tra chương trình để loại trừ mọi lỗi sẽ là việc rất khó, thậm chí là không thể.

Lấy has_no_e làm ví dụ, hiển nhiên là có hai trường hợp để kiểm tra: với những từ có chứa chữ ’e’ cần phải trả lại False; còn những từ khác thì phải trả lại True. Bạn có thể dễ dàng tìm được kết quả trong cả hai trường hợp.

Với mỗi trường hợp, vẫn có những trường hợp nhỏ mà khó nhận ra hơn. Trong số những từ có chứa “e”, bạn cần kiểm tra những từ có chứa “e” ở đầu, ở cuối, và ở đoạn giữa của từ. Bạn cần kiểm tra những từ dài, từ ngắn, từ rất ngắn, và cả chuỗi trống nữa. Chuỗi trống chính là ví dụ cho một trường hợp đặc biệt, vốn là một trong số các trường hợp không dễ thấy mà ở đó tường tiềm ẩn lỗi.

Ngoài những trường hợp kiểm tra mà bạn tự tạo ra, bạn còn có thể kiểm tra chương trình với một danh sách từ như words.txt. Bằng cách lướt qua kết quả tìm được, bạn có thể phát hiện được lỗi, nhưng hãy cẩn thận: bạn chỉ bắt được những lỗi theo một kiểu (ở những từ vốn không nên có trong danh sách kết quả, nhưng lại có) chứ không bắt được lỗi theo kiểu còn lại (những từ đáng ra có trong danh sách kết quả nhưng lại không có).

Nói chung, việc kiểm tra có thể giúp bạn tìm ra lỗi, nhưng thật không dễ tạo ra một bộ trường hợp kiểm tra thật tốt, và dù nếu bạn có làm được vậy đi nữa, cũng không có gì đảm bảo được rằng chương trình sẽ đúng.

Theo lời một nhà khoa học máy tính nổi tiếng: “Việc kiểm tra chương trình có thể được dùng để cho thấy sự tồn tại của lỗi, nhưng không bao giờ có thể dùng để chứng tỏ được sự vắng mặt của chúng!”. Nguyên văn:

Program testing can be used to show the presence of bugs, but never to show their absence!

— Edsger W. Dijkstra

9.6 Thuật ngữ

đối tượng file:

Một giá trị để biểu thị một file được mở.

nhận diện bài toán:

Một cách giải quyết bài toán thông qua việc diễn đạt đó như một trường hợp riêng của một bài toán khác đã được giải quyết từ trước.

trường hợp đặc biệt:

Một trường hợp kiểm tra thuộc vào dạng không điển hình hoặc không dễ thấy (và thường cũng khó xử lý một cách thích hợp).

9.7 Bài tập

Bài tập 7

Câu hỏi này được dựa trên mục đố vui phát sóng trong chương trình Car Talk²:

Hãy cho tôi biết một từ trong đó chứa 3 cặp hai chữ cái giống nhau liên tiếp. Tôi sẽ kể ra hai ví dụ gần đạt tiêu chuẩn như vậy. Chẳng hạn, từ “committee”, c-o-m-m-i-t-t-e-e. Từ này sẽ đạt yêu cầu nếu chữ ‘i’ không có ở đó. Hoặc là Mississippi: M-i-s-s-i-s-s-i-p-p-i. Nếu bỏ hết các chữ i trong đó ra, từ này cũng đạt yêu cầu. Nhưng mà có một từ mà tôi biết, nó có 3 cặp đôi chữ cái liên tiếp. Dĩ nhiên là có thể có đến 500 từ tiếng Anh khác như vậy nhưng đến giờ thì tôi chỉ biết được một từ. Đó là từ gì?

Hãy viết một chương trình để tìm ra từ này. Bạn có thể tìm thấy lời giải của tôi ở thinkpython.com/code/cartalk.py.

Sau đây là một câu đố khác trong Car Talk³:

“Một ngày, khi đang lái xe trên đường cao tốc, tôi đột nhiên chú ý đến đồng hồ công-tơ-mét trên xe. Cũng như các công-tơ-mét khác, nó chỉ sáu chữ số, lấy tròn số dặm đường mà xe đi được. Như vậy, nếu xe tôi đã chạy được 300.000 dặm chẳng hạn, thì tôi sẽ nhìn thấy 3-0-0-0-0-0.

“Bây giờ, trở về chuyện ngày hôm đó, tôi đã thấy một chi tiết thú vị. Tôi nhận thấy rằng bốn chữ số cuối cùng đối xứng nhau; nghĩa là đọc xuôi, đọc ngược đều như nhau. Chẳng hạn, 5-4-4-5 là một chuỗi đối xứng, như vậy công-tơ-mét của tôi có thể đã chỉ 3-1-5-4-4-5.

“Một dặm sau đó, 5 chữ số cuối xếp thành danh sách đối xứng. Chẳng hạn, nó có thể là 3-6-5-4-5-6. Một dặm sau, bốn chữ số giữa trong 6 số xếp thành danh sách 4 đối xứng. Bạn vẫn theo kịp tôi chứ? Này nhé, một dặm sau đó thì cả chuỗi 6 số là đối xứng!

“Câu hỏi là, lần đầu tôi nhìn công-tơ-mét thì số chỉ của nó bằng bao nhiêu?”

Bài tập 8

Hãy viết một chương trình Python để kiểm tra tất cả các số gồm sáu chữ số sau đó in ra những số thỏa mãn tất cả các điều kiện như vậy. Bạn có thể xem lời giải của tôi tại thinkpython.com/code/cartalk.py.

Sau đây là một câu đố khác trong chương trình Car Talk mà bạn có thể giải bằng cách tìm kiếm ⁴:

“Gần đây tôi tới thăm mẹ và chúng tôi nhận ra rằng số tuổi của tôi khi viết ngược lại (đổi chỗ hai chữ số) sẽ trở thành tuổi mẹ. Chẳng hạn, nếu mẹ tôi 73 tuổi thì tôi 37. Chúng tôi đã tự hỏi liệu điều này xảy ra được mấy lần nhưng rồi chuyển sang câu chuyện khác mà không tìm ra câu trả lời.

Khi quay trở về nhà tôi đã nhận ra rằng số tuổi của chúng tôi đã có sáu trường hợp đổi chỗ như thế. Đồng thời tôi còn tính được, nếu may mắn thì điều này sẽ xảy ra chỉ trong vài năm tới, và nếu rất may mắn thì nó còn xảy ra thêm một lần nữa. Tóm lại là tổng cộng 8 lần có thể xảy ra. Vậy câu hỏi là, bây giờ tôi đang bao nhiêu tuổi?’’

Bài tập 9

Hãy viết một chương trình Python để dò tìm lời giải cho câu đố này. Gợi ý: bạn có thể tận dụng phương thức chuỗi có tên zfill.

Bạn có thể xem lời giải của tôi tại thinkpython.com/code/cartalk.py.

---

1. wikipedia.org/wiki/Moby_Project. ↩
2. www.cartalk.com/content/puzzler/transcripts/200725. ↩
3. www.cartalk.com/content/puzzler/transcripts/200803. ↩
4. www.cartalk.com/content/puzzler/transcripts/200813 ↩