// Part 1 about Roman Numerals
//=============================
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]
// (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]] = 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)
}
}
optionlist(List(Some(1), Some(2), Some(3)))
optionlist(List(Some(1), None, Some(3)))
optionlist(List())
// (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] = 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))
// 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 = 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)
}
// some test cases
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
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] =
String2RomanNumeral(s).map(RomanNumeral2Int(_))
// 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")
def addromanfile(filename: String) = {
val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim)
lines.map(String2Int(_)).flatten.sum
}
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 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): Boolean = digitList match {
// empty list is valid
case Nil => true
// 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")