הנושאים החמים
הנושאים החמים
כמדי שנה, תחרות התכנות העולמית של גוגל - Google Code Jam - מושכת מכל רחבי העולם אלפי מתכנתים בשאיפה ליוקרה, לפרס כספי נאה, לג'וב נחשק או לפחות לטי-שירט המובטח לחמש-מאות המתחרים המובילים אי-שם בשלבים המתקדמים. הכללים פשוטים: בכל סיבוב מוצגות במילים שלוש בעיות תכנות, ויש לפתור כמה שיותר מהן (בלי חשיבות לסדר) בזמן מוגבל. לכל בעיה מצורפים שני קובצי קלט, אחד קטן ואחד גדול, אותם יש להוריד למחשב, להריץ דרך התוכנית ולהעלות בחזרה לאתר התחרות קובצי פלט בתוך ארבע ושמונה דקות, בהתאמה. והטוב מכל: מותר לתכנת בכל שפה וסביבת פיתוח שמתחשק, כל עוד אפשר להוריד ולהתקין אותן בחינם על מחשב סביר.
ביום ראשון לפנות בוקר (שעון ישראל) הסתיים שלב המוקדמות, שנמשך עשרים וארבע שעות. בשלב סינון התחלתי זה, קריטריון המעבר הוא פתרון של לפחות קובץ קטן אחד וקובץ גדול אחד. להלן הבעיות שהוצגו וניתוחן, בהתבסס בעיקר על ההתרשמות שלי וקצת על ההערות שניתנו בסיום השלב על ידי צוות התחרות. אגב, למטרות בהירות וקיצור, הניסוחים שיוצגו כאן אינם זהים בהכרח למקוריים. <!-- RELEVANTI_ARTICLE_END -->
בהתחלה, כל המתגים במצב OFF. עם מחיאת הכף הראשונה, הראשון עובר למצב ON. במחיאה השניה, המתג השני עובר ל-ON, אבל הראשון חוזר ל-OFF. במחיאה השלישית, המתג השני נשאר ON (מכיוון שהראשון היה OFF ולא סיפק לו חשמל) אך הראשון חוזר להיות ON. במחיאה הרביעית, המתג השלישי עובר ל-ON, ושני הראשונים חוזרים ל-OFF... וכך הלאה. לסוף שרשרת המתגים מחוברת נורה, והשאלה היא, בהינתן N מתגים ו-K מחיאות כף, האם הנורה תהיה דלוקה או כבויה.
<!-- RELEVANTI_ARTICLE_END -->
המחשה של מצבי המתגים בשאלה 1 (איור: עידו גנדל)
<!-- RELEVANTI_ARTICLE_START --> הפתרון הופך לפשוט ברגע שמבינים שהמתגים הללו מתנהגים בדיוק כמו ספרות במספר בינרי שגדל ב-1 עם כל מחיאת כף (בתמונה משמאל). מכאן, הפתרון מובן מאליו - אם N הספרות הבינריות האחרונות של K הן כולן 1, הנורה תדלוק, אחרת היא תהיה כבויה. כ-85% מהמתחרים שניסו לפתור את השאלה הזו הגיעו לתשובה הנכונה.
<!-- RELEVANTI_ARTICLE_END -->
כל אדם משלם שקל תמורת כל נסיעה שהוא משתתף בה. בהינתן K, R ו-N וכן מספר האנשים בכל קבוצה על פי סדרן בתור, כמה שקלים בדיוק יצטברו בקופה בסוף היום?
לכאורה מדובר בשאלה טכנית מאד - פשוט מכניסים את מספרי האנשים בקבוצות למערך ורצים עליו במעגל, ממלאים כל פעם את רכבת ההרים ככל שניתן וסופרים כמה אנשים נסעו. פתרון כזה עובד עבור הקובץ הקטן, אך - כמו תמיד בתחרות הזו - יש גם קונץ: בקובץ הגדול, מספר הנסיעות, המקומות והקבוצות שמוגדר עשוי להיות גדול עד כדי כך שהחישובים יארכו שעות גם במחשב זריז ביותר. קונץ זה משתקף היטב באחוז התשובות הנכונות: 95% מבין העונים עבור הקובץ הקטן, אבל רק 40% עבור הגדול. הדרך המהירה יותר לפתרון היא לא לעבור על המערך במעגל שוב ושוב בלי מחשבה, אלא לנסות לאתר נקודה שבה סדר הקבוצות חוזר על עצמו (תחילת המערך או אפילו נקודה אחרת כלשהי שכבר היינו בה). אם מגלים מעגל פנימי שכזה, אפשר להכפיל את מספר הנוסעים שבו במספר הנסיעות הכולל חלקי מספר הנסיעות שבמעגל ולחסוך בכך המון חישובים מיותרים. גם עם אופטימיזציה כזו, אגב, עשויות להידרש דקות ספורות להשלמת החישוב: ייתכן שמתחרים התייאשו באמצע ועצרו את התוכנה כדי לנסות למצוא ברגע האחרון בעיה שלא היתה שם, וכך עברו את מגבלת הזמן.
<!-- RELEVANTI_ARTICLE_END -->
גם בעזרת משתני BigInt אי אפשר לפתור את החידה בזמן סביר בלי להכיר את האלגוריתם של אוקלידס למציאת הגורם המשותף הגדול ביותר - או להמציא אותו מחדש לבד. נשאלת השאלה, האם נכון להציג שאלות מתמטיות "טהורות" שכאלה בתחרות תכנות? היכן בעצם הגבול בין שאלות שכאלה לבין שאלות "תכנותיות", אם הוא קיים בכלל?
<!-- RELEVANTI_ARTICLE_END -->
שמונת-אלפים חמש-מאות עשרים ושלושה מתמודדים עברו את הסף והתקדמו לשלב הבא, שיתקיים בשלושה מחזורים ביום שבת וראשון, ה-22 וה-23 בחודש. התחרות כבר סגורה, כמובן, למתמודדים חדשים - אך אפשר להתנסות בזמנכם הפנוי בפתרון הבעיות של השלבים שהסתיימו באתר התחרות.
(עידו גנדל, נענע)
ביום ראשון לפנות בוקר (שעון ישראל) הסתיים שלב המוקדמות, שנמשך עשרים וארבע שעות. בשלב סינון התחלתי זה, קריטריון המעבר הוא פתרון של לפחות קובץ קטן אחד וקובץ גדול אחד. להלן הבעיות שהוצגו וניתוחן, בהתבסס בעיקר על ההתרשמות שלי וקצת על ההערות שניתנו בסיום השלב על ידי צוות התחרות. אגב, למטרות בהירות וקיצור, הניסוחים שיוצגו כאן אינם זהים בהכרח למקוריים. <!-- RELEVANTI_ARTICLE_END -->
1. שרשרת המתגים
<!-- RELEVANTI_ARTICLE_START --> אנו מתחילים בבעיה קלאסית של ראיונות עבודה למתכנתים: לשקע החשמל מחוברים, בשרשרת, מתגים חשמליים דו-מצביים (ON ו-OFF) שמעבירים חשמל הלאה רק כאשר הם במצב ON. כל מתג עובר ממצב למצב כשהוא קולט צליל של מחיאת כף, אך לשם כך הוא חייב לקבל אספקת חשמל. כלומר, המתג הראשון בשרשרת (זה שצמוד לשקע שבקיר) מקבל אספקת חשמל שוטפת ולכן יעבור ממצב למצב עם כל מחיאת כף. השני בשרשרת, שמחובר אליו, ישנה מצב בעת מחיאת כף רק אם הראשון היה באותו זמן במצב ON. השלישי יחליף מצב רק אם שני הראשונים הם ON, וכן הלאה.
בהתחלה, כל המתגים במצב OFF. עם מחיאת הכף הראשונה, הראשון עובר למצב ON. במחיאה השניה, המתג השני עובר ל-ON, אבל הראשון חוזר ל-OFF. במחיאה השלישית, המתג השני נשאר ON (מכיוון שהראשון היה OFF ולא סיפק לו חשמל) אך הראשון חוזר להיות ON. במחיאה הרביעית, המתג השלישי עובר ל-ON, ושני הראשונים חוזרים ל-OFF... וכך הלאה. לסוף שרשרת המתגים מחוברת נורה, והשאלה היא, בהינתן N מתגים ו-K מחיאות כף, האם הנורה תהיה דלוקה או כבויה.
<!-- RELEVANTI_ARTICLE_END -->
<!-- RELEVANTI_ARTICLE_START --> הפתרון הופך לפשוט ברגע שמבינים שהמתגים הללו מתנהגים בדיוק כמו ספרות במספר בינרי שגדל ב-1 עם כל מחיאת כף (בתמונה משמאל). מכאן, הפתרון מובן מאליו - אם N הספרות הבינריות האחרונות של K הן כולן 1, הנורה תדלוק, אחרת היא תהיה כבויה. כ-85% מהמתחרים שניסו לפתור את השאלה הזו הגיעו לתשובה הנכונה.
<!-- RELEVANTI_ARTICLE_END -->
3. בתור לרכבת ההרים
<!-- RELEVANTI_ARTICLE_START --> השאלה השלישית (לא לדאוג, לשאלה מס' 2 נגיע בהמשך) עסקה ברכבת הרים בעלת K מקומות ישיבה שנוסעת R פעמים ביום. אל התור נכנסות בתחילת היום N קבוצות של אנשים, כל קבוצה בגודל 1 עד K, וכל האנשים בקבוצה מסוימת מוכנים לנסוע אך ורק ביחד. למשל, אם יש 10 מקומות ישיבה ומספר האנשים בשלוש הקבוצות שמגיעות הוא שמונה, שלושה ואחד, תעלה לנסיעה הראשונה הקבוצה הראשונה בלבד ויישארו שני מקומות פנויים. בסיבוב הבא יעלו שתי הקבוצות הבאות (ארבעה נוסעים). כל קבוצה שמסיימת את הנסיעה עוברת בחזרה לסוף התור.
כל אדם משלם שקל תמורת כל נסיעה שהוא משתתף בה. בהינתן K, R ו-N וכן מספר האנשים בכל קבוצה על פי סדרן בתור, כמה שקלים בדיוק יצטברו בקופה בסוף היום?
לכאורה מדובר בשאלה טכנית מאד - פשוט מכניסים את מספרי האנשים בקבוצות למערך ורצים עליו במעגל, ממלאים כל פעם את רכבת ההרים ככל שניתן וסופרים כמה אנשים נסעו. פתרון כזה עובד עבור הקובץ הקטן, אך - כמו תמיד בתחרות הזו - יש גם קונץ: בקובץ הגדול, מספר הנסיעות, המקומות והקבוצות שמוגדר עשוי להיות גדול עד כדי כך שהחישובים יארכו שעות גם במחשב זריז ביותר. קונץ זה משתקף היטב באחוז התשובות הנכונות: 95% מבין העונים עבור הקובץ הקטן, אבל רק 40% עבור הגדול. הדרך המהירה יותר לפתרון היא לא לעבור על המערך במעגל שוב ושוב בלי מחשבה, אלא לנסות לאתר נקודה שבה סדר הקבוצות חוזר על עצמו (תחילת המערך או אפילו נקודה אחרת כלשהי שכבר היינו בה). אם מגלים מעגל פנימי שכזה, אפשר להכפיל את מספר הנוסעים שבו במספר הנסיעות הכולל חלקי מספר הנסיעות שבמעגל ולחסוך בכך המון חישובים מיותרים. גם עם אופטימיזציה כזו, אגב, עשויות להידרש דקות ספורות להשלמת החישוב: ייתכן שמתחרים התייאשו באמצע ועצרו את התוכנה כדי לנסות למצוא ברגע האחרון בעיה שלא היתה שם, וכך עברו את מגבלת הזמן.
<!-- RELEVANTI_ARTICLE_END -->
2. גורם משותף, מספרים גדולים
<!-- RELEVANTI_ARTICLE_START --> הבעיה הנוספת והקשה ביותר (מספר המתחרים שניסו בכלל להגיש פתרון היה כמחצית מבשאלות האחרות) למעשה לא היתה בעיית תכנות כלל אלא שאלה במתמטיקה. בהינתן שלושה מספרים שונים, שלמים וחיוביים, יש למצוא את המספר הנמוך ביותר שכאשר מוסיפים אותו לשלושתם, מתקבל הגורם המשותף הגדול ביותר. טריק נוסף היו המספרים עצמם, שהיו בחלקם בעלי עשרות או מאות ספרות. כפי שצוין בדיבעד, היה כאן הכרח להשתמש במשתנים מטיפוס BigInt, שכלל אינו קיים בשפות תכנות רבות ויש צורך לכתוב אותו לבד או להשתמש בספריות מיוחדות.
גם בעזרת משתני BigInt אי אפשר לפתור את החידה בזמן סביר בלי להכיר את האלגוריתם של אוקלידס למציאת הגורם המשותף הגדול ביותר - או להמציא אותו מחדש לבד. נשאלת השאלה, האם נכון להציג שאלות מתמטיות "טהורות" שכאלה בתחרות תכנות? היכן בעצם הגבול בין שאלות שכאלה לבין שאלות "תכנותיות", אם הוא קיים בכלל?
<!-- RELEVANTI_ARTICLE_END -->
ומה הלאה
<!-- RELEVANTI_ARTICLE_START --> הטיפוס BigInt, כך נאמר בסיום שלב המוקדמות, הופיע כאן בפעם הראשונה ב-Codejam ויופיע גם בהמשך התחרות. זוהי התפתחות מעניינת מבחינה "פוליטית": הרי אפשר להמציא שאלות שלא ישתמשו במספרים גדולים שכאלה, אז למה להקשות את החיים על מתכנתים בשפות הוותיקות יותר כמו C++, ובמיוחד כשזו השפה השכיחה ביותר בקרב המשתתפים בתחרות (לפי נתוני 2009)?
שמונת-אלפים חמש-מאות עשרים ושלושה מתמודדים עברו את הסף והתקדמו לשלב הבא, שיתקיים בשלושה מחזורים ביום שבת וראשון, ה-22 וה-23 בחודש. התחרות כבר סגורה, כמובן, למתמודדים חדשים - אך אפשר להתנסות בזמנכם הפנוי בפתרון הבעיות של השלבים שהסתיימו באתר התחרות.
(עידו גנדל, נענע)
