פורסם ב זה רק קוד, מתכוננות לראיונות

בעיית פינוי הסנאט

קוד: senate_evacuation.py
זמן קריאה: 16 דקות

השאלה הבאה לקוחה ממאגר השאלות של Google Code Jam, ואתן יכולות לנסות לפתור אותה כאן.

השאלה הולכת ככה – 
שריפה פרצה בסנאט האמריקאי (אבוי!) וצריך לפנות משם את כל הסנטורים. במקום נמצאים סנטורים מ-N מפלגות שמסומנות באותיות A-N ובכל שלב של הפינוי אפשר להוציא עד שני סנטורים.
במהלך הפינוי הסנטורים עדיין יכולים להצביע על חוקים (כל כך שמחה שאני מתכנתת ולא פוליטיקאית!) ולכן צריך לוודא שבכל שלב של הפינוי אין אף מפלגה שחבריה מהווים יותר מ-50% מהקולות שנשארו בסנאט הבוער.
המטרה היא למצוא תוכנית פינוי שמקיימת את התנאים ומובטח לי שקיימת תוכנית כזו.

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


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

אם יש לי קבוצה של איבר אחד בלבד – 

x = {A}

אז האלגוריתם שלי יוציא את A וסיימתי.

אם יש לי קבוצה של שני איברים – 

x = {A,B}

האלגוריתם יוציא את A,B יחד ויסיים.
חשוב לשים לב שאני חייבת להוציא את שניהם יחד, כי אם אני אוציא רק אחד מהם אז השני יהווה יותר מחצי מהקבוצה.

מה קורה במקרה של קבוצה עם שלושה איברים?
ובכן, אני אחשוב על זה שנייה. אם כל האיברים זהים, למשל במקרה הזה  –

x = {A,A,A}

אז המפלגה A מתחילה עם רוב של יותר מחצי מהקבוצה.
אם יש שתי מפלגות, למשל במקרה הזה – 

x = {A,A,B}

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

x = {A,B,C}

מצוין. עכשיו, איך הייתי פותרת את המקרה הזה?
אם הייתי מוציאה זוג איברים מהקבוצה, למשל את A,B יחד, אז C היה נשאר לבד ומהווה רוב. לכן, אני חייבת להוציא קודם רק איבר אחד, למשל את C, ואז יתקבל המצב הזה –

{A,B,C} - {C} = {A,B}

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

אוקי, אני אנסה עוד דוגמא אחת של קבוצה בגודל 4 עם שלוש מפלגות.
לקבוצה של ארבעה סנטורים מ-4 מפלגות יש 6 מצבים חוקיים – 

1. {A, A, B, B}
2. {A, A, B, C}
3. {A, A, C, C}
4. {A, B, B, C}
5. {A, B, C, C}
6. {B, B, C, C}

בכל מצב אחר יהיה רוב לאחת המפלגות (אתן יכולות לבדוק בעצמכן!)
אוקי, איך הייתי פותרת את המקרים האלו?

אני יודעת שאני צריכה להוציא איבר אחד או שניים מהקבוצה ולהגיע למצב חוקי אחר. כלומר – או לקבוצה בגודל 3 עם שלושה איברים שונים או לקבוצה בגודל 2 עם שני איברים שונים (שני מצבים שכבר ראיתי שהם חוקיים).
בכל מצב שבו יש שלוש מפלגות בקבוצה (כלומר, מצבים 2,4,5) אני יכולה להוציא איבר אחד, כדי להגיע לקבוצה {A,B,C} – 

{A, A, B, C} - {A} = {A,B,C}
{A, B, B, C} - {B} = {A,B,C}
{A, B, C, C} - {C} = {A,B,C}

ומשם אני כבר יודעת איך לפתור.
בכל מצב שבו יש שתי מפלגות בקבוצה (כלומר, מצבים 1,3,6) אני יכולה להוציא שני איברים כדי להגיע לקבוצה בגודל שני איברים עם שני איברים שונים – 

{A, A, B, B} - {A,B} = {A,B}
{A, A, C, C} - {A,C} = {A,C}
{B, B, C, C} - {B,C} = {B,C}

ומשם אני כבר יודעת איך לפתור.


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

האלגורים יעבוד בערך ככה –

