// 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")       // 2001

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

// error/none cases

String2Int("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))