Binary file cws/cw04.pdf has changed
--- a/cws/cw04.tex Thu Jan 26 01:43:31 2017 +0000
+++ b/cws/cw04.tex Fri Jan 27 14:55:56 2017 +0000
@@ -36,14 +36,14 @@
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.
+\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, they should be transformed into
- the option on the right:
+ if you have the lists on the left-hand side, they should be transformed into
+ the option on the right-hand side:
\begin{center}
\begin{tabular}{lcl}
@@ -61,28 +61,29 @@
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}.
+\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 empty list of \texttt{RomanDigit}'s.
- You should use the function under Task (1) to produce the result.
- \hfill[2 Marks]
+ 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 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.
+\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}
@@ -102,30 +103,82 @@
\end{tabular}
\end{center}
- The empty list will be converted into integer $0$.\hfill[1 Mark]
+ 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, then
- calculate the integer (an option of an integer) according to the
+ 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 function for reading a file is
+ 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 neded.\\ \mbox{}\hfill[1 Mark]
+ 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 $C$; $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}
--- a/progs/roman.scala Thu Jan 26 01:43:31 2017 +0000
+++ b/progs/roman.scala Fri Jan 27 14:55:56 2017 +0000
@@ -115,3 +115,35 @@
// Part 2 about Validation of Roman Numerals
//===========================================
+
+// (6) Write a function that validates roman numerals according
+// to the rules given in the CW.
+
+def isValidNumeral(digitList: RomanNumeral): Boolean =
+
+
+
+// some test cases
+val invalids = List("IXC", "XCX", "IIII", "IIIII", "DD", "VL",
+ "MIM", "XXCIII", "LXXIIX", "IIIIX", "IIXX",
+ "ICM", "CIM", "VIV", "IVX", "MCMC", "XIIX", "IIXX")
+
+val valids = List("IV", "VI", "IX", "MCMLXXIX", "MCMXLIV", "", "MDCLXI",
+ "MMMCMXCIX", "XLVIII", "MMVIII", "MMXI", "MCMLVI", "III",
+ "XXX", "CCC", "MMM", "VII", "LXVI", "CL", "MCC", "XC",
+ "MDCLXVI")
+
+// (7) Write a recursive function that converts an Integer into a
+// a roman numeral. The input will be between 0 and 3999.
+
+def Int2Roman(n: Int): RomanNumeral =
+
+// (8) Write a function that reads a text file containing valid and
+// invalid roman numerals. Convert all valid roman numerals into integers,
+// add them up and produce the result as a roman numeral (using the
+// function in (7)
+
+def addvalidromanfile(filename: String) =
+
+// a test case
+//addvalidromanfile("roman2.txt")
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/roman2.txt Fri Jan 27 14:55:56 2017 +0000
@@ -0,0 +1,30 @@
+IIII
+IV
+VI
+IX
+MCMXLIV
+
+XLVIII
+
+MIM
+IXC
+XCX
+IIII
+IIIII
+DD
+VL
+XIIX
+abc
+
+III
+XXX
+CCC
+VII
+LXVI
+CL
+MCC
+IV
+IX
+XC
+CXXIX
+
--- a/progs/roman_sol.scala Thu Jan 26 01:43:31 2017 +0000
+++ b/progs/roman_sol.scala Fri Jan 27 14:55:56 2017 +0000
@@ -81,7 +81,7 @@
}
// some test cases
-RomanNumeral2Int(List(I,I,I,I)) // 4
+RomanNumeral2Int(List(I,I,I,I)) // 4 (invalid roman number)
RomanNumeral2Int(List(I,V)) // 4
RomanNumeral2Int(List(V,I)) // 6
RomanNumeral2Int(List(I,X)) // 9
@@ -96,8 +96,8 @@
def String2Int(s: String): Option[Int] =
String2RomanNumeral(s).map(RomanNumeral2Int(_))
-
-String2Int("IIII") // 4 invalid
+// some test cases
+String2Int("IIII") // 4 (though invalid roman numeral)
String2Int("IV") // 4
String2Int("VI") // 6
String2Int("IX") // 9
@@ -112,10 +112,6 @@
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
@@ -128,17 +124,16 @@
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
+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.
@@ -158,26 +153,111 @@
addromanfile("roman.txt")
+// Part 2 about Validation of Roman Numerals
+//===========================================
-
+def Digit2Int(r: RomanDigit) = r match {
+ case I => 1
+ case V => 5
+ case X => 10
+ case L => 50
+ case C => 100
+ case D => 500
+ case M => 1000
+}
def runsAllowed(r: RomanDigit) = r match {
case I | X | C | M => true
case V | L | D => false
}
-def norunsAllowed(r: RomanDigit) = !runsAllowed(r)
-
+def subtractable(r1: RomanDigit, r2: RomanDigit) = (r1, r2) match {
+ case (I, V) | (I, X) => true
+ case (X, L) | (X, C) => true
+ case (C, D) | (C, M) => true
+ case _ => false
+}
-def isValidNumeral(digitList: RomanNumeral): Bool = digitList match {
+def isValidNumeral(digitList: RomanNumeral): Boolean = digitList match {
- // empty list is valid
+ // 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
+ // no more than three runnables in succession
+ case d1::d2::d3::d4::_ if (d1 == d2 && d1 == d3 && d1 == d4 && runsAllowed(d1)) => false
+
+ // no more than one non-runnables in succession
+ case d1::d2::_ if (d1 == d2 && !runsAllowed(d1)) => false
+
+ // subtractable
+ case d1::d2::_ if (Digit2Int(d1) < Digit2Int(d2) && !subtractable(d1, d2)) => false
+
+ // followable1
+ case d1::d2::d3::_ if (Digit2Int(d2) < Digit2Int(d3) && subtractable(d2,d3) &&
+ Digit2Int(d1) < Digit2Int(d2) * 10) => false
+
+ // followable2
+ case d1::d2::d3::_ if (Digit2Int(d1) < Digit2Int(d2) && subtractable(d1,d2) &&
+ Digit2Int(d1) <= Digit2Int(d3)) => false
// A single digit is always allowed
case _::ds => isValidNumeral(ds)
}
+
+
+val invalids = List("IXC", "XCX", "IIII", "IIIII", "DD", "VL", "MIM", "XXCIII", "LXXIIX", "IIIIX",
+ "IIXX", "ICM", "CIM", "VIV", "IVX", "MCMC", "XIIX", "IIXX")
+invalids.map(String2RomanNumeral(_)).flatten.map(isValidNumeral(_))
+invalids.map(String2RomanNumeral(_)).flatten.map((r) => (r, isValidNumeral(r)))
+
+
+val valids = List("IV", "VI", "IX", "MCMLXXIX", "MCMXLIV", "", "MDCLXI",
+ "MMMCMXCIX", "XLVIII", "MMVIII", "MMXI", "MCMLVI", "III",
+ "XXX", "CCC", "MMM", "VII", "LXVI", "CL", "MCC", "XC",
+ "MDCLXVI")
+valids.map(String2RomanNumeral(_)).flatten.map(isValidNumeral(_))
+
+
+
+
+
+def Int2Roman(n: Int): RomanNumeral = n match {
+ case 0 => Nil
+ case n if (1000 <= n) => M :: Int2Roman(n - 1000)
+ case n if (900 <= n) => C :: M :: Int2Roman(n - 900)
+ case n if (500 <= n) => D :: Int2Roman(n - 500)
+ case n if (400 <= n) => C :: D :: Int2Roman(n - 400)
+ case n if (100 <= n) => C :: Int2Roman(n - 100)
+ case n if (90 <= n) => X :: C :: Int2Roman(n - 90)
+ case n if (50 <= n) => L :: Int2Roman(n - 50)
+ case n if (40 <= n) => X :: L :: Int2Roman(n - 40)
+ case n if (10 <= n) => X :: Int2Roman(n - 10)
+ case n if (9 <= n) => I :: X :: Int2Roman(n - 9)
+ case n if (5 <= n) => V :: Int2Roman(n - 5)
+ case n if (4 <= n) => I :: V :: Int2Roman(n - 4)
+ case n if (1 <= n) => I :: Int2Roman(n - 1)
+}
+
+
+Int2Roman(4)
+Int2Roman(6)
+Int2Roman(9)
+Int2Roman(1979)
+Int2Roman(1944)
+
+RomanNumeral2Int(List(I,V))
+RomanNumeral2Int(List(V,I))
+RomanNumeral2Int(List(I,X))
+RomanNumeral2Int(List(M,C,M,L,X,X,I,X))
+RomanNumeral2Int(List(M,C,M,X,L,I,V))
+
+
+def addvalidromanfile(filename: String) = {
+ val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim)
+ val ints = lines.map(String2RomanNumeral(_)).flatten.filter(isValidNumeral(_)).map(RomanNumeral2Int(_))
+ ints.sum
+}
+
+
+addvalidromanfile("roman2.txt")