בעיה י'

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

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

while age != ‘-1’:

    print(age)

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

 

משרד השיכון מקבל בקשות לדיור ציבורי. הדירות שהמשרד מחלק הן מארבעה סוגים: A, B, C, ו-D. 

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

def winners(types, choices):

הפונקציה מוצאת את פרטי הזוכים בדירות. לפונקציה שני פרמטרים אלה – 

• הפרמטר types – רשימה (list) ובה 4 מספרים המציינים כמה דירות מחולקות מכל אחד מארבעת הסוגים, לפי סדר זה, מהראשון לאחרון: כמה דירות A, כמה דירות B, כמה דירות C, וכמה דירות D. הנה דוגמה לרשימה types –

[1, 1, 0, 1]

לפי רשימה זו תחולק דירת A אחת, דירת B אחת, אפס דירות C, ודירת D אחת.

• הפרמטר choices – רשימה של רשומות פנימיות, כל רשומה פנימית מייצגת בקשה לדירה. בכל רשומה פנימית יש זוג ערכים: הערך הראשון הוא מספר זיהוי (מספר שלם ובו 4 ספרות) של מגיש הבקשה או מגישת הבקשה; הערך השני הוא מספר שלם בין 0 (כולל) ל-3 (כולל) המציין את סוג הדירה המבוקש: 0 מציין סוג A, 1 מציין סוג B, 2 מציין סוג C, ו-3 מציין סוג D. אדם אחד לא יכול להגיש יותר מבקשה אחת. הנה דוגמה לרשומה choices –

[(1111, 0), (3333,3), (2222,1), (4444,3)]

לפי רשימה זו מגיש הבקשה שמספר הזיהוי שלו הוא 1111 ביקש דירה מסוג 0 (A), ומגיש הבקשה שמספר הזיהוי שלו הוא 2222 ביקש דירה מסוג 1 (B). 

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

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

[1111, 2222, 3333]

פתרון

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

mountains = [“M1”, “M2”, “M3”]

counts = [7, 8, 3] 

כאן יש זיקה בין השמות ומספרי ההתפרצויות הנמצאים באינדקסים שווים. כך למשל ההר “M2” הנמצא באינדקס 1 ברשימה mountains – מספר ההתפרצויות שלו נמצא באינדקס 1 ברשימה coutns. 

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

types = [1, 1, 0, 1] 

choices = [(1111, 0), (3333,3), (2222,1), (4444,3)]

כאן אנו נדרשים להפנים כי קיימת זיקה בין מספרים – לא אינדקסים! – המופיעים באוסף אחד לאינדקסים באוסף אחר – או, לשם דיוק ברצף (sequence) אחר – ולטפל במספרים בתור אינדקסים אלה. ספציפית עלינו להבין כי המספרים הנמצאים באינדקס 1 בכל אחת ואחת מהרשומות הפנימיות של הרשימה choices מציינים אינדקסים של הרשימה types; באינדקסים אלו מופיעים מספרי דירות שנותרו לחלוקה (אם נותרו). לדוגמה אם זו רשומה פנימית ברשימה choices –

choice = (1111, 0)

עלינו להבין שהערך באינדקס 1 ברשומה זו, כלומר המספר 0, הוא למעשה אינדקס של הרשימה types, אינדקס שבו מופיע מספר המציין כמה דירות מסוג A פנויות לחלוקה. לפי זה עלינו להבין כי כדי לגשת למספר הדירות מסוג A ברשימה types עלינו לכתוב ביטוי זה –

types[choice[1]]

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

    (1) עבור כל רשומה פנימית ברשימה choices, החל מהראשונה ועד לאחרונה, 

         וכל עוד נשארו דירות כלשהן לחלוקה – 

         (1.1) יש להקצות דירה מהסוג המבוקש באמצעות עדכון מספר הדירות 

                  מהסוג המבוקש שנשארו לחלוקה ברשימה types; ספציפית יופחת 1 ממספר זה. 

                  הקצאת דירה מסוג מסוים תתבצע אך ורק אם טרם הוקצו כבר כל הדירות מהסוג הזה,

                  כלומר אם ברשימה types מופיע 0 באינדקס שבו נמצא מספר הדירות מסוג זה.

נתחיל במימוש, בינתיים לא במבנה של פונקציה. מימוש צעד 1 הוא טריוויאלי למדי –

types = [1, 1, 0, 1]

choices = [(1111, 0), (3333,3), (2222,1), (4444,3)]

for applicant, type in choices:

כאן, בכל סיבוב של הסריקה מפורקת הרשומה הפנימית הנסרקת הנוכחית למספר זיהוי ולמספר המציין סוג דירה. כך למשל בסיבוב הראשון applicant == 1111 ו- typeInd == 0. שני הנתונים הללו הם חיוניים לביצוע הפעולות המקצות את הדירות בגוף הפונקציה (צעד 1.1), ואלה הן – 

– נשתמש במספר המוצב במשתנה typeInd בתור אינדקס לרשימה types, באופן שהוסבר למעלה. ספציפית ניגש לערך באינדקס typeInd ברשימה types, כלומר מספר הדירות מהסוג המבוקש, ונבדוק אם הוא גדול מ-0 (או: שונה מ-0), כלומר אם יש דירות מהסוג המבוקש להקצאה, ואם זה המצב – 