def evict_the_senate(senators_counter):
	eviction_plan = []
	while len(senators_counter) > 0:
		senators_to_evict = choose_next_to_evict(senators_counter)
		remove_senators(senators_counter, senators_to_evict)
		eviction_plan.append(senators_to_evict)
	return eviction_plan

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

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

def has_majority(senators_counter, senators_to_remove, num_senators):
	senators_counter[senators_to_remove] -= 1
	max_party_count = senators_counter[max(senators_counter, key=senators_counter.get)]
	return max_party_count/(num_senators-1) > 0.5
def choose_next_to_evict(senators_counter):
	num_senators = sum(senators_counter.values())
	for party in senators_counter.keys():
		if !has_majority(deep_copy(senators_counter), party, num_senators):
			return [party]

מממ… אוקי, אני כבר רואה שאני מסתבכת פה.
בשביל הסרה של איבר יחיד אני צריכה לעבור על כל האיברים כדי למצוא הוצאה חוקית, ובעבור כל אחד לחשב Max. כלומר, הסיבוכיות של בדיקת הוצאה של סנטור יחיד היא N2.
אבל, אני צריכה גם לבדוק את כל ההוצאות של שני איברים כדי למצוא. מספר האפשרויות לבחור שני איברים מתוך N הוא N2. לכן הסיבוכיות הכוללת של choose_next_to_evict תהיה N3.
למי שמתעניינת, החישוב הוא כזה (תודה לאל לוויקיפדיה שיכולה להזכיר לי את חוקי הקומבינטוריקה כל כך הרבה שנים אחרי התיכון) – 

N! / 2! * (N-2)! = 
N*(N-1)*(N-2)! / 2 * (N-2)! ~ N^2

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

{A,A,A,B,B,C}

במקרה הזה אם אני אוציא את B או C אני אקבל רשימה לא חוקית, שבה A מהווה יותר מ-50%, אבל אם אני אוציא את A אני אקבל רשימה חוקית.
למה? כי A הוא האיבר הכי נפוץ ברשימה. הוצאה של אחד מהאיברים הכי נפוצים ברשימה רק תגדיל את האחוזים של האיברים המועטים, ולכן פחות סביר* שהיא תגדיל את התדירות של אחד מהם לאל מעל 50% ותגרום למצב לא חוקי.
לעומת זאת, C ו-B הם פחות נפוצים, והוצאה של אחד מהם עלולה לגרום לעלייה של A (שכבר מהווה 50%) ליותר מ-50%.

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

{A,A,A,B,B,B}

במקרה כזה יש שני איברים שהם הכי נפוצים – A ו-B, והוצאה של אחד מהם תביא למצב לא חוקי, ולכן במצב כזה צריך להוציא שניים.
האם יש עוד מצבים כאלה?
כדי שהסרה של איבר אחד תגרום לתת קבוצה להוות יותר מ-50% מגודל הקבוצה החדש צריך להתקיים התנאי הבא.

נניח ש-x היא תת קבוצה של y, אז –

x <= ½y

אחרי הסרה של איבר אחד שלא משתייך ל-x מתקיים –

x &gt; ½(y-1)
↓
x &gt; ½y-½ 

שתי המשוואות יחד יוצרות –

½y-½ < x <= ½y

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

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

אני אכתוב את האלגוריתם הזה –

def choose_next_to_evict(senators_counter):
	If len(senators_counter) == 2:
		return senators_counter.keys()
	else:
		return [max(senators_counter, key=senators_counter.get)]

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

מגניב, עכשיו רק לחבר את הכל יחד –

def remove_senators(senators_counter, senators_to_evict):
	for senator in senators_to_evict:
		senators_counter[senator] -= 1
		if senators_counter[senator] == 0:
			senators_counter.pop(senator)
def format_results(eviction_plan_list):
	eviction_plan_list = [“”.join(senators) for senators in eviction_plan_list]
	return “ “.join(eviction_plan_list)
def evict_the_senate(senators_counter):
	eviction_plan = []
	while len(senators_counter) &gt; 0:
		senators_to_evict = choose_next_to_evict(senators_counter)
		remove_senators(senators_counter, senators_to_evict)
		eviction_plan.append(senators_to_evict)
	return format_results(eviction_plan)

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

הגיע הזמן להריץ כמה דוגמאות –

senators_counter = {}
evict_the_senate([]):
	eviction_plan = []
	return []
