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

1. למה חזרות זה כל כך מסובך

אלגוריתם נאיבי לחישוב "כמה ספרות במקום הנכון" ו"כמה ספרות במקום הלא נכון" יכול להיכתב בתור לולאה כפולה:

blacks = 0
whites = 0
for idx1, i in enumerate(str(value)):
    for idx2, j in enumerate(str(other)):
        if i == j:
            if idx1 == idx2:
                blacks += 1
            else:
                whites += 1

כאשר whites מייצג את מספר הספרות במקום הלא נכון, ו blacks את מספר הספרות שנמצאות בדיוק במקום הנכון בין שני מספרים - האחד שמור במשתנה value והשני במשתנה other.

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

2. פיתרון בפייתון שמתמודד גם עם כפילויות

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

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

class Guess:
    def __init__(self, value: int):
        digitgroups = itertools.groupby(
            sorted(list(enumerate(str(value))), key=lambda m: m[1]),
            lambda m: m[1])

        self.value = {
            k: set([i[0] for i in v])
            for k, v in digitgroups
        }

    def compare(self, other: "Guess") -> Result:
        white = 0
        black = 0
        for digit in self.value.keys():
            if digit in other.value:
                intersection = self.value[digit].intersection(other.value[digit])
                black += len(intersection)
                white += min(len(self.value[digit] - intersection), len(other.value[digit] - intersection))

        return Result(white=white, black=black)

ועכשיו ההשוואה נותנת את התוצאה הנכונה:

g1 = Guess(112)
g2 = Guess(221)

# prints: Result(white=2, black=0)
print(g1.compare(g2))

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