• בלוג
  • aoc2023
  • פיתרון יום 6 ב Advent Of Code 2023 בסקאלה (הכי קל בינתיים)

פיתרון יום 6 ב Advent Of Code 2023 בסקאלה (הכי קל בינתיים)

14/01/2024

אחרי 5 ימים מבלבלים, יום 6 של Advent Of Code השאיר קצת אוויר לנשימה. בואו נצא לדרך למירוץ הסירות עם סקאלה.

1. האתגר

במשחק היום אנחנו מקבלים טבלה של זמנים ומרחקים:

Time:      7  15   30
Distance:  9  40  200

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

  1. אם נטען במשך 2 מילי שניות יהיו לנו עוד 5 מילי שניות לנסוע במהירות 2, ונעבור מרחק של 10 מילימטר (גדול מהמרחק בטבלה).

  2. אם נטען במשך 3 מילי שניות יהיו לנו עוד 4 מילי שניות לנסוע ונעבור 12 מילימטר.

  3. אם נטען במשך 4 מילי שניות יהיו לנו עוד 3 מילי שניות לנסוע ונעבור שוב 12 מילימטר.

  4. אם נטען במשך 5 מילי שניות יהיו לנו עוד 2 מילי שניות לנסוע ונעבור 10 מילימטר.

במירוץ השני יש 8 דרכים לנצח ובשלישי 9 דרכים לנצח, והמשימה היא לכפול את מספר הדרכים לנצח בכל מירוץ. בדוגמה מקבלים 288.

2. פיתרון בעזרת חישוב

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

(t-x) * x

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

(t-x) * x > d

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

import Math.{sqrt, pow, max, min}
import scala.io.Source
import scala.util.chaining.*

object aoc2023day6 {
  val demoInput: String = """Time:      7  15   30
                            |Distance:  9  40  200""".stripMargin

  private def parseInput(input: Source): List[(Long, Long)] =
    input.getLines().toList match
      case List(times, distances) =>
        val timesValues = """\b(\d+)\b""".r.findAllIn(times).toList.map(_.toLong)
        val distanceValues = """\b(\d+)\b""".r.findAllIn(distances).toList.map(_.toLong)
        timesValues.zip(distanceValues)

  private def waysToWin(time: Long, distance: Long): Long =
    val x1 = ((time + sqrt(pow(time, 2) - 4 * distance)) / 2)
    val x2 = ((time - sqrt(pow(time, 2) - 4 * distance)) / 2)
    val start = min(x1, x2).floor + 1
    val end = max(x1, x2).ceil - 1

    (end - start + 1).toLong

  @main
  def day6_part1(): Unit =
    println(parseInput(Source.fromResource("day6.txt"))
      .map(waysToWin)
      .product)
}

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

3. חלק 2

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

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

  private def parseInputPart2(input: Source): (Long, Long) =
    input.getLines().toList match
      case List(times, distances) =>
        val timesValues = times.replaceAll("\\s", "").substring(5).toLong
        val distanceValues = distances.replaceAll("\\s", "").substring(9).toLong
        (timesValues, distanceValues)

השימוש ב substring מוריד את הטקסט בתחילת השורה (המילים Time ו Distance). וכן אפשר היה לבנות שם ביטוי רגולארי יותר גנרי אבל בהקשר של התרגיל לא היה הרבה טעם.