ToCode

זאת כבר לא הבורות שלנו שמעכבת אותנו נתן סובו מ zed זרק את המשפט הבא בראיון על הטכנולוגיה של זד, או יותר נכון על הבחירה שלהם לזרוק את Atom שהיה עורך הטקסט שהם עבדו עליו לפני ולהתחיל הכל מחדש. הוא אמר- "הגענו לנקודה שזו כבר לא היתה הבורות שלנו שמעכבת אותנו, זאת באמת הפלטפורמה" זה היה אחרי שלוש שנים של עבודה על Atom. שלוש שנים של ניסיונות לשפר את הביצועים. שלוש שנים של התמודדות עם האתגר של כתיבת Desktop Application מהיר בכלים ווביים. האם היה עדיף לו הם היו מתחילים עם Rust כבר ב 2014 במקום לכתוב את Atom? ברור שלא. קודם כל כי ראסט לא היתה קיימת ב 2014, אבל יותר חשוב הם עוד לא הכירו מספיק טוב את הבעיה, עוד לא הבינו לעומק את האלגוריתמים שצריך לפתח בשביל לבנות עורך טקסט ואת הדרישות והצרכים של המתכנתים שאמורים להשתמש באותו עורך. העבודה על אטום, יחד עם ההתקדמות הטכנולוגית שקרתה באותו הזמן, הביאו אותם לנקודה שבה היה עדיף להתחיל מחדש. וזה לקח טוב לכל פרויקט שאנחנו בונים - בתחילת הדרך, כשאנחנו עדיין לא מכירים מספיק את הבעיה ואת העולם הטכנולוגי שלה, זה בסדר לקחת בחירות קלות כדי להתקדם. יותר מבסדר, זאת הדרך היחידה קדימה. אחרי שנתגבר על הבורות שלנו ונבין למה אנחנו צריכים את הכלים המתקדמים יותר נהיה במקום הרבה יותר בשל כדי לשפר את הטכנולוגיה, או לזרוק הכל ולהתחיל מחדש משהו טוב יותר.

counts match
      case Nil if springs.forall(Set('.', '?').contains(_)) =>
        1
      case Nil =>
        0
      case head :: tail =>
        mem.getOrElseUpdate(s"${springs} ${counts}", {
          val firstDamaged = springs.indexOf('#')
          val end = if (firstDamaged != -1) firstDamaged else springs.length - 1
          0.to(end)
            .map { i => assignGroup(springs.substring(i), head) }
            .collect {
              case Some(springs) => arrangements(mem)(springs, tail)
            }
            .sum
        })



  @main
  def day12part1(): Unit =
    Source.fromResource("day12.txt")
      .getLines()
      .map(unfoldLine(1))
      .map(arrangements())
      .toList
      .sum
      .pipe(println)
}

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

  def unfoldLine(factor: Int)(line: String): (String, List[Int]) =
    line.split(' ') match
      case Array(springs, counts) =>
        val unfoldedCounts = ((counts + ",") * factor).stripSuffix(",")
        val unfoldedSprings = ((springs + "?") * factor).stripSuffix("?")
        (unfoldedSprings, unfoldedCounts.split(',').map(_.toInt).toList)

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

.# 1

הם בעצם מתכוונים שהקלט שלנו הוא:

.#?.#?.#?.#?.# 1,1,1,1,1

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

פיתרון Advent Of Code 2023 יום 12 ב Scala אני מקווה שלא התעייפתם מהחידות של אריק, אני בטוח לא התעייפתי וממשיך (גם אם לאט) במטרה לסיים יום אחד את כל 25 החידות. הפירסום היום מלווה באופטימיות זהירה שכן אנחנו כמעט בחצי הדרך. בואו נראה מה מחכה לנו ביום 12, איזה פיתרון לא עבד ומה בסוף כן פתר את החידה. האתגר - הצלבת נתונים באתגר היום כל שורת קלט מייצגת רצף של מעיינות, חלקם מתפקדים וחלקם מקולקלים. נסמן את המקולקלים ב # ואת המתפקדים בנקודה. המידע מגיע בשתי צורות, קודם כל רשימה של כל המעיינות המתפקדים והתקולים, אחריהם רווח ואז רשימה של הקבוצות של התקולים. לדוגמה שורת הקלט הבאה:

