# HG changeset patch # User Christian Urban # Date 1561189192 -3600 # Node ID 59779ce322a6b269b28b1bdc053d302bd0d21c0e # Parent ecd989eee8bd30e0b096285b6a584b5ddeb02301 updated diff -r ecd989eee8bd -r 59779ce322a6 LINKS --- a/LINKS Wed Mar 20 21:50:20 2019 +0000 +++ b/LINKS Sat Jun 22 08:39:52 2019 +0100 @@ -4,19 +4,33 @@ https://sigma.software/about/media/pillars-functional-programming-part-1 +===================== +Maven repository for jars (par collections for example) + +https://search.maven.org/search?q=g:org.scala-lang.modules%20a:scala-parser-combinators_2.13 ===================== lectures on scala https://github.com/scalasummerschool/lectures +===================== +Scala course at Lund University +https://github.com/lunduniversity/introprog +http://cs.lth.se/pgk/download/ ===================== an argument for pure functions and programming https://dev.to/pietvandongen/pure-bliss-with-pure-functions-in-java-1mba ===================== +Abstract syntax tree generation + +https://stackoverflow.com/questions/10419101/how-can-i-find-the-statements-in-a-scala-program-from-within-a-compiler-plugin + + +===================== 95 hardest sudoku problems http://www.dos486.com/sudoku/top95.txt diff -r ecd989eee8bd -r 59779ce322a6 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r ecd989eee8bd -r 59779ce322a6 cws/cw03.tex --- a/cws/cw03.tex Wed Mar 20 21:50:20 2019 +0000 +++ b/cws/cw03.tex Sat Jun 22 08:39:52 2019 +0100 @@ -19,6 +19,12 @@ \section*{Coursework 8 (Scala)} +\mbox{}\hfill\textit{``The problem with object-oriented languages is they’ve got all this implicit,}\\ +\mbox{}\hfill\textit{environment that they carry around with them. You wanted a banana but}\\ +\mbox{}\hfill\textit{what you got was a gorilla holding the banana and the entire jungle.''}\smallskip\\ +\mbox{}\hfill\textit{ --- Joe Armstrong (creator of the Erlang programming language)}\bigskip + +\noindent This coursework is worth 10\%. It is about searching and backtracking. The first part is due on 29 November at 11pm; the second, more advanced part, is due on 20 December at 11pm. You are diff -r ecd989eee8bd -r 59779ce322a6 cws/cw06.pdf Binary file cws/cw06.pdf has changed diff -r ecd989eee8bd -r 59779ce322a6 cws/cw06.tex --- a/cws/cw06.tex Wed Mar 20 21:50:20 2019 +0000 +++ b/cws/cw06.tex Sat Jun 22 08:39:52 2019 +0100 @@ -7,7 +7,7 @@ \section*{Resit Exam} -The Scala part of the exam is worth 30\%. It is about `jumps' +The Scala part of the exam is worth 50\%. It is about `jumps' within lists. \IMPORTANTEXAM{} @@ -109,7 +109,7 @@ \end{center} - \mbox{}\hfill[Marks: 8\%] + \mbox{}\hfill[Marks: 12\%] \item[(2)] Write a function \texttt{search} that tests whether there is a way to reach the end of a list. This is not always the @@ -125,7 +125,7 @@ In case of the empty list, \texttt{search} should return true since the end of the list is already reached. - \mbox{}\hfill\mbox{[Marks: 10\%]} + \mbox{}\hfill\mbox{[Marks: 18\%]} \item[(3)] Write a function \texttt{jumps} that calculates the shortest sequence of steps needed to reach the end of a list. One @@ -138,7 +138,7 @@ \texttt{None}. In the special case of the empty list, \texttt{jumps} should return \texttt{None} - \mbox{}\hfill\mbox{[Marks: 12\%]} + \mbox{}\hfill\mbox{[Marks: 20\%]} \end{itemize}\bigskip diff -r ecd989eee8bd -r 59779ce322a6 cws/cw07.tex --- a/cws/cw07.tex Wed Mar 20 21:50:20 2019 +0000 +++ b/cws/cw07.tex Sat Jun 22 08:39:52 2019 +0100 @@ -4,22 +4,24 @@ \begin{document} -\section*{Replacement Coursework 1 (Roman Numerals)} +\section*{Scala Part (Roman Numerals)} -This coursework is worth 10\%. It is about translating roman numerals -into integers and also about validating roman numerals. The coursework -is due on 2 February at 5pm. Make sure the files you submit can be -processed by just calling \texttt{scala <>}.\bigskip +This coursework is worth 50\%. It is about translating roman numerals +into integers. Make sure the files you submit can be +processed by just calling + +\begin{center} + \texttt{scala <>} +\end{center}%\bigskip \noindent \textbf{Important:} Do not use any mutable data structures in your submission! They are not needed. This menas you cannot use -\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your +\texttt{ListBuffer}s, \texttt{Array}s, for example. Do not use \texttt{return} in your code! It has a different meaning in Scala, than in Java. Do not use \texttt{var}! This declares a mutable variable. Make sure the functions you submit are defined on the ``top-level'' of Scala, not -inside a class or object. Also note that the running time will be -restricted to a maximum of 360 seconds on my laptop. +inside a class or object. \subsection*{Disclaimer} @@ -30,7 +32,7 @@ you can freely use.\bigskip -\subsection*{Part 1 (Translation)} +\subsection*{Tasks} \noindent Roman numerals are strings consisting of the letters $I$, $V$, $X$, @@ -42,7 +44,7 @@ \begin{itemize} \item[(1)] First write a polymorphic function that recursively transforms a list of options into an option of a list. For example, - if you have the lists on the left-hand side, they should be transformed into + if you have the lists on the left-hand side below, they should be transformed into the options on the right-hand side: \begin{center} @@ -58,12 +60,12 @@ This means the function should produce \texttt{None} as soon as a \texttt{None} is inside the list. Otherwise it produces a list of all \texttt{Some}s. In case the list is empty, it - produces \texttt{Some} of the empty list. \hfill[1 Mark] + produces \texttt{Some} of the empty list. \hfill[15\% Marks] \item[(2)] Write first a function that converts the characters $I$, $V$, $X$, $L$, $C$, $D$, and $M$ into an option of a \texttt{RomanDigit}. - If it is one of the roman digits, it should produce \texttt{Some}; + If the input is one of the roman digits, the function should produce \texttt{Some}; otherwise \texttt{None}. Next write a function that converts a string into a @@ -74,12 +76,12 @@ \texttt{None}. The empty string is just the empty \texttt{RomanNumeral}, that is the empty list of \texttt{RomanDigit}'s. You should use the function under Task (1) - to produce the result. \hfill[2 Marks] + to produce the result. \hfill[15\% Marks] \item[(3)] Write a recursive function \texttt{RomanNumral2Int} that converts a \texttt{RomanNumeral} into an integer. You can assume the generated integer will be between 0 and 3999. The argument of the - function is a list of roman digits. It should look how this list + function is a list of roman digits. It should analyse how this list starts and then calculate what the corresponding integer is for this ``start'' and add it with the integer for the rest of the list. That means if the argument is of the form shown on the left-hand side, it @@ -103,27 +105,29 @@ \end{tabular} \end{center} - The empty list will be converted to integer $0$.\hfill[1 Mark] + The empty list will be converted to integer $0$.\hfill[10\% Mark] -\item[(4)] Write a function that takes a string and if possible - converts it into the internal representation. If successful, it then - calculates the integer (an option of an integer) according to the +\item[(4)] Write a function that takes a string as input and if possible + converts it into the internal representation of Roman Numerals. If successful, it then + calculates the corresponding integer (actually an option of an integer) according to the function in (3). If this is not possible, then return - \texttt{None}.\hfill[1 Mark] + \texttt{None}.\\ + \mbox{}\hfill[10\% Mark] -\item[(5)] The file \texttt{roman.txt} contains a list of roman numerals. - Read in these numerals, convert them into integers and then add them all - up. The Scala function for reading a file is - - \begin{center} - \texttt{Source.fromFile("filename")("ISO-8859-9")} - \end{center} - - Make sure you process the strings correctly by ignoring whitespaces - where needed.\\ \mbox{}\hfill[1 Mark] +%\item[(5)] The file \texttt{roman.txt} contains a list of roman numerals. +% Read in these numerals, convert them into integers and then add them all +% up. The Scala function for reading a file is +% +% \begin{center} +% \texttt{Source.fromFile("filename")("ISO-8859-9")} +% \end{center} +% +% Make sure you process the strings correctly by ignoring whitespaces +% where needed.\\ \mbox{}\hfill[1 Mark] \end{itemize} +\end{document} \subsection*{Part 2 (Validation)} diff -r ecd989eee8bd -r 59779ce322a6 handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed diff -r ecd989eee8bd -r 59779ce322a6 handouts/pep-ho.tex --- a/handouts/pep-ho.tex Wed Mar 20 21:50:20 2019 +0000 +++ b/handouts/pep-ho.tex Sat Jun 22 08:39:52 2019 +0100 @@ -82,7 +82,7 @@ \end{quote} \noindent -If you are interested there are also experimental backends of Scala +If you are interested, there are also experimental backends of Scala for producing code under Android (\url{http://scala-android.org}); for generating JavaScript code (\url{https://www.scala-js.org}); and there is work under way to have a native Scala compiler generating X86-code @@ -159,7 +159,7 @@ seem to make your life harder, rather than easier, for the small programs we will write in this module. They are really meant to be used when you have a million-lines codebase, rather than our -``toy-programs''\ldots{}for example why on earth am I required to create a +``toy-programs'' we will write in PEP\ldots{}for example why on earth am I required to create a completely new project with several subdirectories when I just want to try out 20-lines of Scala code? Your mileage may vary though. ;o) @@ -432,6 +432,9 @@ scala> "12345".length scala> List(1,2,1).size scala> Set(1,2,1).size +scala> List(1) == List(1) +scala> Array(1) == Array(1) +scala> Array(1).sameElements(Array(1)) \end{lstlisting}\smallskip \noindent diff -r ecd989eee8bd -r 59779ce322a6 progs/lecture1.scala --- a/progs/lecture1.scala Wed Mar 20 21:50:20 2019 +0000 +++ b/progs/lecture1.scala Sat Jun 22 08:39:52 2019 +0100 @@ -143,6 +143,16 @@ val name: String = "leo" +// type errors +math.sqrt("64") + +// produces +// +// error: type mismatch; +// found : String("64") +// required: Double +// math.sqrt("64") + // Pairs/Tuples //============== @@ -468,6 +478,15 @@ count_intersection2(A, B) +//another example +def test() = { + var cnt = 0 + for(i <- (1 to 1000000).par) cnt += 1 + println(cnt) +} + +test() + //for measuring time def time_needed[T](n: Int, code: => T) = { val start = System.nanoTime() diff -r ecd989eee8bd -r 59779ce322a6 progs/mandelbrot.scala --- a/progs/mandelbrot.scala Wed Mar 20 21:50:20 2019 +0000 +++ b/progs/mandelbrot.scala Sat Jun 22 08:39:52 2019 +0100 @@ -11,6 +11,7 @@ import javax.swing.WindowConstants import scala.language.implicitConversions + // complex numbers case class Complex(val re: Double, val im: Double) { // represents the complex number re + im * i diff -r ecd989eee8bd -r 59779ce322a6 progs/roman.scala --- a/progs/roman.scala Wed Mar 20 21:50:20 2019 +0000 +++ b/progs/roman.scala Sat Jun 22 08:39:52 2019 +0100 @@ -1,6 +1,7 @@ -// Part 1 about Roman Numerals -//============================= +// Replacement Exam: Scala Part +//======================================= +// Roman Digits and Numerals abstract class RomanDigit case object I extends RomanDigit @@ -18,16 +19,25 @@ // As soon as a None is inside the list, the result is None. // Otherwise produce a list of all Some's appended. -def optionlist[A](xs: List[Option[A]]): Option[List[A]] = +//def optionlist[A](xs: List[Option[A]]): Option[List[A]] = + + +// some testcases +//optionlist(List(Some(1), Some(2), Some(3))) // -> Some(List(1, 2, 3)) +//optionlist(List(Some(1), None, Some(3))) // -> None +//optionlist(List()) // -> Some(List()) + + + // (2) Write a function first a function that converts a character // into a roman digit (if possible). Then convert a string into -// a roman numeral (if possible). If this is not possible, the functions -// should return None. +// a roman numeral (if possible). In both cases, if the conversion +// is not possible, the functions should return None. -def Char2RomanDigit(c: Char): Option[RomanDigit] = +//def Char2RomanDigit(c: Char): Option[RomanDigit] = -def String2RomanNumeral(s: String) : Option[RomanNumeral] = +//def String2RomanNumeral(s: String) : Option[RomanNumeral] = // some test cases @@ -42,108 +52,63 @@ // (3) Write a recursive function RomanNumral2Int that converts a // RomanNumeral into an integer. -def RomanNumeral2Int(rs: RomanNumeral): Int = +//def RomanNumeral2Int(rs: RomanNumeral): Int = // some test cases -RomanNumeral2Int(List(I,I,I,I)) // 4 -RomanNumeral2Int(List(I,V)) // 4 -RomanNumeral2Int(List(V,I)) // 6 -RomanNumeral2Int(List(I,X)) // 9 -RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 -RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 +//RomanNumeral2Int(List(I,I,I,I)) // 4 +//RomanNumeral2Int(List(I,V)) // 4 +//RomanNumeral2Int(List(V,I)) // 6 +//RomanNumeral2Int(List(I,X)) // 9 +//RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 +//RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 + + // (4) Write a function that converts a string (containing -// a roman numeral) into an integer (if possible). If not +// a roman numeral) into an integer (if possible). If // this is not possible, the functions should return None. -def String2Int(s: String): Option[Int] = - -// some test cases -String2Int("IIII") // 4 (though invalid roman numeral) -String2Int("IV") // 4 -String2Int("VI") // 6 -String2Int("IX") // 9 -String2Int("MCMLXXIX") // 1979 -String2Int("MCMXLIV") // 1944 -String2Int("") // 0 -String2Int("MDCLXI") // 1661 -String2Int("MMMCMXCIX") // 3999 -String2Int("XLVIII") // 48 -String2Int("MMVIII") // 2008 - -String2Int("MMXI") // 2011 -String2Int("MIM") // 1999 -String2Int("MCMLVI") // 1956 - -String2Int("III") // 3 -String2Int("XXX") // 30 -String2Int("CCC") // 300 -String2Int("MMM") // 3000 -String2Int("VII") // 7 -String2Int("LXVI") // 66 -String2Int("CL") // 150 -String2Int("MCC") // 1200 -String2Int("IV") // 4 -String2Int("IX") // 9 -String2Int("XC") // 90 -String2Int("MDCLXVI") // 1666 - -String2Int("VIV") // 9 (but should be written as IX) -String2Int("IVX") // 14 (also invalid) - -// error cases -String2Int("MC?I") -String2Int("abc") - - -// (5) The file roman.txt contains a list of roman numerals. -// Read in these numerals from the file, convert them into -// integers and then add them all up. - -import io.Source -import scala.util._ - -// function for reading files: -// Source.fromFile("file_name")("ISO-8859-9") - -def addromanfile(filename: String) = - -//test case -addromanfile("roman.txt") - - -// Part 2 about Validation of Roman Numerals -//=========================================== - -// (6) Write a function that validates roman numerals according -// to the rules given in the CW. - -def isValidNumeral(digitList: RomanNumeral): Boolean = +//def String2Int(s: String): Option[Int] = // some test cases -val invalids = List("IXC", "XCX", "IIII", "IIIII", "DD", "VL", - "MIM", "XXCIII", "LXXIIX", "IIIIX", "IIXX", - "ICM", "CIM", "VIV", "IVX", "MCMC", "XIIX", "IIXX") +//String2Int("IIII") // 4 (though invalid roman numeral) +//String2Int("IV") // 4 +//String2Int("VI") // 6 +//String2Int("IX") // 9 +//String2Int("MCMLXXIX") // 1979 +//String2Int("MCMXLIV") // 1944 +//String2Int("") // 0 +//String2Int("MDCLXI") // 1661 +//String2Int("MMMCMXCIX") // 3999 +//String2Int("XLVIII") // 48 +//String2Int("MMVIII") // 2008 -val valids = List("IV", "VI", "IX", "MCMLXXIX", "MCMXLIV", "", "MDCLXI", - "MMMCMXCIX", "XLVIII", "MMVIII", "MMXI", "MCMLVI", "III", - "XXX", "CCC", "MMM", "VII", "LXVI", "CL", "MCC", "XC", - "MDCLXVI") - -// (7) Write a recursive function that converts an Integer into a -// a roman numeral. The input will be between 0 and 3999. +//String2Int("MMXI") // 2011 +//String2Int("MIM") // 1999 +//String2Int("MCMLVI") // 1956 -def Int2Roman(n: Int): RomanNumeral = +//String2Int("III") // 3 +//String2Int("XXX") // 30 +//String2Int("CCC") // 300 +//String2Int("MMM") // 3000 +//String2Int("VII") // 7 +//String2Int("LXVI") // 66 +//String2Int("CL") // 150 +//String2Int("MCC") // 1200 +//String2Int("IV") // 4 +//String2Int("IX") // 9 +//String2Int("XC") // 90 +//String2Int("MDCLXVI") // 1666 -// (8) Write a function that reads a text file containing valid and -// invalid roman numerals. Convert all valid roman numerals into integers, -// add them up and produce the result as a roman numeral (using the -// function in (7) +//String2Int("VIV") // 9 (but should be written as IX) +//String2Int("IVX") // 14 (also invalid) -def addvalidromanfile(filename: String) = +// error cases +//String2Int("I I I I") +//String2Int("MC?I") +//String2Int("abc") -// a test case -//addvalidromanfile("roman2.txt") + diff -r ecd989eee8bd -r 59779ce322a6 progs/roman_sol.scala --- a/progs/roman_sol.scala Wed Mar 20 21:50:20 2019 +0000 +++ b/progs/roman_sol.scala Sat Jun 22 08:39:52 2019 +0100 @@ -126,62 +126,12 @@ String2Int("XC") // 90 String2Int("MDCLXVI") // 1666 -String2Int("VIV") // 9 (but should be written as IX) -String2Int("IVX") // 14 (also invalid) -// error cases -String2Int("MC?I") +// error/none cases +String2Int("MC?I") String2Int("abc") -// (5) The file roman.txt contains a list of roman numerals. -// Read in these numerals, convert them into integers and then -// add them all up. - -import io.Source -import scala.util._ - -// function for reading files: -// Source.fromFile("file_name")("ISO-8859-9") - -def addromanfile(filename: String) = { - val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim) - lines.map(String2Int(_)).flatten.sum -} - - -addromanfile("roman.txt") - -val ls = """IIII -IV -VI -IX -MCMLXXIX -MCMXLIV - -MDCLXI -MMMCMXCIX -XLVIII -MMVIII - -MMXI -MIM -MCMLVI - -III -XXX -CCC -MMM -VII -LXVI -CL -MCC -IV -IX -XC -MDCLXVI""".split("\n").map(_.trim).map(String2Int(_)).flatten - -String2Int("MIM") // Part 2 about Validation of Roman Numerals //=========================================== @@ -283,11 +233,3 @@ RomanNumeral2Int(List(M,C,M,X,L,I,V)) -def addvalidromanfile(filename: String) = { - val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim) - val ints = lines.map(String2RomanNumeral(_)).flatten.filter(isValidNumeral(_)).map(RomanNumeral2Int(_)) - ints.sum -} - - -addvalidromanfile("roman2.txt") diff -r ecd989eee8bd -r 59779ce322a6 slides/slides05.tex --- a/slides/slides05.tex Wed Mar 20 21:50:20 2019 +0000 +++ b/slides/slides05.tex Sat Jun 22 08:39:52 2019 +0100 @@ -248,6 +248,7 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% ~2,237,800 lines of proof in 474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%