מצא את המילה האחרונה

השאלה הבאה היא שאלה ממש קלילה באופן יחסי (והתחשק לי משהו קליל), אבל היא הייתה מעניינת כי היו לה הרבה מקרי קיצון שאם לא נבדקו היו יכולים להכשיל את האלגוריתם.

השאלה היא כזו –
בהינתן מחרוזת s שיכולה להכיל רק אותיות באנגלית ותווי רווח, החזר את המילה האחרונה במחרוזת (מילה מוגדרת כרצף אותיות ללא רווחים).

במבט ראשון השאלה הזו נראית סופר קלילה.

צריך לרוץ על המחרוזת מימין לשמאל, וכשמגיעים לרווח לעצור ולהחזיר את המילה שמצאנו.
האלגוריתם הראשון שעלה לי לראש היה זה –

def find_last_word(s):
    if len(s) == 0:
        return ""
    last_word = ""
    i = len(s) - 1
    while s[i] != " ":
        last_word = s[i] + last_word
        i -= 1
    return last_word

דוגמא ראשונה – מחרוזת ריקה –

s=””
len(s) = 0
return “”

את מקרה הקיצון של המחרוזת הריקה כיסיתי בפונקציה שלי, כי אני כבר רגילה באופן אוטומטי להתייחס אליו.

אז הלאה לדוגמא הבאה.

s=”a”
len(s) = 1
i=0
last_word = “”
s[0] = “a”
last_word = “a”
i=-1
s[-1] → Failure

אוי, גרמתי לאלגוריתם שלי לזרוק שגיאה.
למה? כי כשהתבקשתי למצוא את המילה האחרונה ישר חשבתי על מחרוזת שמכילה מספר מילים, ולא חשבתי על מחרוזת שמכילה מילה אחת, ללא רווחים.
אני אתקן את האלגוריתם כדי שלא יכשל על הדוגמא הנ”ל.

def find_last_word(s):
    last_word = ""
    i = len(s) - 1
    while i>=0 and s[i] != " ":
        last_word = s[i] + last_word
        i -= 1
    return last_word

מעולה. עוד נקודה שמעניין לשים לב אליה עכשיו, זה שההוספה של התנאי i>=0 גם מכסה את המקרה של מחרוזת ריקה, כך שעכשיו אני יכולה להוריד את הבדיקה הראשונית שלי. כשהמחרוזת ריקה האורך שלה הוא 0, ויתקבל i=-1, הלולאה לא תרוץ, והאלגורית יחזיר מחרוזת ריקה.

עוד דוגמא, יש עוד בעיות לתקן.
למשל, במקרה הבא –

s = “dog “
len(s)=4
i=3
last_word=””
s[3] = ‘ ‘
return “”

האלגוריתם החזיר פלט לא נכון – לא בדקתי אם המחרוזת מסתיימת במקרה ברווחים.
אני אוסיף תיקון.

def find_last_word(s):
    last_word = ""
    i = len(s) - 1
    while i >= 0 and s[i] == " ":
        i -= 1
    while i >= 0 and s[i] != " ":
        last_word = s[i] + last_word
        i -= 1
    return last_word

אני אריץ שוב את אותה הדוגמא.

s = “dog “
len(s)=4
last_word=””
i=3
s[3] = ‘ ‘
i=2
s[2]=g
last_word=”g”
i=1
s[1]=o
last_word=”og”
i=0
s[0]=d
last_word=”dog”
i=-1
return ”dog”

עכשיו אני אנסה דוגמא של מחרוזת שמכילה רק רווחים.

s=” “
len(s) = 1
i=0
s[0] = ‘ ‘
i=-1
return “”

נראה טוב, על ידי בדיקות זהירות מצאתי את כל הבאגים (אני מקווה) ויש לי אלגוריתם מלא.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/last_word.py