\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
\begin{document}
\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 coursework
is due on 2 February at 5pm. Make sure the files you submit can be
processed by just calling \texttt{scala <<filename.scala>>}.\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
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.
\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*{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} (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, 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[1 Mark]
\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};
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[2 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
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[1 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
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 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}
\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: