בעיה ו'

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

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

while age != ‘-1’:

    print(age)

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

 

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

{1234:32, 4567:36, 3544:45}

לפי מילון זה 3544 הוא מספר זיהוי של אזרחית ו-45 הוא הגיל שלה. 

נניח כי לפי כללי משרד הפנים, זוג יכול להרשם בתור זוג נשוי אך ורק אם מתקיים תנאי זה: סכום הגילים של בני הזוג יחד אינו גדול ממספר כלשהו המשתנה מעת לעת. לדוגמה אם המספר הוא 80 והמילון הוא הנתון בדוגמה, אז הזוג 1234 ו-4567 וגם הזוג 1234 ו-3544 יכולים להרשם בתור זוגות נשואים, ולעומתם הזוג 4567 ו-3544 אינו יכול להרשם בתור זוג נשוי, כי סכום הגילים של בני הזוג, 36 ו-45 הוא 81, כלומר גדול מ-80. 

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

def oneEligible(idsAndAges, maxSum):

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

[[3544, 1234], {4567: 36}]

החיפוש שתבצע הפונקציה יתחשב באילוצים אלה:

• לאחר איתור הזוג הזכאי הראשון תוחזר הרשימה הנדרשת ולא תימשך בדיקת הזכאות.

• הפונקציה לא תבדוק זכאות של אדם עם עצמו.

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

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

 

פתרון

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

נתון אוסף של ערכים, ויש למצוא את כל הצירופים השונים זה מזה של זוגות ערכים באוסף. 

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

myAges = {1234:32, 4567:36, 3544:45}  

maxSum = 80 

for key1, val1 in myAges.items(): 

    for key2, val2 in myAges.items(): 

        if key1 != key2 and val1 + val2 <= maxSum: 

            print(key1, key2)

>>>

1234 4567

1234 3544

4567 1234

3544 1234

 

הלולאה החיצונית סורקת את כל הזוגות במילון, ומפרקת כל זוג למפתח ולערך. גם הלולאה הפנימית סורקת את כל הזוגות במילון, ומפרקת כל זוג למפתח ולערך. הוראת ההדפסה בגוף הלולאה הפנימית מדפיסה זוגות של מספרי זיהוי. הביטוי הלוגי בהוראת ה-if מוודא שיודפסו אך ורק זוגות המקיימים שני תנאים אלה: מספרי הזיהוי בהם שונים זה מזה, וסכום הגילים שאליהם ממופים מספרי זיהוי אלה ממלא אינו גדול מהמספר המוצב במשתנה maxSum כפי שאפשר לראות מהפלט, הקוד מוצא את כל הזוגות המקיימים את התנאי. עם זאת הוא מדפיס כל זוג יותר מפעם אחת. זה אינו מה שנדרש כאן: לפי השאלה די למצוא זוג אחד כלשהו המקיים את התנאי. קושי זה יוכל להיפתר מיד כשנכניס את הקוד אל תוך פונקציה, כיוון שנוכל להשתמש בהוראת return להחזיר את הזוג הראשון המקיים את התנאי (ראו בעיה א’, סעיף ב’). הנה הצעה ראשונה לכתיבת הפונקציה, והיא גם כבר כוללת את ערך ההחזרה מהסוג המבוקש –

def oneEligible(idsAndAges, maxSum): 

    for key1, val1 in idsAndAges.items(): 

        for key2, val2 in idsAndAges.items(): 

            if key1 != key2 and val1 + val2 <= maxSum: 

                del idsAndAges[key1]

                del idsAndAges[key2]

                return [[key1, key2], idsAndAges]

    return [[], idsAndAges]

 

print(oneEligible({1234:32, 4567:36, 3544:45}  , 80))

>>>

[[1234, 4567], {3544: 45}]

 

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

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

נמשיך בכתיבת הפתרון. הפונקציה oneEligible בגרסתה הנוכחית ממלאת שתיים משלוש הדרישות שהשאלה כופה. ראשית היא אינה בודקת זכאות של אדם עם עצמו (בשל הבדיקה אם המפתחות שונים זה מזה – הביטוי הלוגי הראשון בהוראת ה-if). שנית לאחר איתור הזוג הזכאי הראשון מוחזרים מיד הנתונים בנוגע אליו והמילון ללא נתונים אלה. בה בעת הפונקציה אינה מקיימת דרישה שלישית זו: אם נבדקה פעם אחת הזכאות של זוג מסוים ונמצא כי אין לו זכאות, הזכאות של הזוג לא תיבדק פעם נוספת. הפונקציה בגרסתה כרגע אינה מוודאת שסכום הגילים של הזוג key1 ו-key2 טרם נבדק בסיבובים קודמים של הלולאות. כדי להיווכח בדבר נפריד בין שני התנאים הנבדקים בלולאה הפנימית, נוסיף הוראת הדפסה לאחר הבדיקה המוודאת שאין נבדקת זכאות של אדם עם עצמו, ונשנה מעט את המילון המועבר לפונקציה –

def oneEligible(idsAndAges, maxSum): 

    for key1, val1 in idsAndAges.items(): 

        for key2, val2 in idsAndAges.items():             

            if key1 != key2: 

                print(key1, key2)

                if val1 + val2 <= maxSum:

                    del idsAndAges[key1]

                    del idsAndAges[key2]

                    return [[key1, key2], idsAndAges]

    return [[], idsAndAges]

 

print(oneEligible({1234:52, 4567:36, 3544:45}  , 80))

>>>

1234 4567

1234 3544

4567 1234

4567 3544

3544 1234

3544 4567

[[], {1234: 52, 4567: 36, 3544: 45}]

כפי שאפשר להיווכח מהפלט, יש זוגות שסכום גיליהם נבדק יותר מפעם אחת, למשל אלה שמספרי הזיהוי שלהם הם 1234 ו-4567. כאמור השאלה דורשת להימנע מבדיקות כפולות כאלו. בשאלה 5 פתרנו בעיה דומה באמצעות הכנסת כל זוג נבדק לרשימת עזר, ובדיקה, רגע לפני שנבדק הזוג הבא, אם זוג זה כבר נמצא ברשימה. כאן נבחן גישה שונה מזו לפתרון הבעיה. בקוד המשוכתב לפי גישה זו הלולאה החיצונית גם כן תסרוק כל אחד ואחד מהזוגות מספר זיהוי-גיל במילון idsAndAges. אך הפעם, מיד בתחילת כל סיבוב שלה, נמחק מהמילון את זוג שהמפתח בו הוא מספר הזיהוי הנוכחי שנסרק בלולאה זו. מה נשיג במחיקה זו? ראשית הלולאה הפנימית כבר לא תסרוק את הזוג של בעל מספר הזיהוי הנסרק בלולאה החיצונית – וזה מצוין, כיוון שכך מראש לא נבחן מועמדות של אדם עם עצמו. שנית, המחיקה תגרום לכך שבסיבובים הבאים של לולאת ה-for החיצונית לא ייבחנו זוגות שאחד מחבריו הוא האדם הנוכחי שסורקת הלולאה הזאת – וגם זה מצוין: הרי אם יהיו סיבובים נוספים ללולאה החיצונית, פירוש הדבר שנבדקו מועמדות כל הזוגות שבעל מספר זיהוי זה הוא חבר בהם, ולא התבצעה הוראת ה-return, כלומר נמצא שאין ולו אחד מזוגות אלה הרשאי להרשם בתור זוג נשוי.  נניח למשל שנתון מילון הדוגמה ושבמהלך ביצוע לולאת ה-for החיצונית הגענו למפתח 1234. נמחק מיד את הזוג במילון ש-1234 הוא המפתח שלו. הלולאה הפנימית תסרוק את כל זוגות מספרי הזיהוי שהמספר 1234 מופיע בהם חוץ מהזוג שהוא מופיע בו פעמיים, כלומר –

1234 4567

1234 3544