* .#.### 1,1,3 *

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

.#.###.#.###### 1,3,1,6

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

???.### 1,1,3

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

?###???????? 3,2,1

כל ההשלמות האלה חוקיות:

.###.##.#...
.###.##..#..
.###.##...#.
.###.##....#
.###..##.#..
.###..##..#.
.###..##...#
.###...##.#.
.###...##..#
.###....##.#

אז במקום לגלות השלמה אחת חוקית לכל שורה, המשימה שלנו היא למצוא כמה אפשרויות יש להשלמה לכל שורה, ואז לסכום את כל האפשרויות. איך לא לפתור את התרגיל כיוון ראשון שחשבתי עליו כשראיתי את האתגר היה ללכת על פשוט, כלומר אם יש 7 סימני שאלה במחרוזת לנסות את כל האפשרויות לבחור סולמיות ונקודות במקום אותם 7 סימני שאלה ולראות מה מתאים לרשימת הקבוצות שבסוף השורה. וזה עבד ובאמת פתר את החלק הראשון של השאלה אבל בחלק השני היה מוקש שגרם לרעיון שלי להתרסק. אתם מבינים הבעיה באותו רעיון נאיבי היא סיבוכיות זמן הריצה - אם יש 7 סימני שאלה אנחנו צריכים לנסות 2 בחזקת 7 אפשרויות כלומר 128 אפשרויות. זה ממש סביר. אבל אם יש 30 סימני שאלה נצטרך לנסות 2 בחזקת 30 אפשרויות שזה כבר הרבה יותר מדי. מה כן עובד הדרך קדימה היא לכן לוותר על הסיבוכיות המעריכית ולמצוא אלגוריתם יעיל יותר. דרך אחת כזאת תהיה לחלק הניסוי שלנו לשלבים - תחילה נמצא איפה אפשר לשים את הקבוצה הראשונה, בדרך כלל יהיו מספר אפשרויות (במקרה הגרוע אורך המחרוזת אפשרויות) אבל זה בסדר. עכשיו לכל אפשרות נמצא איפה אפשר לשים את הקבוצה השניה, וגם כאן יהיו מספר אפשרויות, ואז נמשיך לכל אפשרות למצוא כמה אפשרויות יש לנו לשים את הקבוצה השלישית וכך הלאה. הפיתרון הזה מגיע לאותה תוצאה אבל הוא עובד הרבה יותר מהר - גם כי מספר הצעדים קטן יותר וגם ואולי בעיקר כי צעדים חוזרים על עצמם. שילוב Memoization מאפשר לצמצם משמעותית את מספר החישובים ולהגיע לתוצאה הנכונה בזמן סביר, גם בקלטים גדולים. קוד? הנה בסקאלה-

import scala.io.Source
import scala.util.chaining._
import scala.collection.mutable
object aoc2023day12 {
  val demoInput: String = """???.### 1,1,3
                            |.??..??...?##. 1,1,3
                            |?#?#?#?#?#?#?#? 1,3,1,6
                            |????.#...#... 4,1,1
                            |????.######..#####. 1,6,5
                            |?###???????? 3,2,1""".stripMargin


  def unfoldLine(factor: Int)(line: String): (String, List[Int]) =
    line.split(' ') match
      case Array(springs, counts) =>
        val unfoldedCounts = ((counts + ",") * factor).stripSuffix(",")
        val unfoldedSprings = ((springs + "?") * factor).stripSuffix("?")
        (unfoldedSprings, unfoldedCounts.split(',').map(_.toInt).toList)


  def assignGroup(springs: String, groupSize: Int): Option[String] =
    val startRe = s"""^[#?]{${groupSize}}[.?].*""".r
    val finalRe = s"""^[#?]{${groupSize}}""".r

    if (startRe.matches(springs)) {
      Some(springs.substring(groupSize + 1))
    } else if (finalRe.matches(springs)) {
      Some("")
    } else {
      None
    }


  def arrangements(mem: mutable.HashMap[String, Long] = new mutable.HashMap[String, Long]())(springs: String, counts: List[Int]): Long =

יותר מדי אינפורמציה חבר לומד תכנות לבד מהבית כדי למצוא עבודה. כל פעם שאנחנו מדברים הוא בא עם סיפורים חדשים - "שמע השבוע התחלתי ללמוד Tensor Flow כי בכל מקום צריכים את זה" "סיימתי קורס פייתון של 40 שעות וידאו ביודמי - היה מעולה ולמדתי המון" "תגיד מה דעתך על AWS? התחלתי ללמוד להסמכה של CLF-C01 כי הבנתי שחייבים את זה בשביל להתקבל לעבודה כ MLOps" ואני מבין את הקושי. אתה לבד, אתה מסתכל על אינסוף חומר שיש באינטרנט, כל כמה ימים אתה פוגש בן אדם אחר שממליץ לך על הדבר שאתה ממש חייב ללמוד כי ככה תמצא עבודה הכי מהר, ואתה לא יודע מה לעשות. אבל הכי גרוע זה שאתה מרגיש שאתה כבר "מבין את זה", זהו סיימת קורס פייתון ראית 40 שעות וידאו ביודמי, בנית 10 פרויקטים מהקורס ופתרת את כל השיעורי בית. אתה בטוח שאתה יודע פייתון אבל עדיין לא מצליח למצוא עבודה. לכן הבעיה חייבת להיות שצריך לדעת עוד דברים. אבל מעגל הקסמים הזה לא מסתיים. לא משנה כמה דברים חדשים אתה לומד, אתה מוצא את עצמך באותו מקום. אתה עדיין מחפש עבודה, כל דבר חדש שאתה לומד גורם לך לשכוח קצת מהדבר הקודם, וכל ראיון ממשיכים לבקש ממך לענות על דברים שעדיין לא למדת. מאיפה יש כל כך הרבה דברים בעולם שצריך ללמוד? זה אי פעם ייגמר? הקושי הוא לראות שעדיין לא סיימת ללמוד אפילו דבר אחד כמו שצריך. שקורס 40 שעות פייתון ופרויקטים של הקורס זה לא מספיק כדי לדעת פייתון. האתגר הוא להבין איך ללמוד את אותו דבר יותר לעומק, ולשלב את הלימוד עם עשייה ובניית פרויקט ברמה גבוהה. כן גם ב 2024, הדרך הכי מהירה למצוא עבודה היא להגיע עם תיק עבודות ויכולת מוכחת. פרויקט גם עוזר למקד את המאמצים ולהחליט מה צריך ללמוד מתוך אינסוף חומרי הלימוד שברשת, וגם מראה לעולם שאתה יודע להתמקד ולגרום לדברים לקרות.

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

def to_list_of_digits(s: str) -> list[int]:
    result = []
    for ch in s:
        if ch.isdigit():
            result.append(int(ch))
    return result

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

def to_list_of_digits(s: str) -> list[int]:
    return [int(ch) for ch in s if ch.isdigit()]

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

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

טיפ פייטסט: איך ועל איזה בדיקות לדלג? אחד הפיצ'רים החמודים של פייטסט הוא היכולת "לסמן" בדיקות בכל דרך שתבחרו. יוצרים קובץ בשם pytest.ini עם תוכן שנראה בערך ככה:

[pytest]
markers =
    integration: integration test
    slow: slow test
    version: tests to run before deploying a new version

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

@pytest.mark.integration
def test_website():
    pass

ולהריץ את כל הבדיקות שמסומנות בקטגוריה integration:

$ pytest -m integration

או להריץ את כל הדברים שלא מהקטגוריה עם:

$ pytest -m "not integration"

פייטסט גם כולל המון סימונים מובנים למשל הסימון skip שגורם לפייטסט לדלג על בדיקה, skipif שמקבל תנאי וגורם לדילוג על בדיקה רק אם התנאי מתקיים ו xfail שמסמן שבדיקה צריכה להיכשל (ולכן לא צריך להתרגש מכישלון). אבל האתגר היותר משמעותי הוא לא איך להשתמש בפיצ'ר אלא מתי להשתמש בו - כלומר על איזה בדיקות כדאי לדלג ואיזה קטגוריות להגדיר, מתי להוסיף xfail ומתי skip ומתי בכלל עדיף למחוק את הבדיקה. ננסה לענות על זה בכמה כללי אצבע- 1. רוב הפיצ'רים של בדיקות הם יותר טובים כשלא משתמשים בהם. זה נכון לגבי mock-ים, לגבי before ו after וכן גם לגבי דילוגים. אם אתם יכולים בלי זה עדיף. 2. לפעמים זה נוח להגדיר סט מסוים של בדיקות שצריכות רכיב תשתית כדי לעבוד. לדוגמה בדיקות אינטגרציה שצריכות לעבוד מול בסיס נתונים ולפני שמפעילים אותן צריך להעלות קונטיינר של בסיס הנתונים. אז נגיד את האמת הכי טוב לדאוג שהבדיקות יפעילו לעצמן את הקונטיינר של בסיס הנתונים או ישתמשו בגירסת In Memory של בסיס הנתונים, אבל לא תמיד זה אפשרי. במצבים כאלה שווה לסמן את הבדיקות שצריכות שנעשה משהו לפני כדי שאפשר יהיה לפעמים לדלג עליהן. 3. לפעמים יש בדיקות שנכשלות מדי פעם אבל כרגע אין לנו זמן לבדוק למה. ברוב מוחלט של המקרים כדאי למחוק את הבדיקות האלה כי אם המוצר עובד כמו שצריך והבדיקה לפעמים נכשלת אז כנראה שיש בעיה בבדיקה או שהיא בודקת מסלולים לא רלוונטיים. ובכל זאת אולי יש איזה ערך סנטימנטלי לבדיקה או סיבה אחרת להשאיר את הקוד, ואז נוח לראות שיש בדיקה כזאת למרות שכרגע היא לא עובדת. אני כן חייב להודות שמהניסיון שלי נדיר מאוד שמישהו מוצא זמן לתקן בדיקה שהיתה ב skip. 4. בדף התיעוד יש דוגמה ל skipif שמדלגת על בדיקה לפי מערכת הפעלה. אישית כשאני כותב בדיקה שצריכה לרוץ רק על מערכת הפעלה מסוימת אני אעדיף לא לראות אותה ב skip או ב xfail כי המשמעות של סימונים אלה היא בדרך כלל שיש איזה בעיה בבדיקה. במקום זה הייתי בקוד הבדיקה מוסיף את הבדיקה ומסמן "הצלחה" אם זאת לא מערכת ההפעלה המתאימה. אלה הטיפים שלי לדילוגים, אם גם לכם יש שיטות שעוזרות להסתדר עם דילוגים מוזמנים לשתף בתגובות או בטלגרם.

זה צריך לקחת שבועיים גם בשיחה על זמנים כדאי להיות ברורים. כשאתה אומר "זה צריך לקחת שבועיים" הכוונה ש- 1. לא בדקתי, אבל נראה לי שזה מה שהיה לוקח לי. 2. לא בדקתי, אבל נראה לי שאני הייתי מסיים את זה בשבוע ולקחתי מרווח ביטחון. 2. אני מוכן לעבוד רק עם מפתחים שמצליחים לסיים משימה כזאת בשבועיים. אם זה ייקח לך יותר כנראה שיש לך בעיה. 3. הדד ליין שלנו כלפי לקוח חיצוני דורש שנסיים את זה בשבועיים. אם יש בעיה חשוב להרים דגל כמה שיותר מהר ונרדד חלקים מהפיצ'ר. 4. בעיקרון זאת משימה של יומיים אבל אני משאיר לך זמן לריפקטורינג כי התשתית של המערכת לא בנויה לתמוך במנגנון הזה. 5. בעיקרון זאת משימה של יומיים אבל אני משאיר לך זמן למידה כי אני יודע שלא עבדת עם החלקים האלה במערכת או עם הטכנולוגיה הזאת בעבר. 6. ישבתי כבר חודשיים לעשות Research על המשימה וגיליתי דרך מהירה לפתור את האתגר. אני יודע שזה נראה מסובך אבל אחרי שנשב זה יראה ממש פשוט. אם אתם בצד שנותן הוראות נסו להיות כמה שפחות מעורפלים. הבן אדם שמולכם לא קורא מחשבות ואתם יכולים לחסוך הרבה מתח לשני הצדדים אם תהיו ברורים. ואם אתם בצד שמקבל את ההוראה אל תתביישו לשאול. רוב הסיכויים שהבן אדם שמולכם רוצה בטובתכם. חסכו לכולם אי הבנה ותשאלו גם אם נראה לכם שהבנתם בדיוק מה קורה שם.

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

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

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

...#......
.......#..
* ......... *
..........
......#...
.#........
.........#
..........
.......#..
* ...#..... *

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

   v  v  v
 ...#......
 .......#..
 #.........
>..........<
 ......#...
 .#........
 .........#
>..........<
 .......#..
 #...#.....
   ^  ^  ^

ואחרי שמשקללים פנימה את תנועת הגלקסיות נגלה שהתמונה האמיתית של המרחקים היא:

....#........
.........#...
* ............ *
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
* ....#....... *

פיתרון בסקאלה דבר ראשון שאפשר לשים לב הוא שקל למדוד את המרחק בין שתי גלקסיות:

  def distance(p1: (Int, Int), p2: (Int, Int)): Int =
      Math.max(p1._1, p2._1) - Math.min(p1._1, p2._1) +
      Math.max(p1._2, p2._2) - Math.min(p1._2, p2._2)

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

  implicit class Crossable[X](xs: Iterable[X]) {
    def cross[Y](ys: Iterable[Y]): Iterable[(X, Y)] = for {x <- xs; y <- ys} yield (x, y)
  }

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

  def parseInput(input: Source, expansion: Int = 1): Map[(Int, Int), Char] =
    val beforeExpansion = input
      .getLines()
      .zipWithIndex
      .collect {
        case (line: String, index: Int) => line.toList.zipWithIndex.map((ch, column) => (index, column, ch))
      }
      .flatten
      .flatMap {
        case (row, column, ch) => Map((row, column) -> ch)
      }
      .toMap

