בחזרה סמלית למקורות של הבלוג, אנחנו מתחילים סדרה חדשה של חידות, שאלות ואתגרי תכנות. השאלה הראשונה מגיעה היישר משלב המוקדמות של תחרות Google Code Jam בשנת 2021. מוכנים?

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

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

אז החלטתי לחזור בצורה נחושה ומסודרת לעולם של חידות התכנות הקלאסיות – שיכולות להגיע מתחרויות, אתרי חידות, ספרי תרגול וכו' – ולשתף אתכם בתהליך. השפות שבהן אתמקד הן C (עדיין ברירת המחדל בעולם ה-8-ביט) ופייתון, שנראית לי הבחירה ההגיונית כיום לפיתוח יישומי desktop מהסוג שאני, לפחות, צריך לפעמים.

אוקיי, אז בלי יותר מדי דיבורים, נקפוץ ישר למים עם החידה הראשונה, Moons and Umbrellas, שהגיעה כאמור מ-Google Code Jam 2021. הרמה אמורה להיות קלה. אני ממליץ כמובן בחום לקרוא את המקור, הנה בכל אופן תקציר: אמן מצייר רצפים של סהרונים ומטריות, שמזכירים גרפית את האותיות C ו-J. מסתבר שלמישהו אחר יש זכויות יוצרים על הצירופים JC ו-CJ, כך שעל כל מופע של כל צירוף כזה ברצף מסוים, האמן יצטרך לשלם תמלוגים. אנחנו מקבלים כקלט את סכומי התשלום על כל CJ וכל JC, וכן מחרוזת עם רצף אחד, שיכול להיות שחלק ממנו טרם צויר, לדוגמה "CJ??J". אנחנו צריכים לחשב מהו סכום התמלוגים המינימלי שהאמן יצטרך לשלם על הרצף הזה, בהינתן שהוא יכול לבחור אם לשים במקום כל סימן שאלה C או J.

אם אתם רוצים לפתור לבד, זה הזמן לעצור ולנסות.

שנתחיל?

הרפלקס המיידי שלי, בלי לחשוב בכלל, היה לעבור (ברקורסיה מן הסתם) על כל האפשרויות: למלא את סימני השאלה, אם יש כאלה, בכל צירוף שהוא, לסכום את התמלוגים לכל אחד ולבחור את המינימום. זהו רעיון גרוע להדהים. מה אם יש במחרוזת 32 סימני שאלה? התוכנית שלי תעבור על 4,294,967,296 אפשרויות? אז בואו נעצור ונחשוב ברצינות.

אם נסתכל על כל זוג סמלים ברצף שלם, יש לנו בעצם רק ארבע אפשרויות: CC, CJ, JC או JJ. רק על שתי הראשונות צריך לשלם. מה מאפיין אותן, לעומת שני האחרונות? שינוי. התווים שונים זה מזה. מכאן אפשר, עדיין בלי לחשוב בכלל על אלגוריתמים, לזהות כיוון שנראה מאוד מבטיח: ככל שיהיו פחות שינויים לאורך הרצף, כך הסכום לתשלום יהיה קטן יותר.

איך מבטיחים מינימום שינויים? פשוט מאוד, לא משנים. אם יש במחרוזת שלנו, נניח, C ואחריו שלושה סימני שאלה, נשנה את כל השלושה ל-C. שום שינוי מ-C ל-J או להיפך. פשוט, נכון? מחרוזת אחרת אולי תכפה שינויים בגלל מה שכבר קיים בה (כמו "C?J" – מה שלא נעשה, חייב להיות שינוי אחד מ-C ל-J), אבל היא לא יכולה להכריח אותנו להוסיף שינויים.

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

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

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

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