מימוש משחק בול פגיעה חלק ב׳ – טיפול בכפילויות

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

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

למשל, אם הקוד שבחרתי היה –

["red”, “red”, “pink”, “pink”]

והשחקנית השניה ניחשה – 

["red”, “red”, “red”, “pink”]

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

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

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

אז מה הבעיה?

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

def check_guess(code, code_set, guess):
    bul = 0
    pgia = 0
    for i in range(0,len(guess)):
        color = guess[i]
        if color == code[i]:
            bul += 1
        elif color in code_set:
            pgia += 1
    return bul, pgia

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

אני אריץ הדגמה מהירה של העניין – 

code = [“blue”, “red”, “pink”, “purple”]
code_set = {“blue”, “red”, “pink”, “purple”}
guess = [“blue”, “blue”, “blue”, “blue”]

check_guess(code, code_set, guess):
	bul = 0
	pgia = 0
	i = 0
	color = “blue”
	color == code[0] → “blue” == “blue” → True
	bul = 1
	i = 1
	color = “blue”
	color == code[1] → “blue” == “red” → False
	color in code_set → “blue” in {“blue”, “red”, “pink”, “purple”} → True
	pgia = 1
	.
	.
	.
	bul = 1
	pgia = 3

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

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

בואו נתקן את האלגוריתם

הפתרון הראשון שעולה לי לראש הוא להסיר כל צבע שכבר השתמשנו בו מה-code_set. במקרה כזה, אחרי שבול או פגיעה נספרים לצבע מסוים לא נשתמש בהם שוב בטעות.
למשל, בהרצה שעשיתי למעלה, אחרי שגילינו את הבול הראשון הצבע “blue״ היה מוסר מהסט, וכל הניחושים הבאים לא היו נחשבים לפגיעות.

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

def check_guess(code, code_set, guess):
    bul = 0
    pgia = 0
    for i in range(0,len(guess)):
        color = guess[i]
        if color == code[i]:
            bul += 1
		  code_set.pop(color)
        elif color in code_set:
            pgia += 1
		  code_set.pop(color)
    return bul, pgia

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

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

code = [“red”, “blue “pink”, “purple”]
code_set = {“red”, “blue”, “pink”, “purple”}
guess = [“blue”, “blue”, “blue”, “blue”]

check_guess(code, code_set, guess):
	bul = 0
	pgia = 0
	i = 0
	color = “blue”
	color == code[0] → “blue” == “red” → False
	color in code_set → “blue” in {“red”, “blue”, “pink”, “purple”} → True
	pgia = 1
	code_set = {“red”, “pink”, “purple”}
	i = 1
	color = “blue”
	color == code[1] → “blue” == “blue” → True
	bul = 1	
	.
	.
	.
	bul = 1
	pgia = 1

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

יש לי שני רעיונות למימושים שנותנים עדיפות אבסולוטית לבולים על פני פגיעות – 

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

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

אני אשנה את האלגוריתם שלי בהתאם למסקנות – 

def check_guess(code, code_counter, guess):
    bul = 0
    pgia = 0
    for i in range(0,len(guess)):
        color = guess[i]
        if color == code[i]:
            bul += 1
		  decrease_color(code_counter, color)
    for i in range(0,len(guess)):
        color = guess[i]
        if color in code_counter:
            pgia += 1
		  decrease_color(code_counter, color)
 
    return bul, pgia

הידד!

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

פוסטים נוספים בסדרת בול-פגיעה