    val emptyColumnsCounts = beforeExpansion
      .keys
      .map {(i, j) => j}
      .toList
      .sorted
      .scan(0) { (acc, columnNumber) =>
        if (isEmptyColumn(beforeExpansion, columnNumber)) acc + expansion else acc
      }

    val emptyRowCounts = beforeExpansion
      .keys
      .map { (i, j) => i }
      .toList
      .sorted
      .scan(0) { (acc, rowNumber) =>
        if (isEmptyRow(beforeExpansion, rowNumber)) acc + expansion else acc
      }

    val afterExpansion = beforeExpansion.map {
      case ((row, column), ch) =>
        ((row + emptyRowCounts(row), column + emptyColumnsCounts(column)), ch)
    }

    afterExpansion

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

    val afterExpansion = beforeExpansion.map {
      case ((row, column), ch) =>
        ((row + emptyRowCounts(row), column + emptyColumnsCounts(column)), ch)
    }

והחלק האחרון הוא חישוב סכום המרחקים:

  @main
  def day11part1(): Unit =
    val map = parseInput(Source.fromResource("day11.txt"))
    val galaxies = map
      .filter { case ((i, j), ch) => ch != '.' }
      .keys
      .toList

    (galaxies cross galaxies)
      .map(distance)
      .sum
      .pipe(_ / 2)
      .pipe(println)