บทนี้นำเสนอกรณีศึกษากรณีที่สอง ซึ่งเกี่ยวกับปริศนาทายคำ โดยการค้นหาคำที่มี คุณสมบัติตามที่กำหนด เช่น เราจะหาพาลินโดรม (palindrome) ที่ยาวที่สุด ในภาษาอังกฤษ และหาคำที่มีอักษรในคำเรียงตามลำดับตัวอักษร และผมจะนำเสนอ แผนการพัฒนาโปรแกรมอีกแบบหนึ่ง: การลดทอนให้เป็นปัญหาที่ถูกแก้ไปแล้ว

สำหรับแบบฝึกหัดในบทนี้ เราต้องการรายการ หรือ ลิสต์ (list) ของคำภาษาอังกฤษ มันมีหลาย ชุดให้ใช้บนอินเทอร์เน็ต แต่อันที่เหมาะกับจุดประสงค์ของเราคือรายการคำที่จัดเก็บและเผยแพร่สู่ สาธารณะโดย แกรดี้ วอร์ด (Grady Ward) ซึ่งเป็นส่วนหนึ่งของโครงการโมบี้เลซิคอน (Moby lexicon project) (ดูเพิ่มที่ http://wikipedia.org/wiki/Moby_Project) มันเป็นรายการที่มี 113,809 คำที่ใช้เล่นเกมครอสเวิร์ด (crossword) อย่างเป็นทางการ; นั่นคือ คำที่ให้ใช้ได้ในครอสเวิร์ดและ เกมเกี่ยวกับคำศัพท์อื่นๆ ในรายการคำโมบี้นี้มีชื่อไฟล์ว่า 113809of.fic; เราสามารถดาวน์โหลด สำเนาของไฟล์โดยใช้ชื่อที่ง่ายกว่าว่า words.txt จาก http://thinkpython2.com/code/words.txt

ไฟล์นี้ถูกเก็บอยู่ในรูปแบบตัวข้อความธรรมดา ดังนั้นเราสามารถเปิดมันโดยใช้โปรแกรมแก้ไขข้อความ (text editor) แต่เราก็สามารถอ่านมันจากไพธอนได้ด้วย ฟังก์ชันที่มีอยู่ในตัว open รับชื่อของไฟล์เข้ามาเป็นพารามิเตอร์ และคืนค่าเป็น วัตถุไฟล์ (file object) ที่เราสามารถใช้ในการอ่านไฟล์ได้

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

fin เป็นชื่อที่ใช้โดยทั่วไปสำหรับวัตถุไฟล์ที่ใช้สำหรับอินพุตหรือนำเข้าข้อมูล วัตถุไฟล์มีหลาย เมธอดสำหรับการอ่าน รวมถึงเมธอด readline ซึ่งอ่านอักขระต่างๆ จากไฟล์จนกว่าจะเจอ บรรทัดใหม่ (newline) และคืนค่าเป็นสายอักขระ:

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

คำแรกในลิสต์นี้ คือ “aa” ซึ่งแปลว่าลาวาชนิดหนึ่ง ลำดับอักขระ \n แทนอักขระ เริ่มบรรทัดใหม่ (newline character) ซึ่งแบ่งคำนี้จากคำถัดไป

วัตถุไฟล์จดจำว่ามันอ่านถึงไหนแล้วในไฟล์นั้น ดังนั้น ถ้าเราเรียก readline อีกครั้งหนึ่ง เราจะได้คำถัดไป:

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

คำถัดไป คือคำว่า “aah” ซึ่งเป็นคำที่แท้จริง ดังนั้น หยุดมองผมแบบนั้นซะที หรือ ถ้ามันเป็นอักขระเริ่มบรรทัดใหม่ที่ทำให้ขัดใจ เราสามารถกำจัดมันด้วยเมธอด ของสายอักขระที่ชื่อว่า strip:

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

เราสามารถใช้วัตถุไฟล์เป็นส่วนหนึ่งของลูป for ได้ โปรแกรมนี้อ่านไฟล์ words.txt และพิมพ์แต่ละคำออกมาคำละบรรทัด:

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

เฉลยสำหรับแบบฝึกหัดต่อไปนี้จะอยู่ในหัวข้อถัดไป อย่างน้อยเราควรพยายามที่จะทำแต่ละข้อ ก่อนที่จะไปดูเฉลย

แบบฝึกหัด 1
ให้เขียนโปรแกรมซึ่งอ่านไฟล์ words.txt และพิมพ์คำที่มีความยาวมากกว่า 20 อักขระ (ไม่นับเว้นวรรค)

แบบฝึกหัด 2
ในปี ค.ศ. 1939 เอิร์นเนิสต์ วินเซนต์ ไรต์ (Ernest Vincent Wright) ได้ตีพิมพ์ นวนิยาย ความยาว 50,000 คำที่ชื่อว่า แกดสบี้ (Gadsby) ซึ่งไม่มีอักษร “e” อยู่เลย เนื่องจาก “e” เป็นอักษรที่นิยมใช้เป็นปกติในภาษาอังกฤษ มันจึงไม่ง่ายเลยที่จะทำแบบนั้น

ที่จริงแล้ว มันยากที่จะสร้างความคิดโดดเดี่ยวโดยปราศจากสัญลักษณ์ที่นิยมใช้อันนี้ การทำเป็นไป อย่างเชื่องช้าในตอนแรก แต่ด้วยความรอบคอบและการฝึกฝนอันยาวนาน เราสามารถค่อยๆ เพิ่ม ความง่ายขึ้น

เอาเถอะ ผมจะหยุดตรงนี้

ให้เขียนฟังก์ชันที่ชื่อว่า has_no_e ที่คืนค่า True ถ้าคำที่กำหนดให้ไม่มีอักษร “e” ในคำนั้น

ให้แก้ไขโปรแกรมจากหัวข้อที่แล้วให้พิมพ์แค่คำที่ไม่มี “e” และคำนวณเปอร์เซนต์ของคำในรายการ ที่ไม่มี “e”

แบบฝึกหัด 3
ให้เขียนฟังก์ชันที่ชื่อว่า avoids ซึ่งรับคำหนึ่งคำ และสายอักขระของอักษรต้องห้าม และ คืนค่า True ถ้าคำนั้นไม่มีอักษรต้องห้ามที่กำหนดให้เลย

ให้แก้ไขโปรแกรมเพื่อรับสายอักขระของอักษรต้องห้ามจากผู้ใช้ และจากนั้นพิมพ์จำนวน คำที่ไม่มีอักษรต้องห้ามใดๆ เลย

เราสามารถหาการรวมกันของอักษรต้องห้าม 5 ตัว ที่แยกคำออกไปเป็นจำนวนน้อยที่สุดออกไปได้หรือไม่?

แบบฝึกหัด 4
ให้เขียนฟังก์ชันที่ชื่อว่า uses_only ซึ่งรับคำหนึ่งคำ และสายอักขระของอักษร และ คืนค่าเป็น True ถ้าคำนั้นมีแค่อักษรในลิสต์ที่กำหนดให้ เราสามารถสร้างประโยคโดย ใช้แค่อักษรใน acefhlo ได้หรือไม่? แล้วที่ไม่ใช่คำว่า “Hoe alfalfa” ล่ะ?

แบบฝึกหัด 5
ให้เขียนฟังก์ชันที่ชื่อว่า uses_all ที่รับคำหนึ่งคำ และสายอักขระของอักษรบังคับ (ที่ต้องใช้) และให้คืนค่าเป็น True ถ้าคำนั้นใช้อักษรบังคับอย่างน้อยตัวละหนึ่งครั้ง มีคำกี่คำที่ใช้ สระทั้งหมดใน aeiou? แล้วใน aeiouy ล่ะ?

แบบฝึกหัด 6
ให้เขียนฟังก์ชันชื่อว่า is_abecedarian ซึ่งคืนค่าเป็น True ถ้าอักษรในคำ นั้นปรากฏตามลำดับตัวอักษร (ใช้อักษรคู่ได้) มีคำที่เป็น เอบีซีดาเรียน (abecedarian) ทั้งหมดกี่คำ?

แบบฝึกหัดทั้งหมดในหัวข้อที่แล้วมีบางอย่างที่เหมือนกัน: มันสามารถแก้ได้โดยใช้ รูปแบบการค้นหาที่เราเจอในหัวข้อที่ 8.6 ตัวอย่างที่ง่ายที่สุดคือ:

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

ลูป for แวะผ่านอักขระใน word ถ้าเราเจออักษร “e” เราสามารถคืนค่า False; ได้ทันที ไม่เช่นนั้น เราต้องไปที่อักษรตัวถัดไป ถ้าเราออกจากลูปแบบปกติแล้ว นั่นหมายความว่า เราไม่เจอ “e” ดังนั้น เราสามารถคืนค่า True ได้

เราอาจจะเขียนฟังก์ชันนี้ให้กระชับขึ้นโดยการใช้ตัวดำเนินการ in แต่ผมเริ่มจาก เวอร์ชันนี้เพราะมันสาธิตตรรกะของรูปแบบการค้นหา

ฟังก์ชัน avoids มันครอบคลุมมากกว่าเวอร์ชันของ has_no_e แต่มัน มีโครงสร้างที่เหมือนกัน:

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

เราสามารถคืนค่า False ทันทีที่เราเจออักษรต้องห้าม; ถ้าเราไปถึงการจบลูปแล้ว เราก็คืนค่า True กลับไป

ฟังก์ชัน uses_only ก็เหมือนกัน ยกเว้นว่าความหมายของเงื่อนไขก็จะกลับกัน:

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

แทนที่จะใช้รายการของอักษรต้องห้าม เรามีรายการของอักษรที่ใช้ได้ ถ้าเราเจออักษรใน word ที่ไม่ได้อยู่ใน available เราสามารถคืนค่า False กลับไปได้

ฟังก์ชัน uses_all ก็เหมือนกัน ยกเว้นว่าเรากลับหน้าที่ของคำและสายอักขระ ของอักษร:

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

แทนที่จะแวะผ่านอักษรต่างๆ ใน word ลูปนี้แวะผ่านอักษรบังคับเท่านั้น ถ้าอักษรบังคับ ตัวไหนไม่ปรากฏในคำ เราสามารถคืนค่าเป็น False ได้

ถ้าเราคิดจริงจังเหมือนกับนักวิทยาการคอมพิวเตอร์ เราจะรู้จำได้ว่า uses_all เป็นกรณีตัวอย่างของปัญหาที่ถูกแก้ไปแล้ว และเราก็จะเขียนว่า:

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

นี่คือตัวอย่างของแผนการพัฒนาโปรแกรมที่เรียกว่า การลดทอนให้เป็นปัญหาที่ถูกแก้ไปแล้ว ซึ่งหมายความว่าเรารู้จำว่าปัญหาที่เรากำลังแก้อยู่นี้เป็นกรณีตัวอย่างของปัญหาที่เคยถูกแก้ไปแล้ว แล้วเราก็ประยุกต์ใช้ทางแก้ปัญหาที่มันมีอยู่แล้ว

ผมเขียนฟังก์ชันในหัวข้อที่แล้วด้วยลูป for เพราะผมแค่ต้องการอักขระในสายอักขระ; ผมไม่ได้ต้องการที่จะทำอะไรกับดัชนี

สำหรับฟังก์ชัน is_abecedarian เราต้องเปรียบเทียบอักษรที่อยู่ติดกัน ซึ่งจะยุ่งยากหน่อย เมื่อใช้ลูป for:

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

ทางเลือกหนึ่งคือการใช้การเรียกซ้ำ (recursion):

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

อีกทางหนึ่งคือการใช้ลูป 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

ลูปเริ่มที่ i=0 และจบเมื่อ i=len(word)-1 ในแต่ละครั้งที่รันลูป มันจะเปรียบเทียบ อักขระตัวที่ $i$th (ซึ่งเราสามารถคิดว่ามันเป็นอักขระตัวปัจจุบันได้) กับอักขระตัวที่ $i+1$th (ซึ่งเราสามารถคิดว่ามันเป็นอักขระตัวถัดไป)

ถ้าอักขระตัวถัดไปน้อยกว่า (มาก่อนตามลำดับตัวอักษร) ตัวปัจจุบันแล้ว เราค้นพบตัวทำลาย แนวโน้มการเป็น abecedarian และเราจะคืนค่าเป็น False

ถ้าเราไปถึงตอนท้ายของลูปโดยไม่เจออะไรผิดพลาดแล้ว คำนั้นก็ผ่านการทดสอบ ในการโน้มน้าว ตัวเราเองว่าลูปนั้นจบแบบถูกต้อง ให้พิจารณาตัวอย่างเช่นคำว่า 'flossy' ความยาวของคำคือ 5 ดังนั้น ครั้งสุดท้ายที่ลูปทำงานคือเมื่อ i is 4 ซึ่งเป็นดัชนีของอักขระตัวรองสุดท้าย ในการวนซ้ำรอบสุดท้าย มันเปรียบเทียบอักขระตัวรองสุดท้ายนี้กับอักขระตัวสุดท้าย ซึ่งเป็นสิ่งที่ เราต้องการ

นี่คือเวอร์ชันของฟังก์ชัน is_palindrome (ไปดูแบบฝึกหัดที่ 3) ซึ่ง ใช้ดัชนีสองตัว; ตัวแรกเริ่มที่จุดเริ่มต้นและนับขึ้นไปในคำ; อีกตัวเริ่มที่ตอนจบแล้วนับถอยหลังลงมา

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

หรือเราสามารถจะลดทอนให้เป็นปัญหาที่ถูกแก้ไปแล้ว และเขียนว่า:

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

โดยการใช้ฟังก์ชัน is_reverse จากหัวข้อที่ [is_reverse]

การทดสอบโปรแกรมนั้นยาก ฟังก์ชันต่างๆ ในบทนี้มันค่อนข้างง่ายที่จะทดสอบ เพราะว่าเรา สามารถตรวจสอบผลลัพธ์โดยมือได้ ถึงกระนั้น มันก็ยังถือว่าอยู่ระหว่างความยากและเป็นไปไม่ได้ที่จะเลือก ชุดของคำเพื่อทดสอบหาข้อผิดพลาดที่สามารถเกิดขึ้นได้ทั้งหมด

เอาฟังก์ชัน has_no_e เป็นตัวอย่าง มีสองกรณีที่ชัดเจนที่จะตรวจสอบ: คำที่มี 'e' จะต้อง คืนค่ากลับมาเป็น False และคำที่ไม่มีควรจะคืนค่ากลับมาเป็น True เราควรจะไม่มีปัญหา ในการคิดคำหนึ่งคำในแต่ละกรณี

ในแต่ละกรณี มีกรณีย่อยบางอันที่ไม่ค่อยชัดเจนเท่า เราควรจะทดสอบด้วยคำที่มี 'e' ตอนขึ้นต้น, ลงท้าย และตรงกลางๆ คำ เราควรทดสอบด้วยคำยาว คำสั้น และคำสั้นมากๆ เช่น สายอักขระว่าง สายอักขระว่างเป็นตัวอย่างของ กรณีพิเศษ ซึ่งเป็นหนึ่งในกรณีที่ไม่ค่อยชัดเจนที่มีข้อผิดพลาด เกิดขึ้นบ่อยๆ

นอกจากการทดสอบกรณีที่เราเป็นคนสร้างขึ้นมาแล้ว เราสามารถทดสอบโปรแกรมของเรา ด้วยรายการคำศัพท์ เช่น words.txt อีกด้วย ในการตรวจเอ้าต์พุต เราอาจจะ สามารถจับข้อผิดพลาดได้ แต่ให้ระวัง เราอาจจะจับข้อผิดพลาดประเภทหนึ่ง (คำที่ไม่ควรจะ มีในเอ้าต์พุต แต่ดันมี) และ ไม่สามารถจับอีกประเภทหนึ่งได้ (คำที่ควรจะมีในเอ้าต์พุต แต่ดันไม่มี)

โดยทั่วไปแล้ว การทดสอบสามารถช่วยเราหาบัก (bug) ได้ แต่มันไม่ง่ายที่จะสร้างชุดทดสอบที่ดี และแม้กระทั่งถึงเราสร้างได้ เราอาจจะไม่สามารถแน่ใจได้ว่าโปรแกรมเราถูกต้องอย่างหมดจดหรือไม่ ตามที่นักวิทยาการคอมพิวเตอร์ในตำนานได้กล่าวไว้:

การทดสอบโปรแกรมสามารถใช้เพื่อแสดงว่ามีบัก แต่มันไม่สามารถแสดงได้ว่าไม่มีบัก!

— เอ็ดสเกอร์ ไดก์สตรา (Edsger W. Dijkstra)

• วัตถุไฟล์ (file object): ค่าที่ใช้แทนไฟล์ที่ถูกเปิดใช้งาน
• ลดทอนให้เป็นปัญหาที่ถูกแก้ไปแล้ว (reduction to a previously solved problem): วิธีการแก้ปัญหาโดยการทำให้อยู่ในรูปแบบของปัญหาที่เคยถูกแก้ไปแล้ว
• กรณีพิเศษ (special case): กรณีทดสอบที่ไม่ปกติ หรือไม่ชัดแจ้ง (และไม่น่าจะถูกจัดการได้อย่างถูกต้อง)

แบบฝึกหัด 7
คำถามนี้มาจากปริศนาในวิทยุรายการ Car Talk (http://www.cartalk.com/content/puzzlers):

จงหาคำมาหนึ่งคำที่มีอักษรคู่สามคู่ติดกัน ผมจะให้สองสามคำที่เกือบจะเป็น แต่ไม่ได้เป็น เช่น คำว่า committee, c-o-m-m-i-t-t-e-e มันจะเยี่ยมเลยยกเว้นดันมี ‘i’ ที่แอบเข้าไปอยู่ในคำ หรือคำว่า Mississippi: M-i-s-s-i-s-s-i-p-p-i ถ้าเราสามารถเอา i ออกมาได้ ก็จะใช้ได้ แต่มีอีกคำที่มีอักษรคู่สามคู่ติดกัน และเท่าที่ผมรู้ มันอาจจะเป็นคำเดียวด้วยซ้ำ แน่นอนว่ามันอาจจะมี 500 คำอื่น แต่ผมสามารถคิดได้แค่คำเดียว คำนั้นคือคำว่าอะไร?

จงเขียนโปรแกรมเพื่อหาคำนั้น เฉลย: http://thinkpython2.com/code/cartalk1.py.

แบบฝึกหัด 8
นี่คือปริศนาอีกข้อจากรายการ Car Talk (http://www.cartalk.com/content/puzzlers):

“ผมขับรถบนทางหลวงเมื่อวันก่อน และบังเอิญสังเกตเครื่องวัดระยะทาง เหมือนเครื่องวัด ระยะทางส่วนมาก มันแสดงเลขหกหลักเป็นจำนวนไมล์ถ้วนๆ เท่านั้น ดังนั้น ถ้ารถของ ผมเดินทางมาแล้ว 300000 ไมล์ ผมก็จะเห็นเลข 3-0-0-0-0-0 เป็นต้น

“คราวนี้นะ สิ่งที่ผมเห็นมันน่าสนใจมาก ผมสังเกตว่าเลขสี่ตัวสุดท้ายเป็นแบบพาลินโดรม (palindromic); นั่นคือ มันเป็นเลขตัวเดียวกันทั้งไปหน้าแล้วกลับหลัง เช่น 5-4-4-5 เป็นพาลินโดรม ดังนั้น เครื่องวัดระยะ ทางของผมอาจจะขึ้นว่า 3-1-5-4-4-5

“อีกหนึ่งไมล์ต่อมา เลขห้าตัวสุดท้ายก็เป็นแบบพาลินโดรม เช่น มันอาจจะเป็น 3-6-5-4-5-6 และอีกหนึ่งไมล์หลังจากนั้น เลขสี่ตัวตรงกลางก็เป็นแบบพาลินโดรม คุณพร้อมแล้วใช่ไหม? อีกหนึ่งไมล์ต่อมา เลขทั้งหกตัวก็เป็นแบบพาลินโดรม!

“คำถามคือ เลขตัวแรกที่ผมสังเกตเห็น คือเลขอะไร?”

ให้เขียนโปรแกรมไพธอนที่ทดสอบเลขที่มีหกหลักทั้งหมด และพิมพ์เลขที่ตรงกับสิ่งที่กำหนดข้างต้น ออกมา เฉลย: http://thinkpython2.com/code/cartalk2.py.

แบบฝึกหัด 9
นี่ก็เป็นปริศนาอีกข้อจากรายการ Car Talk ที่เราสามารถแก้ได้ด้วยการค้นหา (http://www.cartalk.com/content/puzzlers):

“เร็วๆ นี้ ผมได้ไปเยี่ยมแม่ของผม และเราพบว่าเลขสองหลักที่เป็นอายุของผมนั้นเมื่ออ่านย้อนกลับ แล้วจะเป็นอายุของแม่ เช่น ถ้าแม่อายุ 73 ผมจะอายุ 37 เราสงสัยว่าสิ่งนี้มันเกิดขึ้นบ่อยขนาดไหน ในปีที่ผ่านๆ มา แต่เราก็ออกทะเลไปคุยเรื่องอื่น และก็ไม่ได้คิดหาคำตอบ

“เมื่อผมกลับถึงบ้าน ผมก็พบว่าเลขของอายุของพวกเรานั้นกลับกันมาหกครั้งแล้ว ผมยังพบว่าถ้าเราโชคดี มันจะเกิดขึ้นอีกครั้งในอีกไม่กี่ปีนี้ และถ้าเราโชคดีมากๆ มันก็จะเกิดขึ้นอีกครั้งหลักจากนั้น ดังนั้น คำถามคือ ตอนนี้ผมอายุเท่าไหร่กันนะ”

ให้เขียนโปรแกรมไพธอนที่ค้นหาคำตอบแก่ปริศนานี้ คำใบ้: เราอาจจะพบว่า เมธอดของสายอักขระที่ชื่อว่า zfill นั้นเป็นประโยชน์

เฉลย: http://thinkpython2.com/code/cartalk3.py.

https://greenteapress.com/thinkpython2/html/thinkpython2010.html