sten1ee / 2021-homework-1-funs-and-queues-solutions

краен срок: 09.04.2021

Няколко функцийки и една опашка

Най-добрият начин да се прихванат основите на нов език е чрез малки задачки. Затова сме ви подготвили няколко. Първото ви домашно е да имплементирате шест малки функции и да реализирате неизменима опашка.

fromDigits – Генериране на число от цифри (1 точка)

Реализирайте функция fromDigits, която от списък от цифри генерира число в бройна система с определена основа. Сигнатурата на функцията е следната:

def fromDigits(digits: List[Int], radix: Int = 10): Int

Реда на цифрите в списъка съвпада с реда на цифровия запис на числото – единиците са последният елемент, radix-иците (или десетиците) предпоследният, и т.н. Всяка цифра е представена в digits чрез числовата си стойност, така цифрата '5' е представена от числото 5, а цифрата 'B', която бихме срещнали в шестнайдесетична бройна система, чрез числото 11. Елементите на digits са числа между 0 и radix. Ако digits е празен списък, то генерираното число трябва да е 0.

Примери:

fromDigits(List(1, 2, 3)) // 123
fromDigits(List(1, 12, 4), 16) // 452; съответства на шестнайдесетичното число 1C4

parseInteger – Парсване на числов низ (1 точка)

Най-често бихме получили цифри чрез символен низ – въведен от потребителя, изпратен ни от някоя система, или по друг начин. Имплементирайте функция, която директно изчислява числената стойност на такива низове:

def parseInteger(integer: String, radix: Int = 10): Int

integer може да започва с незадължителния символ '-', а всички останали символи са цифри от 0 до 9 или букви от A до Z (съответства на регулярния израз -?[0-9A-Z]+). Числовата стойност на буквите е 10 за A, 11 за B, ..., 35 за Z. Така най-голямата възможна основа е 36. Ако integer започва с -, то резултатът е отрицанието на числото, съответстващо на цифрите вдясно.

За реализиране на parseInteger не е позволено да използвате вградени в библиотеките на Scala и Java функции като Integer.parseInt, които вече извършват това.

Ако желаете, можете да превърнете даден низ в списък, използвайки метода toList.

Примери:

parseInteger("123") // 123
parseInteger("1C4", 16) // 452
parseInteger("-0111001", 2) // -57

zipMap – Трансформация на елементите на два списъка едновременно (1 точка)

Често ни се налага да реализираме трансформации върху съчетани елементите от няколко източника, вместо само от един. Реализирайте функция zipMap, която приема два списъка a и b и функция на два параметъра f и генерира списък, формиран от прилаганията на f върху елементите на една и съща позиция в a и b.

Ако имаме списъци List(1, 2) и List(3, 4), то резултатният списък ще бъде List(f(1, 3), f(2, 4))

Ако a и b са с различна дължина, то оставащите елементи на по-дългия списък се игнорират.

def zipMap[A, B](a: List[A], b: List[A])(f: (A, A) => B): List[B]

Примери:

zipMap(List(1, 2, 3), List(4, 5, 6))(_ * _) // List(4, 10, 18)
zipMap(List(3, 6), List(20, 30, 40))((x, y) => y - x) // List(17, 24)

countCoinChangeVariants – Броене на възможностите да върнем ресто (1,5 точки)

Напишете функция, която брои всички възможни начини да върнем ресто (change) за определена сума, ако разполагаме с неизчерпаем източник на монети с определени деноминации (denominations). Сумата от използваните монети трябва да е точно равна на търсеното ресто.

Като пример, ако е необходимо да върнем ресто от 6 пари и разполагаме с монети с деноминации 1, 2 и 5, то имаме 5 начина да го постигнем (редът на монетите не е от значение):

1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 2
1 + 1 + 2 + 2
2 + 2 + 2
1 + 5

Сигнатурата на функцията е следната:

def countCoinChangeVariants(denominations: Set[Int], change: Int): Int

Пример:

countCoinChangeVariants(Set(1, 2, 5), 6) // 5

combinations – Генериране на всички комбинации на елементи от списък (1,5 точки)

Напишете функция, генерираща всички възможни комбинации без повторение от n-ти клас (т.е. n избрани елемента) на елементите от подаден списък.

def combinations[A](xs: List[A], n: Int): List[List[A]]

Примери:

combinations(List(1, 2, 3), 2) // List(List(1, 2), List(1, 3), List(2, 3))
combinations(List(1, 2, 3, 4, 5), 3) // List(List(1, 2, 3), List(1, 2, 4), List(1, 2, 5), List(1, 3, 4), List(1, 3, 5), List(1, 4, 5), List(2, 3, 4), List(2, 3, 5), List(2, 4, 5), List(3, 4, 5))

Елементите на подадения списък xs ще са уникални.

Насоки: методът tails на списъците генерира всички възможни краища на списъка:

List(1, 2, 3, 4).tails.toList // List(List(1, 2, 3, 4), List(2, 3, 4), List(3, 4), List(4), List())

Помислете как тези списъци биха могли да ви помогнат за генериране на комбинациите.

За реализация на функцията не е разрешено използването на съществуващия върху списъци метод combinations.

Опашка

(1 точка)

Реализирайте неизменима (immutable) опашка от елементи Queue[A] със следните операции:

• peek: A – връща елемента от началото на опашката. Ако опашката е празна хвърлете NoSuchElementException
• push(n: A): Queue[A] – връща нова опашка, с елемента n добавен в края на текущата
• pop: Queue[A] – връща нова опашка, в която елемента в началото е премахнат. Ако опашката е празна хвърлете NoSuchElementException
• isEmpty: Boolean – казва дали опашката е празна или не
• size: Int – връща броя на елементите на опашката

Оставяме вътрешната реализация на опашката и това как изглежда нейният конструктор на вас.

Допълнително реализирайте companion обект към опашката със следните два метода:

• empty[A]: Queue[A] – връща празна опашка
• apply[A](xs: A*): Queue – създава опашка от елементите xs

Декларацията на опашката изглежда по следния начин:

class Queue[A](/* ??? */) {
  def peek: A = ???

  def push(a: A): Queue[A] = ???
  def pop: Queue[A] = ???

  def isEmpty: Boolean = ???
  def size: Int = ???
}

object Queue {
  def empty[A]: Queue[A] = ???

  def apply[A](xs: A*): Queue[A] = ???
}

Ако желаете да скриета конструктора на опашката, можете да го направите по следния начин (companion обекта все още има достъп до него):

class Queue private (/* ??? */) { /* ... */}

(1 точка*)

Помислете как може да имплементирате опашката ефективно. Ако не се досещате, направете проучване. Ако постигнете амортизирано константна сложност за операциите peek, push, pop и isEmpty, то ще получите и тази точка.

bfsTraversal – Проследяване на обхождане в ширина (2 точки*)

Класическо приложение на опашка е за реализиране на търсене в ширина в граф. Дефинирайте функция bfsTraversal, която да използва опашката, която реализирахте. Функцията приема начален и краен възел и функция, връщаща списък от съседите на подадения ѝ възел в ориентирания граф, в който се извършва търсенето. Вместо класическото приложение на алгоритъма (търсене на най-кратък път), ще искаме да проследим възлите, през които той минава, докато не намери търсения краен възел. Резултатът от bfsTraversal е опашка от реда на посещение на възлите, започваща със start, като в нея реда на посетените съседи трябва да съвпада с реда в списъка, върнат от neighbours. Ако алгоритъмът открие end, то той трябва да е последният елемент от опашката, ако не, то резултатът е всички възли, които сте обходили докато алгоритъмът приключи търсенето.

Сигнатурата на функцията е следната:

def bfsTraversal(neighbours: Int => List[Int])(start: Int, end: Int): Queue[A]

Графът може да не е дървовиден и затова за да избегнете повторно посещение на възел може да използвате Set за да запазвате вече посетените.

Пример:

За графа

1 -> 2, 5, 8
2 -> 1, 3, 6
3 -> 2, 4
4 -> 3
5 -> 6
6 -> 7
8 -> 9

При начален възел 1 и краен 6 търсеният резултат е опашката от 1, 2, 5, 8, 3, 6. При начален възел 4 и краен 6 резултатът е 4, 3, 2, 1, 6.

Допълнителни указания

Използвайте проекта, предоставен в тази директория. Попълнете скелета от пакета homework1. В src/test/scala може да намерите няколко теста. Насърчаваме ви да добавите собствени за да тествате вашите решения.

Оценяване

Всяка от функции и опашката са отбелязани с точките, които носят, за общо 10 точки. Точките, отбелязани със звездичка* са с леко повишена сложност.

Очакваме от вас решения, които са написани и подредени в добър стил и не използват изменяемост (mutability). Като първо домашно няма да ви взимаме точки за стил (освен за крайни случаи), но за следващите домашни ще сме по-стриктни.

Любопитно

• Ако искате вашата опашка да включва стандартните методи, които виждаме върху колекции, то тя трябва да имплементира trait-а Iterable[A]. За целта е необходимо да предоставите имплементация на следния метод и ще получите наготово всички останали, като map, filter, take и т.н.

  def iterator: Iterator[Int]

  Забележете, че при това методи като map връщат Iterable вместо Queue, което съвпада с поведението на такъв тип интерфейси/mixin-и в други езици, но не и с това, което виждаме по другите колекции в Scala. По-късно в курса ще разгледаме как Scala ни позволява да връщаме конкретния тип (в случая Queue) вместо абстракцията, която имплементира.

• Имплементираната опашка е параметризирана. Опитайте се да си отговорите на въпроса опашка от Int стойности може ли да бъде разглеждана като опашка от AnyVal стойности? По този въпрос ще размишляваме по-късно в курса.