o נפחית 1 מהמספר הזה ברשימה types כדי לציין שהוקצתה דירה מסוג זה, כנדרש. 

o נוסיף את applicant, מספר הזיהוי המופיע ברשומה הפנימית הנסרקת הנוכחית, לקבוצה של מספרי זיהוי של מגישי בקשות שזכו לדירה; קבוצה – כיוון שלפי הנדרש אוסף מספר הזיהוי צריך להיות ללא כפילויות. 

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

הנה קוד המממש את המתואר, בתוספת הוראות הדפסה שיועילו להמשך הדיון – 

types = [1, 1, 0, 1]

choices = ((1111, 0), (3333,3), (2222,1), (4444,3))

winners = set() 

for applicant, typeInd in choices: 

    if types[typeInd] > 0: 

        types[typeInd] -= 1 

        winners.add(applicant)

    print(types)

winners = sorted(list(winners))

print(winners)

>>>

[0, 1, 0, 1]

[0, 1, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[1111, 2222, 3333]

כפי שאפשר להיווכח מהפלט, הקוד משלים את פעולתו בלי תקלות, אולם הוא אינו ממלא דרישה מסוימת המופיעה בבעיה ובאלגוריתם הכללי שהוצג לעיל, והיא זו: אם לפני שהסתיימה סריקת הרשימה choices ייגמרו כל הדירות לחלוקה מכל הסוגים, הסריקה תיפסק מיד. אנו רואים כאן כי כבר לאחר הסריקה של הבקשה השלישית ברשימה choices נגמרו כל הדירות מכל הסוגים, ובכל זאת הסריקה ממשיכה. אם כן שוב אנו עומדים במצב עניינים שכבר נתקלנו בו ביותר מפתרון אחד: האם לעצור לולאת for באמצעות ביצוע הוראת break לפי קיום תנאי מסוים, או לשנות את סוג הלולאה מ-for ל-while ולהימנע מהוראת break. גם כאן נבחר בלולאת while, כיוון שהיא טבעית יותר במימוש של אלגוריתם מסוג “כל עוד”. היא תמשיך להסתובב כל עוד לא נגמרו כל הדירות להקצאה. כך תראה השורה הראשונה בלולאה – 

while sum(types) != 0:

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

שלא כמו לולאת ה-for שהשתמשנו בה, לולאת ה-while כפי שהתחלנו לכתוב אותה אינה סורקת את רשימת הבקשות לדירות, כלומר את הרשומות הפנימיות ברשימה choices, ועלינו לטפל בעניין זה. כיצד סורקים ערכים ברצף באמצעות לולאת while? גישה אחת שכבר נקטנו בה היא “לסרוק” אינדקסים של הרצף בלולאה, מ-0 ועד אורך הרצף פחות 1, ובכל סיבוב של הלולאה להשתמש באינדקס הנוכחי כדי לגשת לערך הבא באוסף (ראו למשל בעיה ???). כאן ננקוט בגישה שונה מזו ומוכרת לנו מהפתרון לבעיה ו’ (אם טרם עיינתם בו מומלץ מאוד לעשות זאת קודם להמשך הקריאה כאן): בכל סיבוב של הלולאה ניגש לערך המופיע בראש הרצף, כלומר באינדקס 0, נשתמש בערך זה לפי הצורך, ולאחר מכן נמחק את הערך הזה מהרצף; בסיבוב הבא שוב ניגש לערך בראש הרצף – והוא כבר יהיה הערך שהיה באינדקס 1 ברצף המקורי, לאחר המחיקה, וגם לאחר שנטפל בו נמחק אותו; וכן הלאה עד שהרשימה תתרוקן. במונחים של הבעיה הנוכחית, בכל סיבוב של הלולאה ניגש לרשומה הפנימית הנמצאת בתחילת הרשימה choices, ולאחר מכן נמחק רשומה פנימית זו מהרשימה choices, כדי שבסיבוב הבא הרשומה הפנימית בראש הרשימה choices  תכיל את המידע בנוגע לבקשה השניה, וכן הלאה   (בכל סיבוב נשתמש בנתונים ברשומה הפנימית הנמצאת בראש הרשימה ולא באלה הנמצאים ברשומה הנמצאת בסוף הרשימה, כפי שעשינו בפתרון לבעיה ו’, כיוון שכאן נאמר לנו במפורש שיש לסרוק את רשימת הבקשות choices מתחילתה ועד סופה). הנה הקוד המלא, הפעם בגרסת הפונקציה – 

def winners(types, choices): 

    winners = set() 

    while sum(types) != 0 and choices: 

        applicant, typeInd = choices[0]         

        if types[typeInd] > 0: 

            types[typeInd] -= 1 

            winners.add(applicant)

        del choices[0]

    return sorted(list(winners))

 

types = [1, 1, 0, 1]

choices = [(1111, 0), (3333,3), (2222,1), (4444,3)]

print(winners(types, choices))

>>>

[1111, 2222, 3333]

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

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

הנה אם כן המימוש הסופי של הפונקציה –

def winners(types, choices): 

    choices = choices[:]

    winners = set() 

    while sum(types) != 0 and choices: 

        applicant, typeInd = choices[0]         

        if types[typeInd] > 0: 

            types[typeInd] -= 1 

            winners.add(applicant)

        del choices[0]

    return sorted(list(winners))

בראש גוף הפונקציה כתבנו –

choices = choices[:]

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