79 case I::V::r => 4 + RomanNumeral2Int(r) |
79 case I::V::r => 4 + RomanNumeral2Int(r) |
80 case I::r => 1 + RomanNumeral2Int(r) |
80 case I::r => 1 + RomanNumeral2Int(r) |
81 } |
81 } |
82 |
82 |
83 // some test cases |
83 // some test cases |
84 RomanNumeral2Int(List(I,I,I,I)) // 4 |
84 RomanNumeral2Int(List(I,I,I,I)) // 4 (invalid roman number) |
85 RomanNumeral2Int(List(I,V)) // 4 |
85 RomanNumeral2Int(List(I,V)) // 4 |
86 RomanNumeral2Int(List(V,I)) // 6 |
86 RomanNumeral2Int(List(V,I)) // 6 |
87 RomanNumeral2Int(List(I,X)) // 9 |
87 RomanNumeral2Int(List(I,X)) // 9 |
88 RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 |
88 RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 |
89 RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 |
89 RomanNumeral2Int(List(M,C,M,X,L,I,V)) // 1944 |
126 String2Int("CL") // 150 |
122 String2Int("CL") // 150 |
127 String2Int("MCC") // 1200 |
123 String2Int("MCC") // 1200 |
128 String2Int("IV") // 4 |
124 String2Int("IV") // 4 |
129 String2Int("IX") // 9 |
125 String2Int("IX") // 9 |
130 String2Int("XC") // 90 |
126 String2Int("XC") // 90 |
131 String2Int("ICM") // ?? 901 |
|
132 String2Int("CIM") // ?? 899 |
|
133 String2Int("MDCLXVI") // 1666 |
127 String2Int("MDCLXVI") // 1666 |
134 |
128 |
135 String2Int("VIV") // 9, but should be written as IX |
129 String2Int("VIV") // 9 (but should be written as IX) |
136 String2Int("IVX") // 14 invalid |
130 String2Int("IVX") // 14 (also invalid) |
137 |
131 |
138 // error cases |
132 // error cases |
139 String2Int("MC?I") |
133 String2Int("MC?I") |
140 String2Int("abc") |
134 String2Int("abc") |
141 |
135 |
|
136 |
142 // (5) The file roman.txt contains a list of roman numerals. |
137 // (5) The file roman.txt contains a list of roman numerals. |
143 // Read in these numerals, convert them into integers and then |
138 // Read in these numerals, convert them into integers and then |
144 // add them all up. |
139 // add them all up. |
145 |
140 |
146 import io.Source |
141 import io.Source |
156 |
151 |
157 |
152 |
158 addromanfile("roman.txt") |
153 addromanfile("roman.txt") |
159 |
154 |
160 |
155 |
161 |
156 // Part 2 about Validation of Roman Numerals |
162 |
157 //=========================================== |
|
158 |
|
159 def Digit2Int(r: RomanDigit) = r match { |
|
160 case I => 1 |
|
161 case V => 5 |
|
162 case X => 10 |
|
163 case L => 50 |
|
164 case C => 100 |
|
165 case D => 500 |
|
166 case M => 1000 |
|
167 } |
163 |
168 |
164 def runsAllowed(r: RomanDigit) = r match { |
169 def runsAllowed(r: RomanDigit) = r match { |
165 case I | X | C | M => true |
170 case I | X | C | M => true |
166 case V | L | D => false |
171 case V | L | D => false |
167 } |
172 } |
168 |
173 |
169 def norunsAllowed(r: RomanDigit) = !runsAllowed(r) |
174 def subtractable(r1: RomanDigit, r2: RomanDigit) = (r1, r2) match { |
170 |
175 case (I, V) | (I, X) => true |
171 |
176 case (X, L) | (X, C) => true |
172 def isValidNumeral(digitList: RomanNumeral): Bool = digitList match { |
177 case (C, D) | (C, M) => true |
173 |
178 case _ => false |
174 // empty list is valid |
179 } |
|
180 |
|
181 def isValidNumeral(digitList: RomanNumeral): Boolean = digitList match { |
|
182 |
|
183 // empty list is valid |
175 case Nil => true |
184 case Nil => true |
176 |
185 |
177 // a following digit that is equal or larger is an error |
186 // no more than three runnables in succession |
178 case d1::d2::_ if (d1 <= d2) => false |
187 case d1::d2::d3::d4::_ if (d1 == d2 && d1 == d3 && d1 == d4 && runsAllowed(d1)) => false |
|
188 |
|
189 // no more than one non-runnables in succession |
|
190 case d1::d2::_ if (d1 == d2 && !runsAllowed(d1)) => false |
|
191 |
|
192 // subtractable |
|
193 case d1::d2::_ if (Digit2Int(d1) < Digit2Int(d2) && !subtractable(d1, d2)) => false |
|
194 |
|
195 // followable1 |
|
196 case d1::d2::d3::_ if (Digit2Int(d2) < Digit2Int(d3) && subtractable(d2,d3) && |
|
197 Digit2Int(d1) < Digit2Int(d2) * 10) => false |
|
198 |
|
199 // followable2 |
|
200 case d1::d2::d3::_ if (Digit2Int(d1) < Digit2Int(d2) && subtractable(d1,d2) && |
|
201 Digit2Int(d1) <= Digit2Int(d3)) => false |
179 |
202 |
180 // A single digit is always allowed |
203 // A single digit is always allowed |
181 case _::ds => isValidNumeral(ds) |
204 case _::ds => isValidNumeral(ds) |
182 |
205 |
183 } |
206 } |
|
207 |
|
208 |
|
209 val invalids = List("IXC", "XCX", "IIII", "IIIII", "DD", "VL", "MIM", "XXCIII", "LXXIIX", "IIIIX", |
|
210 "IIXX", "ICM", "CIM", "VIV", "IVX", "MCMC", "XIIX", "IIXX") |
|
211 invalids.map(String2RomanNumeral(_)).flatten.map(isValidNumeral(_)) |
|
212 invalids.map(String2RomanNumeral(_)).flatten.map((r) => (r, isValidNumeral(r))) |
|
213 |
|
214 |
|
215 val valids = List("IV", "VI", "IX", "MCMLXXIX", "MCMXLIV", "", "MDCLXI", |
|
216 "MMMCMXCIX", "XLVIII", "MMVIII", "MMXI", "MCMLVI", "III", |
|
217 "XXX", "CCC", "MMM", "VII", "LXVI", "CL", "MCC", "XC", |
|
218 "MDCLXVI") |
|
219 valids.map(String2RomanNumeral(_)).flatten.map(isValidNumeral(_)) |
|
220 |
|
221 |
|
222 |
|
223 |
|
224 |
|
225 def Int2Roman(n: Int): RomanNumeral = n match { |
|
226 case 0 => Nil |
|
227 case n if (1000 <= n) => M :: Int2Roman(n - 1000) |
|
228 case n if (900 <= n) => C :: M :: Int2Roman(n - 900) |
|
229 case n if (500 <= n) => D :: Int2Roman(n - 500) |
|
230 case n if (400 <= n) => C :: D :: Int2Roman(n - 400) |
|
231 case n if (100 <= n) => C :: Int2Roman(n - 100) |
|
232 case n if (90 <= n) => X :: C :: Int2Roman(n - 90) |
|
233 case n if (50 <= n) => L :: Int2Roman(n - 50) |
|
234 case n if (40 <= n) => X :: L :: Int2Roman(n - 40) |
|
235 case n if (10 <= n) => X :: Int2Roman(n - 10) |
|
236 case n if (9 <= n) => I :: X :: Int2Roman(n - 9) |
|
237 case n if (5 <= n) => V :: Int2Roman(n - 5) |
|
238 case n if (4 <= n) => I :: V :: Int2Roman(n - 4) |
|
239 case n if (1 <= n) => I :: Int2Roman(n - 1) |
|
240 } |
|
241 |
|
242 |
|
243 Int2Roman(4) |
|
244 Int2Roman(6) |
|
245 Int2Roman(9) |
|
246 Int2Roman(1979) |
|
247 Int2Roman(1944) |
|
248 |
|
249 RomanNumeral2Int(List(I,V)) |
|
250 RomanNumeral2Int(List(V,I)) |
|
251 RomanNumeral2Int(List(I,X)) |
|
252 RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) |
|
253 RomanNumeral2Int(List(M,C,M,X,L,I,V)) |
|
254 |
|
255 |
|
256 def addvalidromanfile(filename: String) = { |
|
257 val lines = Source.fromFile(filename)("ISO-8859-9").getLines.toList.map(_.trim) |
|
258 val ints = lines.map(String2RomanNumeral(_)).flatten.filter(isValidNumeral(_)).map(RomanNumeral2Int(_)) |
|
259 ints.sum |
|
260 } |
|
261 |
|
262 |
|
263 addvalidromanfile("roman2.txt") |