החלק הראשון של יום 8 ב Advent Of Code היה ממש פשוט וכלל כמה טיפים לגבי פונקציית reduce בפייתון.

1. האתגר

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

LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)

השורה הראשונה מייצגת מסלול ואחריה יש שורה ריקה ואז המפה. המפה מכילה שורות כשכל שורה מורכבת ממזהה של מקום ואז שתי אפשרויות לאן להמשיך ממנו - האות L אומרת שצריך להמשיך שמאלה לאפשרות הראשונה, והאות R אומרת שצריך להמשיך ימינה לאפשרות השניה. המסלול מתחיל תמיד ב AAA וצריך להגיע ל ZZZ. בדוגמה שלנו נתחיל ב AAA, נלך שמאלה ונגיע ל BBB, אחרי זה שוב שמאלה ואנחנו חוזרים ל AAA (כי בשורה של BBB האפשרות הראשונה היא AAA), אחרי זה ימינה שוב ל BBB. בגלל שההוראות נגמרו אבל עדיין לא הגענו לסוף נבצע אותן פעם נוספת נלך שמאלה, שמאלה וימינה ואז נגיע ל ZZZ. סך הכל לקח לנו 6 צעדים להגיע לסוף.

2. פיענוח הקלט בפייתון

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

def parse(input: typing.TextIO) -> tuple[str, dict[str, tuple[str, str]]]:
    instructions = input.readline().strip()
    map = {}
    input.readline()
    for line in input:
        if m := re.search(r"(\w+) = \((\w+), (\w+)\)", line):
            key, left, right = m.groups()
            map[key] = (left, right)

    return instructions, map

3. פיתרון פונקציונאלי עם reduce

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

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

def step(map):
    def handler(location, direction):
        if direction == "L":
            return map[location][0]
        elif direction == "R":
            return map[location][1]
        else:
            raise Exception(f"Unknown direction {direction}")

    return handler

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

לפייתון יש אומנם פונקציה functools.reduce שמבצעת reduce אבל היא לא מתאימה פה בגלל שהיא לא יודעת לעבוד עם איטרטורים. במקומה נשתמש ב itertools.accumulate כדי לקבל את התוצאה:

instructions, map = parse(open('input.txt'))
print(len(list(itertools.takewhile(lambda n: n != 'ZZZ',
                               itertools.accumulate(itertools.cycle(instructions),
                                                    step(map),
                                                    initial='AAA')))))