נוסיף ונניח כי בסיבוב הבא של הלולאה החיצונית ייסרק האדם שמספר הזיהוי שלו הוא 4567. הלולאה הפנימית כבר לא תמצא את המספר 1234 באוסף המפתחות – הזוג שזה המפתח שלו נמחק בסיבוב הקודם – וממילא לא תסרוק את הזוג המכיל את המספרים 1234 ו-4567 – כפי הנדרש, שהרי כבר זוג זה נסרק קודם (אמנם בסדר אחר). 

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

def oneEligible(idsAndAges, maxSum): 

    for key1, val1 in idsAndAges.items(): 

        del idsAndAges[key1]

        for key2, val2 in idsAndAges.items():             

            if key1 != key2 and val1 + val2 <= maxSum:

                del idsAndAges[key1]

                del idsAndAges[key2]

                return [[key1, key2], idsAndAges]

    return [[], idsAndAges]

 

print(oneEligible({1234:52, 4567:36, 3544:45}  , 80))

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

    for key1, val1 in idsAndAges.items():

RuntimeError: dictionary changed size during iteration

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

def oneEligible(idsAndAges, maxSum): 

    for key1, val1 in idsAndAges.items():         

        for key2, val2 in idsAndAges.items():             

            if key1 != key2 and val1 + val2 <= maxSum:

                del idsAndAges[key1]

                del idsAndAges[key2]

                return [[key1, key2], idsAndAges]

            del idsAndAges[key1]

    return [[], idsAndAges]

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

[(1234, 52), (4567, 36), (3544, 45)]

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

def oneEligible(idsAndAges, maxSum): 

    itemsCopy = list(idsAndAges.items()) 

    while itemsCopy: 

        key1, val1 = itemsCopy.pop()

        for key2, val2 in itemsCopy:                                     

print(key1, key2) 

            if val1 + val2 <= maxSum:

                del idsAndAges[key1]

                del idsAndAges[key2]

                return [[key1, key2], idsAndAges]

    return [[], idsAndAges]

 

print(oneEligible({1234:52, 4567:36, 3544:45}  , 80))

>>>

3544 1234

3544 4567

4567 1234

[[], {1234: 52, 4567: 36, 3544: 45}]

כמה נקודות ראויות לתשומת לב בקוד הזה – 

• לפי הפלט הזוגות המתקבלים בכל סיבוב וסיבוב של הלולאה הפנימית הם מראש שונים מכל הזוגות שכבר נסרקו (בשל המחיקה, כפי שהוסבר לעיל). לכן הפונקציה בגרסתה זו כבר אינה מוודאת שאין נבדקת זכאות של אדם מול עצמו (באמצעות התנאי key1 != key2) – אין בכך צורך, כיוון שממילא הזוג מספר זיהוי-גיל הנסרק בלולאה החיצונית אינו קיים כבר ברשימה itemsCopy כשהלולאה הפנימית מתחילה לסרוק רשימה זו.

• שליפת הזוג מרשימת הזוגות itemsCopy בראש לולאת ה-while מתבצעת באמצעות הפעלת הפונקציה pop על רשימת הזוגות. כשאין מועברים ארגומנטים לפונקציה pop, כמו במקרה שלפנינו, הפונקציה מוחקת מהרשימה את הערך האחרון בה ומחזירה אותו; כאן ערך זה הוא רשומה של זוג מספר זיהוי-גיל, לדוגמה (3544, 45). מבחינת הקוד כאן אין חשיבות למקום שממנו נשלף הזוג מספר זיהוי-גיל מהרשימהitemsCopy , הרי נאמר בשאלה שאפשר להחזיר מידע על כל זוג המקיים את תנאי הזכאות לרישום לנישואין. 

• לפי תנאי לולאת ה-while לולאה זו נמשכת כל עוד רשימת הזוגות itemsCopy אינה ריקה, כלומר כל עוד טרם סרקנו – וממילא גם מחקנו – את כל הזוגות מספר זיהוי-גיל ברשימה זו. 

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