// 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 casesString2RomanNumeral("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 casesRomanNumeral2Int(List(I,I,I,I)) // 4 (invalid roman number)RomanNumeral2Int(List(I,V)) // 4RomanNumeral2Int(List(V,I)) // 6RomanNumeral2Int(List(I,X)) // 9RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979RomanNumeral2Int(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 casesString2Int("IIII") // 4 (though invalid roman numeral) String2Int("IV") // 4String2Int("VI") // 6String2Int("IX") // 9String2Int("MCMLXXIX") // 1979String2Int("MCMXLIV") // 1944String2Int("") // 0String2Int("MDCLXI") // 1661String2Int("MMMCMXCIX") // 3999String2Int("XLVIII") // 48String2Int("MMVIII") // 2008String2Int("MMXI") // 2011 String2Int("MIM") // 2001String2Int("MCMLVI") // 1956 String2Int("III") // 3String2Int("XXX") // 30String2Int("CCC") // 300String2Int("MMM") // 3000String2Int("VII") // 7String2Int("LXVI") // 66String2Int("CL") // 150String2Int("MCC") // 1200String2Int("IV") // 4String2Int("IX") // 9String2Int("XC") // 90String2Int("MDCLXVI") // 1666// error/none casesString2Int("MC?I") String2Int("abc")// 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))