לעולם לא אשכח את ההתרגשות שלי ביום ה 4/12/2017 כאשר בשעה שבע בבוקר אריק ווסטל פתח את החידה הרביעית של Advent Of Code אותה שנה. הסיבה למסיבה היתה תוכן החידה, שבמבט ראשון נראה לי כמו הזדמנות נפלאה לכתוב ביטויים רגולאריים ולהיכנס לרשימת הפותרים המהירים של התחרות.

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

\b(\w+)\b.*\b\1\b

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

import fileinput, re

count = 0

pat = re.compile(r'\b(\w+)\b.*\b\1\b')

with fileinput.input() as file:
    for line in file:
        if not pat.search(line):
            count += 1

print(count)

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

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

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

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

dad can add

אנחנו נשנה את המשפט ל:

add acn add

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

import fileinput, re

count1 = 0
count2 = 0

pat = re.compile(r'\b(\w+)\b.*\b\1\b')

with fileinput.input() as file:
    for line in file:
        if not pat.search(line):
            count1 += 1

        line2 = re.sub(
                r'\b(\w+)\b',
                lambda m: ''.join(sorted(m.group(1))),
                line)

        if not pat.search(line2):
            count2 += 1

print(count1)
print(count2)

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

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