פיתרון Advent Of Code 2015 יום 3 ב Ruby

22/05/2021

בהתקף נוסטלגיה החלטתי להסתכל על קצת חידות ישנות של Advent Of Code ונתקלתי בחידת היום השלישי של 2015 שפשוט צעקה רובי וגם לימדה אותי משהו על שימוש חוזר בקוד.

1. החידה - חלק 1

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

לדוגמה עבור דף הוראות שנראה כך:

^>v<

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

בהינתן דף הוראות עיזרו לסנטה לגלות בכמה בתים שונים הוא הולך לבקר.

2. הפיתרון

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

בקוד רובי זה נראה כך:

MOVEMENT = {
  ">" => 1,
  "<" => -1,
  "^" => 1i,
  "v" => -1i
}.freeze

def all_houses(path)
  path
    .chars
    .map { |c| MOVEMENT[c] }
    .inject([0 + 0i]) { |acc, val| acc << acc[-1] + val }
end

def unique_houses(path)
  all_houses(path)
    .uniq
    .size
end

# part 1
input = File.read("input.txt").strip
puts unique_houses(input)

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

3. חלק 2

בחלק השני של החידה סנטה מקבל רובוט עוזר. הם מחלקים את דף ההוראות כך שסנטה מקבל את ההוראות במקומות האי-זוגיים והעוזר את ההוראות במקומות הזוגיים. עכשיו אותו דף הוראות ^>v< יגרום לסנטה ולעוזר שלו לבקר בסך הכל ב-3 בתים: סנטה ילך בית אחד צפונה ואחד דרומה, והעוזר ילך בית אחד מזרחה ואז צעד אחד חזרה מערבה.

יחד עם העוזר - בכמה בתים שונים ביקרו סנטה והרובוט?

4. פיתרון חלק 2

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

santa, robot = input.chars.partition.each_with_index {|_, i| i.even? }

הבעיה שעכשיו במשתנים santa ו robot יש לנו מערכים במקום מחרוזות, ולכן אי אפשר לשלוח אותם לפונקציה all_houses שיצרנו קודם.

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

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

# part 2
santa, robot = input.chars.partition.each_with_index {|_, i| i.even? }.map(&:join)
puts (all_houses(santa) + all_houses(robot)).uniq.size

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