diff -r 19b75e899d37 -r 9c03b5e89a2a cws/cw07.tex --- a/cws/cw07.tex Fri Apr 26 17:29:30 2024 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,193 +0,0 @@ -\documentclass{article} -\usepackage{../style} -\usepackage{../langs} - -\begin{document} - -\section*{Scala Part (Roman Numerals)} - -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, \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. - - -\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 - - -\subsection*{Tasks} - -\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} (defined in \texttt{roman.scala}), and then from -this internal representation converted into Integers. - -\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 below, they should be transformed into - the options on the right-hand side: - - \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[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 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 - \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 the empty list of - \texttt{RomanDigit}'s. You should use the function under Task (1) - 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 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 - 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 to integer $0$.\hfill[10\% Mark] - -\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}.\\ - \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] -\end{itemize} - -\end{document} - -\subsection*{Part 2 (Validation)} - -As you can see the function under Task (3) can produce some unexpected -results. For example for $XXCIII$ it produces 103. The reason for this -unexpected result is that $XXCIII$ is actually not a valid roman -number, neither is $IIII$ for 4 nor $MIM$ for 1999. Although actual -Romans were not so fussy about this,\footnote{They happily used - numbers like $XIIX$ or $IIXX$ for 18.} but modern times declared -that there are precise rules for what a valid roman number is, namely: - -\begin{itemize} -\item Repeatable roman digits are $I$, $X$, $C$ and $M$. The other ones - are non-repeatable. Repeatable digits can be repeated upto 3 times in a - number (for example $MMM$ is OK); non-repeatable digits cannot be - repeated at all (for example $VV$ is excluded). - -\item If a smaller digits precedes a bigger digit, then $I$ can precede $V$ and $X$; $X$ can preced - $L$ and $C$; and $C$ can preced $D$ and $M$. No other combination is permitted in this case. - -\item If a smaller digit precedes a bigger digit (for example $IV$), then the smaller number - must be either the first digit in the number, or follow a digit which is at least 10 times its value. - So $VIV$ is excluded, because $I$ follows $V$ and $I * 10$ is bigger than $V$; but $XIV$ is - allowed, because $I$ follows $X$ and $I * 10$ is equal to $X$. - -\item Let us say two digits are called a \emph{compound} roman digit - when a smaller digit precedes a bigger digit (so $IV$, $XL$, $CM$ - for example). If a compound digit is followed by another digit, then - this digit must be smaller than the first digit in the compound - digit. For example $IXI$ is excluded, but $XLI$ is not. - -\item The empty roman numeral is valid. -\end{itemize} - -\noindent -The tasks in this part are as follows: - -\begin{itemize} -\item[(6)] Implement a recursive function \texttt{isValidNumeral} that - takes a \texttt{RomanNumeral} as argument and produces true if \textbf{all} - the rules above are satisfied, and otherwise false. - - Hint: It might be more convenient to test when the rules fail and then return false; - return true in all other cases. - \mbox{}\hfill[2 Marks] - -\item[(7)] Write a recursive function that converts an Integer into a \texttt{RomanNumeral}. - You can assume the function will only be called for integers between 0 and 3999.\mbox{}\hfill[1 Mark] - -\item[(8)] Write a function that reads a text file (for example \texttt{roman2.txt}) - containing valid and invalid roman numerals. Convert all valid roman numerals into - integers, add them up and produce the result as a \texttt{RomanNumeral} (using the function - from (7)). \hfill[1 Mark] -\end{itemize} - - -\end{document} - - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: