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

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

"נתונה מחרוזת (באורך 2 לפחות) שהתווים בה הם בתחום a-z. חובה להסיר תו אחד, ואחד בלבד, מהמחרוזת. האם ניתן לעשות זאת כך שמספר המופעים של כל ערך בתווים הנותרים יהיה זהה?"

נניח שקיבלנו את המחרוזת "xxyz". התשובה היא "כן", כי אם נבחר להסיר את התו הראשון או השני – משמאל כמובן – נקבל מחרוזת שכל אחד מערכי התווים בה (x, y, z) מופיע בדיוק פעם אחת. לעומת זאת, עבור המחרוזת "qqww" התשובה היא "לא", כי לא משנה איזה תו נסיר, יישאר אחד כמוהו ושניים עם הערך השני.

רוצים לנסות לפתור בלי רמזים? זה הזמן…

על סמך הדוגמאות שהוצגו, מישהו עלול לקפוץ למסקנות ולהציע את האלגוריתם הבא: "נמצא תו עם מספר מופעים מקסימלי, נסיר מופיע אחד שלו ונבדוק אם כל התווים שנשארו מופיעים אותו מספר פעמים." אבל זה לא יעבוד. האתר, שבנדיבות לא-רגילה גם מראה את הקלט שגרם לתוצאה שגויה, יציג בפנינו משהו כמו "xxyzz". האלגוריתם הנ"ל יטען שאין פתרון, אבל אם נמחק את y, שמספר המופעים שלו הוא דווקא המינימלי, נקבל מחרוזת עם שני x ושני z, שכן עומדת בדרישות.

רוצים לפתור עכשיו? שאר הפוסט יחכה…

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

בשלב זה זנחתי את הגישה הנינוחה שאני מאמץ בדרך כלל מול שאלות קלות, והתחלתי לחשוב לעומק וברצינות על כל מקרי הקצה ואיך לבדוק אותם. עוד כמה ניסיונות שגויים – מקצתם לוגיים, השאר שגיאות הקלדה טפשיות – והשאלה נפתרה. רק אז הרשיתי לעצמי להסתכל על תגובות ופתרונות של מתכנתים אחרים באתר. רבים טענו שהשאלה צריכה להיות בקטגוריה "בינוני" ולא "קל", וחלק גם פתרו אותה brute-force, כלומר בדקו את כל אפשרויות המחיקה בזו אחר זו וספרו את התווים הנותרים בכל אחת, עד שהגיעו לתשובה (וזה התקבל במערכת ולא גרם לחריגה מהזמן המוקצב, כי אורך המחרוזת המרבי הוגבל ל-100 תווים). למען הסר ספק, יש פתרון אחר, הרבה יותר מהיר ולא עד כדי כך מורכב.

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

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

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