שלום אורח התחבר

משחקים עם קלוז'ר: פיתרון Advent Of Code 2021 יום 5

נושאים:יומי

תרגילי Advent Of Code הם המקום המושלם להתאמן על שפת תכנות חדשה, ובמיוחד כזאת שיודעת להתמודד יפה עם נתונים ומניפולציות עליהם. קלוז'ר בהחלט מתאימה להגדרה. את יום 5 הצלחתי לפתור עם טריק פשוט אחד - ועוד קצת קוד מסביבו. הנה הסיפור המלא.

1המשימה ביום 5

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

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

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

2איך לגשת לפיתרון

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

3קוד קלוז'ר

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

(defn fill-points-in-range [start end f]
  (->> (range (min start end) (inc (max start end)))
      (map f)))

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

שאר הקוד יחסית פשוט:

(defn process-line [acc line]
  (let [[x1 y1 x2 y2] 
        (->> line
             (re-seq #"(\d+),(\d+) -> (\d+),(\d+)")
             (first)
             (drop 1)
             (map read-string))]
    (cond
      (= x1 x2) (reduce #(%2 %1)
                        acc
                        (fill-points-in-range y1 y2 (fn [y] #(update %1 [x1 y] (fn [v] (inc (or v 0)))))))
      (= y1 y2) (reduce #(%2 %1)
                        acc
                        (fill-points-in-range x1 x2 (fn [x] #(update %1 [x y1] (fn [v] (inc (or v 0)))))))
      :else acc)))


(def input
  (->> "input.txt"
       (slurp)
       (clojure.string/split-lines)
       (reduce process-line {})))


(pprint (count (filter (fn [[_ v]] (> v 1)) input)))

שימו לב לשורה:

(fill-points-in-range y1 y2 (fn [y] #(update %1 [x1 y] (fn [v] (inc (or v 0))))))

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

אחרי שיש לי את המטריצה מוכנה עם כל הנתונים השורה:

(pprint (count (filter (fn [[_ v]] (> v 1)) input)))

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

4חלק 2

בחלק השני רצינו לטפל גם בקווים אלכסוניים. בשביל זה הוספתי את הפונקציה:

(defn fill-points-in-line [x1 y1 x2 y2 f]
  (conj (map f
             (range x1 x2 (if (> x1 x2) -1 1))
             (range y1 y2 (if (> y1 y2) -1 1)))
        (f x2 y2)))

היא יותר מסובכת מהקווים האופקיים והאנכיים כי הפעם גם ה x וגם ה y משתנים והשינוי צריך להיות בהתאמה. לשמחתי map ב clojure יודעת לקבל כמה טווחים ופשוט מעבירה כמה פרמטרים לפונקציה.

אחרי שסגרנו את הפינה הזאת אפשר לשלב את הפונקציה ב process-line ולהחליף את בלוק ה else שהיה שם ב:

:else (reduce #(%2 %1) acc (fill-points-in-line x1 y1 x2 y2 (fn [x y] #(update %1 [x y] (fn [v] (inc (or v 0))))))))))

והתוכנית המלאה:

(use 'clojure.pprint)

(defn fill-points-in-range [start end f]
  (->> (range (min start end) (inc (max start end)))
      (map f)))

(defn fill-points-in-line [x1 y1 x2 y2 f]
  (conj (map f
             (range x1 x2 (if (> x1 x2) -1 1))
             (range y1 y2 (if (> y1 y2) -1 1)))
        (f x2 y2)))

(defn process-line [acc line]
  (let [[x1 y1 x2 y2] 
        (->> line
             (re-seq #"(\d+),(\d+) -> (\d+),(\d+)")
             (first)
             (drop 1)
             (map read-string))]
    (cond
      (= x1 x2) (reduce #(%2 %1)
                        acc
                        (fill-points-in-range y1 y2 (fn [y] #(update %1 [x1 y] (fn [v] (inc (or v 0)))))))
      (= y1 y2) (reduce #(%2 %1)
                        acc
                        (fill-points-in-range x1 x2 (fn [x] #(update %1 [x y1] (fn [v] (inc (or v 0)))))))
      :else acc)))
      ; :else (reduce #(%2 %1) acc (fill-points-in-line x1 y1 x2 y2 (fn [x y] #(update %1 [x y] (fn [v] (inc (or v 0))))))))))

(def input
  (->> "input.txt"
       (slurp)
       (clojure.string/split-lines)
       (reduce process-line {})))


(pprint (count (filter (fn [[_ v]] (> v 1)) input)))

את התרגיל המקורי תוכלו למצוא בקישור: https://adventofcode.com/2021/day/5

ולנסות לפתור אותו בעצמכם בשפת התכנות האהובה עליכם או לשחק עם פיתרון הקלוז'ר שלי ולהציע שיפורים.

מעדיפים לקרוא מהטלגרם? בקרו אותנו ב:@tocodeil

או הזינו את כתובת המייל וקבלו את הפוסט היומי בכל בוקר אליכם לתיבה:


נהניתם מהפוסט? מוזמנים לשתף ולהגיב