--- a/cws/cw04.tex Wed Jan 25 01:25:17 2017 +0000
+++ b/cws/cw04.tex Wed Jan 25 14:36:39 2017 +0000
@@ -4,13 +4,12 @@
\begin{document}
-\section*{Replacement Coursework 1 (Roman Nmerals)}
+\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 cursework
-is due on 1 February at 5pm. Make sure the files you submit can
-be processed by just calling \texttt{scala
- <<filename.scala>>}.\bigskip
+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
@@ -19,20 +18,112 @@
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.
+inside a class or object. Also note that the running time will be
+restricted to a maximum of 360 seconds.
\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
+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}, and then from this internal representation
+converted into an Integer.
+
+\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, they should be transformed into
+ the option on the right:
+
+ \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 a function first a function that converts a character
+ $I$, $V$, $X$, $L$, $C$, $D$, or $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 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 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 into 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, then
+ calculate 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 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 neded.\\ \mbox{}\hfill[1 Mark]
+\end{itemize}
+
+
\subsection*{Part 2 (Validation)}
--- a/progs/roman.scala Wed Jan 25 01:25:17 2017 +0000
+++ b/progs/roman.scala Wed Jan 25 14:36:39 2017 +0000
@@ -1,3 +1,7 @@
+// Part 1 about Roman Numerals
+//=============================
+
+
abstract class RomanDigit
case object I extends RomanDigit
case object V extends RomanDigit
@@ -6,3 +10,101 @@
case object C extends RomanDigit
case object D extends RomanDigit
case object M extends RomanDigit
+
+type RomanNumeral = List[RomanDigit]
+
+// (1) First write a polymorphic function that recursively
+// transforms a list of options into an option of a list.
+// As soon as a None is inside the list, the result is None.
+// Otherwise produce a list of all Some's appended.
+
+def optionlist[A](xs: List[Option[A]]): Option[List[A]] =
+
+// (2) Write a function first a function that converts a character
+// into a roman digit (if possible). Then convert a string into
+// a roman numeral (if possible). If this is not possible, the functions
+// should return None.
+
+def Char2RomanDigit(c: Char): Option[RomanDigit] =
+
+def String2RomanNumeral(s: String) : Option[RomanNumeral] =
+
+
+// some test cases
+//String2RomanNumeral("IIII")
+//String2RomanNumeral("IV")
+//String2RomanNumeral("VI")
+//String2RomanNumeral("IX")
+//String2RomanNumeral("MCMLXXIX")
+//String2RomanNumeral("MCMXLIV")
+//String2RomanNumeral("M C M X L I V") // None
+
+// (3) Write a recursive function RomanNumral2Int that converts a
+// RomanNumeral into an integer.
+
+def RomanNumeral2Int(rs: RomanNumeral): Int =
+
+
+// some test cases
+RomanNumeral2Int(List(I,I,I,I)) // 4
+RomanNumeral2Int(List(I,V)) // 4
+RomanNumeral2Int(List(V,I)) // 6
+RomanNumeral2Int(List(I,X)) // 9
+RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979
+RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944
+
+// (4) Write a function that converts a string (containing
+// a roman numeral) into an integer (if possible). If not
+// this is not possible, the functions should return None.
+
+def String2Int(s: String): Option[Int] =
+
+// some test cases
+String2Int("IIII") // 4 (though invalid roman numeral)
+String2Int("IV") // 4
+String2Int("VI") // 6
+String2Int("IX") // 9
+String2Int("MCMLXXIX") // 1979
+String2Int("MCMXLIV") // 1944
+String2Int("") // 0
+String2Int("MDCLXI") // 1661
+String2Int("MMMCMXCIX") // 3999
+String2Int("XLVIII") // 48
+String2Int("MMVIII") // 2008
+
+String2Int("MMXI") // 2011
+String2Int("MIM") // 1999
+String2Int("MCMLVI") // 1956
+
+String2Int("III") // 3
+String2Int("XXX") // 30
+String2Int("CCC") // 300
+String2Int("MMM") // 3000
+String2Int("VII") // 7
+String2Int("LXVI") // 66
+String2Int("CL") // 150
+String2Int("MCC") // 1200
+String2Int("IV") // 4
+String2Int("IX") // 9
+String2Int("XC") // 90
+String2Int("MDCLXVI") // 1666
+
+String2Int("VIV") // 9 (but should be written as IX)
+String2Int("IVX") // 14 (also invalid)
+
+// error cases
+String2Int("MC?I")
+String2Int("abc")
+
+
+
+
+// (5) The file roman.txt contains a list of roman numerals.
+// Read in these numerals, convert them into integers and then
+// add them all up.
+
+import io.Source
+import scala.util._
+
+// function for reading files:
+// Source.fromFile("file_name")("ISO-8859-9")
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/roman.txt Wed Jan 25 14:36:39 2017 +0000
@@ -0,0 +1,28 @@
+IIII
+IV
+VI
+IX
+MCMLXXIX
+MCMXLIV
+
+MDCLXI
+MMMCMXCIX
+XLVIII
+MMVIII
+
+MMXI
+MIM
+MCMLVI
+
+III
+XXX
+CCC
+MMM
+VII
+LXVI
+CL
+MCC
+IV
+IX
+XC
+MDCLXVI
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/roman_sol.scala Wed Jan 25 14:36:39 2017 +0000
@@ -0,0 +1,136 @@
+abstract class RomanDigit
+case object I extends RomanDigit
+case object V extends RomanDigit
+case object X extends RomanDigit
+case object L extends RomanDigit
+case object C extends RomanDigit
+case object D extends RomanDigit
+case object M extends RomanDigit
+
+type RomanNumeral = List[RomanDigit]
+
+def optionlist[A](xs: List[Option[A]]): Option[List[A]] = xs match {
+ case Nil => Some(Nil)
+ case x::xs => (x, optionlist(xs)) match {
+ case (None, _) => None
+ case (_, None) => None
+ case (Some(y), Some(ys)) => Some(y::ys)
+ }
+}
+
+def char2romandigit(c: Char): Option[RomanDigit] = c match {
+ case 'I' => Some(I)
+ case 'V' => Some(V)
+ case 'X' => Some(X)
+ case 'L' => Some(L)
+ case 'C' => Some(C)
+ case 'D' => Some(D)
+ case 'M' => Some(M)
+ case _ => None
+}
+
+def String2RomanNumeral(s: String) : Option[RomanNumeral] =
+ optionlist(s.toList.map(char2romandigit))
+
+String2RomanNumeral("IIII")
+String2RomanNumeral("IV")
+String2RomanNumeral("VI")
+String2RomanNumeral("IX")
+String2RomanNumeral("MCMLXXIX")
+String2RomanNumeral("MCMXLIV")
+String2RomanNumeral("M C M X L I V") // None
+
+////////////////
+
+def RomanNumeral2Int(rs: RomanNumeral): Int = rs match {
+ case Nil => 0
+ case M::r => 1000 + RomanNumeral2Int(r)
+ case C::M::r => 900 + RomanNumeral2Int(r)
+ case D::r => 500 + RomanNumeral2Int(r)
+ case C::D::r => 400 + RomanNumeral2Int(r)
+ case C::r => 100 + RomanNumeral2Int(r)
+ case X::C::r => 90 + RomanNumeral2Int(r)
+ case L::r => 50 + RomanNumeral2Int(r)
+ case X::L::r => 40 + RomanNumeral2Int(r)
+ case X::r => 10 + RomanNumeral2Int(r)
+ case I::X::r => 9 + RomanNumeral2Int(r)
+ case V::r => 5 + RomanNumeral2Int(r)
+ case I::V::r => 4 + RomanNumeral2Int(r)
+ case I::r => 1 + RomanNumeral2Int(r)
+}
+
+RomanNumeral2Int(List(I,I,I,I)) // 4
+RomanNumeral2Int(List(I,V)) // 4
+RomanNumeral2Int(List(V,I)) // 6
+RomanNumeral2Int(List(I,X)) // 9
+RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979
+RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944
+
+
+def String2Int(s: String): Option[Int] =
+ String2RomanNumeral(s).map(RomanNumeral2Int(_))
+
+
+String2Int("IIII") // 4 invalid
+String2Int("IV") // 4
+String2Int("VI") // 6
+String2Int("IX") // 9
+String2Int("MCMLXXIX") // 1979
+String2Int("MCMXLIV") // 1944
+String2Int("") // 0
+String2Int("MDCLXI") // 1661
+String2Int("MMMCMXCIX") // 3999
+String2Int("XLVIII") // 48
+String2Int("MMVIII") // 2008
+
+String2Int("MMXI") // 2011
+String2Int("MIM") // 1999
+String2Int("MCMLVI") // 1956
+String2Int("XXCIII") // ?? 103 / 83
+String2Int("LXXIIX") // ?? 80 / 78
+String2Int("IIIIX") // ?? 12 invalid
+String2Int("IIXX") // ?? 20 / 18 invalid
+
+String2Int("III") // 3
+String2Int("XXX") // 30
+String2Int("CCC") // 300
+String2Int("MMM") // 3000
+String2Int("VII") // 7
+String2Int("LXVI") // 66
+String2Int("CL") // 150
+String2Int("MCC") // 1200
+String2Int("IV") // 4
+String2Int("IX") // 9
+String2Int("XC") // 90
+String2Int("ICM") // ?? 901
+String2Int("CIM") // ?? 899
+String2Int("MDCLXVI") // 1666
+
+String2Int("VIV") //9, but should be written as IX
+String2Int("IVX") // 14 invalid
+
+// error cases
+String2Int("MC?I")
+String2Int("abc")
+
+
+def runsAllowed(r: RomanDigit) = r match {
+ case I | X | C | M => true
+ case V | L | D => false
+}
+
+def norunsAllowed(r: RomanDigit) = !runsAllowed(r)
+
+
+def isValidNumeral(digitList: RomanNumeral): Bool = digitList match {
+
+ // empty list is valid
+ case Nil => true
+
+ // a following digit that is equal or larger is an error
+ case d1::d2::_ if (d1 <= d2) => false
+
+ // A single digit is always allowed
+ case _::ds => isValidNumeral(ds)
+
+}