אתגר AoC 2017 יום 7

aoc2017
#1

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

מתייג את כולם כדי שתבואו…
@YOEL, @11115, @splintor, @Amirkr, @miryeh, @itamard, @Dima_Gimburg

קירקס רקורסיבי

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

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

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

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

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

                gyxo
              /     
         ugml - ebii
       /      \     
      |         jptl
      |        
      |         pbga
     /        /
tknk --- padx - havc
     \        \
      |         qoyq
      |             
      |         ktlj
       \      /     
         fwft - cntj
              \     
                xhth

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

https://adventofcode.com/2017/day/7

#2

הי הי,

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

חלק 2

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

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

אבל - בשביל ש tknk יהיה מאוזן המשקל של ugml, padx ו fwft צריך להיות זהה, ופה כבר יש לנו בעיה:

ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243

מסתבר ש ugml כבד יותר משתי התוכניות האחרות. המשקל של ugml שהוא 68 הוא כבד מדי. אם ugml היה שוקל 60 כל הסכומים היו יוצאים אותו הדבר והכל היה מאוזן. לכן התשובה לחידה בדוגמא היא 60.

כתבו תוכנית אוטומטית שמחשבת את זה ואחרי זה לכו לבקר את אריק לאסוף את הכוכב שלכם:
https://adventofcode.com/2017/day/7

#4

הפתרון שלי לחלק הראשון:

לייק 1
#5

הפתרון שלי לחלק השני:

לייק 1