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

1. האתגר היומי

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

ספר הוראות לדוגמא נראה כך:

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

בצד שמאל אנחנו רואים את החומר שצריך ובצד ימין את החומר שנוצר ממנו. כך בשביל לבנות יחידת דלק אנחנו צריכים E אחד ושבעה A-ים. אפשר לייצר עשרה A-ים בעזרת 10 יחידות של ORE. בשביל ה E אנחנו צריכים D אחד ועוד שיבעה A-ים, וכך הלאה לפי המתכון. חומר הגלם הבסיסי ביותר הוא ORE וממנו אפשר לייצר את כל שאר המוצרים, וזה גם החומר שנמצא בשפע על שבתאי. השאלה שאנחנו צריכים לפתור היא כמה ORE עלינו לחצוב כדי שנוכל לבנות יחידת דלק אחת.

בספר ההוראות שבדוגמא אנחנו צריכים 31 יחידות של ORE בשביל יחידת דלק. אנחנו משתמשים ב 30 יחידות כדי לבנות 30 יחידות של A, ועוד יחידה אחת כדי לבנות את B. בעזרת ה A-ים שבנינו נוכל לבנות את C, D ו E בהתאמה עד שנגיע לבנות את הדלק.

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

2. חלק 0 - איך ניגשים לפתור את זה

הרעיון של האלגוריתם לא מסובך אבל עשוי להיות מבלבל במבט ראשון:

1. נחזיק רשימת ציוד הפוכה, כלומר לכל חומר נדע איזה חומרים יוצרים אותו.
2. נחזיק רשימה של החומר שאנחנו רוצים לבנות (בהתחלה זה יהיה 1 דלק).

עכשיו נרוץ בלולאה, ובכל איטרציה:

1. נבחר חומר אחד שאנחנו רוצים לבנות.
2. נמצא מתוך רשימת הציוד איזה חומרים צריך בשביל לבנות אותו.
3. נחליף את החומר בחומרים שצריך בשביל לבנות אותו.

עכשיו נשאר לנו רק להבין מה עושים עם העודפים. בדוגמא שראינו הצלחנו לייצר רק 30 יחידות של A ולא 40, בגלל שהמפעל שלנו יכל לייצר רק 10 יחידות של A במכה. לכן כל פעם שהיינו צריכים 7 יחידות של A בעצם בנינו 10 יחידות (כי זה כל מה שידענו לבנות). אז בעצם אם ניקח בחשבון גם את העודפים הלולאה שלנו צריכה להיראות כך:

1. נבחר חומר אחד שאנחנו רוצים לבנות.
2. נמצא מתוך רשימת הציוד איזה חומרים צריך בשביל לבנות אותו.
3. נבדוק במחסן העודפים איזה מהחומרים כבר יש לנו.
4. נוסיף לרשימת הציוד לבניה רק את החומרים שלא היו לנו במחסן.

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

1. נבחר חומר לבניה שלא תלוי באף חומר אחר מהרשימה.
2. נמצא מתוך רשימת הציוד איזה חומרים צריך בשביל לבנות אותו.
3. נבדוק במחסן העודפים איזה מהחומרים כבר יש לנו.
4. נוסיף לרשימת הציוד לבניה רק את החומרים שלא היו לנו במחסן.

ועכשיו אנחנו מוכנים להתחיל לקודד.

3. חלק 1 - פיענוח ספר ההוראות

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

בקלוז'ר המפה שמתארת את ספר ההוראות מהדוגמה שלנו היא:

{
    {:qty 1, :mat "FUEL"} [{:qty 7, :mat "A"} {:qty 1, :mat "E"}],
    {:qty 1, :mat "E"} [{:qty 7, :mat "A"} {:qty 1, :mat "D"}],
    {:qty 1, :mat "D"} [{:qty 7, :mat "A"} {:qty 1, :mat "C"}],
    {:qty 1, :mat "C"} [{:qty 7, :mat "A"} {:qty 1, :mat "B"}],
    {:qty 1, :mat "B"} [{:qty 1, :mat "ORE"}],
    {:qty 10, :mat "A"} [{:qty 10, :mat "ORE"}]
}

ובשביל לייצר אותה מתוך טקסט הקלט השתמשתי בקוד הבא:

