# HG changeset patch # User Christian Urban # Date 1485354999 0 # Node ID 67ce930b5935633ddb80297e4e9d0e300b72bc73 # Parent 07780accd5dfa7c58c0ec427a8ce87ea0bc019d0 updated diff -r 07780accd5df -r 67ce930b5935 cws/cw04.tex --- a/cws/cw04.tex Wed Jan 25 01:25:17 2017 +0000 +++ b/cws/cw04.tex Wed Jan 25 14:36:39 2017 +0000 @@ -4,13 +4,12 @@ \begin{document} -\section*{Replacement Coursework 1 (Roman Nmerals)} +\section*{Replacement Coursework 1 (Roman Numerals)} This coursework is worth 10\%. It is about translating roman numerals -into integers and also about validating roman numerals. The cursework -is due on 1 February at 5pm. Make sure the files you submit can -be processed by just calling \texttt{scala - <>}.\bigskip +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 \noindent \textbf{Important:} Do not use any mutable data structures in your @@ -19,20 +18,112 @@ 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. +inside a class or object. Also note that the running time will be +restricted to a maximum of 360 seconds. \subsection*{Disclaimer} -It should be understood that the work you submit represents -your own effort! You have not copied from anyone else. An -exception is the Scala code I showed during the lectures or -uploaded to KEATS, which you can freely use.\bigskip +It should be understood that the work you submit represents your own +effort! You have not copied from anyone else. An exception is the +Scala code I showed during the lectures or uploaded to KEATS, which +you can freely use.\bigskip \subsection*{Part 1 (Translation)} +\noindent +Roman numerals are strings consisting of the letters $I$, $V$, $X$, +$L$, $C$, $D$, and $M$. Such strings should be transformed into an +internal representation using the datatypes \texttt{RomanDigit} and +\texttt{RomanNumeral}, and then from this internal representation +converted into an Integer. + +\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, they should be transformed into + the option on the right: + + \begin{center} + \begin{tabular}{lcl} + \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ & + \texttt{Some(List(1, 2, 3))} \\ + \texttt{List(Some(1), None, Some(3))} & $\Rightarrow$ & + \texttt{None} \\ + \texttt{List()} & $\Rightarrow$ & \texttt{Some(List())} + \end{tabular} + \end{center} + + 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] + + +\item[(2)] Write a function first a function that converts a character + $I$, $V$, $X$, $L$, $C$, $D$, or $M$ into an option of a \texttt{RomanDigit}. + If it is one of the roman digits, it should produce \texttt{Some}; + otherwise \texttt{None}. + + Next write a function that converts a string into a \texttt{RomanNumeral}. + Again, this function should return an \texttt{Option}: + If the string consists of $I$, $V$, $X$, $L$, $C$, $D$, and $M$ only, then + it produces \texttt{Some}; otherwise if there is any other character in + the string, it should produce \texttt{None}. The empty string is just + the empty \texttt{RomanNumeral}, that is empty list of \texttt{RomanDigit}'s. + You should use the function under Task (1) to produce the result. + \hfill[2 Marks] + +\item[(3)] Write a recursive function 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 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 should do + the calculation on the right-hand side. + + \begin{center} + \begin{tabular}{lcl} + $M::r$ & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\ + $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\ + $D::r$ & $\Rightarrow$ & $500 + \text{roman numeral of rest}\; r$\\ + $C::D::r$ & $\Rightarrow$ & $400 + \text{roman numeral of rest}\; r$\\ + $C::r$ & $\Rightarrow$ & $100 + \text{roman numeral of rest}\; r$\\ + $X::C::r$ & $\Rightarrow$ & $90 + \text{roman numeral of rest}\; r$\\ + $L::r$ & $\Rightarrow$ & $50 + \text{roman numeral of rest}\; r$\\ + $X::L::r$ & $\Rightarrow$ & $40 + \text{roman numeral of rest}\; r$\\ + $X::r$ & $\Rightarrow$ & $10 + \text{roman numeral of rest}\; r$\\ + $I::X::r$ & $\Rightarrow$ & $9 + \text{roman numeral of rest}\; r$\\ + $V::r$ & $\Rightarrow$ & $5 + \text{roman numeral of rest}\; r$\\ + $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\ + $I::r$ & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$ + \end{tabular} + \end{center} + + The empty list will be converted into integer $0$.\hfill[1 Mark] + +\item[(4)] Write a function that takes a string and if possible + converts it into the internal representation. If successful, then + calculate the integer (an option of an integer) according to the + function in (3). If this is not possible, then return + \texttt{None}.\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 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 neded.\\ \mbox{}\hfill[1 Mark] +\end{itemize} + + \subsection*{Part 2 (Validation)} diff -r 07780accd5df -r 67ce930b5935 progs/roman.scala --- a/progs/roman.scala Wed Jan 25 01:25:17 2017 +0000 +++ b/progs/roman.scala Wed Jan 25 14:36:39 2017 +0000 @@ -1,3 +1,7 @@ +// Part 1 about Roman Numerals +//============================= + + abstract class RomanDigit case object I extends RomanDigit case object V extends RomanDigit @@ -6,3 +10,101 @@ case object C extends RomanDigit case object D extends RomanDigit case object M extends RomanDigit + +type RomanNumeral = List[RomanDigit] + +// (1) First write a polymorphic function that recursively +// transforms a list of options into an option of a list. +// 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]] = + +// (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. + +def Char2RomanDigit(c: Char): Option[RomanDigit] = + +def String2RomanNumeral(s: String) : Option[RomanNumeral] = + + +// some test cases +//String2RomanNumeral("IIII") +//String2RomanNumeral("IV") +//String2RomanNumeral("VI") +//String2RomanNumeral("IX") +//String2RomanNumeral("MCMLXXIX") +//String2RomanNumeral("MCMXLIV") +//String2RomanNumeral("M C M X L I V") // None + +// (3) Write a recursive function RomanNumral2Int that converts a +// RomanNumeral into an integer. + +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 + +// (4) Write a function that converts a string (containing +// a roman numeral) into an integer (if possible). If not +// 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, 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") diff -r 07780accd5df -r 67ce930b5935 progs/roman.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/roman.txt Wed Jan 25 14:36:39 2017 +0000 @@ -0,0 +1,28 @@ +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 diff -r 07780accd5df -r 67ce930b5935 progs/roman_sol.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/roman_sol.scala Wed Jan 25 14:36:39 2017 +0000 @@ -0,0 +1,136 @@ +abstract class RomanDigit +case object I extends RomanDigit +case object V extends RomanDigit +case object X extends RomanDigit +case object L extends RomanDigit +case object C extends RomanDigit +case object D extends RomanDigit +case object M extends RomanDigit + +type RomanNumeral = List[RomanDigit] + +def optionlist[A](xs: List[Option[A]]): Option[List[A]] = xs match { + case Nil => Some(Nil) + case x::xs => (x, optionlist(xs)) match { + case (None, _) => None + case (_, None) => None + case (Some(y), Some(ys)) => Some(y::ys) + } +} + +def char2romandigit(c: Char): Option[RomanDigit] = c match { + case 'I' => Some(I) + case 'V' => Some(V) + case 'X' => Some(X) + case 'L' => Some(L) + case 'C' => Some(C) + case 'D' => Some(D) + case 'M' => Some(M) + case _ => None +} + +def String2RomanNumeral(s: String) : Option[RomanNumeral] = + optionlist(s.toList.map(char2romandigit)) + +String2RomanNumeral("IIII") +String2RomanNumeral("IV") +String2RomanNumeral("VI") +String2RomanNumeral("IX") +String2RomanNumeral("MCMLXXIX") +String2RomanNumeral("MCMXLIV") +String2RomanNumeral("M C M X L I V") // None + +//////////////// + +def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { + case Nil => 0 + case M::r => 1000 + RomanNumeral2Int(r) + case C::M::r => 900 + RomanNumeral2Int(r) + case D::r => 500 + RomanNumeral2Int(r) + case C::D::r => 400 + RomanNumeral2Int(r) + case C::r => 100 + RomanNumeral2Int(r) + case X::C::r => 90 + RomanNumeral2Int(r) + case L::r => 50 + RomanNumeral2Int(r) + case X::L::r => 40 + RomanNumeral2Int(r) + case X::r => 10 + RomanNumeral2Int(r) + case I::X::r => 9 + RomanNumeral2Int(r) + case V::r => 5 + RomanNumeral2Int(r) + case I::V::r => 4 + RomanNumeral2Int(r) + case I::r => 1 + RomanNumeral2Int(r) +} + +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 + + +def String2Int(s: String): Option[Int] = + String2RomanNumeral(s).map(RomanNumeral2Int(_)) + + +String2Int("IIII") // 4 invalid +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("XXCIII") // ?? 103 / 83 +String2Int("LXXIIX") // ?? 80 / 78 +String2Int("IIIIX") // ?? 12 invalid +String2Int("IIXX") // ?? 20 / 18 invalid + +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("ICM") // ?? 901 +String2Int("CIM") // ?? 899 +String2Int("MDCLXVI") // 1666 + +String2Int("VIV") //9, but should be written as IX +String2Int("IVX") // 14 invalid + +// error cases +String2Int("MC?I") +String2Int("abc") + + +def runsAllowed(r: RomanDigit) = r match { + case I | X | C | M => true + case V | L | D => false +} + +def norunsAllowed(r: RomanDigit) = !runsAllowed(r) + + +def isValidNumeral(digitList: RomanNumeral): Bool = digitList match { + + // empty list is valid + case Nil => true + + // a following digit that is equal or larger is an error + case d1::d2::_ if (d1 <= d2) => false + + // A single digit is always allowed + case _::ds => isValidNumeral(ds) + +}