--- /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:
Binary file pre_solition1/collatz.jar has changed
--- 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)}")
-
-}
-
-
-
Binary file pre_solution1/collatz.jar has changed
--- /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)}")
+
+}
+
+
+
Binary file pre_solution2/docdiff.jar has changed
--- /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.
+
+*/
+
+
+}
Binary file pre_solution3/postfix.jar has changed
--- /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
+
+}
+
+
Binary file pre_solution3/postfix2.jar has changed
--- /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
+
+
+
+}
Binary file pre_templates1/collatz.jar has changed
Binary file pre_templates2/docdiff.jar has changed
--- /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.
+
+*/
+
+}
Binary file pre_templates3/postfix.jar has changed
--- /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
+
+}
+
+
Binary file pre_templates3/postfix2.jar has changed
--- /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
+
+}
--- /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
+ }
+}
+
+
+*/
+
+}
--- 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
-}
-
-}
--- 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
--- /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.
+*/
+
+}
--- /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
--- /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"))
--- /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))
--- /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)
--- /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)
--- /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
+
+}
+
+
--- /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
+
+
+
+}
--- /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
+
--- /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", "/"))
--- /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)
--- /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)
--- /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
+ }
+}
+
+
+*/
+
+}
Binary file solutions2/docdiff.jar has changed
--- 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.
-
-*/
-
-
-}
Binary file solutions3/knight1.jar has changed
--- 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))
-
-
-
-
-
-}
-
-
Binary file solutions4/knight1.jar has changed
--- /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))
+
+
+
+
+
+}
+
+
Binary file solutions4/postfix.jar has changed
Binary file solutions4/postfix2.jar has changed
Binary file templates2/docdiff.jar has changed
--- 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.
-
-*/
-
-}
--- 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
- }
-}
-
-
-*/
-
-}
Binary file templates4/postfix.jar has changed
--- 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
-
-}
-
-
Binary file templates4/postfix2.jar has changed
--- 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
-
-}
--- 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.
-*/
-
-}
--- 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
--- 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"))
--- 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))
--- 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)
--- 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)
--- 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
- }
-}
-
-
-*/
-
-}
--- 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
-
-}
-
-
--- 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
-
-
-
-}
--- 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
-
--- 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", "/"))
--- 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)
--- 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)