# HG changeset patch # User Christian Urban # Date 1604193691 0 # Node ID 663c2a9108d1c7c714034786a6a37d632f246eab # Parent 40657f9a4e4a9a483849a07908580b8f6586563b updated diff -r 40657f9a4e4a -r 663c2a9108d1 cws/pre_cw02.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cws/pre_cw02.tex Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,160 @@ +% !TEX program = xelatex +\documentclass{article} +\usepackage{../style} +\usepackage{disclaimer} +\usepackage{../langs} + +\begin{document} + + +%% should ask to lower case the words. + +\section*{Preliminary Part 7 (Scala, 3 Marks)} + +\mbox{}\hfill\textit{``What one programmer can do in one month,}\\ +\mbox{}\hfill\textit{two programmers can do in two months.''}\smallskip\\ +\mbox{}\hfill\textit{ --- Frederick P.~Brooks (author of The Mythical Man-Month)}\bigskip\medskip + +\IMPORTANT{You are asked to implement a Scala program for measuring similarity in + texts. The preliminary part is due on \cwSEVEN{} at 5pm and worth 3\%.} + +\noindent +Also note that the running time of each part will be restricted to a +maximum of 30 seconds on my laptop. + +\DISCLAIMER{} + + +\subsection*{Reference Implementation} + +Like the C++ part, the Scala part works like this: you +push your files to GitHub and receive (after sometimes a long delay) some +automated feedback. In the end we will take a snapshot of the submitted files and +apply an automated marking script to them.\medskip + +\noindent +In addition, the Scala part comes with reference +implementations in form of \texttt{jar}-files. This allows you to run +any test cases on your own computer. For example you can call Scala on +the command line with the option \texttt{-cp docdiff.jar} and then +query any function from the template file. Say you want to find out +what the function \texttt{occurrences} produces: for this you just need +to prefix it with the object name \texttt{CW7a}. If you want to find out what +these functions produce for the list \texttt{List("a", "b", "b")}, +you would type something like: + +\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] +$ scala -cp docdiff.jar + +scala> CW7a.occurrences(List("a", "b", "b")) +... +\end{lstlisting}%$ + +\subsection*{Hints} + +\noindent +\textbf{For the Preliminary Part:} useful operations involving regular +expressions: +\[\texttt{reg.findAllIn(s).toList}\] +\noindent finds all +substrings in \texttt{s} according to a regular regular expression +\texttt{reg}; useful list operations: \texttt{.distinct} +removing duplicates from a list, \texttt{.count} counts the number of +elements in a list that satisfy some condition, \texttt{.toMap} +transfers a list of pairs into a Map, \texttt{.sum} adds up a list of +integers, \texttt{.max} calculates the maximum of a list.\bigskip + + + +\newpage +\subsection*{Preliminary Part (3 Marks, file docdiff.scala)} + +It seems source code plagiarism---stealing and submitting someone +else's code---is a serious problem at other +universities.\footnote{Surely, King's students, after all their + instructions and warnings, would never commit such an offence. Yes?} +Detecting such plagiarism is time-consuming and disheartening for +lecturers at those universities. To aid these poor souls, let's +implement in this part a program that determines the similarity +between two documents (be they source code or texts in English). A +document will be represented as a list of strings. + + +\subsection*{Tasks} + +\begin{itemize} +\item[(1)] Implement a function that `cleans' a string by finding all + (proper) words in this string. For this use the regular expression + \texttt{\textbackslash{}w+} for recognising words and the library function + \texttt{findAllIn}. The function should return a document (a list of + strings).\\ + \mbox{}\hfill [0.5 Marks] + +\item[(2)] In order to compute the overlap between two documents, we + associate each document with a \texttt{Map}. This Map represents the + strings in a document and how many times these strings occur in the + document. A simple (though slightly inefficient) method for counting + the number of string-occurrences in a document is as follows: remove + all duplicates from the document; for each of these (unique) + strings, count how many times they occur in the original document. + Return a Map associating strings with occurrences. For example + + \begin{center} + \pcode{occurrences(List("a", "b", "b", "c", "d"))} + \end{center} + + produces \pcode{Map(a -> 1, b -> 2, c -> 1, d -> 1)} and + + \begin{center} + \pcode{occurrences(List("d", "b", "d", "b", "d"))} + \end{center} + + produces \pcode{Map(d -> 3, b -> 2)}.\hfill[1 Mark] + +\item[(3)] You can think of the Maps calculated under (2) as memory-efficient + representations of sparse ``vectors''. In this subtask you need to + implement the \emph{product} of two such vectors, sometimes also called + \emph{dot product} of two vectors.\footnote{\url{https://en.wikipedia.org/wiki/Dot_product}} + + For this dot product, implement a function that takes two documents + (\texttt{List[String]}) as arguments. The function first calculates + the (unique) strings in both. For each string, it multiplies the + corresponding occurrences in each document. If a string does not + occur in one of the documents, then the product for this string is zero. At the end + you need to add up all products. For the two documents in (2) the dot + product is 7, because + + \[ + \underbrace{1 * 0}_{"a"} \;\;+\;\; + \underbrace{2 * 2}_{"b"} \;\;+\;\; + \underbrace{1 * 0}_{"c"} \;\;+\;\; + \underbrace{1 * 3}_{"d"} \qquad = 7 + \] + + \hfill\mbox{[1 Mark]} + +\item[(4)] Implement first a function that calculates the overlap + between two documents, say $d_1$ and $d_2$, according to the formula + + \[ + \texttt{overlap}(d_1, d_2) = \frac{d_1 \cdot d_2}{max(d_1^2, d_2^2)} + \] + + where $d_1^2$ means $d_1 \cdot d_1$ and so on. + You can expect this function to return a \texttt{Double} between 0 and 1. The + overlap between the lists in (2) is $0.5384615384615384$. + + Second, implement a function that calculates the similarity of + two strings, by first extracting the substrings using the clean + function from (1) + and then calculating the overlap of the resulting documents.\\ + \mbox{}\hfill\mbox{[0.5 Marks]} +\end{itemize} + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solition1/collatz.jar Binary file pre_solition1/collatz.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solition1/collatz.scala --- a/pre_solition1/collatz.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,50 +0,0 @@ -// Basic Part about the 3n+1 conjecture -//================================== - -// generate jar with -// > scala -d collatz.jar collatz.scala - -object CW6a { // for purposes of generating a jar - -def collatz(n: Long): Long = - if (n == 1) 0 else - if (n % 2 == 0) 1 + collatz(n / 2) else - 1 + collatz(3 * n + 1) - - -def collatz_max(bnd: Long): (Long, Long) = { - val all = for (i <- (1L to bnd)) yield (collatz(i), i) - all.maxBy(_._1) -} - -//collatz_max(1000000) -//collatz_max(10000000) -//collatz_max(100000000) - -/* some test cases -val bnds = List(10, 100, 1000, 10000, 100000, 1000000) - -for (bnd <- bnds) { - val (steps, max) = collatz_max(bnd) - println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") -} - -*/ - -def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 - -def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) - -def last_odd(n: Long) : Long = - if (is_hard(n)) n else - if (n % 2 == 0) last_odd(n / 2) else - last_odd(3 * n + 1) - - -//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") -for (i <- 1 to 100) println(s"$i: ${collatz(i)}") - -} - - - diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution1/collatz.jar Binary file pre_solution1/collatz.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution1/collatz.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_solution1/collatz.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,50 @@ +// Basic Part about the 3n+1 conjecture +//================================== + +// generate jar with +// > scala -d collatz.jar collatz.scala + +object CW6a { // for purposes of generating a jar + +def collatz(n: Long): Long = + if (n == 1) 0 else + if (n % 2 == 0) 1 + collatz(n / 2) else + 1 + collatz(3 * n + 1) + + +def collatz_max(bnd: Long): (Long, Long) = { + val all = for (i <- (1L to bnd)) yield (collatz(i), i) + all.maxBy(_._1) +} + +//collatz_max(1000000) +//collatz_max(10000000) +//collatz_max(100000000) + +/* some test cases +val bnds = List(10, 100, 1000, 10000, 100000, 1000000) + +for (bnd <- bnds) { + val (steps, max) = collatz_max(bnd) + println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") +} + +*/ + +def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 + +def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) + +def last_odd(n: Long) : Long = + if (is_hard(n)) n else + if (n % 2 == 0) last_odd(n / 2) else + last_odd(3 * n + 1) + + +//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") +for (i <- 1 to 100) println(s"$i: ${collatz(i)}") + +} + + + diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution2/docdiff.jar Binary file pre_solution2/docdiff.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution2/docdiff.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_solution2/docdiff.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,117 @@ +// Preliminary Part about Code Similarity +//======================================== + + +object CW7a { + +//(1) Complete the clean function below. It should find +// all words in a string using the regular expression +// \w+ and the library function +// +// some_regex.findAllIn(some_string) +// +// The words should be Returned as a list of strings. + +def clean(s: String) : List[String] = + ("""\w+""".r).findAllIn(s).toList + + +//(2) The function occurrences calculates the number of times +// strings occur in a list of strings. These occurrences should +// be calculated as a Map from strings to integers. + +def occurrences(xs: List[String]): Map[String, Int] = + (for (x <- xs.distinct) yield (x, xs.count(_ == x))).toMap + +//(3) This functions calculates the dot-product of two documents +// (list of strings). For this it calculates the occurrence +// maps from (2) and then multiplies the corresponding occurrences. +// If a string does not occur in a document, the product is zero. +// The function finally sums up all products. + +def prod(lst1: List[String], lst2: List[String]) : Int = { + val words = (lst1 ::: lst2).distinct + val occs1 = occurrences(lst1) + val occs2 = occurrences(lst2) + words.map{ w => occs1.getOrElse(w, 0) * occs2.getOrElse(w, 0) }.sum +} + +//(4) Complete the functions overlap and similarity. The overlap of +// two documents is calculated by the formula given in the assignment +// description. The similarity of two strings is given by the overlap +// of the cleaned (see (1)) strings. + +def overlap(lst1: List[String], lst2: List[String]) : Double = { + val m1 = prod(lst1, lst1) + val m2 = prod(lst2, lst2) + prod(lst1, lst2).toDouble / (List(m1, m2).max) +} + +def similarity(s1: String, s2: String) : Double = + overlap(clean(s1), clean(s2)) + + +/* + + +val list1 = List("a", "b", "b", "c", "d") +val list2 = List("d", "b", "d", "b", "d") + +occurrences(List("a", "b", "b", "c", "d")) // Map(a -> 1, b -> 2, c -> 1, d -> 1) +occurrences(List("d", "b", "d", "b", "d")) // Map(d -> 3, b -> 2) + +prod(list1,list2) // 7 + +overlap(list1, list2) // 0.5384615384615384 +overlap(list2, list1) // 0.5384615384615384 +overlap(list1, list1) // 1.0 +overlap(list2, list2) // 1.0 + +// Plagiarism examples from +// https://desales.libguides.com/avoidingplagiarism/examples + +val orig1 = """There is a strong market demand for eco-tourism in +Australia. Its rich and diverse natural heritage ensures Australia's +capacity to attract international ecotourists and gives Australia a +comparative advantage in the highly competitive tourism industry.""" + +val plag1 = """There is a high market demand for eco-tourism in +Australia. Australia has a comparative advantage in the highly +competitive tourism industry due to its rich and varied natural +heritage which ensures Australia's capacity to attract international +ecotourists.""" + +similarity(orig1, plag1) + + +// Plagiarism examples from +// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php + +val orig2 = """No oil spill is entirely benign. Depending on timing and +location, even a relatively minor spill can cause significant harm to +individual organisms and entire populations. Oil spills can cause +impacts over a range of time scales, from days to years, or even +decades for certain spills. Impacts are typically divided into acute +(short-term) and chronic (long-term) effects. Both types are part of a +complicated and often controversial equation that is addressed after +an oil spill: ecosystem recovery.""" + +val plag2 = """There is no such thing as a "good" oil spill. If the +time and place are just right, even a small oil spill can cause damage +to sensitive ecosystems. Further, spills can cause harm days, months, +years, or even decades after they occur. Because of this, spills are +usually broken into short-term (acute) and long-term (chronic) +effects. Both of these types of harm must be addressed in ecosystem +recovery: a controversial tactic that is often implemented immediately +following an oil spill.""" + +overlap(clean(orig2), clean(plag2)) +similarity(orig2, plag2) + +// The punchline: everything above 0.6 looks suspicious and +// should be looked at by staff. + +*/ + + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution3/postfix.jar Binary file pre_solution3/postfix.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution3/postfix.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_solution3/postfix.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,103 @@ +// Shunting Yard Algorithm +// by Edsger Dijkstra +// ======================== + +object CW8a { + +type Toks = List[String] + +// the operations in the simple version +val ops = List("+", "-", "*", "/") + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2) + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// (6) Implement below the shunting yard algorithm. The most +// convenient way to this in Scala is to implement a recursive +// function and to heavily use pattern matching. The function syard +// takes some input tokens as first argument. The second and third +// arguments represent the stack and the output of the shunting yard +// algorithm. +// +// In the marking, you can assume the function is called only with +// an empty stack and an empty output list. You can also assume the +// input os only properly formatted (infix) arithmetic expressions +// (all parentheses will be well-nested, the input only contains +// operators and numbers). + +// You can implement any additional helper function you need. I found +// it helpful to implement two auxiliary functions for the pattern matching: +// + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) + + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + + +// test cases +//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + +//syard(split("10 + 12 * 33")) // 10 12 33 * + +//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * +//syard(split("5 + 7 / 2")) // 5 7 2 / + +//syard(split("5 * 7 / 2")) // 5 7 * 2 / +//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + + +//syard(split("3 + 4 + 5")) // 3 4 + 5 + +//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + +//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + +//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + + +// (7) Implement a compute function that evaluates an input list +// in postfix notation. This function takes a list of tokens +// and a stack as argumenta. The function should produce the +// result as an integer using the stack. You can assume +// this function will be only called with proper postfix +// expressions. + +def op_comp(s: String, n1: Int, n2: Int) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 +} + +def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +} + + diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution3/postfix2.jar Binary file pre_solution3/postfix2.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_solution3/postfix2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_solution3/postfix2.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,100 @@ +// Shunting Yard Algorithm +// including Associativity for Operators +// ===================================== + +object CW8b { + +// type of tokens +type Toks = List[String] + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// left- and right-associativity +abstract class Assoc +case object LA extends Assoc +case object RA extends Assoc + +// power is right-associative, +// everything else is left-associative +def assoc(s: String) : Assoc = s match { + case "^" => RA + case _ => LA +} + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2, + "^" -> 4) + +// the operations in the basic version of the algorithm +val ops = List("+", "-", "*", "/", "^") + +// (8) Implement the extended version of the shunting yard algorithm. +// This version should properly account for the fact that the power +// operation is right-associative. Apart from the extension to include +// the power operation, you can make the same assumptions as in +// basic version. + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = assoc(op1) match { + case LA => precs(op1) <= precs(op2) + case RA => precs(op1) < precs(op2) +} + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + +def op_comp(s: String, n1: Int, n2: Int) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 + case "^" => BigInt(n2).pow(n1).toInt +} + +def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + + + + +//compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +//compute(syard(split("10 + 12 * 33"))) // 406 +//compute(syard(split("( 5 + 7 ) * 2"))) // 24 +//compute(syard(split("5 + 7 / 2"))) // 8 +//compute(syard(split("5 * 7 / 2"))) // 17 +//compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +//compute(syard(split("4 ^ 3 ^ 2"))) // 262144 +//compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 +//compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + +//syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + +//compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) // 3 + +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + + + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates1/collatz.jar Binary file pre_templates1/collatz.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates2/docdiff.jar Binary file pre_templates2/docdiff.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates2/docdiff.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_templates2/docdiff.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,115 @@ +// Preliminary Part about Code Similarity +//======================================== + + +object CW7a { + + +//(1) Complete the clean function below. It should find +// all words in a string using the regular expression +// \w+ and the library function +// +// some_regex.findAllIn(some_string) +// +// The words should be Returned as a list of strings. + + +def clean(s: String) : List[String] = ??? + + + +//(2) The function occurrences calculates the number of times +// strings occur in a list of strings. These occurrences should +// be calculated as a Map from strings to integers. + + +def occurrences(xs: List[String]): Map[String, Int] = ??? + + +//(3) This functions calculates the dot-product of two documents +// (list of strings). For this it calculates the occurrence +// maps from (2) and then multiplies the corresponding occurrences. +// If a string does not occur in a document, the product is zero. +// The function finally sums up all products. + + +def prod(lst1: List[String], lst2: List[String]) : Int = ??? + + +//(4) Complete the functions overlap and similarity. The overlap of +// two documents is calculated by the formula given in the assignment +// description. The similarity of two strings is given by the overlap +// of the cleaned strings (see (1)). + + +def overlap(lst1: List[String], lst2: List[String]) : Double = ??? + +def similarity(s1: String, s2: String) : Double = ??? + + + +/* Test cases + + +val list1 = List("a", "b", "b", "c", "d") +val list2 = List("d", "b", "d", "b", "d") + +occurrences(List("a", "b", "b", "c", "d")) // Map(a -> 1, b -> 2, c -> 1, d -> 1) +occurrences(List("d", "b", "d", "b", "d")) // Map(d -> 3, b -> 2) + +prod(list1,list2) // 7 + +overlap(list1, list2) // 0.5384615384615384 +overlap(list2, list1) // 0.5384615384615384 +overlap(list1, list1) // 1.0 +overlap(list2, list2) // 1.0 + +// Plagiarism examples from +// https://desales.libguides.com/avoidingplagiarism/examples + +val orig1 = """There is a strong market demand for eco-tourism in +Australia. Its rich and diverse natural heritage ensures Australia's +capacity to attract international ecotourists and gives Australia a +comparative advantage in the highly competitive tourism industry.""" + +val plag1 = """There is a high market demand for eco-tourism in +Australia. Australia has a comparative advantage in the highly +competitive tourism industry due to its rich and varied natural +heritage which ensures Australia's capacity to attract international +ecotourists.""" + +similarity(orig1, plag1) // 0.8679245283018868 + + +// Plagiarism examples from +// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php + +val orig2 = """No oil spill is entirely benign. Depending on timing and +location, even a relatively minor spill can cause significant harm to +individual organisms and entire populations. Oil spills can cause +impacts over a range of time scales, from days to years, or even +decades for certain spills. Impacts are typically divided into acute +(short-term) and chronic (long-term) effects. Both types are part of a +complicated and often controversial equation that is addressed after +an oil spill: ecosystem recovery.""" + +val plag2 = """There is no such thing as a "good" oil spill. If the +time and place are just right, even a small oil spill can cause damage +to sensitive ecosystems. Further, spills can cause harm days, months, +years, or even decades after they occur. Because of this, spills are +usually broken into short-term (acute) and long-term (chronic) +effects. Both of these types of harm must be addressed in ecosystem +recovery: a controversial tactic that is often implemented immediately +following an oil spill.""" + +overlap(clean(orig2), clean(plag2)) // 0.728 +similarity(orig2, plag2) // 0.728 + + + +// The punchline: everything above 0.6 looks suspicious and +// should be investigated by staff. + +*/ + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates3/postfix.jar Binary file pre_templates3/postfix.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates3/postfix.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_templates3/postfix.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,81 @@ +// Shunting Yard Algorithm +// by Edsger Dijkstra +// ======================== + +object CW8a { + +// type of tokens +type Toks = List[String] + +// the operations in the basic version of the algorithm +val ops = List("+", "-", "*", "/") + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2) + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + + +// (1) Implement below the shunting yard algorithm. The most +// convenient way to this in Scala is to implement a recursive +// function and to heavily use pattern matching. The function syard +// takes some input tokens as first argument. The second and third +// arguments represent the stack and the output of the shunting yard +// algorithm. +// +// In the marking, you can assume the function is called only with +// an empty stack and an empty output list. You can also assume the +// input os only properly formatted (infix) arithmetic expressions +// (all parentheses will be well-nested, the input only contains +// operators and numbers). + +// You can implement any additional helper function you need. I found +// it helpful to implement two auxiliary functions for the pattern matching: +// + +def is_op(op: String) : Boolean = ??? +def prec(op1: String, op2: String) : Boolean = ??? + + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? + + +// test cases +//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + +//syard(split("10 + 12 * 33")) // 10 12 33 * + +//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * +//syard(split("5 + 7 / 2")) // 5 7 2 / + +//syard(split("5 * 7 / 2")) // 5 7 * 2 / +//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + + +//syard(split("3 + 4 + 5")) // 3 4 + 5 + +//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + +//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + +//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + + + +// (2) Implement a compute function that evaluates an input list +// in postfix notation. This function takes a list of tokens +// and a stack as argumenta. The function should produce the +// result as an integer using the stack. You can assume +// this function will be only called with proper postfix +// expressions. + +def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? + + +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +} + + diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates3/postfix2.jar Binary file pre_templates3/postfix2.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates3/postfix2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_templates3/postfix2.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,69 @@ +// Shunting Yard Algorithm +// including Associativity for Operators +// ===================================== + +object CW8b { + + +// type of tokens +type Toks = List[String] + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// left- and right-associativity +abstract class Assoc +case object LA extends Assoc +case object RA extends Assoc + + +// power is right-associative, +// everything else is left-associative +def assoc(s: String) : Assoc = s match { + case "^" => RA + case _ => LA +} + + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2, + "^" -> 4) + +// the operations in the basic version of the algorithm +val ops = List("+", "-", "*", "/", "^") + +// (3) Implement the extended version of the shunting yard algorithm. +// This version should properly account for the fact that the power +// operation is right-associative. Apart from the extension to include +// the power operation, you can make the same assumptions as in +// basic version. + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ??? + + +// test cases +// syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + + + +// (4) Implement a compute function that produces an Int for an +// input list of tokens in postfix notation. + +def compute(toks: Toks, st: List[Int] = Nil) : Int = ??? + + +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 +// compute(syard(split("4 ^ 3 ^ 2"))) // 262144 +// compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 +// compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 +// compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_templates4/knight1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_templates4/knight1.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,114 @@ +// Preliminary Part about finding Knight's tours +//=============================================== + + +object CW8a { + +// If you need any auxiliary function, feel free to +// implement it, but do not make any changes to the +// templates below. Also have a look whether the functions +// at the end are of any help. + + + +type Pos = (Int, Int) // a position on a chessboard +type Path = List[Pos] // a path...a list of positions + +//(1) Complete the function that tests whether the position x +// is inside the board and not yet element in the path. + +//def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ... + + + +//(2) Complete the function that calculates for a position x +// all legal onward moves that are not already in the path. +// The moves should be ordered in a "clockwise" manner. + + +//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... + + +//some testcases +// +//assert(legal_moves(8, Nil, (2,2)) == +// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) + + +//(3) Complete the two recursive functions below. +// They exhaustively search for knight's tours starting from the +// given path. The first function counts all possible tours, +// and the second collects all tours in a list of paths. + +//def count_tours(dim: Int, path: Path) : Int = ... + +//def enum_tours(dim: Int, path: Path) : List[Path] = ... + + +//(4) Implement a first-function that finds the first +// element, say x, in the list xs where f is not None. +// In that case Return f(x), otherwise None. If possible, +// calculate f(x) only once. + +//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... + + +// testcases +// +//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None +// +//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) +//first(List((1, 0),(2, 0),(3, 0)), foo) // None + + +//(5) Implement a function that uses the first-function from (5) for +// trying out onward moves, and searches recursively for a +// knight tour on a dim * dim-board. + + +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + + +/* Helper functions + + +// for measuring time +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + +// can be called for example with +// time_needed(count_tours(dim, List((0, 0)))) +// in order to print out the time that is needed for +// running count_tours + + + + +// for printing a board +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") + } + println + } +} + + +*/ + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing1/collatz.scala --- a/pre_testing1/collatz.scala Sat Oct 31 16:47:46 2020 +0000 +++ b/pre_testing1/collatz.scala Sun Nov 01 01:21:31 2020 +0000 @@ -1,37 +1,51 @@ -object CW6a { +// Basic Part about the 3n+1 conjecture +//================================== + +// generate jar with +// > scala -d collatz.jar collatz.scala + +object CW6a { // for purposes of generating a jar -//(1) Complete the collatz function below. It should -// recursively calculate the number of steps needed -// until the collatz series reaches the number 1. -// If needed, you can use an auxiliary function that -// performs the recursion. The function should expect -// arguments in the range of 1 to 1 Million. -def stepsCounter(n: Long, s: Long) : Long = n match{ - case 1 => s - case n if(n%2==0) => stepsCounter(n/2,s+1) - case _ => stepsCounter(3*n+1, s+1) +def collatz(n: Long): Long = + if (n == 1) 0 else + if (n % 2 == 0) 1 + collatz(n / 2) else + 1 + collatz(3 * n + 1) + + +def collatz_max(bnd: Long): (Long, Long) = { + val all = for (i <- (1L to bnd)) yield (collatz(i), i) + all.maxBy(_._1) } -def collatz(n: Long) : Long = n match { - case n if(n>0) => stepsCounter(n,0) - case n if(n<=0) => stepsCounter(1,0) +//collatz_max(1000000) +//collatz_max(10000000) +//collatz_max(100000000) + + +/* some test cases +val bnds = List(10, 100, 1000, 10000, 100000, 1000000) + +for (bnd <- bnds) { + val (steps, max) = collatz_max(bnd) + println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") +} + +*/ + +def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 + +def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) + +def last_odd(n: Long) : Long = + if (is_hard(n)) n else + if (n % 2 == 0) last_odd(n / 2) else + last_odd(3 * n + 1) + + +//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") +for (i <- 1 to 100) println(s"$i: ${collatz(i)}") + } -//(2) Complete the collatz_max function below. It should -// calculate how many steps are needed for each number -// from 1 up to a bound and then calculate the maximum number of -// steps and the corresponding number that needs that many -// steps. Again, you should expect bounds in the range of 1 -// up to 1 Million. The first component of the pair is -// the maximum number of steps and the second is the -// corresponding number. - -def collatz_max(bnd: Long) : (Long, Long) = { - val allCollatz = for(i<-1L until bnd) yield collatz(i) - val pair = (allCollatz.max, (allCollatz.indexOf(allCollatz.max) +1).toLong) - pair -} - -} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing1/collatz_test.sh --- a/pre_testing1/collatz_test.sh Sat Oct 31 16:47:46 2020 +0000 +++ b/pre_testing1/collatz_test.sh Sun Nov 01 01:21:31 2020 +0000 @@ -15,7 +15,7 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) } # functional tests @@ -27,41 +27,41 @@ # purity test function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|collection.mutable|util.control|new Array' "$1" 2> /dev/null 1> /dev/null) + (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null) } +### compilation test + +echo -e "collatz.scala runs?" >> $out + +if (scala_compile collatz.scala) +then + echo -e " --> success" >> $out + tsts=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN collatz.scala\n" >> $out + tsts=$(( 1 )) +fi + + + # var, .par return, ListBuffer test # -echo -e "collatz.scala does not contain vars, returns etc?" >> $out - -if (scala_vars collatz.scala) -then - echo -e " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out - tsts0=$(( 0 )) -else - echo -e " --> success" >> $out - tsts0=$(( 0 )) -fi - -### compilation test - +echo -e "collatz.scala does not contain VARS, RETURNS etc?" >> $out -if [ $tsts0 -eq 0 ] +if [ $tsts -eq 0 ] then - echo -e "collatz.scala runs?" >> $out + if (scala_vars collatz.scala) + then + echo -e " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out + tsts=$(( 1 )) + else + echo -e " --> success" >> $out + tsts=$(( 0 )) + fi +fi - if (scala_compile collatz.scala) - then - echo -e " --> success" >> $out - tsts=$(( 0 )) - else - echo -e " --> SCALA DID NOT RUN COLLATZ.SCALA\n" >> $out - tsts=$(( 1 )) - fi -else - tsts=$(( 1 )) -fi ### collatz tests diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,101 @@ +// Preliminary Part about Code Similarity +//======================================== + +object CW7a { + + +//(1) Complete the clean function below. It should find +// all words in a string using the regular expression +// \w+ and the library function +// +// some_regex.findAllIn(some_string) +// +// The words should be Returned as a list of strings. + + +//def clean(s: String) : List[String] = ... +def clean(s: String) : List[String] = + "\\w+".r.findAllIn(s).toList + +//(2) The function occurrences calculates the number of times +// strings occur in a list of strings. These occurrences should +// be calculated as a Map from strings to integers. + + +//def occurrences(xs: List[String]): Map[String, Int] = .. +def occurrences(xs: List[String]) : Map[String, Int] = + xs.groupBy(identity).view.mapValues(_.size).toMap + +//(3) This functions calculates the dot-product of two documents +// (list of strings). For this it calculates the occurrence +// maps from (2) and then multiplies the corresponding occurrences. +// If a string does not occur in a document, the product is zero. +// The function finally sums up all products. + + +//def prod(lst1: List[String], lst2: List[String]) : Int = .. +def prod(lst1: List[String], lst2: List[String]) : Int = + occurrences(lst1).map(x => occurrences(lst2).getOrElse(x._1, 0) * x._2).reduce(_ + _) + +//(4) Complete the functions overlap and similarity. The overlap of +// two documents is calculated by the formula given in the assignment +// description. The similarity of two strings is given by the overlap +// of the cleaned strings (see (1)). + + +//def overlap(lst1: List[String], lst2: List[String]) : Double = ... +def overlap(lst1: List[String], lst2: List[String]) : Double = + prod(lst1, lst2).toDouble/Math.max(prod(lst1, lst1).toDouble, prod(lst2, lst2).toDouble) +//def similarity(s1: String, s2: String) : Double = ... +def similarity(s1: String, s2: String) : Double = + overlap(clean(s1), clean(s2)) + + +/* Test cases +import CW7a._ +val list1 = List("a", "b", "b", "c", "d") +val list2 = List("d", "b", "d", "b", "d") +occurrences(List("a", "b", "b", "c", "d")) +occurrences(List("d", "b", "d", "b", "d")) +prod(list1,list2) // 7 +overlap(list1, list2) // 0.5384615384615384 +overlap(list2, list1) // 0.5384615384615384 +overlap(list1, list1) // 1.0 +overlap(list2, list2) // 1.0 +// Plagiarism examples from +// https://desales.libguides.com/avoidingplagiarism/examples +val orig1 = """There is a strong market demand for eco-tourism in +Australia. Its rich and diverse natural heritage ensures Australia's +capacity to attract international ecotourists and gives Australia a +comparative advantage in the highly competitive tourism industry.""" +val plag1 = """There is a high market demand for eco-tourism in +Australia. Australia has a comparative advantage in the highly +competitive tourism industry due to its rich and varied natural +heritage which ensures Australia's capacity to attract international +ecotourists.""" +similarity(orig1, plag1) // 0.8679245283018868 +// Plagiarism examples from +// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php +val orig2 = """No oil spill is entirely benign. Depending on timing and +location, even a relatively minor spill can cause significant harm to +individual organisms and entire populations. Oil spills can cause +impacts over a range of time scales, from days to years, or even +decades for certain spills. Impacts are typically divided into acute +(short-term) and chronic (long-term) effects. Both types are part of a +complicated and often controversial equation that is addressed after +an oil spill: ecosystem recovery.""" +val plag2 = """There is no such thing as a "good" oil spill. If the +time and place are just right, even a small oil spill can cause damage +to sensitive ecosystems. Further, spills can cause harm days, months, +years, or even decades after they occur. Because of this, spills are +usually broken into short-term (acute) and long-term (chronic) +effects. Both of these types of harm must be addressed in ecosystem +recovery: a controversial tactic that is often implemented immediately +following an oil spill.""" +overlap(clean(orig2), clean(plag2)) // 0.728 +similarity(orig2, plag2) // 0.728 +// The punchline: everything above 0.6 looks suspicious and +// should be investigated by staff. +*/ + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff_test.sh Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,135 @@ +#!/bin/bash + +# to make the script fail safely +set -euo pipefail + + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback for your submission docdiff.scala" >> $out +echo "" >> $out + + +# compilation tests + +function scala_compile { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) +} + +# functional tests + +function scala_assert { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null) +} + + + +### compilation test + +echo -e "docdiff.scala runs?" >> $out + +if (scala_compile docdiff.scala) +then + echo -e " --> success" >> $out + tsts=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN docdiff.scala\n" >> $out + tsts=$(( 1 )) +fi + + +# var, .par return, ListBuffer test +# +echo -e "docdiff.scala does not contain vars, returns etc?" >> $out + +if [ $tsts -eq 0 ] +then + if (scala_vars docdiff.scala) + then + echo -e " --> FAIL (make triple-sure your program conforms to the required format)\n" >> $out + tsts=$(( 1 )) + else + echo -e " --> success" >> $out + tsts=$(( 0 )) + fi +fi + +### docdiff clean tests + +if [ $tsts -eq 0 ] +then + echo -e "docdiff.scala tests:" >> $out + echo -e " clean(\"ab a abc\") == List(\"ab\", \"a\", \"abc\")" >> $out + echo -e " clean(\"ab*a abc1\") == List(\"ab\", \"a\", \"abc1\")" >> $out + + if (scala_assert "docdiff.scala" "docdiff_test1.scala") + then + echo -e " --> success\n" >> $out + else + echo -e " --> ONE OF THE TESTS FAILED\n" >> $out + fi +fi + +### docdiff occurrences tests + +if [ $tsts -eq 0 ] +then + echo -e " occurrences(List(\"a\", \"b\", \"b\", \"c\", \"d\")) == " >> $out + echo -e " Map(\"a\" -> 1, \"b\" -> 2, \"c\" -> 1, \"d\" -> 1)" >> $out + echo -e " " >> $out + echo -e " occurrences(List(\"d\", \"b\", \"d\", \"b\", \"d\")) == " >> $out + echo -e " Map(\"d\" -> 3, \"b\" -> 2)" >> $out + + if (scala_assert "docdiff.scala" "docdiff_test2.scala") + then + echo -e " --> success\n" >> $out + else + echo -e " --> ONE OF THE TESTS FAILED\n" >> $out + fi +fi + +### docdiff prod tests + +if [ $tsts -eq 0 ] +then + echo -e " val l1 = List(\"a\", \"b\", \"b\", \"c\", \"d\")" >> $out + echo -e " val l2 = List(\"d\", \"b\", \"d\", \"b\", \"d\")" >> $out + echo -e " " >> $out + echo -e " prod(l1, l2) == 7 " >> $out + echo -e " prod(l1, l1) == 7 " >> $out + echo -e " prod(l2, l2) == 13 " >> $out + + if (scala_assert "docdiff.scala" "docdiff_test3.scala") + then + echo -e " --> success\n" >> $out + else + echo -e " --> ONE OF THE TESTS FAILED\n" >> $out + fi +fi + +### docdiff overlap tests + +if [ $tsts -eq 0 ] +then + echo -e " val l1 = List(\"a\", \"b\", \"b\", \"c\", \"d\")" >> $out + echo -e " val l2 = List(\"d\", \"b\", \"d\", \"b\", \"d\")" >> $out + echo -e " " >> $out + echo -e " overlap(l1, l2) == 0.5384615384615384 " >> $out + echo -e " overlap(l1, l1) == 1.0 " >> $out + echo -e " overlap(l2, l2) == 1.0 " >> $out + + if (scala_assert "docdiff.scala" "docdiff_test4.scala") + then + echo -e " --> success\n" >> $out + else + echo -e " --> ONE OF THE TESTS FAILED\n" >> $out + fi +fi diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff_test1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff_test1.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,6 @@ + +import CW7a._ + +assert(clean("ab a abc") == List("ab", "a", "abc")) + +assert(clean("ab*a abc1") == List("ab", "a", "abc1")) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff_test2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff_test2.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,6 @@ + +import CW7a._ + +assert(occurrences(List("a", "b", "b", "c", "d")) == Map("a" -> 1, "b" -> 2, "c" -> 1, "d" -> 1)) + +assert(occurrences(List("d", "b", "d", "b", "d")) == Map("d" -> 3, "b" -> 2)) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff_test3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff_test3.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,11 @@ + +import CW7a._ + +val urban_list1 = List("a", "b", "b", "c", "d") +val urban_list2 = List("d", "b", "d", "b", "d") + +assert(prod(urban_list1, urban_list2) == 7) + +assert(prod(urban_list1, urban_list1) == 7) + +assert(prod(urban_list2, urban_list2) == 13) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing2/docdiff_test4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing2/docdiff_test4.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,11 @@ + +import CW7a._ + +val urban_list1 = List("a", "b", "b", "c", "d") +val urban_list2 = List("d", "b", "d", "b", "d") + +assert(overlap(urban_list1, urban_list2) == 0.5384615384615384) + +assert(overlap(urban_list1, urban_list1) == 1.0) + +assert(overlap(urban_list2, urban_list2) == 1.0) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,103 @@ +// Shunting Yard Algorithm +// by Edsger Dijkstra +// ======================== + +object CW8a { + +type Toks = List[String] + +// the operations in the simple version +val ops = List("+", "-", "*", "/") + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2) + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// (6) Implement below the shunting yard algorithm. The most +// convenient way to this in Scala is to implement a recursive +// function and to heavily use pattern matching. The function syard +// takes some input tokens as first argument. The second and third +// arguments represent the stack and the output of the shunting yard +// algorithm. +// +// In the marking, you can assume the function is called only with +// an empty stack and an empty output list. You can also assume the +// input os only properly formatted (infix) arithmetic expressions +// (all parentheses will be well-nested, the input only contains +// operators and numbers). + +// You can implement any additional helper function you need. I found +// it helpful to implement two auxiliary functions for the pattern matching: +// + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) + + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + + +// test cases +//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + +//syard(split("10 + 12 * 33")) // 10 12 33 * + +//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * +//syard(split("5 + 7 / 2")) // 5 7 2 / + +//syard(split("5 * 7 / 2")) // 5 7 * 2 / +//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + + +//syard(split("3 + 4 + 5")) // 3 4 + 5 + +//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + +//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + +//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + + +// (7) Implement a compute function that evaluates an input list +// in postfix notation. This function takes a list of tokens +// and a stack as argumenta. The function should produce the +// result as an integer using the stack. You can assume +// this function will be only called with proper postfix +// expressions. + +def op_comp(s: String, n1: Int, n2: Int) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 +} + +def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + +// test cases +// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +// compute(syard(split("10 + 12 * 33"))) // 406 +// compute(syard(split("( 5 + 7 ) * 2"))) // 24 +// compute(syard(split("5 + 7 / 2"))) // 8 +// compute(syard(split("5 * 7 / 2"))) // 17 +// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +} + + diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix2.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,100 @@ +// Shunting Yard Algorithm +// including Associativity for Operators +// ===================================== + +object CW8b { + +// type of tokens +type Toks = List[String] + +// helper function for splitting strings into tokens +def split(s: String) : Toks = s.split(" ").toList + +// left- and right-associativity +abstract class Assoc +case object LA extends Assoc +case object RA extends Assoc + +// power is right-associative, +// everything else is left-associative +def assoc(s: String) : Assoc = s match { + case "^" => RA + case _ => LA +} + +// the precedences of the operators +val precs = Map("+" -> 1, + "-" -> 1, + "*" -> 2, + "/" -> 2, + "^" -> 4) + +// the operations in the basic version of the algorithm +val ops = List("+", "-", "*", "/", "^") + +// (8) Implement the extended version of the shunting yard algorithm. +// This version should properly account for the fact that the power +// operation is right-associative. Apart from the extension to include +// the power operation, you can make the same assumptions as in +// basic version. + +def is_op(op: String) : Boolean = ops.contains(op) + +def prec(op1: String, op2: String) : Boolean = assoc(op1) match { + case LA => precs(op1) <= precs(op2) + case RA => precs(op1) < precs(op2) +} + +def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { + case (Nil, _, _) => out.reverse ::: st + case (num::in, st, out) if (num.forall(_.isDigit)) => + syard(in, st, num :: out) + case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => + syard(op1::in, st, op2 :: out) + case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) + case ("("::in, st, out) => syard(in, "("::st, out) + case (")"::in, op2::st, out) => + if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) + case (in, st, out) => { + println(s"in: ${in} st: ${st} out: ${out.reverse}") + Nil + } +} + +def op_comp(s: String, n1: Long, n2: Long) = s match { + case "+" => n2 + n1 + case "-" => n2 - n1 + case "*" => n2 * n1 + case "/" => n2 / n1 + case "^" => Math.pow(n2, n1).toLong +} + +def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match { + case (Nil, st) => st.head + case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) + case (num::in, st) => compute(in, num.toInt::st) +} + + + + +//compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 +//compute(syard(split("10 + 12 * 33"))) // 406 +//compute(syard(split("( 5 + 7 ) * 2"))) // 24 +//compute(syard(split("5 + 7 / 2"))) // 8 +//compute(syard(split("5 * 7 / 2"))) // 17 +//compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 + +//compute(syard(split("4 ^ 3 ^ 2"))) // 262144 +//compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 +//compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + +//syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + +//compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) // 3 + +//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 + + + +} diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix_test.sh Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,162 @@ +#!/bin/bash +set -euo pipefail + + +out=${1:-output} + +echo -e "" > $out + +echo -e "Below is the feedback for your submission postfix.scala and postfix2.scala" >> $out +echo -e "" >> $out + +# compilation tests + +function scala_compile { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) +} + +# functional tests + +function scala_assert { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null) +} + + + +# compilation test + +echo -e "postfix.scala runs?" >> $out + +if (scala_compile postfix.scala) +then + echo -e " --> yes" >> $out + tsts=$(( 0 )) + else + echo -e " --> SCALA DID NOT RUN postfix.scala\n" >> $out + tsts=$(( 1 )) +fi + + +# var, return, ListBuffer test +# +echo -e "postfix.scala does not contain vars, returns etc?" >> $out + +if [ $tsts -eq 0 ] +then + if (scala_vars postfix.scala) + then + echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out + tsts=$(( 1 )) + else + echo -e " --> success" >> $out + tsts=$(( 0 )) + fi +fi + + +### postfix tests + +if [ $tsts -eq 0 ] +then + echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"\*\", \"+\")" >> $out + echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" >> $out + echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" >> $out + echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"\*\", \"2\", \"/\")" >> $out + + if (scala_assert "postfix.scala" "postfix_test7.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + + + +if [ $tsts -eq 0 ] +then + echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" >> $out + echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" >> $out + echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" >> $out + echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" >> $out + echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" >> $out + echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" >> $out + + if (scala_assert "postfix.scala" "postfix_test8.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + +echo -e "" >> $out + +### postfix2 tests + + +# compilation test + +echo -e "postfix2.scala runs?" >> $out + +if (scala_compile postfix2.scala) +then + echo -e " --> yes" >> $out + tsts1=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN postfix2.scala\n" >> $out + tsts1=$(( 1 )) +fi + + +# var, return, ListBuffer test +# +echo -e "\n\npostfix2.scala does not contain vars, returns etc?" >> $out + +if [ $tsts1 -eq 0 ] +then + if (scala_vars postfix2.scala) + then + echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out + tsts1=$(( 1 )) + else + echo -e " --> success" >> $out + tsts1=$(( 0 )) + fi +fi + + +if [ $tsts1 -eq 0 ] +then + echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"\*\", \"+\")" >> $out + echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" >> $out + echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" >> $out + echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"\*\", \"2\", \"/\")" >> $out + echo -e " syard(split(\"3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3\")) == " >> $out + echo -e " List(\"3\", \"4\", \"8\", \"\*\", \"5\", \"1\", \"-\", \"2\", \"3\", \"^\", \"^\", \"/\", \"+\")" >> $out + echo -e " " >> $out + echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" >> $out + echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" >> $out + echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" >> $out + echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" >> $out + echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" >> $out + echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" >> $out + echo -e " compute(syard(split(\"4 ^ 3 ^ 2\"))) == 262144" >> $out + echo -e " compute(syard(split(\"4 ^ ( 3 ^ 2 )\"))) == 262144" >> $out + echo -e " compute(syard(split(\"( 4 ^ 3 ) ^ 2\"))) == 4096" >> $out + echo -e " compute(syard(split(\"( 3 + 1 ) ^ 2 ^ 3\"))) == 65536" >> $out + + if (scala_assert "postfix2.scala" "postfix_test9.scala") + then + echo -e " --> success" >> $out + else + echo -e " --> \n ONE TEST FAILED\n" >> $out + fi +fi + diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix_test7.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix_test7.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,7 @@ +import CW8a._ + + +assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) +assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) +assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) +assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix_test8.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix_test8.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,8 @@ +import CW8a._ + +assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) +assert(compute(syard(split("10 + 12 * 33"))) == 406) +assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) +assert(compute(syard(split("5 + 7 / 2"))) == 8) +assert(compute(syard(split("5 * 7 / 2"))) == 17) +assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing3/postfix_test9.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing3/postfix_test9.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,21 @@ +import CW8b._ + + +assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) +assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) +assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) +assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) +assert(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) == List("3", "4", "8", "*", "5", "1", "-", "2", "3", "^", "^", "/", "+")) + + + +assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) +assert(compute(syard(split("10 + 12 * 33"))) == 406) +assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) +assert(compute(syard(split("5 + 7 / 2"))) == 8) +assert(compute(syard(split("5 * 7 / 2"))) == 17) +assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) +assert(compute(syard(split("4 ^ 3 ^ 2"))) == 262144) +assert(compute(syard(split("4 ^ ( 3 ^ 2 )"))) == 262144) +assert(compute(syard(split("( 4 ^ 3 ) ^ 2"))) == 4096) +assert(compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) == 65536) diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing4/knight1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pre_testing4/knight1.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,147 @@ +// Preliminary Part about finding Knight's tours +//=============================================== + + +object CW9a { + +// If you need any auxiliary function, feel free to +// implement it, but do not make any changes to the +// templates below. Also have a look whether the functions +// at the end are of any help. + + + +type Pos = (Int, Int) // a position on a chessboard +type Path = List[Pos] // a path...a list of positions + +//(1) Complete the function that tests whether the position x +// is inside the board and not yet element in the path. + +def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { + if ((!(path.contains(x))) && (x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)) + true + else false +} + +//(2) Complete the function that calculates for a position x +// all legal onward moves that are not already in the path. +// The moves should be ordered in a "clockwise" manner. + + +def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {//List[Pos] + val changes = List((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)) + val returnList = (for ((y,z) <- changes) yield( + //println(y,z)-2,-1 + if ((is_legal(dim,path,((x._1 + y) , (x._2 + z)))) == true) + Some(x._1 + y , x._2 + z) + else + None + )) + returnList.flatten +} + + +//some testcases +// +//assert(legal_moves(8, Nil, (2,2)) == + //List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) + + +//(3) Complete the two recursive functions below. +// They exhaustively search for knight's tours starting from the +// given path. The first function counts all possible tours, +// and the second collects all tours in a list of paths. + +def count_tours(dim: Int, path: Path) : Int = (dim,path) match {//Int + case (_, Nil) => 0 + case (0, path) => 0 + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + 0 + else + 1 + else (for (j <- legal_moves(dim,path, path.head)) yield count_tours(dim,j::path)).sum + } +} + +def enum_tours(dim: Int, path: Path) : List[Path] = (dim,path) match { + case (_, Nil) => Nil + case (0, path) => Nil + case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) + if(path.size < dim*dim) + Nil + else + List(path) + else (for (j <- legal_moves(dim,path, path.head)) yield enum_tours(dim,j::path)).flatten + } + +} + + +//(4) Implement a first-function that finds the first +// element, say x, in the list xs where f is not None. +// In that case Return f(x), otherwise None. If possible, +// calculate f(x) only once. + +//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... + + +// testcases +// +//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None +// +//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) +//first(List((1, 0),(2, 0),(3, 0)), foo) // None + + +//(5) Implement a function that uses the first-function from (5) for +// trying out onward moves, and searches recursively for a +// knight tour on a dim * dim-board. + + +//def first_tour(dim: Int, path: Path) : Option[Path] = ... + + + + + + +/* Helper functions + + +// for measuring time +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + +// can be called for example with +// time_needed(count_tours(dim, List((0, 0)))) +// in order to print out the time that is needed for +// running count_tours + + + + +// for printing a board +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") + } + println + } +} + + +*/ + +} diff -r 40657f9a4e4a -r 663c2a9108d1 solutions2/docdiff.jar Binary file solutions2/docdiff.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 solutions2/docdiff.scala --- a/solutions2/docdiff.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,117 +0,0 @@ -// Preliminary Part about Code Similarity -//======================================== - - -object CW7a { - -//(1) Complete the clean function below. It should find -// all words in a string using the regular expression -// \w+ and the library function -// -// some_regex.findAllIn(some_string) -// -// The words should be Returned as a list of strings. - -def clean(s: String) : List[String] = - ("""\w+""".r).findAllIn(s).toList - - -//(2) The function occurrences calculates the number of times -// strings occur in a list of strings. These occurrences should -// be calculated as a Map from strings to integers. - -def occurrences(xs: List[String]): Map[String, Int] = - (for (x <- xs.distinct) yield (x, xs.count(_ == x))).toMap - -//(3) This functions calculates the dot-product of two documents -// (list of strings). For this it calculates the occurrence -// maps from (2) and then multiplies the corresponding occurrences. -// If a string does not occur in a document, the product is zero. -// The function finally sums up all products. - -def prod(lst1: List[String], lst2: List[String]) : Int = { - val words = (lst1 ::: lst2).distinct - val occs1 = occurrences(lst1) - val occs2 = occurrences(lst2) - words.map{ w => occs1.getOrElse(w, 0) * occs2.getOrElse(w, 0) }.sum -} - -//(4) Complete the functions overlap and similarity. The overlap of -// two documents is calculated by the formula given in the assignment -// description. The similarity of two strings is given by the overlap -// of the cleaned (see (1)) strings. - -def overlap(lst1: List[String], lst2: List[String]) : Double = { - val m1 = prod(lst1, lst1) - val m2 = prod(lst2, lst2) - prod(lst1, lst2).toDouble / (List(m1, m2).max) -} - -def similarity(s1: String, s2: String) : Double = - overlap(clean(s1), clean(s2)) - - -/* - - -val list1 = List("a", "b", "b", "c", "d") -val list2 = List("d", "b", "d", "b", "d") - -occurrences(List("a", "b", "b", "c", "d")) // Map(a -> 1, b -> 2, c -> 1, d -> 1) -occurrences(List("d", "b", "d", "b", "d")) // Map(d -> 3, b -> 2) - -prod(list1,list2) // 7 - -overlap(list1, list2) // 0.5384615384615384 -overlap(list2, list1) // 0.5384615384615384 -overlap(list1, list1) // 1.0 -overlap(list2, list2) // 1.0 - -// Plagiarism examples from -// https://desales.libguides.com/avoidingplagiarism/examples - -val orig1 = """There is a strong market demand for eco-tourism in -Australia. Its rich and diverse natural heritage ensures Australia's -capacity to attract international ecotourists and gives Australia a -comparative advantage in the highly competitive tourism industry.""" - -val plag1 = """There is a high market demand for eco-tourism in -Australia. Australia has a comparative advantage in the highly -competitive tourism industry due to its rich and varied natural -heritage which ensures Australia's capacity to attract international -ecotourists.""" - -similarity(orig1, plag1) - - -// Plagiarism examples from -// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php - -val orig2 = """No oil spill is entirely benign. Depending on timing and -location, even a relatively minor spill can cause significant harm to -individual organisms and entire populations. Oil spills can cause -impacts over a range of time scales, from days to years, or even -decades for certain spills. Impacts are typically divided into acute -(short-term) and chronic (long-term) effects. Both types are part of a -complicated and often controversial equation that is addressed after -an oil spill: ecosystem recovery.""" - -val plag2 = """There is no such thing as a "good" oil spill. If the -time and place are just right, even a small oil spill can cause damage -to sensitive ecosystems. Further, spills can cause harm days, months, -years, or even decades after they occur. Because of this, spills are -usually broken into short-term (acute) and long-term (chronic) -effects. Both of these types of harm must be addressed in ecosystem -recovery: a controversial tactic that is often implemented immediately -following an oil spill.""" - -overlap(clean(orig2), clean(plag2)) -similarity(orig2, plag2) - -// The punchline: everything above 0.6 looks suspicious and -// should be looked at by staff. - -*/ - - -} diff -r 40657f9a4e4a -r 663c2a9108d1 solutions3/knight1.jar Binary file solutions3/knight1.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 solutions3/knight1.scala --- a/solutions3/knight1.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,177 +0,0 @@ -// Part 1 about finding and counting Knight's tours -//================================================== - -object CW8a { // for preparing the jar - -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions - - -// for measuring time in the JAR -def time_needed[T](code: => T) : T = { - val start = System.nanoTime() - val result = code - val end = System.nanoTime() - println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") - result -} - -// for printing a board -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") - } - println - } -} - -def is_legal(dim: Int, path: Path, x: Pos): Boolean = - 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) - -// testcases -//assert(is_legal(8, Nil, (3, 4)) == true) -//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false) -//assert(is_legal(2, Nil, (0, 0)) == true) - - -def add_pair(x: Pos, y: Pos): Pos = - (x._1 + y._1, x._2 + y._2) - -def moves(x: Pos): List[Pos] = - List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), - (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _)) - -// 1 mark - -def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = - moves(x).filter(is_legal(dim, path, _)) - - - -// testcases -//assert(legal_moves(8, Nil, (2,2)) == -// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == -// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0))) -//assert(legal_moves(1, Nil, (0,0)) == List()) -//assert(legal_moves(2, Nil, (0,0)) == List()) -//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) - -// 2 marks - -def tcount_tours(dim: Int, path: Path): Int = { - if (path.length == dim * dim) 1 - else - (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum -} - -def count_tours(dim: Int, path: Path) = - time_needed(tcount_tours(dim: Int, path: Path)) - - -def tenum_tours(dim: Int, path: Path): List[Path] = { - if (path.length == dim * dim) List(path) - else - (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten -} - -def enum_tours(dim: Int, path: Path) = - time_needed(tenum_tours(dim: Int, path: Path)) - -// test cases - -/* -def count_all_tours(dim: Int) = { - for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) -} - -def enum_all_tours(dim: Int): List[Path] = { - (for (i <- (0 until dim).toList; - j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten -} - - -println("Number of tours starting from (0, 0)") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0))))) -} - -println("Number of tours starting from all fields") - -for (dim <- 1 to 5) { - println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim))) -} - -for (dim <- 1 to 5) { - val ts = enum_tours(dim, List((0, 0))) - println(s"${dim} x ${dim} ") - if (ts != Nil) { - print_board(dim, ts.head) - println(ts.head) - } -} -*/ - -// 1 mark - -def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { - case Nil => None - case x::xs => { - val result = f(x) - if (result.isDefined) result else first(xs, f) - } -} - -// test cases -//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None -// -//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) -//first(List((1, 0),(2, 0),(3, 0)), foo) - - -// 1 mark - -def tfirst_tour(dim: Int, path: Path): Option[Path] = { - if (path.length == dim * dim) Some(path) - else - first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path)) -} - -def first_tour(dim: Int, path: Path) = - time_needed(tfirst_tour(dim: Int, path: Path)) - - -/* -for (dim <- 1 to 8) { - val t = first_tour(dim, List((0, 0))) - println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) -} -*/ - -// 15 secs for 8 x 8 -//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get) -//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get) - -// no result for 4 x 4 -//val ts2 = time_needed(0, first_tour(4, List((0, 0)))) - -// 0.3 secs for 6 x 6 -//val ts3 = time_needed(0, first_tour(6, List((0, 0)))) - -// 15 secs for 8 x 8 -//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get)) - - - - - -} - - diff -r 40657f9a4e4a -r 663c2a9108d1 solutions4/knight1.jar Binary file solutions4/knight1.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 solutions4/knight1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/solutions4/knight1.scala Sun Nov 01 01:21:31 2020 +0000 @@ -0,0 +1,177 @@ +// Part 1 about finding and counting Knight's tours +//================================================== + +object CW8a { // for preparing the jar + +type Pos = (Int, Int) // a position on a chessboard +type Path = List[Pos] // a path...a list of positions + + +// for measuring time in the JAR +def time_needed[T](code: => T) : T = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") + result +} + +// for printing a board +def print_board(dim: Int, path: Path): Unit = { + println + for (i <- 0 until dim) { + for (j <- 0 until dim) { + print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") + } + println + } +} + +def is_legal(dim: Int, path: Path, x: Pos): Boolean = + 0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x) + +// testcases +//assert(is_legal(8, Nil, (3, 4)) == true) +//assert(is_legal(8, List((4, 1), (1, 0)), (4, 1)) == false) +//assert(is_legal(2, Nil, (0, 0)) == true) + + +def add_pair(x: Pos, y: Pos): Pos = + (x._1 + y._1, x._2 + y._2) + +def moves(x: Pos): List[Pos] = + List(( 1, 2),( 2, 1),( 2, -1),( 1, -2), + (-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x, _)) + +// 1 mark + +def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] = + moves(x).filter(is_legal(dim, path, _)) + + + +// testcases +//assert(legal_moves(8, Nil, (2,2)) == +// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == +// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) +//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) +//assert(legal_moves(8, Nil, (0,1)) == List((1,3), (2,2), (2,0))) +//assert(legal_moves(1, Nil, (0,0)) == List()) +//assert(legal_moves(2, Nil, (0,0)) == List()) +//assert(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))) + +// 2 marks + +def tcount_tours(dim: Int, path: Path): Int = { + if (path.length == dim * dim) 1 + else + (for (x <- legal_moves(dim, path, path.head)) yield tcount_tours(dim, x::path)).sum +} + +def count_tours(dim: Int, path: Path) = + time_needed(tcount_tours(dim: Int, path: Path)) + + +def tenum_tours(dim: Int, path: Path): List[Path] = { + if (path.length == dim * dim) List(path) + else + (for (x <- legal_moves(dim, path, path.head)) yield tenum_tours(dim, x::path)).flatten +} + +def enum_tours(dim: Int, path: Path) = + time_needed(tenum_tours(dim: Int, path: Path)) + +// test cases + +/* +def count_all_tours(dim: Int) = { + for (i <- (0 until dim).toList; + j <- (0 until dim).toList) yield count_tours(dim, List((i, j))) +} + +def enum_all_tours(dim: Int): List[Path] = { + (for (i <- (0 until dim).toList; + j <- (0 until dim).toList) yield enum_tours(dim, List((i, j)))).flatten +} + + +println("Number of tours starting from (0, 0)") + +for (dim <- 1 to 5) { + println(s"${dim} x ${dim} " + time_needed(0, count_tours(dim, List((0, 0))))) +} + +println("Number of tours starting from all fields") + +for (dim <- 1 to 5) { + println(s"${dim} x ${dim} " + time_needed(0, count_all_tours(dim))) +} + +for (dim <- 1 to 5) { + val ts = enum_tours(dim, List((0, 0))) + println(s"${dim} x ${dim} ") + if (ts != Nil) { + print_board(dim, ts.head) + println(ts.head) + } +} +*/ + +// 1 mark + +def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match { + case Nil => None + case x::xs => { + val result = f(x) + if (result.isDefined) result else first(xs, f) + } +} + +// test cases +//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None +// +//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) +//first(List((1, 0),(2, 0),(3, 0)), foo) + + +// 1 mark + +def tfirst_tour(dim: Int, path: Path): Option[Path] = { + if (path.length == dim * dim) Some(path) + else + first(legal_moves(dim, path, path.head), (x:Pos) => tfirst_tour(dim, x::path)) +} + +def first_tour(dim: Int, path: Path) = + time_needed(tfirst_tour(dim: Int, path: Path)) + + +/* +for (dim <- 1 to 8) { + val t = first_tour(dim, List((0, 0))) + println(s"${dim} x ${dim} " + (if (t == None) "" else { print_board(dim, t.get) ; "" })) +} +*/ + +// 15 secs for 8 x 8 +//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get) +//val ts1 = time_needed(0,first_tour(8, List((1, 1))).get) + +// no result for 4 x 4 +//val ts2 = time_needed(0, first_tour(4, List((0, 0)))) + +// 0.3 secs for 6 x 6 +//val ts3 = time_needed(0, first_tour(6, List((0, 0)))) + +// 15 secs for 8 x 8 +//time_needed(0, print_board(8, first_tour(8, List((0, 0))).get)) + + + + + +} + + diff -r 40657f9a4e4a -r 663c2a9108d1 solutions4/postfix.jar Binary file solutions4/postfix.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 solutions4/postfix2.jar Binary file solutions4/postfix2.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 templates2/docdiff.jar Binary file templates2/docdiff.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 templates2/docdiff.scala --- a/templates2/docdiff.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,116 +0,0 @@ -// Preliminary Part about Code Similarity -//======================================== - - -object CW7a { - - -//(1) Complete the clean function below. It should find -// all words in a string using the regular expression -// \w+ and the library function -// -// some_regex.findAllIn(some_string) -// -// The words should be Returned as a list of strings. - - -//def clean(s: String) : List[String] = ... - - - -//(2) The function occurrences calculates the number of times -// strings occur in a list of strings. These occurrences should -// be calculated as a Map from strings to integers. - - -//def occurrences(xs: List[String]): Map[String, Int] = .. - - -//(3) This functions calculates the dot-product of two documents -// (list of strings). For this it calculates the occurrence -// maps from (2) and then multiplies the corresponding occurrences. -// If a string does not occur in a document, the product is zero. -// The function finally sums up all products. - - -//def prod(lst1: List[String], lst2: List[String]) : Int = .. - - -//(4) Complete the functions overlap and similarity. The overlap of -// two documents is calculated by the formula given in the assignment -// description. The similarity of two strings is given by the overlap -// of the cleaned strings (see (1)). - - -//def overlap(lst1: List[String], lst2: List[String]) : Double = ... - -//def similarity(s1: String, s2: String) : Double = ... - - - - -/* Test cases - - -val list1 = List("a", "b", "b", "c", "d") -val list2 = List("d", "b", "d", "b", "d") - -occurrences(List("a", "b", "b", "c", "d")) // Map(a -> 1, b -> 2, c -> 1, d -> 1) -occurrences(List("d", "b", "d", "b", "d")) // Map(d -> 3, b -> 2) - -prod(list1,list2) // 7 - -overlap(list1, list2) // 0.5384615384615384 -overlap(list2, list1) // 0.5384615384615384 -overlap(list1, list1) // 1.0 -overlap(list2, list2) // 1.0 - -// Plagiarism examples from -// https://desales.libguides.com/avoidingplagiarism/examples - -val orig1 = """There is a strong market demand for eco-tourism in -Australia. Its rich and diverse natural heritage ensures Australia's -capacity to attract international ecotourists and gives Australia a -comparative advantage in the highly competitive tourism industry.""" - -val plag1 = """There is a high market demand for eco-tourism in -Australia. Australia has a comparative advantage in the highly -competitive tourism industry due to its rich and varied natural -heritage which ensures Australia's capacity to attract international -ecotourists.""" - -similarity(orig1, plag1) // 0.8679245283018868 - - -// Plagiarism examples from -// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php - -val orig2 = """No oil spill is entirely benign. Depending on timing and -location, even a relatively minor spill can cause significant harm to -individual organisms and entire populations. Oil spills can cause -impacts over a range of time scales, from days to years, or even -decades for certain spills. Impacts are typically divided into acute -(short-term) and chronic (long-term) effects. Both types are part of a -complicated and often controversial equation that is addressed after -an oil spill: ecosystem recovery.""" - -val plag2 = """There is no such thing as a "good" oil spill. If the -time and place are just right, even a small oil spill can cause damage -to sensitive ecosystems. Further, spills can cause harm days, months, -years, or even decades after they occur. Because of this, spills are -usually broken into short-term (acute) and long-term (chronic) -effects. Both of these types of harm must be addressed in ecosystem -recovery: a controversial tactic that is often implemented immediately -following an oil spill.""" - -overlap(clean(orig2), clean(plag2)) // 0.728 -similarity(orig2, plag2) // 0.728 - - - -// The punchline: everything above 0.6 looks suspicious and -// should be investigated by staff. - -*/ - -} diff -r 40657f9a4e4a -r 663c2a9108d1 templates3/knight1.scala --- a/templates3/knight1.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,114 +0,0 @@ -// Preliminary Part about finding Knight's tours -//=============================================== - - -object CW8a { - -// If you need any auxiliary function, feel free to -// implement it, but do not make any changes to the -// templates below. Also have a look whether the functions -// at the end are of any help. - - - -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions - -//(1) Complete the function that tests whether the position x -// is inside the board and not yet element in the path. - -//def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ... - - - -//(2) Complete the function that calculates for a position x -// all legal onward moves that are not already in the path. -// The moves should be ordered in a "clockwise" manner. - - -//def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ... - - -//some testcases -// -//assert(legal_moves(8, Nil, (2,2)) == -// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == -// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) - - -//(3) Complete the two recursive functions below. -// They exhaustively search for knight's tours starting from the -// given path. The first function counts all possible tours, -// and the second collects all tours in a list of paths. - -//def count_tours(dim: Int, path: Path) : Int = ... - -//def enum_tours(dim: Int, path: Path) : List[Path] = ... - - -//(4) Implement a first-function that finds the first -// element, say x, in the list xs where f is not None. -// In that case Return f(x), otherwise None. If possible, -// calculate f(x) only once. - -//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... - - -// testcases -// -//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None -// -//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) -//first(List((1, 0),(2, 0),(3, 0)), foo) // None - - -//(5) Implement a function that uses the first-function from (5) for -// trying out onward moves, and searches recursively for a -// knight tour on a dim * dim-board. - - -//def first_tour(dim: Int, path: Path) : Option[Path] = ... - - - - - - -/* Helper functions - - -// for measuring time -def time_needed[T](code: => T) : T = { - val start = System.nanoTime() - val result = code - val end = System.nanoTime() - println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") - result -} - -// can be called for example with -// time_needed(count_tours(dim, List((0, 0)))) -// in order to print out the time that is needed for -// running count_tours - - - - -// for printing a board -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") - } - println - } -} - - -*/ - -} diff -r 40657f9a4e4a -r 663c2a9108d1 templates4/postfix.jar Binary file templates4/postfix.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 templates4/postfix.scala --- a/templates4/postfix.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -// Shunting Yard Algorithm -// by Edsger Dijkstra -// ======================== - -object CW9a { - -// type of tokens -type Toks = List[String] - -// the operations in the basic version of the algorithm -val ops = List("+", "-", "*", "/") - -// the precedences of the operators -val precs = Map("+" -> 1, - "-" -> 1, - "*" -> 2, - "/" -> 2) - -// helper function for splitting strings into tokens -def split(s: String) : Toks = s.split(" ").toList - - -// (1) Implement below the shunting yard algorithm. The most -// convenient way to this in Scala is to implement a recursive -// function and to heavily use pattern matching. The function syard -// takes some input tokens as first argument. The second and third -// arguments represent the stack and the output of the shunting yard -// algorithm. -// -// In the marking, you can assume the function is called only with -// an empty stack and an empty output list. You can also assume the -// input os only properly formatted (infix) arithmetic expressions -// (all parentheses will be well-nested, the input only contains -// operators and numbers). - -// You can implement any additional helper function you need. I found -// it helpful to implement two auxiliary functions for the pattern matching: -// -// def is_op(op: String) : Boolean = ... -// def prec(op1: String, op2: String) : Boolean = ... - - -// def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... - - -// test cases -//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + -//syard(split("10 + 12 * 33")) // 10 12 33 * + -//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * -//syard(split("5 + 7 / 2")) // 5 7 2 / + -//syard(split("5 * 7 / 2")) // 5 7 * 2 / -//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + - -//syard(split("3 + 4 + 5")) // 3 4 + 5 + -//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + -//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + -//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + - - -// (2) Implement a compute function that evaluates an input list -// in postfix notation. This function takes a list of tokens -// and a stack as argumenta. The function should produce the -// result as an integer using the stack. You can assume -// this function will be only called with proper postfix -// expressions. - -// def compute(toks: Toks, st: List[Int] = Nil) : Int = ... - - -// test cases -// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 -// compute(syard(split("10 + 12 * 33"))) // 406 -// compute(syard(split("( 5 + 7 ) * 2"))) // 24 -// compute(syard(split("5 + 7 / 2"))) // 8 -// compute(syard(split("5 * 7 / 2"))) // 17 -// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 - -} - - diff -r 40657f9a4e4a -r 663c2a9108d1 templates4/postfix2.jar Binary file templates4/postfix2.jar has changed diff -r 40657f9a4e4a -r 663c2a9108d1 templates4/postfix2.scala --- a/templates4/postfix2.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,69 +0,0 @@ -// Shunting Yard Algorithm -// including Associativity for Operators -// ===================================== - -object CW9b { - - -// type of tokens -type Toks = List[String] - -// helper function for splitting strings into tokens -def split(s: String) : Toks = s.split(" ").toList - -// left- and right-associativity -abstract class Assoc -case object LA extends Assoc -case object RA extends Assoc - - -// power is right-associative, -// everything else is left-associative -def assoc(s: String) : Assoc = s match { - case "^" => RA - case _ => LA -} - - -// the precedences of the operators -val precs = Map("+" -> 1, - "-" -> 1, - "*" -> 2, - "/" -> 2, - "^" -> 4) - -// the operations in the basic version of the algorithm -val ops = List("+", "-", "*", "/", "^") - -// (3) Implement the extended version of the shunting yard algorithm. -// This version should properly account for the fact that the power -// operation is right-associative. Apart from the extension to include -// the power operation, you can make the same assumptions as in -// basic version. - -// def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = ... - - -// test cases -// syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + - - -// (4) Implement a compute function that produces a Long(!) for an -// input list of tokens in postfix notation. - -//def compute(toks: Toks, st: List[Long] = Nil) : Long = ... - - -// test cases -// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 -// compute(syard(split("10 + 12 * 33"))) // 406 -// compute(syard(split("( 5 + 7 ) * 2"))) // 24 -// compute(syard(split("5 + 7 / 2"))) // 8 -// compute(syard(split("5 * 7 / 2"))) // 17 -// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 -// compute(syard(split("4 ^ 3 ^ 2"))) // 262144 -// compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 -// compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 -// compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 - -} diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff.scala --- a/testing2/docdiff.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,101 +0,0 @@ -// Preliminary Part about Code Similarity -//======================================== - -object CW7a { - - -//(1) Complete the clean function below. It should find -// all words in a string using the regular expression -// \w+ and the library function -// -// some_regex.findAllIn(some_string) -// -// The words should be Returned as a list of strings. - - -//def clean(s: String) : List[String] = ... -def clean(s: String) : List[String] = - "\\w+".r.findAllIn(s).toList - -//(2) The function occurrences calculates the number of times -// strings occur in a list of strings. These occurrences should -// be calculated as a Map from strings to integers. - - -//def occurrences(xs: List[String]): Map[String, Int] = .. -def occurrences(xs: List[String]) : Map[String, Int] = - xs.groupBy(identity).view.mapValues(_.size).toMap - -//(3) This functions calculates the dot-product of two documents -// (list of strings). For this it calculates the occurrence -// maps from (2) and then multiplies the corresponding occurrences. -// If a string does not occur in a document, the product is zero. -// The function finally sums up all products. - - -//def prod(lst1: List[String], lst2: List[String]) : Int = .. -def prod(lst1: List[String], lst2: List[String]) : Int = - occurrences(lst1).map(x => occurrences(lst2).getOrElse(x._1, 0) * x._2).reduce(_ + _) - -//(4) Complete the functions overlap and similarity. The overlap of -// two documents is calculated by the formula given in the assignment -// description. The similarity of two strings is given by the overlap -// of the cleaned strings (see (1)). - - -//def overlap(lst1: List[String], lst2: List[String]) : Double = ... -def overlap(lst1: List[String], lst2: List[String]) : Double = - prod(lst1, lst2).toDouble/Math.max(prod(lst1, lst1).toDouble, prod(lst2, lst2).toDouble) -//def similarity(s1: String, s2: String) : Double = ... -def similarity(s1: String, s2: String) : Double = - overlap(clean(s1), clean(s2)) - - -/* Test cases -import CW7a._ -val list1 = List("a", "b", "b", "c", "d") -val list2 = List("d", "b", "d", "b", "d") -occurrences(List("a", "b", "b", "c", "d")) -occurrences(List("d", "b", "d", "b", "d")) -prod(list1,list2) // 7 -overlap(list1, list2) // 0.5384615384615384 -overlap(list2, list1) // 0.5384615384615384 -overlap(list1, list1) // 1.0 -overlap(list2, list2) // 1.0 -// Plagiarism examples from -// https://desales.libguides.com/avoidingplagiarism/examples -val orig1 = """There is a strong market demand for eco-tourism in -Australia. Its rich and diverse natural heritage ensures Australia's -capacity to attract international ecotourists and gives Australia a -comparative advantage in the highly competitive tourism industry.""" -val plag1 = """There is a high market demand for eco-tourism in -Australia. Australia has a comparative advantage in the highly -competitive tourism industry due to its rich and varied natural -heritage which ensures Australia's capacity to attract international -ecotourists.""" -similarity(orig1, plag1) // 0.8679245283018868 -// Plagiarism examples from -// https://www.utc.edu/library/help/tutorials/plagiarism/examples-of-plagiarism.php -val orig2 = """No oil spill is entirely benign. Depending on timing and -location, even a relatively minor spill can cause significant harm to -individual organisms and entire populations. Oil spills can cause -impacts over a range of time scales, from days to years, or even -decades for certain spills. Impacts are typically divided into acute -(short-term) and chronic (long-term) effects. Both types are part of a -complicated and often controversial equation that is addressed after -an oil spill: ecosystem recovery.""" -val plag2 = """There is no such thing as a "good" oil spill. If the -time and place are just right, even a small oil spill can cause damage -to sensitive ecosystems. Further, spills can cause harm days, months, -years, or even decades after they occur. Because of this, spills are -usually broken into short-term (acute) and long-term (chronic) -effects. Both of these types of harm must be addressed in ecosystem -recovery: a controversial tactic that is often implemented immediately -following an oil spill.""" -overlap(clean(orig2), clean(plag2)) // 0.728 -similarity(orig2, plag2) // 0.728 -// The punchline: everything above 0.6 looks suspicious and -// should be investigated by staff. -*/ - -} diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff_test.sh --- a/testing2/docdiff_test.sh Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,136 +0,0 @@ -#!/bin/bash - -# to make the script fail safely -set -euo pipefail - - -out=${1:-output} - -echo "" > $out - -echo "Below is the feedback for your submission docdiff.scala" >> $out -echo "" >> $out - - -# compilation tests - -function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) -} - -# functional tests - -function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) -} - -# purity test - -function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) -} - - -# var, .par return, ListBuffer test -# -echo "docdiff.scala does not contain vars, returns etc?" >> $out - -if (scala_vars docdiff.scala) -then - echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out - tsts0=$(( 0 )) -else - echo -e " --> success" >> $out - tsts0=$(( 0 )) -fi - -### compilation test - - -if [ $tsts0 -eq 0 ] -then - echo "docdiff.scala runs?" >> $out - - if (scala_compile docdiff.scala) - then - echo -e " --> success" >> $out - tsts=$(( 0 )) - else - echo -e " --> SCALA DID NOT RUN docdiff.scala" >> $out - tsts=$(( 1 )) - fi -else - tsts=$(( 1 )) -fi - -### docdiff clean tests - -if [ $tsts -eq 0 ] -then - echo -e "docdiff.scala tests:" >> $out - echo -e " clean(\"ab a abc\") == List(\"ab\", \"a\", \"abc\")" >> $out - echo -e " clean(\"ab*a abc1\") == List(\"ab\", \"a\", \"abc1\")" >> $out - - if (scala_assert "docdiff.scala" "docdiff_test1.scala") - then - echo -e " --> success\n" >> $out - else - echo -e " --> ONE OF THE TESTS FAILED\n" >> $out - fi -fi - -### docdiff occurrences tests - -if [ $tsts -eq 0 ] -then - echo -e " occurrences(List(\"a\", \"b\", \"b\", \"c\", \"d\")) == " >> $out - echo -e " Map(\"a\" -> 1, \"b\" -> 2, \"c\" -> 1, \"d\" -> 1)" >> $out - echo -e " " >> $out - echo -e " occurrences(List(\"d\", \"b\", \"d\", \"b\", \"d\")) == " >> $out - echo -e " Map(\"d\" -> 3, \"b\" -> 2)" >> $out - - if (scala_assert "docdiff.scala" "docdiff_test2.scala") - then - echo -e " --> success\n" >> $out - else - echo -e " --> ONE OF THE TESTS FAILED\n" >> $out - fi -fi - -### docdiff prod tests - -if [ $tsts -eq 0 ] -then - echo -e " val l1 = List(\"a\", \"b\", \"b\", \"c\", \"d\")" >> $out - echo -e " val l2 = List(\"d\", \"b\", \"d\", \"b\", \"d\")" >> $out - echo -e " " >> $out - echo -e " prod(l1, l2) == 7 " >> $out - echo -e " prod(l1, l1) == 7 " >> $out - echo -e " prod(l2, l2) == 13 " >> $out - - if (scala_assert "docdiff.scala" "docdiff_test3.scala") - then - echo -e " --> success\n" >> $out - else - echo -e " --> ONE OF THE TESTS FAILED\n" >> $out - fi -fi - -### docdiff overlap tests - -if [ $tsts -eq 0 ] -then - echo -e " val l1 = List(\"a\", \"b\", \"b\", \"c\", \"d\")" >> $out - echo -e " val l2 = List(\"d\", \"b\", \"d\", \"b\", \"d\")" >> $out - echo -e " " >> $out - echo -e " overlap(l1, l2) == 0.5384615384615384 " >> $out - echo -e " overlap(l1, l1) == 1.0 " >> $out - echo -e " overlap(l2, l2) == 1.0 " >> $out - - if (scala_assert "docdiff.scala" "docdiff_test4.scala") - then - echo -e " --> success\n" >> $out - else - echo -e " --> ONE OF THE TESTS FAILED\n" >> $out - fi -fi diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff_test1.scala --- a/testing2/docdiff_test1.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ - -import CW7a._ - -assert(clean("ab a abc") == List("ab", "a", "abc")) - -assert(clean("ab*a abc1") == List("ab", "a", "abc1")) diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff_test2.scala --- a/testing2/docdiff_test2.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ - -import CW7a._ - -assert(occurrences(List("a", "b", "b", "c", "d")) == Map("a" -> 1, "b" -> 2, "c" -> 1, "d" -> 1)) - -assert(occurrences(List("d", "b", "d", "b", "d")) == Map("d" -> 3, "b" -> 2)) diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff_test3.scala --- a/testing2/docdiff_test3.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ - -import CW7a._ - -val urban_list1 = List("a", "b", "b", "c", "d") -val urban_list2 = List("d", "b", "d", "b", "d") - -assert(prod(urban_list1, urban_list2) == 7) - -assert(prod(urban_list1, urban_list1) == 7) - -assert(prod(urban_list2, urban_list2) == 13) diff -r 40657f9a4e4a -r 663c2a9108d1 testing2/docdiff_test4.scala --- a/testing2/docdiff_test4.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ - -import CW7a._ - -val urban_list1 = List("a", "b", "b", "c", "d") -val urban_list2 = List("d", "b", "d", "b", "d") - -assert(overlap(urban_list1, urban_list2) == 0.5384615384615384) - -assert(overlap(urban_list1, urban_list1) == 1.0) - -assert(overlap(urban_list2, urban_list2) == 1.0) diff -r 40657f9a4e4a -r 663c2a9108d1 testing3/knight1.scala --- a/testing3/knight1.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,147 +0,0 @@ -// Preliminary Part about finding Knight's tours -//=============================================== - - -object CW8a { - -// If you need any auxiliary function, feel free to -// implement it, but do not make any changes to the -// templates below. Also have a look whether the functions -// at the end are of any help. - - - -type Pos = (Int, Int) // a position on a chessboard -type Path = List[Pos] // a path...a list of positions - -//(1) Complete the function that tests whether the position x -// is inside the board and not yet element in the path. - -def is_legal(dim: Int, path: Path, x: Pos) : Boolean = { - if ((!(path.contains(x))) && (x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)) - true - else false -} - -//(2) Complete the function that calculates for a position x -// all legal onward moves that are not already in the path. -// The moves should be ordered in a "clockwise" manner. - - -def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {//List[Pos] - val changes = List((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)) - val returnList = (for ((y,z) <- changes) yield( - //println(y,z)-2,-1 - if ((is_legal(dim,path,((x._1 + y) , (x._2 + z)))) == true) - Some(x._1 + y , x._2 + z) - else - None - )) - returnList.flatten -} - - -//some testcases -// -//assert(legal_moves(8, Nil, (2,2)) == - //List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))) -//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == -// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))) -//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6))) - - -//(3) Complete the two recursive functions below. -// They exhaustively search for knight's tours starting from the -// given path. The first function counts all possible tours, -// and the second collects all tours in a list of paths. - -def count_tours(dim: Int, path: Path) : Int = (dim,path) match {//Int - case (_, Nil) => 0 - case (0, path) => 0 - case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) - if(path.size < dim*dim) - 0 - else - 1 - else (for (j <- legal_moves(dim,path, path.head)) yield count_tours(dim,j::path)).sum - } -} - -def enum_tours(dim: Int, path: Path) : List[Path] = (dim,path) match { - case (_, Nil) => Nil - case (0, path) => Nil - case (dim, path) => { if (legal_moves(dim,path, path.head).size == 0) - if(path.size < dim*dim) - Nil - else - List(path) - else (for (j <- legal_moves(dim,path, path.head)) yield enum_tours(dim,j::path)).flatten - } - -} - - -//(4) Implement a first-function that finds the first -// element, say x, in the list xs where f is not None. -// In that case Return f(x), otherwise None. If possible, -// calculate f(x) only once. - -//def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = ... - - -// testcases -// -//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None -// -//first(List((1, 0),(2, 0),(3, 0),(4, 0)), foo) // Some(List((4,0))) -//first(List((1, 0),(2, 0),(3, 0)), foo) // None - - -//(5) Implement a function that uses the first-function from (5) for -// trying out onward moves, and searches recursively for a -// knight tour on a dim * dim-board. - - -//def first_tour(dim: Int, path: Path) : Option[Path] = ... - - - - - - -/* Helper functions - - -// for measuring time -def time_needed[T](code: => T) : T = { - val start = System.nanoTime() - val result = code - val end = System.nanoTime() - println(f"Time needed: ${(end - start) / 1.0e9}%3.3f secs.") - result -} - -// can be called for example with -// time_needed(count_tours(dim, List((0, 0)))) -// in order to print out the time that is needed for -// running count_tours - - - - -// for printing a board -def print_board(dim: Int, path: Path): Unit = { - println - for (i <- 0 until dim) { - for (j <- 0 until dim) { - print(f"${path.reverse.indexOf((j, dim - i - 1))}%3.0f ") - } - println - } -} - - -*/ - -} diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix.scala --- a/testing4/postfix.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,103 +0,0 @@ -// Shunting Yard Algorithm -// by Edsger Dijkstra -// ======================== - -object CW9a { - -type Toks = List[String] - -// the operations in the simple version -val ops = List("+", "-", "*", "/") - -// the precedences of the operators -val precs = Map("+" -> 1, - "-" -> 1, - "*" -> 2, - "/" -> 2) - -// helper function for splitting strings into tokens -def split(s: String) : Toks = s.split(" ").toList - -// (6) Implement below the shunting yard algorithm. The most -// convenient way to this in Scala is to implement a recursive -// function and to heavily use pattern matching. The function syard -// takes some input tokens as first argument. The second and third -// arguments represent the stack and the output of the shunting yard -// algorithm. -// -// In the marking, you can assume the function is called only with -// an empty stack and an empty output list. You can also assume the -// input os only properly formatted (infix) arithmetic expressions -// (all parentheses will be well-nested, the input only contains -// operators and numbers). - -// You can implement any additional helper function you need. I found -// it helpful to implement two auxiliary functions for the pattern matching: -// - -def is_op(op: String) : Boolean = ops.contains(op) - -def prec(op1: String, op2: String) : Boolean = precs(op1) <= precs(op2) - - -def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { - case (Nil, _, _) => out.reverse ::: st - case (num::in, st, out) if (num.forall(_.isDigit)) => - syard(in, st, num :: out) - case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => - syard(op1::in, st, op2 :: out) - case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) - case ("("::in, st, out) => syard(in, "("::st, out) - case (")"::in, op2::st, out) => - if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) - case (in, st, out) => { - println(s"in: ${in} st: ${st} out: ${out.reverse}") - Nil - } -} - - -// test cases -//syard(split("3 + 4 * ( 2 - 1 )")) // 3 4 2 1 - * + -//syard(split("10 + 12 * 33")) // 10 12 33 * + -//syard(split("( 5 + 7 ) * 2")) // 5 7 + 2 * -//syard(split("5 + 7 / 2")) // 5 7 2 / + -//syard(split("5 * 7 / 2")) // 5 7 * 2 / -//syard(split("9 + 24 / ( 7 - 3 )")) // 9 24 7 3 - / + - -//syard(split("3 + 4 + 5")) // 3 4 + 5 + -//syard(split("( ( 3 + 4 ) + 5 )")) // 3 4 + 5 + -//syard(split("( 3 + ( 4 + 5 ) )")) // 3 4 5 + + -//syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) // 3 4 5 + + - -// (7) Implement a compute function that evaluates an input list -// in postfix notation. This function takes a list of tokens -// and a stack as argumenta. The function should produce the -// result as an integer using the stack. You can assume -// this function will be only called with proper postfix -// expressions. - -def op_comp(s: String, n1: Int, n2: Int) = s match { - case "+" => n2 + n1 - case "-" => n2 - n1 - case "*" => n2 * n1 - case "/" => n2 / n1 -} - -def compute(toks: Toks, st: List[Int] = Nil) : Int = (toks, st) match { - case (Nil, st) => st.head - case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) - case (num::in, st) => compute(in, num.toInt::st) -} - -// test cases -// compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 -// compute(syard(split("10 + 12 * 33"))) // 406 -// compute(syard(split("( 5 + 7 ) * 2"))) // 24 -// compute(syard(split("5 + 7 / 2"))) // 8 -// compute(syard(split("5 * 7 / 2"))) // 17 -// compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 - -} - - diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix2.scala --- a/testing4/postfix2.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,100 +0,0 @@ -// Shunting Yard Algorithm -// including Associativity for Operators -// ===================================== - -object CW9b { - -// type of tokens -type Toks = List[String] - -// helper function for splitting strings into tokens -def split(s: String) : Toks = s.split(" ").toList - -// left- and right-associativity -abstract class Assoc -case object LA extends Assoc -case object RA extends Assoc - -// power is right-associative, -// everything else is left-associative -def assoc(s: String) : Assoc = s match { - case "^" => RA - case _ => LA -} - -// the precedences of the operators -val precs = Map("+" -> 1, - "-" -> 1, - "*" -> 2, - "/" -> 2, - "^" -> 4) - -// the operations in the basic version of the algorithm -val ops = List("+", "-", "*", "/", "^") - -// (8) Implement the extended version of the shunting yard algorithm. -// This version should properly account for the fact that the power -// operation is right-associative. Apart from the extension to include -// the power operation, you can make the same assumptions as in -// basic version. - -def is_op(op: String) : Boolean = ops.contains(op) - -def prec(op1: String, op2: String) : Boolean = assoc(op1) match { - case LA => precs(op1) <= precs(op2) - case RA => precs(op1) < precs(op2) -} - -def syard(toks: Toks, st: Toks = Nil, out: Toks = Nil) : Toks = (toks, st, out) match { - case (Nil, _, _) => out.reverse ::: st - case (num::in, st, out) if (num.forall(_.isDigit)) => - syard(in, st, num :: out) - case (op1::in, op2::st, out) if (is_op(op1) && is_op(op2) && prec(op1, op2)) => - syard(op1::in, st, op2 :: out) - case (op1::in, st, out) if (is_op(op1)) => syard(in, op1::st, out) - case ("("::in, st, out) => syard(in, "("::st, out) - case (")"::in, op2::st, out) => - if (op2 == "(") syard(in, st, out) else syard(")"::in, st, op2 :: out) - case (in, st, out) => { - println(s"in: ${in} st: ${st} out: ${out.reverse}") - Nil - } -} - -def op_comp(s: String, n1: Long, n2: Long) = s match { - case "+" => n2 + n1 - case "-" => n2 - n1 - case "*" => n2 * n1 - case "/" => n2 / n1 - case "^" => Math.pow(n2, n1).toLong -} - -def compute(toks: Toks, st: List[Long] = Nil) : Long = (toks, st) match { - case (Nil, st) => st.head - case (op::in, n1::n2::st) if (is_op(op)) => compute(in, op_comp(op, n1, n2)::st) - case (num::in, st) => compute(in, num.toInt::st) -} - - - - -//compute(syard(split("3 + 4 * ( 2 - 1 )"))) // 7 -//compute(syard(split("10 + 12 * 33"))) // 406 -//compute(syard(split("( 5 + 7 ) * 2"))) // 24 -//compute(syard(split("5 + 7 / 2"))) // 8 -//compute(syard(split("5 * 7 / 2"))) // 17 -//compute(syard(split("9 + 24 / ( 7 - 3 )"))) // 15 - -//compute(syard(split("4 ^ 3 ^ 2"))) // 262144 -//compute(syard(split("4 ^ ( 3 ^ 2 )"))) // 262144 -//compute(syard(split("( 4 ^ 3 ) ^ 2"))) // 4096 -//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 - -//syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) // 3 4 8 * 5 1 - 2 3 ^ ^ / + -//compute(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3"))) // 3 - -//compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) // 65536 - - - -} diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix_test.sh --- a/testing4/postfix_test.sh Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,164 +0,0 @@ -#!/bin/bash -set -euo pipefail - - -out=${1:-output} - -echo -e "" > $out - -echo -e "Below is the feedback for your submission of CW 9, Preliminary Part." >> $out -echo -e "" >> $out - - -# compilation tests - -function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) -} - -# functional tests - -function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" 2> /dev/null 1> /dev/null) -} - -# purity test - -function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) -} - - -# var, return, ListBuffer test -# -echo -e "postfix.scala does not contain vars, returns etc?" >> $out - -if (scala_vars postfix.scala) -then - echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out - tsts0=$(( 0 )) -else - echo -e " --> success" >> $out - tsts0=$(( 0 )) -fi - - -# compilation test - -if [ $tsts0 -eq 0 ] -then - echo -e "postfix.scala runs?" >> $out - - if (scala_compile postfix.scala) - then - echo -e " --> yes" >> $out - tsts1=$(( 0 )) - else - echo -e " --> SCALA DID NOT RUN POSTFIX.SCALA\n" >> $out - tsts1=$(( 1 )) - fi -else - tsts1=$(( 1 )) -fi - -### postfix tests - -if [ $tsts1 -eq 0 ] -then - echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"\*\", \"+\")" >> $out - echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" >> $out - echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" >> $out - echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"\*\", \"2\", \"/\")" >> $out - - if (scala_assert "postfix.scala" "postfix_test7.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - - - -if [ $tsts1 -eq 0 ] -then - echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" >> $out - echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" >> $out - echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" >> $out - echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" >> $out - echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" >> $out - echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" >> $out - - if (scala_assert "postfix.scala" "postfix_test8.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - -echo -e "" >> $out - -### postfix2 tests - -# var, return, ListBuffer test -# -echo -e "\n\npostfix2.scala does not contain vars, returns etc?" >> $out - -if (scala_vars postfix2.scala) -then - echo -e " --> FAIL (make triple-sure your program conforms to the required format)" >> $out - tsts0=$(( 0 )) -else - echo -e " --> success" >> $out - tsts0=$(( 0 )) -fi - - -# compilation test - -if [ $tsts0 -eq 0 ] -then - echo -e "postfix2.scala runs?" >> $out - - if (scala_compile postfix2.scala) - then - echo -e " --> yes" >> $out - tsts1=$(( 0 )) - else - echo -e " --> SCALA DID NOT RUN POSTFIX2.SCALA\n" >> $out - tsts1=$(( 1 )) - fi -else - tsts1=$(( 1 )) -fi - - -if [ $tsts1 -eq 0 ] -then - echo -e " syard(split(\"3 + 4 * ( 2 - 1 )\")) == List(\"3\", \"4\", \"2\", \"1\", \"-\", \"\*\", \"+\")" >> $out - echo -e " syard(split(\"( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )\")) == List(\"3\", \"4\", \"5\", \"+\", \"+\")" >> $out - echo -e " syard(split(\"5 + 7 / 2\")) == List(\"5\", \"7\", \"2\", \"/\", \"+\")" >> $out - echo -e " syard(split(\"5 * 7 / 2\")) == List(\"5\", \"7\", \"\*\", \"2\", \"/\")" >> $out - echo -e " syard(split(\"3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3\")) == " >> $out - echo -e " List(\"3\", \"4\", \"8\", \"\*\", \"5\", \"1\", \"-\", \"2\", \"3\", \"^\", \"^\", \"/\", \"+\")" >> $out - echo -e " " >> $out - echo -e " compute(syard(split(\"3 + 4 * ( 2 - 1 )\"))) == 7" >> $out - echo -e " compute(syard(split(\"10 + 12 * 33\"))) == 406" >> $out - echo -e " compute(syard(split(\"( 5 + 7 ) * 2\"))) == 24" >> $out - echo -e " compute(syard(split(\"5 + 7 / 2\"))) == 8" >> $out - echo -e " compute(syard(split(\"5 * 7 / 2\"))) == 17" >> $out - echo -e " compute(syard(split(\"9 + 24 / ( 7 - 3 )\"))) == 15" >> $out - echo -e " compute(syard(split(\"4 ^ 3 ^ 2\"))) == 262144" >> $out - echo -e " compute(syard(split(\"4 ^ ( 3 ^ 2 )\"))) == 262144" >> $out - echo -e " compute(syard(split(\"( 4 ^ 3 ) ^ 2\"))) == 4096" >> $out - echo -e " compute(syard(split(\"( 3 + 1 ) ^ 2 ^ 3\"))) == 65536" >> $out - - if (scala_assert "postfix2.scala" "postfix_test9.scala") - then - echo -e " --> success" >> $out - else - echo -e " --> \n ONE TEST FAILED\n" >> $out - fi -fi - diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix_test7.scala --- a/testing4/postfix_test7.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -import CW9a._ - - -assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) -assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) -assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) -assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix_test8.scala --- a/testing4/postfix_test8.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,8 +0,0 @@ -import CW9a._ - -assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) -assert(compute(syard(split("10 + 12 * 33"))) == 406) -assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) -assert(compute(syard(split("5 + 7 / 2"))) == 8) -assert(compute(syard(split("5 * 7 / 2"))) == 17) -assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) diff -r 40657f9a4e4a -r 663c2a9108d1 testing4/postfix_test9.scala --- a/testing4/postfix_test9.scala Sat Oct 31 16:47:46 2020 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,21 +0,0 @@ -import CW9b._ - - -assert(syard(split("3 + 4 * ( 2 - 1 )")) == List("3", "4", "2", "1", "-", "*", "+")) -assert(syard(split("( ( ( 3 ) ) + ( ( 4 + ( 5 ) ) ) )")) == List("3", "4", "5", "+", "+")) -assert(syard(split("5 + 7 / 2")) == List("5", "7", "2", "/", "+")) -assert(syard(split("5 * 7 / 2")) == List("5", "7", "*", "2", "/")) -assert(syard(split("3 + 4 * 8 / ( 5 - 1 ) ^ 2 ^ 3")) == List("3", "4", "8", "*", "5", "1", "-", "2", "3", "^", "^", "/", "+")) - - - -assert(compute(syard(split("3 + 4 * ( 2 - 1 )"))) == 7) -assert(compute(syard(split("10 + 12 * 33"))) == 406) -assert(compute(syard(split("( 5 + 7 ) * 2"))) == 24) -assert(compute(syard(split("5 + 7 / 2"))) == 8) -assert(compute(syard(split("5 * 7 / 2"))) == 17) -assert(compute(syard(split("9 + 24 / ( 7 - 3 )"))) == 15) -assert(compute(syard(split("4 ^ 3 ^ 2"))) == 262144) -assert(compute(syard(split("4 ^ ( 3 ^ 2 )"))) == 262144) -assert(compute(syard(split("( 4 ^ 3 ) ^ 2"))) == 4096) -assert(compute(syard(split("( 3 + 1 ) ^ 2 ^ 3"))) == 65536)