1 \documentclass{article}

     2 \usepackage{../style}

     3 \usepackage{../langs}

     4 

     5 \begin{document}

     6 

     7 \section*{Scala Part (Roman Numerals)}

     8 

     9 This coursework is worth 50\%. It is about translating roman numerals

    10 into integers.  Make sure the files you submit can be

    11 processed by just calling

    12 

    13 \begin{center}

    14   \texttt{scala <<filename.scala>>}

    15 \end{center}%\bigskip

    16 

    17 \noindent

    18 \textbf{Important:} Do not use any mutable data structures in your

    19 submission! They are not needed. This menas you cannot use 

    20 \texttt{ListBuffer}s, \texttt{Array}s, for example. Do not use \texttt{return} in your

    21 code! It has a different meaning in Scala, than in Java.  Do not use

    22 \texttt{var}! This declares a mutable variable.  Make sure the

    23 functions you submit are defined on the ``top-level'' of Scala, not

    24 inside a class or object. 

    25 

    26 

    27 \subsection*{Disclaimer}

    28 

    29 It should be understood that the work you submit represents your own

    30 effort! You have not copied from anyone else. An exception is the

    31 Scala code I showed during the lectures or uploaded to KEATS, which

    32 you can freely use.\bigskip

    33 

    34 

    35 \subsection*{Tasks}

    36 

    37 \noindent

    38 Roman numerals are strings consisting of the letters $I$, $V$, $X$,

    39 $L$, $C$, $D$, and $M$. Such strings should be transformed into an

    40 internal representation using the datatypes \texttt{RomanDigit} and

    41 \texttt{RomanNumeral} (defined in \texttt{roman.scala}), and then from

    42 this internal representation converted into Integers.

    43 

    44 \begin{itemize}

    45 \item[(1)] First write a polymorphic function that recursively

    46   transforms a list of options into an option of a list. For example,

    47   if you have the lists on the left-hand side below, they should be transformed into

    48   the options on the right-hand side:

    49 

    50   \begin{center}

    51   \begin{tabular}{lcl}  

    52     \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ &

    53     \texttt{Some(List(1, 2, 3))} \\

    54     \texttt{List(Some(1), None, Some(3))} & $\Rightarrow$ &

    55     \texttt{None} \\

    56     \texttt{List()} & $\Rightarrow$ & \texttt{Some(List())}

    57   \end{tabular}  

    58   \end{center}

    59 

    60   This means the function should produce \texttt{None} as soon

    61   as a \texttt{None} is inside the list. Otherwise it produces

    62   a list of all \texttt{Some}s. In case the list is empty, it

    63   produces \texttt{Some} of the empty list. \hfill[15\% Marks]

    64 

    65  

    66 \item[(2)] Write first a function that converts the characters $I$, $V$,

    67   $X$, $L$, $C$, $D$, and $M$ into an option of a \texttt{RomanDigit}.

    68   If the input is one of the roman digits, the function should produce \texttt{Some};

    69   otherwise \texttt{None}.

    70   

    71   Next write a function that converts a string into a

    72   \texttt{RomanNumeral}.  Again, this function should return an

    73   \texttt{Option}: If the string consists of $I$, $V$, $X$, $L$, $C$,

    74   $D$, and $M$ only, then it produces \texttt{Some}; otherwise if

    75   there is any other character in the string, it should produce

    76   \texttt{None}. The empty string is just the empty

    77   \texttt{RomanNumeral}, that is the empty list of

    78   \texttt{RomanDigit}'s.  You should use the function under Task (1)

    79   to produce the result.  \hfill[15\% Marks]

    80 

    81 \item[(3)] Write a recursive function \texttt{RomanNumral2Int} that

    82   converts a \texttt{RomanNumeral} into an integer. You can assume the

    83   generated integer will be between 0 and 3999.  The argument of the

    84   function is a list of roman digits. It should analyse how this list

    85   starts and then calculate what the corresponding integer is for this

    86   ``start'' and add it with the integer for the rest of the list. That

    87   means if the argument is of the form shown on the left-hand side, it

    88   should do the calculation on the right-hand side.

    89 

    90   \begin{center}

    91   \begin{tabular}{lcl}

    92     $M::r$    & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\

    93     $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\

    94     $D::r$    & $\Rightarrow$ & $500 + \text{roman numeral of rest}\; r$\\

    95     $C::D::r$ & $\Rightarrow$ & $400 + \text{roman numeral of rest}\; r$\\

    96     $C::r$    & $\Rightarrow$ & $100 + \text{roman numeral of rest}\; r$\\

    97     $X::C::r$ & $\Rightarrow$ & $90 + \text{roman numeral of rest}\; r$\\

    98     $L::r$    & $\Rightarrow$ & $50 + \text{roman numeral of rest}\; r$\\

    99     $X::L::r$ & $\Rightarrow$ & $40 + \text{roman numeral of rest}\; r$\\

   100     $X::r$    & $\Rightarrow$ & $10 + \text{roman numeral of rest}\; r$\\

   101     $I::X::r$ & $\Rightarrow$ & $9 + \text{roman numeral of rest}\; r$\\

   102     $V::r$    & $\Rightarrow$ & $5 + \text{roman numeral of rest}\; r$\\

   103     $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\

   104     $I::r$    & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$

   105   \end{tabular}  

   106   \end{center}    

   107 

   108   The empty list will be converted to integer $0$.\hfill[10\% Mark]

   109   

   110 \item[(4)] Write a function that takes a string as input and if possible

   111   converts it into the internal representation of Roman Numerals. If successful, it then

   112   calculates the corresponding integer (actually an option of an integer) according to the

   113   function in (3).  If this is not possible, then return

   114   \texttt{None}.\\

   115   \mbox{}\hfill[10\% Mark]

   116 

   117 

   118 %\item[(5)] The file \texttt{roman.txt} contains a list of roman numerals.

   119 %  Read in these numerals, convert them into integers and then add them all

   120 %  up. The Scala function for reading a file is

   121 %

   122 %  \begin{center}

   123 %  \texttt{Source.fromFile("filename")("ISO-8859-9")}

   124 %  \end{center}

   125 %

   126 %  Make sure you process the strings correctly by ignoring whitespaces

   127 %  where needed.\\ \mbox{}\hfill[1 Mark]

   128 \end{itemize}

   129 

   130 \end{document}

   131 

   132 \subsection*{Part 2 (Validation)}

   133 

   134 As you can see the function under Task (3) can produce some unexpected

   135 results. For example for $XXCIII$ it produces 103. The reason for this

   136 unexpected result is that $XXCIII$ is actually not a valid roman

   137 number, neither is $IIII$ for 4 nor $MIM$ for 1999. Although actual

   138 Romans were not so fussy about this,\footnote{They happily used

   139   numbers like $XIIX$ or $IIXX$ for 18.} but modern times declared

   140 that there are precise rules for what a valid roman number is, namely:

   141 

   142 \begin{itemize}

   143 \item Repeatable roman digits are $I$, $X$, $C$ and $M$. The other ones

   144   are non-repeatable. Repeatable digits can be repeated upto 3 times in a

   145   number (for example $MMM$ is OK); non-repeatable digits cannot be

   146   repeated at all (for example $VV$ is excluded).

   147   

   148 \item If a smaller digits precedes a bigger digit, then $I$ can precede $V$ and $X$; $X$ can preced

   149   $L$ and $C$; and $C$ can preced $D$ and $M$. No other combination is permitted in this case.

   150 

   151 \item If a smaller digit precedes a bigger digit (for example $IV$), then the smaller number   

   152   must be either the first digit in the number, or follow a digit which is at least 10 times its value.

   153   So $VIV$ is excluded, because $I$ follows $V$ and $I * 10$ is bigger than $V$; but $XIV$ is

   154   allowed, because $I$ follows $X$ and $I * 10$ is equal to $X$.

   155 

   156 \item Let us say two digits are called a \emph{compound} roman digit

   157   when a smaller digit precedes a bigger digit (so $IV$, $XL$, $CM$

   158   for example). If a compound digit is followed by another digit, then

   159   this digit must be smaller than the first digit in the compound

   160   digit. For example $IXI$ is excluded, but $XLI$ is not.

   161 

   162 \item The empty roman numeral is valid.  

   163 \end{itemize}

   164 

   165 \noindent

   166 The tasks in this part are as follows:

   167 

   168 \begin{itemize}

   169 \item[(6)] Implement a recursive function \texttt{isValidNumeral} that

   170   takes a \texttt{RomanNumeral} as argument and produces true if \textbf{all}

   171   the rules above are satisfied, and otherwise false.

   172 

   173   Hint: It might be more convenient to test when the rules fail and then return false;

   174   return true in all other cases.

   175   \mbox{}\hfill[2 Marks]

   176 

   177 \item[(7)] Write a recursive function that converts an Integer into a \texttt{RomanNumeral}.

   178   You can assume the function will only be called for integers between 0 and 3999.\mbox{}\hfill[1 Mark]

   179   

   180 \item[(8)] Write a function that reads a text file (for example \texttt{roman2.txt})

   181   containing valid and invalid roman numerals. Convert all valid roman numerals into

   182   integers, add them up and produce the result as a \texttt{RomanNumeral} (using the function

   183   from (7)). \hfill[1 Mark]

   184 \end{itemize}

   185   

   186 

   187 \end{document}

   188 

   189 

   190 %%% Local Variables: 

   191 %%% mode: latex

   192 %%% TeX-master: t

   193 %%% End: