34 |
34 |
35 \noindent |
35 \noindent |
36 Roman numerals are strings consisting of the letters $I$, $V$, $X$, |
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 |
37 $L$, $C$, $D$, and $M$. Such strings should be transformed into an |
38 internal representation using the datatypes \texttt{RomanDigit} and |
38 internal representation using the datatypes \texttt{RomanDigit} and |
39 \texttt{RomanNumeral}, and then from this internal representation |
39 \texttt{RomanNumeral} (defined in \texttt{roman.scala}), and then from |
40 converted into an Integer. |
40 this internal representation converted into Integers. |
41 |
41 |
42 \begin{itemize} |
42 \begin{itemize} |
43 \item[(1)] First write a polymorphic function that recursively |
43 \item[(1)] First write a polymorphic function that recursively |
44 transforms a list of options into an option of a list. For example, |
44 transforms a list of options into an option of a list. For example, |
45 if you have the lists on the left, they should be transformed into |
45 if you have the lists on the left-hand side, they should be transformed into |
46 the option on the right: |
46 the option on the right-hand side: |
47 |
47 |
48 \begin{center} |
48 \begin{center} |
49 \begin{tabular}{lcl} |
49 \begin{tabular}{lcl} |
50 \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ & |
50 \texttt{List(Some(1), Some(2), Some(3))} & $\Rightarrow$ & |
51 \texttt{Some(List(1, 2, 3))} \\ |
51 \texttt{Some(List(1, 2, 3))} \\ |
59 as a \texttt{None} is inside the list. Otherwise it produces |
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 |
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] |
61 produces \texttt{Some} of the empty list. \hfill[1 Mark] |
62 |
62 |
63 |
63 |
64 \item[(2)] Write a function first a function that converts a character |
64 \item[(2)] Write first a function that converts the characters $I$, $V$, |
65 $I$, $V$, $X$, $L$, $C$, $D$, or $M$ into an option of a \texttt{RomanDigit}. |
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}; |
66 If it is one of the roman digits, it should produce \texttt{Some}; |
67 otherwise \texttt{None}. |
67 otherwise \texttt{None}. |
68 |
68 |
69 Next write a function that converts a string into a \texttt{RomanNumeral}. |
69 Next write a function that converts a string into a |
70 Again, this function should return an \texttt{Option}: |
70 \texttt{RomanNumeral}. Again, this function should return an |
71 If the string consists of $I$, $V$, $X$, $L$, $C$, $D$, and $M$ only, then |
71 \texttt{Option}: If the string consists of $I$, $V$, $X$, $L$, $C$, |
72 it produces \texttt{Some}; otherwise if there is any other character in |
72 $D$, and $M$ only, then it produces \texttt{Some}; otherwise if |
73 the string, it should produce \texttt{None}. The empty string is just |
73 there is any other character in the string, it should produce |
74 the empty \texttt{RomanNumeral}, that is empty list of \texttt{RomanDigit}'s. |
74 \texttt{None}. The empty string is just the empty |
75 You should use the function under Task (1) to produce the result. |
75 \texttt{RomanNumeral}, that is the empty list of |
76 \hfill[2 Marks] |
76 \texttt{RomanDigit}'s. You should use the function under Task (1) |
|
77 to produce the result. \hfill[2 Marks] |
77 |
78 |
78 \item[(3)] Write a recursive function RomanNumral2Int that converts a |
79 \item[(3)] Write a recursive function \texttt{RomanNumral2Int} that |
79 \texttt{RomanNumeral} into an integer. You can assume the generated |
80 converts a \texttt{RomanNumeral} into an integer. You can assume the |
80 integer will be between 0 and 3999. The argument of the function is |
81 generated integer will be between 0 and 3999. The argument of the |
81 a list of roman digits. It should look how this list starts and then |
82 function is a list of roman digits. It should look how this list |
82 calculate what the corresponding integer is for this ``start'' and |
83 starts and then calculate what the corresponding integer is for this |
83 add it with the integer for the rest of the list. That means if the |
84 ``start'' and add it with the integer for the rest of the list. That |
84 argument is of the form shown on the left-hand side, it should do |
85 means if the argument is of the form shown on the left-hand side, it |
85 the calculation on the right-hand side. |
86 should do the calculation on the right-hand side. |
86 |
87 |
87 \begin{center} |
88 \begin{center} |
88 \begin{tabular}{lcl} |
89 \begin{tabular}{lcl} |
89 $M::r$ & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\ |
90 $M::r$ & $\Rightarrow$ & $1000 + \text{roman numeral of rest}\; r$\\ |
90 $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\ |
91 $C::M::r$ & $\Rightarrow$ & $900 + \text{roman numeral of rest}\; r$\\ |
100 $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\ |
101 $I::V::r$ & $\Rightarrow$ & $4 + \text{roman numeral of rest}\; r$\\ |
101 $I::r$ & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$ |
102 $I::r$ & $\Rightarrow$ & $1 + \text{roman numeral of rest}\; r$ |
102 \end{tabular} |
103 \end{tabular} |
103 \end{center} |
104 \end{center} |
104 |
105 |
105 The empty list will be converted into integer $0$.\hfill[1 Mark] |
106 The empty list will be converted to integer $0$.\hfill[1 Mark] |
106 |
107 |
107 \item[(4)] Write a function that takes a string and if possible |
108 \item[(4)] Write a function that takes a string and if possible |
108 converts it into the internal representation. If successful, then |
109 converts it into the internal representation. If successful, it then |
109 calculate the integer (an option of an integer) according to the |
110 calculates the integer (an option of an integer) according to the |
110 function in (3). If this is not possible, then return |
111 function in (3). If this is not possible, then return |
111 \texttt{None}.\hfill[1 Mark] |
112 \texttt{None}.\hfill[1 Mark] |
112 |
113 |
113 |
114 |
114 \item[(5)] The file \texttt{roman.txt} contains a list of roman numerals. |
115 \item[(5)] The file \texttt{roman.txt} contains a list of roman numerals. |
115 Read in these numerals, convert them into integers and then add them all |
116 Read in these numerals, convert them into integers and then add them all |
116 up. The function for reading a file is |
117 up. The Scala function for reading a file is |
117 |
118 |
118 \begin{center} |
119 \begin{center} |
119 \texttt{Source.fromFile("filename")("ISO-8859-9")} |
120 \texttt{Source.fromFile("filename")("ISO-8859-9")} |
120 \end{center} |
121 \end{center} |
121 |
122 |
122 Make sure you process the strings correctly by ignoring whitespaces |
123 Make sure you process the strings correctly by ignoring whitespaces |
123 where neded.\\ \mbox{}\hfill[1 Mark] |
124 where needed.\\ \mbox{}\hfill[1 Mark] |
124 \end{itemize} |
125 \end{itemize} |
125 |
126 |
126 |
127 |
127 \subsection*{Part 2 (Validation)} |
128 \subsection*{Part 2 (Validation)} |
128 |
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 $C$; $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 |
129 |
182 |
130 \end{document} |
183 \end{document} |
131 |
184 |
132 |
185 |
133 %%% Local Variables: |
186 %%% Local Variables: |