בעיה י"ז

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

age = input(‘Insert age; -1 to stop: ‘)

while age != ‘-1’:

    print(age)

    age = input(‘Insert age; -1 to stop: ‘)

 

כתבו את הפונקציה minimalText –

def minimalText(filename, chars):

לפונקציה שני פרמטרים אלה –

• filename – שם (מחרוזת) של קובץ טקסט הנמצא בתיקיית העבודה (working directory).

• chars – מילון שבו כל מפתח הוא תו וכל ערך הוא מספר שלם חיובי, לדוגמה –

{‘a’: 2, ‘b’: 1}

הפונקציה פותחת לקריאה את הקובץ filename ומחזירה את המחרוזת הקצרה ביותר המתחילה בתחילת הקובץ ומכילה את כל התווים המופיעים במילון chars, כל תו לפחות כמספר הפעמים השווה למספר שהתו ממופה אליו במילון chars. עבור מילון הדוגמה הפונקציה תחזיר את המחרוזת הקצרה ביותר מתחילת הקובץ ומכילה לפחות פעמיים את התו ‘a’ ולפחות פעם אחת את התו ‘b’. אם אין בקובץ את מספר ההופעות של התווים שצוין במילון, הפונקציה תחזיר מחרוזת ריקה. 

למשל נניח שמילון הדוגמה מועבר לפונקציה ושזה תוכן הקובץ ששמו מועבר לפונקציה –

Francis Bacon,

the great philosopher,

was born 

in 1561.

בקובץ 4 שורות. התו האחרון בו (לפני תו סוף הקובץ) הוא התו נקודה. המחרוזת שהפונקציה תחזיר היא זו –

“Francis Bacon,\nthe great philosopher, was b”

זו המחרוזת הקצרה ביותר המתחילה בתחילת הקובץ ושיש בה את התו ‘a’ לפחות פעמיים ואת התו ‘b’ לפחות – למעשה: בדיוק – פעם אחת.

פתרון

לראשונה אנו באים לעסוק בטיפול בקבצים, וספציפית בטיפול בקבצי טקסט. עקרונית יש שתי דרכים לטפל בקבצים. הדרך האחת היא לקרוא את כל תוכן הקובץ למחרוזת אחת, ולאחר מכן לטפל במחרוזת זו באמצעות הכלים לטיפול במחרוזות הקיימים בשפה. בגישה זאת ננקוט בפתרון לבעיה הבאה, שאף היא עוסקת בקבצי טקסט. הדרך האחרת היא באמצעות הזזת מצביע לקובץ (המתקבל בתור ערך החזרה של הפונקציה open) בתוך הקובץ וביצוע פעולות אגב תנועתו. הפתרון לבעיה הנוכחית מבוסס על גישה זו, ומיוסד על אלגוריתם זה – 

(1) נציב את המצביע לקובץ בתחילת הקובץ. 

(2) נאתחל משתנה בשם s ונאתחל אותו למחרוזת ריקה 

(3) נזיז את המצביע לקובץ, כל תזוזה בגודל של תו אחד בקובץ, וכל עוד לא הגענו לסוף הקובץ, ובכל תזוזה כזו –

    (3.1) נקרא את התו שהמצביע חלף על פניו 

    (3.2) נוסיף את התו הזה לסוף המחרוזת s

    (3.3) נבדוק אם המחרוזת s הנוכחית מקיימת את התנאי הנדרש בבעיה (כלומר יש בה את 

            התווים הנדרשים כל אחד במספר ההופעות הנדרש) 

        (3.3.1) אם כן – נחזיר את s

(4) נחזיר מחרוזת ריקה 

 

בצעד 3 באלגוריתם מתקבלות במשתנה s בזו אחר זו מחרוזות שכל אחת מהן מתחילה בתחילת הקובץ והיא גדולה בתו אחד יותר מהמחרוזת הקודמת. כך עבור קובץ הדוגמה –

Francis Bacon,

the great philosopher,

was born 

in 1561.

יתקבלו המחרוזות האלו –

“F”

“Fr”

“Fra”

“Fran”

“Franc”

וכן הלאה. צעד 3.3 יוודא שברגע שתימצא מחרוזת המקיימת את התנאי המוצג בבעיה היא תוחזר מיד. אם מחרוזת כזו לא תימצא עד סוף הלולאה המתבצעת בצעד 3, תוחזר בצעד 4 מחרוזת ריקה, כנדרש. 

אם כן נתחיל את המימוש בקבלת מצביע לקובץ והנחתו בתחילת הקובץ. כיוון שהטיפול בקובץ מתמצה בקריאה ממנו, נזמן את הפונקציה open באופן שתגדיר פתיחה לצורך קריאה, כך –

f = open(filename, “r”)

בזימון הפונקציה open בררת המחדל היא פתיחה לצורך קריאה ולכן אפשר גם לא להעביר את הארגומנט “r”. 

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

לאחר פתיחת הקובץ המצביע f מוצב לפני התו הראשון בקובץ. בקובץ המוצג כדוגמה בתיאור הבעיה המצביע f מוצב לפני האות הראשונה במילה Francis. כאמור נסרוק את הקובץ באמצעות הזזת המצביע, וספציפית באמצעות הזזתו תו-תו, כל עוד לא נגיע לתו סוף הקובץ (מחרוזת ריקה). אם כן הקוד יכיל לולאת while וזה יהיה השלד שלה –

ch = f.read(1)

while ch != “”: 

    . . . 

    ch = f.read(1)

בכל זימון של הפונקציה read בקוד זה אנו מעבירים אליה את המספר 1. בזימון זה פעולתה כפולה: היא מזיזה את המצביע לקובץ אל מעבר לתו שהמבציע נמצא כרגע לפניו. וגם מחזירה את התו הזה שהמצביע חלף על פניו. כך עבור קובץ הדוגמה הזה –

Francis Bacon,

the great philosopher,

was born 

in 1561.

הוראת ה-read לפני הלולאה תקרא את המחרוזת באורך 1 המופיע מימין למצביע f. כאמור לאחר ביצוע הפונקציה open מצביע זה נמצא משמאל לאות F. לכן זימון הפונקציה read יחזיר את המחרוזת ‘F’ והמצביע f יוזז תו אחד קדימה, כלומר הוא יוצב בין האות F לאות r. בסוף הסיבוב הראשון של הלולאה יחזיר הזימון של הפונקציה read את המחרוזת ‘r’ והמצביע f שוב יוזז צעד אחד קדימה, אל המקום שבין האות r לאות a. כך תמשיך הלולאה להסתובב עד שהפונקציה read תחזיר את התו נקודה שבסוף הקובץ. הביצוע הבא של הוראת ה-read יחזיר מחרוזת ריקה – התו המציין סוף קובץ – ובנקודה זו תנאי הלולאה כבר לא יתקיים והלולאה תעצר. 

נמשיך אל בניית המחרוזת s. לפי האלגוריתם שניסחנו, עלינו להגדיר לפני הלולאה משתנה המכיל מחרוזת ריקה, ובכל סיבוב של הלולאה להוסיף לו את התו שקראנו זה עתה. הנה הקוד המשוכתב –

s = “”

ch = f.read(1)

while ch != “”: 

    s += ch 

    . . . 

    ch = f.read(1)

כך למשל תבנה המחרוזת s בהינתן קובץ הדוגמה –

“”

“F”

“Fr”

“Fra”

“Fran”

“Franc”

וכן הלאה.

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

s = “”

ch = f.read(1)

while ch != “”: 

    s += ch 

    all = True 

    for k, v in chars: 

        if s.count(k) < v: 

        all = False 

    if all: 

        ch = “”

        continue 

    ch = f.read(1)

בגוף לולאת ה-while, לאחר הוספת התו הנוכחי שנקרא מהקובץ למחרוזת s ההולכת וגדלה, מוגדר המשתנה all. זה משתנה דגל, והוא נועד לאותת אם המחרוזת s מכילה את כל התווים במילון chars, כל אחד ואחד במספר הופעותיו הנדרש. לפני הלולאה אנו מניחים שזה המצב ולכן מאתחלים את all ל-True. בכל סיבוב וסיבוב מתבצעת בדיקה של כל התווים המופיעים במילון chars: האם כל אחד ואחד מהם מופיע במספר ההופעות הנדרש במחרוזת s. אם יש לפחות תו אחד שאינו מופיע במחרוזת s במספר הפעמים הנדרש, ערכו של all מוחלף ב-False. שוב נדגים את האמור באמצעות מילון הדוגמה וקובץ הדוגמה. נניח למשל שבסיבוב הנוכחי המחרוזת שיש במשתנה s היא זו 

“Francis Bacon,\nthe great phi”

לולאת ה-for תסרוק את שני המפתחות במילון, התו ‘a’ והתו ‘b’. היא תמצא שהתו ‘a’ מופיע במחרוזת לפחות פעמיים, כנדרש, אך התו ‘b’ אינו מופיע בה כלל, שלא כנדרש. לכן מוצב הערך False במשתנה all, תנאי ה-if שמחוץ ללולאת ה-for אינו מתקיים, ולולאת ה-while ממשיכה להסתובב. אם לעומת זאת בסיבוב הנוכחי המחרוזת שיש במשתנה s היא זו –

“Francis Bacon,\nthe great philosopher, was b”

לולאת ה-for מוצאת שמספר ההופעות של ‘a’ במחרוזת וגם מספר ההופעות של ‘b’ במחרוזת עומדים בנדרש, ולכן בסוף הלולאההערך במשתנה all הוא עדיין True. במקרה זה יש לסיים את לולאת ה-while מיד, כיוון שיש בידינו המחרוזת הקצרה ביותר הנדרשת ואין כל צורך להמשיך לקרוא מהקובץ. לצורך העצירה תנאי לולאה ה-while צריך לא להתקיים עוד, וזו הסיבה שמוצבת מחרוזת ריקה במשתנה ch. ברגע שמתבצעת ההוראה continue הזרימה עוברת לבדיקת תנאי הלולאה ובה מתברר כי התנאי כבר אינו מתקיים והלולאה נפסקת. 

