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

1. החידה

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

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

לדוגמה אם במטוס יש 128 שורות אז ההוראות FBFBBFF יובילו אותנו כך:

1. ה F הראשון שולח אותנו לקידמת המטוס כלומר אנחנו יודעים שצריך לשבת בין שורה 0 ל 63.
2. ה B שאחריו לוקח אותנו לחלק האחורי בחצי המטוס שלנו, כלומר צריך לשבת בין שורה 32 ל 63.
3. ה F הבא בתור אומר שצריך ללכת לחלק הקדמי של חצי המטוס שלנו, כלומר בין שורה 32 ל 47.
4. ה B הבא שולח אותנו לחלק האחורי של חצי המטוס שלנו, כלומר בין שורה 40 ל 47.
5. ה B הבא מצמצם את הטווח לשורות 44 עד 47.
6. ה F הבא מצמצם את הטווח לשורות 44 עד 45.
7. וה F האחרון שולח אותנו למקום בשורה 44.

אפשר רק לדמיין את הריבים והצעקות כשאנשים ישבו במקומות אחד של השני וינסו להסביר שזה בעצם המקום שלהם. אגב בשביל להוסיף לבלבול גם מספר הכסא בתוך השורה מקודד באותו האופן הפעם עם האותיות L ו R כש L אומרת ללכת שמאלה לחלק התחתון של המספרים ו R ימינה לחלק העליון (המושבים בכל שורה ממוספרים בין 0 ל 7).

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

2. הטריק

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

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

1. שורה היא מספר בייצוג בינארי בין 0 ל 127
2. כל F מייצג את הסיפרה 0
3. כל B מייצג את הסיפרה 1

הקוד מהדוגמה מייצג את המספר הבינארי 0101100 שערכו 44.

3. פיתרון ברובי

נכתוב את הפונקציות הבאות לפיתרון התרגיל בשפת רובי:

def row(seat)
  seat.gsub("F", "0").gsub("B", "1").to_i(2)
end

def column(seat)
  seat.gsub("L", "0").gsub("R", "1").to_i(2)
end

def seat_id(seat)
  row(seat[0..6]) * 8 + column(seat[7..9])
end

הפונקציה row מקבלת מחרוזת, הופכת את ה F-ים וה B-ים לספרות בינאריות ואז מתרגמת את המחרוזת שהתקבלה למספר לפי בסיס 2. הפונקציה column עושה את אותו דבר עם L ו R, והפונקציה seat_id מקבלת כרטיס טיסה מלא, לוקחת את האותיות של השורה ל row, את האותיות של העמודה ל column ומחברת את הערכים כדי לקבל את המזהה שאנחנו מחפשים.

בהנחה שיש לכם רשימת כרטיסי טיסה בתיקיית input בקובץ day5.txt הקוד הבא יקרא את כולם וידפיס את המזהה הגדול ביותר:

lines = File.read("input/day5.txt").each_line
max_id = lines.map {|line| seat_id(line) }.max
puts max_id

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

https://adventofcode.com/2020/day/5

וכמובן אם אתם אוהבים חידות מהסוג הזה אריק ימשיך לפרסם אותן כל החודש, עם חידה חדשה באתר כל יום בשבע בבוקר שעון ישראל. לרשימת כל החידות בקרו ב Advent Of Code 2020.