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

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

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

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

להמשיך לקרוא אתגר התכנות 5: הרפתקת טקסט! ←

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

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

להמשיך לקרוא אתגר התכנות 4: מיון ערמה ←

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

אז יש לנו קוף שמטפס על רשת שתי-וערב של חבלים. כל צומת (מפגש בין שני חבלים) מסומן על ידי שני מספרים שלמים – קואורדינטות X ו-Y. הקוף מתחיל בצומת 0,0 ויכול לנוע בכל פעם צעד אחד בלבד לכיוון אחד בלבד – כלומר לעבור לצומת עם X גדול ב-1 מהקודם, או עם X קטן ב-1 מהקודם, או עם Y גדול ב-1 מהקודם, או עם Y קטן ב-1 מהקודם (גם מספרים שליליים מותרים). לא ניתן לנוע באלכסון.

יש מגבלה נוספת וחשובה מאד: הקוף אינו יכול לנוע לצומת שסכום הספרות של הקואורדינטות שלו גדול מ-19. לדוגמה, הוא לעולם לא יוכל להגיע לצומת 96,51 כי 9+6+5+1 יותר גדול מ-19. במקרה של קואורדינטה שלילית, אנחנו פשוט מתעלמים מהסימן ומחשבים את הסכום כאילו היא היתה חיובית.

והנה השאלה: כאמור, הקוף מתחיל בצומת 0,0. לכמה צמתים שונים, כולל זה ההתחלתי, הוא יכול להגיע בסך הכל?

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

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

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

A[n] = n

אנחנו נרצה לראות את n מוצג על המסך. איך עושים את זה – ואיך עושים את זה עוד יותר טוב?

להמשיך לקרוא אתגר התכנות, תרגיל 2 ←

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

להמשיך לקרוא MMXIII: אתגר התכנות מתחיל ←

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

להמשיך לקרוא נערת האמצע של הגרפיקה הממוחשבת ←

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

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

להמשיך לקרוא טיימרים בארדואינו: מבוא ←

המעגל המשולב CD4017BE הוא ג'וק מוזר. בזמן שחבריו מריצים קוד, מפעילים פרוטוקולים מתוחכמים, מנהלים מתחים וזרמים או לפחות מבצעים פעולות לוגיות פונדמנטליות, הג'וק הזה – שמכונה Decade Counter ("מונה עשרות") – פשוט סופר עד עשר. ליתר דיוק, יש לו כניסת שעון אחת ועשר יציאות, שממוספרות 0 עד 9, ובכל פעם שהמתח בכניסת השעון עולה, הג'וק מוציא מתח ביציאה הבאה בתור, ורק בה. קצת כמו להסתכל רק על ספרת האחדות של מספר שעולה ועולה בלי סוף. למה זה טוב?

להמשיך לקרוא כמה פעמים ספרת עד עשר (עם ג'וק) ←