senators_counter = {A:2, B:2}
evict_the_senate({A:2, B:2}):
	eviction_plan = []
	senators_to_evict = choose_next_to_evict({A:2, B:2}) → [A,B]
	remove_senators({A:2, B:2}, [A,B]) → senators_counter = {A:1, B:1}
	eviction_plan = [A,B]
	senators_to_evict = choose_next_to_evict({A:1, B:1}) → [A,B]
	remove_senators({A:1, B:1}, [A,B]) → senators_counter = {}
	eviction_plan = [A,B,A,B]
	return [A,B,A,B]
senators_counter = {A:1, B:1, C:1}
evict_the_senate({A:1, B:1, C:1}):
	eviction_plan = []
	senators_to_evict = choose_next_to_evict({A:1, B:1, C:1}) → [A]
	remove_senators({A:1, B:1, C:1}, A) → senators_counter = {B:1, C:1}
	eviction_plan = [A]
	senators_to_evict = choose_next_to_evict({B:1, C:1}) → [B]
	remove_senators({B:1, C:1}, B) → senators_counter = {C:1}
	eviction_plan = [A, B]
	senators_to_evict = choose_next_to_evict({C:1}) → [C]
	remove_senators({C:1}, C) → senators_counter = {}
	eviction_plan = [A, B,C]
	return [A, B,C]

עובד ואני די מרוצה מהפתרון. הגיע הזמן לקודד!

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

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

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

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

10 תגובות בנושא “בעיית פינוי הסנאט

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

    גם הפתרון הזה נוסה בראש בלבד – ט.ל.ח 🙂

    1. נשמע טוב 😊
      אני לגמרי מסכימה שמיון הוא יעיל וכדאי (גם כתבתי על זה משהו בהערה בפוסט).

      לגבי פינוי מדורג שמתחיל מהמפלגות הקטנות יותר ואז עובר לגדולות – למה העדפת את השיטה הזו על פני לפנות את הגדולות קודם?

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

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

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

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

      3. כתבתי שאני רגיש לעלויות נסתרות “לטוב ולרע” – בהחלט ייתכן שאם הייתי הולך לראיון עבודה בתחום שאינו אמבדד, היו זורקים אותי מכל המדרגות בגלל התעסקות עם דברים שקורים ב-O(1)…

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

  2. היי, תודה על ההפניה לשאלה!
    אני חושבת שכדאי לבחון את היעילות קצת אחרת:
    יש את המספר הכולל של חברי הסנאט, נקרא לו M, ויש את מספר המפלגות N. מתקיים M >> N.
    מכיוון שהגודל של הפלט הוא בערך M, הסיבוכיות תהיה לפחות M.
    אצלך הסיבוכיות היא M*N (כמובן O של) כי בכל פעם שמפנים חברי מפלגה, בודקים מי המפלגה הגדולה ביותר.
    מכיוון שיש מעט מפלגות (לכל היותר 26) אז זה כנראה ממש סבבה.
    להלן פתרון שלי בסיבוכיות M בלבד: https://bitbucket.org/snippets/Ella10004/ynxGEM
    האלגוריתם עובד ככה:
    1. בודקים מי המפלגה הגדולה (נקרא לה X) ביותר ומי המפלגה השנייה בגודלה (נקרא לה Y).
    2. מפנים את חברי מפלגה X עד שגודלה שווה לגודל של Y.
    3. מפנים את כל החברים שלא כל המפלגות מלבד מפלגות X, Y.
    4. מפנים בזוגות חבר ממפלגה X וחבר ממפלגה Y עד שמסיימים.

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

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

    זה מביא אותי לניסיון ראשון:
    אם יש מספר אי-זוגי, הוצא נציג מהמפלגה הגדולה ביותר. אם יש מספר זוגי, הוצא שני נציגים, אחד מהמפלגה הגדולה ביותר ואחד מהמפלגה הגדולה ביותר אחרי הוצאת הנציג הראשון.

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

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

    זה מביא אותי לניסיון ראשון:
    אם יש מספר אי-זוגי, הוצא נציג מהמפלגה הגדולה ביותר. אם יש מספר זוגי, הוצא שני נציגים, אחד מהמפלגה הגדולה ביותר ואחד מהמפלגה הגדולה ביותר אחרי הוצאת הנציג הראשון.

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

השאר תגובה