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

סיפור קצת מדכא על דגים ושינויים בקוד

נושאים:יומי

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

הם טועים.

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

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

יום 6 של Advent Of Code האחרון התחיל בים (כל הימים עד עכשיו התחילו בים, אז זה לא מפתיע). אנחנו בצוללת ופוגשים להקה של דגים, ורוצים לגלות כמה מהר הדגים מתרבים. דג צריך יומיים כדי להגיע לבגרות, ואז עוד 6 ימים כדי להוליד דג חדש. אה, ודגים לא מתים.

לדוגמה אם יש לנו להקה שגילאי הדגים בה הם:

3, 2, 3, 5, 4

אז הדג הראשון יוליד דג חדש בעוד שלושה ימים, ואז שוב שישה ימים לאחר מכן, ואז שוב שישה ימים לאחר מכן. הדג השני יוליד דג חדש בעוד 4 ימים, ואז שוב שישה ימים לאחר מכן, ושוב שישה ימים לאחר מכן. כל אחד מהדגים החדשים ייקח יומיים לגדול, ואז אחרי שישה ימים יוליד גם הוא דג חדש.

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

Initial state: 3,4,3,1,2
After  1 day:  2,3,2,0,1
After  2 days: 1,2,1,6,0,8
After  3 days: 0,1,0,5,6,7,8
After  4 days: 6,0,6,4,5,6,7,8,8
After  5 days: 5,6,5,3,4,5,6,7,7,8
After  6 days: 4,5,4,2,3,4,5,6,6,7
After  7 days: 3,4,3,1,2,3,4,5,5,6
After  8 days: 2,3,2,0,1,2,3,4,4,5
After  9 days: 1,2,1,6,0,1,2,3,3,4,8
After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8
After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8

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

2פיתרון 1 - גישה פרוצדורלית

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

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

fish = []

with open('demo.txt') as f:
    fish = [int(x) for x in f.read().split(',')]

def play():
    for index, remaining in enumerate(fish[:]):
        if remaining == 0:
            fish.append(8)
            fish[index] = 6
        else:
            fish[index] -= 1

for i in range(80):
    play()

print(len(fish))

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

3חלק שני - ההתרסקות והתיקון

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

הדרך לפתור את התרגיל למספר גדול של ימים היא לארגן את הדגים בקבוצות, כלומר כל הדגים שיש להם עוד 3 ימים עד שמייצרים דג חדש ישבו בתא אחד במערך, כל אלה שצריכים עוד 4 ימים כדי להתרבות ישבו בתא אחר במערך וכך הלאה. סך הכל יהיה לי מערך של 8 תאים שבכל תא יהיה כתוב כמה דגים יש בקבוצה הזאת. בכל יום שעובר אני מעביר את הדגים תא אחד אחורה במערך, ואלה שהיו בתא 0 נכנסים גם לתא 6 כדי להתחיל סיבוב חדש וגם לתא 8 בתור דגים חדשים.

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

הקוד המעודכן שלי נראה כך:

fish = [0] * 10

with open('demo.txt') as f:
    fish_ages = [int(x) for x in f.read().split(',')]
    for age in fish_ages:
        fish[age] += 1

def play():
    global fish
    new_fish = [*fish[1:], 0]
    new_fish[6] += fish[0]
    new_fish[8] += fish[0]
    fish = new_fish

for i in range(80):
    play()

print(sum(fish))

והוא כבר פותר בלי בעיה את התרגיל גם עבור 256 ימים.

4פיתרון 2 - הגישה הפונקציונאלית

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

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

def flat_map(f, items):
    output = []
    for i in items:
        res = f(i)
        if type(res) == list:
            output.extend(res)
        else:
            output.append(res)
    return output


def process_fish(single_fish):
    if single_fish == 0:
        return [6, 8]
    else:
        return single_fish - 1


def play(fish):
    return flat_map(process_fish, fish)


def part1():
    fish = []

    with open('demo.txt') as f:
        fish = [int(x) for x in f.read().split(',')]

    for i in range(80):
        fish = play(fish)

    print(len(fish))

part1()

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

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

def play(groups):
    new_groups = [*groups[1:], 0]
    new_groups[8] += groups[0]
    new_groups[6] += groups[0]
    return new_groups


def group_fish(fish):
    groups = [0] * 10
    for f in fish:
        groups[f] += 1

    return groups


def part2():
    fish = []
    with open('demo.txt') as f:
        fish = [int(x) for x in f.read().split(',')]

    fish = group_fish(fish)
    for i in range(80):
        fish = play(fish)

    print(sum(fish))


part2()

פונקציית ה main והמבנה הכללי נשאר כמו שהיה, אבל את play שיניתי לגמרי, את flat_map שכל כך התאמצתי לכתוב זרקתי, את process_fish וה if שבתוכה מחקתי והוספתי פונקציה חדשה שמארגנת את הדגים לפי קבוצות.

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

מצד שני בגלל חוסר תמיכה של השפה (אין flat_map) הייתי צריך להתאמץ ולכתוב יותר קוד בשביל להגיע לתוצאה ובסופו של דבר הפיתרון הפונקציונאלי היה ארוך יותר מהפיתרון הנאיבי.

5פיתרון 3 - פיתוח מונחה עצמים

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

class Fish:
    def __init__(self, time_to_reproduce, fish_tank):
        self.time_to_reproduce = time_to_reproduce
        self.fish_tank = fish_tank

    def grow_up(self):
        if self.time_to_reproduce == 0:
            self.time_to_reproduce = 6
            self.fish_tank.create_fish(8)
        else:
            self.time_to_reproduce -= 1

    def __repr__(self):
        return f"{self.time_to_reproduce}"

class FishTank:
    def __init__(self, fish_initial_states):
        self.fish = [Fish(i, self) for i in fish_initial_states]

    def create_fish(self, time_to_reproduce):
        self.fish.append(Fish(time_to_reproduce, self))

    def count(self):
        return len(self.fish)

    def play(self):
        for fish in self.fish[:]:
            fish.grow_up()

################

fish = []

with open('demo.txt') as f:
    fish = [int(x) for x in f.read().split(',')]

tank = FishTank(fish)

for i in range(80):
    tank.play()

print(tank.count())

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

    def play(self):
        for fish in self.fish[:]:
            fish.grow_up()

מקריאת שלושת השורות לא ברור למה אני צריך לשכפל את self.fish לפני שאני קורא ל grow_up. רק אם מדפדפים למעלה אפשר לראות שלכל דג יש בעצם חיבור לאקווריום בו הוא נמצא ושהפונקציה grow_up עלולה לשנות את מערך הדגים.

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

הניסיון הראשון שלי לפיתרון נראה כך אבל הוא לא עבד:

class FishTank:
    def __init__(self, fish_count, next_tanks):
        self.fish = fish_count
        self.next_tanks = next_tanks

    def create_fish(self):
        self.fish += 1

    def count(self):
        return self.fish

    def play(self):
        for fish_tank in self.next_tanks:
            fish_tank.fish += self.fish
        self.fish = 0

    def __repr__(self):
        return f"{self.fish}"

################

fish = []

with open('demo.txt') as f:
    fish = [int(x) for x in f.read().split(',')]

tanks = [FishTank(0, []) for i in range(10)]
for ti in range(9, 1, -1):
    tanks[ti].next_tanks = [tanks[ti - 1]]
tanks[0].next_tanks = [tanks[6], tanks[8]]

for i in fish:
    tanks[i].create_fish()

for i in range(80):
    for ti in range(9, 0, -1):
        tanks[ti].play()

print(sum(t.count() for t in tanks))

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

for i in range(1):
    for ti in range(9, 0, -1):
        tanks[ti].play()

ואז בתוך play יש לנו:

def play(self):
    for fish_tank in self.next_tanks:
        fish_tank.fish += self.fish
    self.fish = 0

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

for i in range(80):
    grown_up_fish_count = tanks[0].count()
    tanks = [*tanks[1:], FishTank(0, [tanks[-2]])]
    tanks[6].fish += grown_up_fish_count
    tanks[8].fish += grown_up_fish_count
    print(tanks)

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

6שורה תחתונה

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

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

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

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

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


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