משחקים עם קלוז'ר: פיתרון AoC 2021 Day 1

04/06/2022

יומי

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

1. מה אנחנו בונים

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

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

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

בחלק השני של התרגיל ובשביל לעשות את המשחק יותר מעניין, אנחנו צריכים לחלק את הסידרה לשלשות, לחשב סכום של כל שלושה מספרים צמודים ואז לספור את מספר העליות בסידרת הסכומים. בדוגמה שלנו זה אומר שהמספר הראשון בסידרת הסכומים הוא 199+200+208 שזה 607, המספר השני בסידרת הסכומים הוא 200+208+210 שזה 618 וכך הלאה. בסידרה הזאת יש 5 מספרים שגדולים יותר מזה שהיה לפניהם.

2. פיתרון קלוז'ר

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

אז אפשר יהיה להריץ filter פשוט על רשימת הזוגות כדי לסנן רק את אלה שבהם השני גדול מהראשון ולספור כמה זוגות נשארו. וככה הגעתי לפונקציה partition של קלוז'ר שיודעת לעשות בדיוק את זה:

user=> (partition 2 1 [199 200 208 210])
((199 200) (200 208) (208 210))

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

(defn count-inc [input]
  (count (filter (partial apply <)
                 (partition 2 1 input))))

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

(require '[clojure.string :as str])

(let [input (->> "input.txt"
                 (slurp)
                 (str/split-lines)
                 (map read-string)
                 )]

  (println (count-inc input))

  (println (count-inc 
            (map 
              (partial apply +) 
              (partition 3 1 input)))))

סך הכל הקוד לשני החלקים לקח 18 שורות (כולל שורות רווח), שזה ממש אחלה.

3. פיתרון ישן שהיה לי בפייתון

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

def part1():
    count = 0
    last_value = 0

    with open('day1.txt') as f:
        for line in f:
            if last_value > 0 and int(line) > last_value:
                count += 1

            last_value = int(line)

    print(count)

def part2():
    count = 0
    last_value = []

    with open('day1.txt') as f:
        for line in f:
            if len(last_value) < 3:
                last_value.append(int(line))
                continue

            next_window = last_value[1:] + [int(line)]
            if sum(next_window) > sum(last_value):
                count += 1

            print(f"prev={last_value}; next={next_window}")

            last_value = next_window

    print(count)

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

4. מחשבות להמשך

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

import sys

prev_depth = int(input())
depth = int(input())
count = 0
while depth:
    if depth > prev_depth:
        count += 1
    prev_depth = depth
    v = sys.stdin.readline()
    if v == '':
        break
    depth = int(v)

print(count)

והנה עוד אחד:

nums = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]
cnt = 0
for i in range(len(nums) - 1):
    if nums[i] < nums[i+1]:
        cnt += 1
print(f'Ans: {cnt}') # 7

מצד שני הפיתרון הזה בפייתון לוקח גישה דומה הרבה יותר למה שכתבתי בקלוז'ר:

def task1():
    data = load_data()
    x, y = data[:-1], data[1:]
    result = sum(1 for xs, ys in zip(x, y) if ys > xs)
    print(result)

כך שאין שום דבר בשפה עצמה שמכריח גישה מסוימת.

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

(defn answer-01 [input]
  (count (filter true? (map < input (rest input)))))

ואז התוכנית כולה הופכת ל:

(ns aoc21-01
  (:require [clojure.string :as str]))

(def input (map parse-long (str/split-lines (slurp "input.txt"))))

(defn answer-01 [input]
  (count (filter true? (map < input (rest input)))))

(def three-sliding-window
  (map + input (next input) (nnext input)))

(defn answer-02 []
  (answer-01 three-sliding-window))

(prn (answer-01 input))
(prn (answer-02))