נציע פתרון נוסף לאיתור המחרוזת המקיימת את התנאי המוצג בבעיה. 

הפתרון נוקט בגישה זו: עבור כל תו שנקרא מהקובץ, נחסיר 1 ממספר ההופעות של תו זה במילון chars; בכך הן נסמן שזה עתה מצאנו הופעה שלו בקובץ הן נעדכן את מספר ההופעות שנותר למצוא. אם בעקבות פעולת ההחסרה התו ממופה למספר 0, פירוש הדבר יהיה שנמצא המספר הנדרש של ההופעות של תו זה בקובץ. במצב זה נמחק מהמילון את הזוג שהתו מופיע בו. נעצור את הלולאה כשהמילון יתרוקן כולו, לאחר שיימצאו בקובץ כל התווים במספר הופעותיהם הנדרש. במבט כללי, אנו משתמשים כאן במילון שכיחויות כדי למנות, אגב סריקת אוסף, את מספר הופעותיהם של ערכים מסוימים באוסף. הנה מימוש של הפונקציה minimalText המבוסס על רעיון זה –

def minimalText(filename, chars): 

    f = open(filename, “r”)

    s = “”  

    ch = f.read(1)  

    while chars != {} and ch != “”: 

        s += ch 

        if ch in chars: 

            if chars[ch] == 1: 

                del chars[ch]            

            else: 

                chars[ch] -= 1            

   if not chars: 

           return s 

        ch = f.read(1)

    f.close() 

    return “”

בגוף הלולאה בדקנו אם התו הנוכחי שנקרא מהקובץ הוא תו (מפתח) במילון. אם זה המצב ונותר למצוא רק עוד הופעה אחת של התו הזה – זו שכרגע מצאנו – נמחק מהמילון את הזוג שהתו הזה הוא המפתח שלו. בכל מקרה אחר נפחית 1 ממספר ההופעות הנדרש של התו. כך בהינתן מילון הדוגמה וקובץ הדוגמה, כשנקרא לראשונה התו ‘a’ והמחרוזת שיש במשתנה s היא זו –

“Fra”

אנו מוצאים לראשונה תו שהוא מפתח במילון, התו ‘a’, ומפחיתים 1 מהערך שהתו הזה ממופה אליו. המילון המתקבל הוא זה –

{‘a’: 1, ‘b’: 1}

וכשנקרא התו ‘a’ השני בקובץ, והמחרוזת שיש במשתנה s היא זו –

“Francis Ba”

אנו שוב מוצאים תו שהוא מפתח במילון, התו ‘a’. כיוון שהערך שהתו הזה ממופה אליו הוא בשלב זה 1, הזוג נמחק מהמילון והמילון המתקבל הוא זה –

{‘b’: 1}

כשנקרא התו ‘a’ השלישי בקובץ, והמחרוזת שיש במשתנה s היא זו –

“Francis Bacon,\nthe grea”

אין אנו מוצאים את התו ‘a’ בתור מפתח במילון ולכן כלל לא נכנסים לגוף הוראת ה-if.  וכשאנחנו מוצאים את ההופעה הראשונה של התו ‘b’, והמחרוזת שיש במשתנה s היא זו –

“Francis Bacon,\nthe great philosopher, was b”

מתברר שהתו ‘b’  הוא מפתח במילון ושהערך שהוא ממופה אליו הוא 1. או אז נמחק הזוג הזה מהמילון, המילון מתרוקן לגמרי, והוראת ה-if הבאה בסוף גוף הלולאה מזהה זאת – כלומר מזהה למעשה שאיתרנו את המחרוזת שיש להחזיר – ומחזירה את המחרוזת הזאת. 

נדגיש: לולאת ה-while יכולה להעצר לא רק כשלא יישארו זוגות במילון, אלא גם כשהגענו לסוף הקובץ לפני שמצאנו את המבוקש. במקרה זה המילון אינו מתרוקן, ולכן ממילא לא מתבצעת החזרת המחרוזת s, הלולאה מגיעה לסיומה, והוראת ההחזרה בסוף הפונקציה מחזירה מחרוזת ריקה. 

שתי הערות לסיום. ראשית שימו לב שדאגנו לסגור את הקובץ לאחר שהשלמנו את הטיפול בו. כדאי לאמץ פרקטיקה זו בטיפול בקבצים, גם כאשר אין כותבים לתוכם. שנית כמו בשאלות קודמות (ראו לעיל, שאלות ???) אנו משנים במקום אוסף שהועבר לפונקציה. כאן זה המילון chars, ועלינו לוודא שמילון זה אינו צריך להישאר במצבו המקורי לאחר זימון הפונקציה.