רובוט חכם בתרגול לשחקים: איך קוראים הוראות בלי לטעות

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

מה בעצם בודקת שאלת רובוט חכם

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

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

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

אוצר הפקודות: תשע משפחות בשני ניסוחים

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

הנושא בשחקים כולל 90 שאלות, שלושים בכל רמת קושי. ברמה הקלה אין אף לולאה, ברמה הבינונית יש לולאה ב-26 שאלות מתוך 30, וברמה הקשה ב-27 מתוך 30, ובחלקן לולאה בתוך לולאה. הנושא בכלל חמ"ן כולל 45 שאלות, ו-42 מהן כוללות לולאה.

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

אותן מילים, ספר חוקים אחר

אחד ההבדלים הוא הכיוון: בשחקים pop מעבירה כדור מ-b ל-a, ובכלל חמ"ן מ-a ל-b, ולכן אותה שורה נותנת שתי תוצאות שונות. לכן קוראים קודם את ספר החוקים של הנושא ורק אחר כך את התוכנית. בכל ארבע הדוגמאות שבהמשך כל סל מחזיק כדורים שלמים וכל כדור נספר כ-1.

1. setb 8
2. set 4
3. popb
4. clear
5. showb

הפתרון: 9. אחרי השורות הראשונות b=8 ו-a=4. popb מעבירה כדור מ-a ל-b, ולכן a=3 ו-b=9. clear מרוקנת את a ואינה נוגעת ב-b, ו-showb מציגה 9. התשובה 12 היא תוצאה של ספר החוקים האחר: אם popb מעבירה מ-b ל-a (b=7, a=5) ו-clear מעבירה את כל כדורי a אל b, מקבלים 12. התשובה 7 היא של מי שהפך את הכיוון של popb אבל השאיר ל-clear את האיפוס, בלי להעביר ממנו כדורים. התשובה 8 היא של מי שדילג על popb.

מה מוצג ומה נשאר בסל

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

1. set 5
2. loop 3 {
3.   show
4.   mult 3
5.   sub 2
6. }

הפתרון: 37. בסיבוב הראשון מוצג 5, ואחריו a הופך ל-15 ואז ל-13. בסיבוב השני מוצג 13, ואחריו a הופך ל-39 ואז ל-37. בסיבוב השלישי מוצג 37, ו-a הופך ל-111 ואז ל-109. הערך הסופי של a הוא 109, אבל הוא אף פעם לא הוצג. התשובה 111 היא ערך ביניים של הסיבוב האחרון, והתשובה 13 היא של מי שספר רק שני סיבובים.

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

לולאה בתוך לולאה: סופרים הרצות, לא שורות

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

1. set 7
2. setb 1
3. loop 2 {
4.   loop 3 {
5.     addb 3
6.   }
7.   sub 3
8. }
9. move
10. show

הפתרון: 20. הפנימית מוסיפה 3 ל-b שלוש פעמים, כלומר 9 בכל סיבוב חיצוני, ושני סיבובים מוסיפים 18 על הכדור שכבר היה ב-b, כך ש-b=19. הפקודה sub 3 רצה פעם אחת בכל סיבוב חיצוני, פעמיים, ולכן a=1. move מוסיפה את 19 הכדורים של b לכדור שנשאר ב-a, ומתקבל 20. התשובה 26 היא של מי ששכח את sub, ו-17 של מי שחיבר את מספרי הסיבובים, 2 ועוד 3, במקום להכפיל אותם.

כשחסר מספר: עובדים אחורה

כשהשאלה מבקשת מספר שיחליף סימן שאלה, לא חייבים לנסות כל תשובה. מתחילים מהתוצאה ומבטלים את הצעדים בסדר הפוך, פעולה הפוכה בכל שלב, ואז בודקים קדימה את ההצבה שקיבלתם. בשחקים יש 14 שאלות עם סימן שאלה מתוך 90, ובכלל חמ"ן יש 13 שאלות עם סימן שאלה או x בתוך התוכנית.

1. set ?
2. loop 3 {
3.   mult 3
4.   sub 2
5. }
6. show

הפתרון: 7. סיבוב אחד כופל ב-3 ומחסיר 2, ולכן מבטלים אותו בהוספת 2 ואחריה חלוקה ב-3. מ-163 מגיעים ל-165 ול-55, משם ל-57 ול-19, ומשם ל-21 ול-7. שלושה סיבובים בוטלו, ו-7 הוא הערך ההתחלתי. בדיקה קדימה: 7, אחר כך 19, 55 ו-163. התשובות האחרות הן החלקה של שלוש טעויות: ביטול ארבעה סיבובים (3), התעלמות מהכפל (169) והתעלמות מ-sub 2 (6, שנותן 136 בבדיקה קדימה).

איך מתרגלים: טבלת מעקב ושלב אחרי שלב

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

1. בדקו באיזה נושא אתם, וזכרו את הכיוון של pop ושל move ואת מה שהפקודה clear עושה.
2. כתבו את הערכים ההתחלתיים של a ושל b בשורה הראשונה של הטבלה.
3. בצעו שורה אחת בכל פעם, ובלולאה רשמו כל סיבוב בנפרד עד שהדפוס ברור.
4. רק כשכל הסיבובים זהים מותר לקצר ולהכפיל, ובדקו את הקיצור על סיבוב אחד.
5. קראו שוב את השאלה: האם מבקשים את מה שהוצג, או את מה שנשאר בסל?

אפשר להתחיל בנושא רובוט חכם בשחקים חבצלות, ולעבור אחר כך לרובוט חכם בכלל חמ"ן, שבו שיעור השאלות עם לולאה מקוננת גבוה יותר (18 מתוך 45, מול 10 מתוך 90 בשחקים), ויש שאלות עם x. שש שאלות מדגימות מכמה משפחות תמצאו במאמר מבחן שחקים לדוגמה, שכולל גם שאלת רובוט עם תוכנית אחרת מאלה כאן.