1 \documentclass{article}

     2 \usepackage{../style}

     3 \usepackage{../langs}

     4 

     5 \begin{document}

     6 

     7 \section*{Replacement Coursework 1 (Roman Numerals)}

     8 

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

    10 into integers and also about validating roman numerals.  The coursework

    11 is due on 2 February at 5pm.  Make sure the files you submit can be

    12 processed by just calling \texttt{scala <<filename.scala>>}.\bigskip

    13 

    14 \noindent

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

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

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

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

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

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

    21 inside a class or object. Also note that the running time will be

    22 restricted to a maximum of 360 seconds on my laptop.

    23 

    24 

    25 \subsection*{Disclaimer}

    26 

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

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

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

    30 you can freely use.\bigskip

    31 

    32 

    33 \subsection*{Part 1 (Translation)}

    34 

    35 \noindent

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

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

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

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

    40 this internal representation converted into Integers.

    41 

    42 \begin{itemize}

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

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

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

    46   the options on the right-hand side:

    47 

    48   \begin{center}

    49   \begin{tabular}{lcl}  

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

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

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

    53     \texttt{None} \\

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

    55   \end{tabular}  

    56   \end{center}

    57 

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

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

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

    61   produces \texttt{Some} of the empty list. \hfill[1 Mark]

    62 

    63  

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

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

    66   If it is one of the roman digits, it should produce \texttt{Some};

    67   otherwise \texttt{None}.

    68   

    69   Next write a function that converts a string into a

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

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

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

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

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

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

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

    77   to produce the result.  \hfill[2 Marks]

    78 

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

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

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

    82   function is a list of roman digits. It should look how this list

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

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

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

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

    87 

    88   \begin{center}

    89   \begin{tabular}{lcl}

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

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

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

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

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

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

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

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

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

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

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

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

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

   103   \end{tabular}  

   104   \end{center}    

   105 

   106   The empty list will be converted to integer $0$.\hfill[1 Mark]

   107   

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

   109   converts it into the internal representation. If successful, it then

   110   calculates the integer (an option of an integer) according to the

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

   112   \texttt{None}.\hfill[1 Mark]

   113 

   114 

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

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

   117   up. The Scala function for reading a file is

   118 

   119   \begin{center}

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

   121   \end{center}

   122 

   123   Make sure you process the strings correctly by ignoring whitespaces

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

   125 \end{itemize}

   126 

   127 

   128 \subsection*{Part 2 (Validation)}

   129 

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

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

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

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

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

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

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

   137 

   138 \begin{itemize}

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

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

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

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

   143   

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

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

   146 

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

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

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

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

   151 

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

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

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

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

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

   157 

   158 \item The empty roman numeral is valid.  

   159 \end{itemize}

   160 

   161 \noindent

   162 The tasks in this part are as follows:

   163 

   164 \begin{itemize}

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

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

   167   the rules above are satisfied, and otherwise false.

   168 

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

   170   return true in all other cases.

   171   \mbox{}\hfill[2 Marks]

   172 

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

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

   175   

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

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

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

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

   180 \end{itemize}

   181   

   182 

   183 \end{document}

   184 

   185 

   186 %%% Local Variables: 

   187 %%% mode: latex

   188 %%% TeX-master: t

   189 %%% End: