+ محدودیت حجم فایل ارسالی: ۴ مگابایت + **این سوال داوری خودکار ندارد!** + پاسخ‌های خود را بصورت *Zip* ارسال کنید تا پس از پایان مسابقه توسط طراحان داوری شود. ---------- **در این سوال شما تنها اجازه دارید که به صورت functional برنامه‌نویسی کنید (اجازه استفاده از نمادهای تغییر پذیر در برنامه ندارید).** تعریف ساختار داده‌ی زیر را در نظر بگیرید: ``` case class Node(id: Int) case class Edge(from: Node, to: Node) ``` با استفاده از این ساختمان داده یک گراف را به صورت مجموعه‎ای از یال‌های آن مي‌توان نمایش داد (مجموعه ای از گونه‌های `List[Edge]`). **الف)** مي‌خواهيم تمامی گره‌هایی را بیابیم که دقیقاً به مقدار $n$ گام با گره‌هاي اولیه فاصله داشته باشند. بدین منظور تابع زیر را پیاده‌سازي کنید: ``` def reachable(n: Int, init: Set[Node], edges: List[Edge]): Set[Node] ``` در این قسمت مي‌توانید فرض کنید n≥0 بنابراین نیازی به بررسی کردن این مورد در پیاده‌سازی تابع نیست. **ب)** فرض کنید که زیرمجموعه‌اي از گره‌های گراف (به اسم *nodes*) داده شده است. با استفاده از تابعی که در بالا تعریف کرديد زیرمجموعه‌اي از *nodes* را بيابید که به حلقه‌اي با اندازه‌ي ۳ در گراف تعلق داشته باشند. برای این قسمت بایستی تابع زیر را پیاده‌سازي کنید. ``` def cycles3(nodes: Set[Node], edges: List[Edge]): Set[Node] ``` ---------- **جهت یادآوری:** توابع مهم لیست در زبان برنامه‌سازي Scala به شرح زیر هستند. • x :: (xs: List[A]): List[A]: prepends the element x to the left of xs, returning a List[A]. • xs ++ (ys: List[A]): List[A]: appends the list ys to the right of xs, returning a List[A]. • xs.apply(n: Int): A, or xs(n: Int): A: returns the n-th element of xs. Throws an exception if there is no element at that index. • xs.drop(n: Int): List[A]: returns a List[A] that contains all elements of xs except the first n ones.If there are less than n elements in xs, returns the empty list. • xs.filter(p: A => Boolean): List[A]: returns all elements from xs that satisfy the predicate p as a List[A]. • xs.flatMap[B](f: A => List[B]): List[B]: applies f to every element of the list xs, and flattens the result into a List[B]. • xs.foldLeft[B](z: B)(op: (B, A) => B): B: applies the binary operator op to a start value and all elements of the list, going left to right. • xs.foldRight[B](z: B)(op: (A, B) => B): B: applies the binary operator op to a start value and all elements of the list, going right to left. • xs.map[B](f: A => B): List[B]: applies f to every element of the list xs and returns a new list of type List[B]. • xs.nonEmpty: Boolean: returns true if the list has at least one element, false otherwise. • xs.reverse: List[A]: reverses the elements of the list xs. • xs.scanLeft[B](z: B)(op: (B, A) => B): List[B]: produces a List[B] containing cumulative results of applying the operator op going left to right, with the start value z. The returning list contains 1 more element than the input list, the head being z itself. For example, List("A", "B", "C").scanLeft("z")(_ + _) returns List("z", "zA", "zAB", "zABC"). scanLeft is similar to foldLeft, except that, instead of returning only the last value of the accumulator, it returns a list of all the intermediate values of the accumulator. • xs.take(n: Int): List[A]: returns a List[A] containing the first n elements of xs. If there are less than n elements in xs, returns these elements. • xs.zip(ys: List[B]): List[(A, B)]: zips elements of xs and ys in a pairwise fashion. If one list is longer than the other one, remaining elements are discarded. Returns a List[(A, B)]. • xs.toSet: Set[A]: returns a set of type Set[A] that contains all elements from the list xs. Note that the resulting set will contain no duplicates and may therefore be smaller than the original list.