|
1 // Part 1 about Roman Numerals |
|
2 //============================= |
|
3 |
1 abstract class RomanDigit |
4 abstract class RomanDigit |
2 case object I extends RomanDigit |
5 case object I extends RomanDigit |
3 case object V extends RomanDigit |
6 case object V extends RomanDigit |
4 case object X extends RomanDigit |
7 case object X extends RomanDigit |
5 case object L extends RomanDigit |
8 case object L extends RomanDigit |
7 case object D extends RomanDigit |
10 case object D extends RomanDigit |
8 case object M extends RomanDigit |
11 case object M extends RomanDigit |
9 |
12 |
10 type RomanNumeral = List[RomanDigit] |
13 type RomanNumeral = List[RomanDigit] |
11 |
14 |
|
15 |
|
16 // (1) First write a polymorphic function that recursively |
|
17 // transforms a list of options into an option of a list. |
|
18 // As soon as a None is inside the list, the result is None. |
|
19 // Otherwise produce a list of all Some's appended. |
|
20 |
12 def optionlist[A](xs: List[Option[A]]): Option[List[A]] = xs match { |
21 def optionlist[A](xs: List[Option[A]]): Option[List[A]] = xs match { |
13 case Nil => Some(Nil) |
22 case Nil => Some(Nil) |
14 case x::xs => (x, optionlist(xs)) match { |
23 case x::xs => (x, optionlist(xs)) match { |
15 case (None, _) => None |
24 case (None, _) => None |
16 case (_, None) => None |
25 case (_, None) => None |
17 case (Some(y), Some(ys)) => Some(y::ys) |
26 case (Some(y), Some(ys)) => Some(y::ys) |
18 } |
27 } |
19 } |
28 } |
20 |
29 |
21 def char2romandigit(c: Char): Option[RomanDigit] = c match { |
30 optionlist(List(Some(1), Some(2), Some(3))) |
|
31 optionlist(List(Some(1), None, Some(3))) |
|
32 optionlist(List()) |
|
33 |
|
34 // (2) Write a function first a function that converts a character |
|
35 // into a roman digit (if possible). Then convert a string into |
|
36 // a roman numeral (if possible). If this is not possible, the functions |
|
37 // should return None. |
|
38 |
|
39 def Char2RomanDigit(c: Char): Option[RomanDigit] = c match { |
22 case 'I' => Some(I) |
40 case 'I' => Some(I) |
23 case 'V' => Some(V) |
41 case 'V' => Some(V) |
24 case 'X' => Some(X) |
42 case 'X' => Some(X) |
25 case 'L' => Some(L) |
43 case 'L' => Some(L) |
26 case 'C' => Some(C) |
44 case 'C' => Some(C) |
28 case 'M' => Some(M) |
46 case 'M' => Some(M) |
29 case _ => None |
47 case _ => None |
30 } |
48 } |
31 |
49 |
32 def String2RomanNumeral(s: String) : Option[RomanNumeral] = |
50 def String2RomanNumeral(s: String) : Option[RomanNumeral] = |
33 optionlist(s.toList.map(char2romandigit)) |
51 optionlist(s.toList.map(Char2RomanDigit)) |
34 |
52 |
|
53 // some test cases |
35 String2RomanNumeral("IIII") |
54 String2RomanNumeral("IIII") |
36 String2RomanNumeral("IV") |
55 String2RomanNumeral("IV") |
37 String2RomanNumeral("VI") |
56 String2RomanNumeral("VI") |
38 String2RomanNumeral("IX") |
57 String2RomanNumeral("IX") |
39 String2RomanNumeral("MCMLXXIX") |
58 String2RomanNumeral("MCMLXXIX") |
40 String2RomanNumeral("MCMXLIV") |
59 String2RomanNumeral("MCMXLIV") |
41 String2RomanNumeral("M C M X L I V") // None |
60 String2RomanNumeral("M C M X L I V") // None |
42 |
61 |
43 //////////////// |
62 |
|
63 // (3) Write a recursive function RomanNumral2Int that converts a |
|
64 // RomanNumeral into an integer. |
44 |
65 |
45 def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { |
66 def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { |
46 case Nil => 0 |
67 case Nil => 0 |
47 case M::r => 1000 + RomanNumeral2Int(r) |
68 case M::r => 1000 + RomanNumeral2Int(r) |
48 case C::M::r => 900 + RomanNumeral2Int(r) |
69 case C::M::r => 900 + RomanNumeral2Int(r) |
57 case V::r => 5 + RomanNumeral2Int(r) |
78 case V::r => 5 + RomanNumeral2Int(r) |
58 case I::V::r => 4 + RomanNumeral2Int(r) |
79 case I::V::r => 4 + RomanNumeral2Int(r) |
59 case I::r => 1 + RomanNumeral2Int(r) |
80 case I::r => 1 + RomanNumeral2Int(r) |
60 } |
81 } |
61 |
82 |
|
83 // some test cases |
62 RomanNumeral2Int(List(I,I,I,I)) // 4 |
84 RomanNumeral2Int(List(I,I,I,I)) // 4 |
63 RomanNumeral2Int(List(I,V)) // 4 |
85 RomanNumeral2Int(List(I,V)) // 4 |
64 RomanNumeral2Int(List(V,I)) // 6 |
86 RomanNumeral2Int(List(V,I)) // 6 |
65 RomanNumeral2Int(List(I,X)) // 9 |
87 RomanNumeral2Int(List(I,X)) // 9 |
66 RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 |
88 RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 |
67 RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 |
89 RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 |
68 |
90 |
|
91 |
|
92 // (4) Write a function that converts a string (containing |
|
93 // a roman numeral) into an integer (if possible). If not |
|
94 // this is not possible, the functions should return None. |
69 |
95 |
70 def String2Int(s: String): Option[Int] = |
96 def String2Int(s: String): Option[Int] = |
71 String2RomanNumeral(s).map(RomanNumeral2Int(_)) |
97 String2RomanNumeral(s).map(RomanNumeral2Int(_)) |
72 |
98 |
73 |
99 |
104 String2Int("XC") // 90 |
130 String2Int("XC") // 90 |
105 String2Int("ICM") // ?? 901 |
131 String2Int("ICM") // ?? 901 |
106 String2Int("CIM") // ?? 899 |
132 String2Int("CIM") // ?? 899 |
107 String2Int("MDCLXVI") // 1666 |
133 String2Int("MDCLXVI") // 1666 |
108 |
134 |
109 String2Int("VIV") //9, but should be written as IX |
135 String2Int("VIV") // 9, but should be written as IX |
110 String2Int("IVX") // 14 invalid |
136 String2Int("IVX") // 14 invalid |
111 |
137 |
112 // error cases |
138 // error cases |
113 String2Int("MC?I") |
139 String2Int("MC?I") |
114 String2Int("abc") |
140 String2Int("abc") |
|
141 |
|
142 // (5) The file roman.txt contains a list of roman numerals. |
|
143 // Read in these numerals, convert them into integers and then |
|
144 // add them all up. |
|
145 |
|
146 import io.Source |
|
147 import scala.util._ |
|
148 |
|
149 // function for reading files: |
|
150 // Source.fromFile("file_name")("ISO-8859-9") |
|
151 |
|
152 def addromanfile(filename: String) = { |
|
153 val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim) |
|
154 lines.map(String2Int(_)).flatten.sum |
|
155 } |
|
156 |
|
157 |
|
158 addromanfile("roman.txt") |
|
159 |
|
160 |
|
161 |
115 |
162 |
116 |
163 |
117 def runsAllowed(r: RomanDigit) = r match { |
164 def runsAllowed(r: RomanDigit) = r match { |
118 case I | X | C | M => true |
165 case I | X | C | M => true |
119 case V | L | D => false |
166 case V | L | D => false |