defn parse-int [s]
  (Integer/parseInt (re-find #"\A-?\d+" s)))

(defn parse [input-str]
  (let [
        lines (str/split-lines input-str)
        ]
    (loop [
           [line & lines] lines
           rules {}
           ]
      (if (nil? line) rules
        (let [
              [_ qty mat] (re-find #"=> (\d+) (\w+)" line)
              inputs (last (re-find #"(.*) =>" line))
              value (vec
                      (map
                        (fn [[qty mat]]
                          { :qty (parse-int qty) :mat mat })
                        (map #(clojure.string/split %1 #" ")
                             (clojure.string/split inputs #"\s*,\s*"))))]
          (recur lines (conj { {:qty (parse-int qty) :mat mat} value } rules)))))))

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

4. חלק 2 - פונקציות עזר

את רשימת החומרים לבניה אני שומר בתור רשימה פשוטה של אוביקטים (כל אוביקט כזכור הוא מפה שערך ה :qty שלה מייצג את הכמות וה :mat מייצג את החומר). כמות שלילית מציינת עודף וחיובית מציינת חומר שצריך לבנות.

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

(defn collect [stash]
    (->>
        stash
        (filter (fn [item] (not= 0.0 (:qty item))))
        (group-by (fn [item] (:mat item)))
        (map (fn [[k v]] { :mat k :qty (apply + (map :qty v)) }))))

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

(defn build [goals]
  (let [
        ore (apply + (map :qty (filter (fn [item] (= (:mat item) "ORE")) goals)))
        non-trivial-goals (filter (fn [item] (not= (:mat item) "ORE")) goals)
        ]
    [ore, non-trivial-goals]))

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

(defn update-map [m f] 
  (reduce-kv (fn [m k v] 
               (assoc m k (f v))) {} m))

(defn remove-from-rulebook [rulebook material]
  (->>
    (update-map rulebook (fn [list-of-items] (filter (fn [item] (not= (:mat item) material)) list-of-items)))
    (filter (fn [[k v]] (not= (:mat k) material)))
    (into {})))

(defn topsort [rulebook]
  (loop [rulebook rulebook
         ordering []]
    (cond
      (every? (fn [[k v]] (empty? v)) rulebook) ordering
      :else (let [
                  [{ mat :mat }, _] (first (filter (fn [[k v]] (empty? v)) rulebook))
                  ]
              (recur
                (remove-from-rulebook rulebook mat)
                (conj ordering mat))))))

(defn make-key-fn [rulebook]
  (let [ranks (into {} (map-indexed (fn [idx item] [item idx]) (topsort (remove-from-rulebook rulebook "ORE"))))]
    (fn [item] (if (pos? (:qty item))
                         (get (:mat item) ranks)
                         999999))))

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

(defn mul [materials times]
  (vec (map (fn [material] (update material :qty (partial * times))) materials)))

(defn calculate-leftovers
  [rule-used goal]
  {:mat (:mat rule-used) :qty (- (:qty goal) (:qty rule-used))})

(defn required-stuff [rulebook goal]
  (let [
        goal-mat (:mat goal)
        goal-qty (:qty goal)
        [product materials] (first (filter (fn [[k v]] (= (:mat k) goal-mat)) rulebook))
        required-times (Math/ceil (/ goal-qty (:qty product)))]
  (conj (mul materials required-times)
        (calculate-leftovers (first (mul [product] required-times)) goal))))

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

5. חלק 3 - חישוב ה ORE הדרוש לבניית יחידת דלק

פונקציית הפיתרון ב Clojure מריצה בדיוק את הלולאה שכתבתי בהתחלה:

(defn required-ore-3 [rulebook goal]
  (let [key-fn (make-key-fn rulebook)]
    (loop [goals [goal]
           ore 0]
      (cond
        (empty? (filter #(> (:qty %) 0) goals)) ore
        :else (let [
                    [ore-this-round goals] (build goals)
                    [next-goal & remaining-goals] (sort-by key-fn goals)
                    required-materials (required-stuff rulebook next-goal)
                    ]
                (recur (collect (into [] (concat remaining-goals required-materials))) (+ ore-this-round ore)))))))

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

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

[{:mat FUEL, :qty 1}]
({:mat A, :qty 7.0} {:mat E, :qty 1.0})
({:mat E, :qty 1.0} {:mat ORE, :qty 10.0} {:mat A, :qty -3.0})
({:mat A, :qty 4.0} {:mat D, :qty 1.0})
({:mat D, :qty 1.0} {:mat ORE, :qty 10.0} {:mat A, :qty -6.0})
({:mat A, :qty 1.0} {:mat C, :qty 1.0})
({:mat C, :qty 1.0} {:mat ORE, :qty 10.0} {:mat A, :qty -9.0})
({:mat A, :qty -2.0} {:mat B, :qty 1.0})
({:mat A, :qty -2.0} {:mat ORE, :qty 1.0})
({:mat A, :qty -2.0})
31.0