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

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

מעשרוני לרומי

הייצוג הרומי מבוסס על שבע אותיות שמייצגות מספרים שונים:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

וברמה העקרונית, פשוט מצרפים את האותיות האלה, מבעלת הערך הגדול אל הקטן (משמאל לימין) כדי "לצבור" את המספר העשרוני המקביל. למשל, מאתיים זה פעמיים מאה, כלומר CC, שש זה VI ואילו 206 זה CCVI.

הבעיה היא שישנם כלל נוסף, שבו הסדר משתנה ואיתו המשמעות. כאשר מספר היחידות (של אחדות, עשרות או מאות), הוא אחד-לפני-האות-הבאה, כלומר 4 או 9, אנחנו לא מצרפים את היחידות כרגיל (למעט יוצא הדופן הנדיר של IIII, שהוזכר בתגובות של החידה ושאנחנו מתעלמים ממנו לצורך העניין), אלא שמים את האות הבאה – ולפניה, מצד שמאל, יחידה אחת. כך למשל ארבעים זה לא XXXX אלא XL, תשעים זה לא LXXXX אלא XC, ארבע-מאות זה לא CCCC אלא CD וכן הלאה.

הכלל הזה אינו כלל רשמי (הנה עוד דרך להסתכל על אופן הבניה של מספרים רומיים), אך הוא יכול לתת כיוון ראשוני לפתרון. אחרי שניסיתי קצת לחשוב על אלגוריתם נוח וקצר שיבצע את כל זה, ולא הצלחתי, בחרתי באופציה מתחכמת: תבניות. הגדרתי מערך של עשר מחרוזות קצרות, אחת עבור כל ספרה (0-9), כשכל אחת מהן מייצגת את האותיות ואת אופן השילוב הרצויים עבור הספרה הספציפית הזו. במחרוזות אלה, התו "0" מייצג את היחידות הנוכחיות, "1" את האות הבאה בתור, ו-"2" מייצג את האות הבאה אחריה.

כך למשל, המחרוזת שתואמת ל-3 היא "000". אם אני עובד באחדות, שסימנן הרומי I, אז שלוש אחדות יומרו פשוט בהתאם למחרוזת ל-III. המחרוזת שתואמת ל-4 היא "01", אז אם אני צריך להמיר את המספר 4, אני אקח את המחרוזת ואמיר את התווים שבה לפי הכלל שהוזכר: IV. אם המספר להמרה הוא 90, מה שאומר שאני עובד עכשיו עם עשרות, אקח את המחרוזת התואמת ל-9 (שהיא "02") ואמיר בתוכה לאותיות התואמות: XC. כל מה שנותר הוא לחלק את המספר העשרוני לאחדות, עשרות, מאות ואלפים, להמיר כל אחד מהם לפי המחרוזות ולצרף למחרוזת אחת גדולה.

מרומי לעשרוני

ההמרה בכיוון ההפוך פשוטה יותר. הרי האותיות כולן לפניי, ואני יודע כמה "שווה" כל אחת מהן. המכשול היחיד הוא אותם מקרים בהם אות "קטנה" מופיעה לפני אות "גדולה", כגון ב-IV או CM. אז אם אני סורק את המספר הרומי מימין לשמאל וסוכם את ערכי האותיות, כאשר אני נתקל באות "קטנה" יותר מזו שכבר הייתי בה, אני צריך פשוט להפחית את הערך שלה מהסכום הכללי. לדוגמה, במספר IX, אני מתחיל מה-X שזה עשר, נתקל באות הקטנה יותר I – ולכן מפחית 1 מהסכום ומקבל את התשובה הנכונה 9.

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