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

1. התרגיל - חלק 1

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

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

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

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

2. מימוש הפונקציות של הקשרים בסקאלה

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

enum Dir:
  case U, D, L, R

case class Knot(x: Int, y: Int) {
  def move(direction: Dir): Knot =
    direction match
      case Dir.R => Knot(this.x + 1, this.y)
      case Dir.L => Knot(this.x - 1, this.y)
      case Dir.U => Knot(this.x, this.y - 1)
      case Dir.D => Knot(this.x, this.y + 1)

  def follow(head: Knot): Knot =
    // head touches tail
    if (((head.x - this.x).abs <= 1) && ((head.y - this.y).abs <= 1)) {
      return this
    }
    var nextPosition = this;

    if (nextPosition.x < head.x) {
      nextPosition = nextPosition.move(Dir.R)
    } else if (nextPosition.x > head.x) {
      nextPosition = nextPosition.move(Dir.L)
    }

    if (nextPosition.y < head.y) {
      nextPosition = nextPosition.move(Dir.D)
    } else if (nextPosition.y > head.y) {
      nextPosition = nextPosition.move(Dir.U)
    }
    nextPosition
}

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

3. פיתרון חלק 1 עם רשימות

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

R 4
U 2

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

R R R R U U

בסקאלה זה יהיה עם הקוד הבא:

def parseInput(input: String): LazyList[Dir] = {
  val Array(name, countStr) = input.split(" ")
  val count = countStr.toInt
  LazyList.fill(count)(Dir.valueOf(name))
}

val inputStream = LazyList.from(Source.fromFile("./input.txt").getLines())
val unpackedInput: LazyList[Dir] = inputStream.flatMap(parseInput)

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

val headMoves: LazyList[Knot] = unpackedInput.scanLeft[Knot](Knot(0, 0))((knot, dir) => knot.move(dir))

בשביל לעקוב אחרי head אני משתמש שוב ב scan אבל הפעם רשימת הקלט היא headMoves והפונקציה תקרא ל follow:

val tailMovesPart1 = headMoves.scanLeft[Knot](Knot(0, 0))((tail, head) => tail.follow(head))

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

@main
def main(): Unit = {
//  val inputStream: LazyList[String] = demoInput.linesIterator.to(LazyList)
  val inputStream = LazyList.from(Source.fromFile("./input.txt").getLines())
  val unpackedInput: LazyList[Dir] = inputStream.flatMap(parseInput)
  val headMoves: LazyList[Knot] = unpackedInput.scanLeft[Knot](Knot(0, 0))((knot, dir) => knot.move(dir))
  val tailMovesPart1 = headMoves.scanLeft[Knot](Knot(0, 0))((tail, head) => tail.follow(head))
  println(tailMovesPart1.toSet.size)

4. חלק 2

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

  var tailMovesPart2: LazyList[Knot] = headMoves
  for (i <- Range(1, 10)) {
    tailMovesPart2 = tailMovesPart2.scanLeft[Knot](Knot(0, 0))((tail, head) => tail.follow(head))
  }

  println(tailMovesPart2.toSet.size)

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