<< problem 607 - Marsh Crossing |
Problem 610: Roman Numerals II
(see projecteuler.net/problem=610)
A random generator produces a sequence of symbols drawn from the set {I, V, X, L, C, D, M, #}.
Each item in the sequence is determined by selecting one of these symbols at random, independently of the other items in the sequence.
At each step, the seven letters are equally likely to be selected, with probability 14% each, but the # symbol only has a 2% chance of selection.
We write down the sequence of letters from left to right as they are generated, and we stop at the first occurrence of the # symbol (without writing it).
However, we stipulate that what we have written down must always (when non-empty) be a valid Roman numeral representation in minimal form.
If appending the next letter would contravene this then we simply skip it and try again with the next symbol generated.
Please take careful note of About... Roman Numerals for the definitive rules for this problem on what constitutes a "valid Roman numeral representation" and "minimal form".
For example, the (only) sequence that represents 49 is XLIX. The subtractive combination IL is invalid because of rule (ii), while XXXXIX is valid but not minimal.
The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation. These are the same rules as were used in Problem 89,
and members are invited to solve that problem first.
Find the expected value of the number represented by what we have written down when we stop. (If nothing is written down then count that as zero.)
Give your answer rounded to 8 places after the decimal point.
My Algorithm
My solution for problem 89 contained two useful functions: number2roman
and roman2number
.
There is a unique optimal Roman string for each number. The monteCarlo()
function generates random string and checks whether x == roman2number(number2roman(x))
But the Monte-Carlo simulation can't find 8 correct digit after the decimal point (it barely finds the correct digits in front of the decimal point).
I split Roman numbers into two groups:
- those below 1000 → "that don't start with an M"
- those greater than or equal to 1000 => "start with an M"
n2r
, read "number-to-Roman") and the inverse mapping r2n
("Roman-to-number").In a second pass I append to each Roman number each possible Roman letter and check whether this produces a valid, optimal Roman number.
The
search()
function needs this information to find the expected value of a number (between 0 and 999) and its continuations:- if there is no continuation, then return the number itself, e.g. you can't append anything to IX =>
search(9) = 9
- if there is at least one continuation, then find the sum of
- if those percentages don't add to 100% (because not every of the seven Roman letters yields a valid continuation) then divide by the sum
search
ing all initial letters except M.Any numbers above 999 consists of one or more M's plus a number between 0 and 999.
I try to add as many M's as possible until the probability of such a number is below my threshold 10^-9
Interactive test
This feature is not available for the current problem.
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <vector>
#include <cmath>
const unsigned int NumLetters = 7;
const char Letters[] = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
// 2% chance to find the terminal symbol
const double Terminal = 0.02;
// each letter has the same probability of 14% (7*14% + 2% = 100%)
const double AnyLetter = 0.14;
// ---------- roman2number and number2roman were copied from problem 89 ----------
// convert valid roman numbers to binary numbers
unsigned int roman2number(const std::string& roman)
{
unsigned int result = 0;
// remember the value of the previous Roman letter
unsigned int last = 0;
// true, if the current letter is subtracted (and the next identical letters)
bool subtract = false;
// walk through the whole string from the end to the beginning ...
for (auto i = roman.rbegin(); i != roman.rend(); i++)
{
unsigned int current = 0;
switch (*i)
{
case 'M': current = 1000; break;
case 'D': current = 500; break;
case 'C': current = 100; break;
case 'L': current = 50; break;
case 'X': current = 10; break;
case 'V': current = 5; break;
case 'I': current = 1; break;
}
// smaller than its right neighbor ? => we must subtract
if (current < last)
{
subtract = true;
last = current;
}
// bigger than its right neighbor ? => we must add
else if (current > last)
{
subtract = false;
last = current;
}
// note: if current == last then we keep the variables "subtract" and "last" in their current state
// add/subtract accordingly
if (subtract)
result -= current;
else
result += current;
}
return result;
}
std::string number2roman(unsigned int number)
{
// apply these rules in the presented order:
// - as long as number >= steps[i] add roman[i] to result
const unsigned int NumRules = 13;
const unsigned int rules[NumRules] =
{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
const char* action[NumRules] =
{ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
// apply all rules ...
std::string result;
for (unsigned int i = 0; i < NumRules; i++)
// ... as often as needed
while (number >= rules[i])
{
// reduce integer
number -= rules[i];
// add letter(s)
result += action[i];
}
return result;
}
// a simple pseudo-random number generator
// (produces the same result no matter what compiler you have - unlike rand() from math.h)
unsigned int myrand()
{
static unsigned long long seed = 0;
seed = 6364136223846793005ULL * seed + 1;
return (unsigned int)(seed >> 30);
}
// ---------- problem-specific code ----------
// store possible continuations for each Roman representation
std::vector<std::vector<unsigned int>> next(1000);
// run randomized simulation
double monteCarlo(unsigned int iterations)
{
double result = 0;
for (unsigned int i = 0; i < iterations; i++)
{
std::string current;
while (true)
{
// choose a random letter
auto choice = myrand() % 1000;
// is it the terminal sign ?
if (choice < Terminal * 1000)
{
result += roman2number(current);
break;
}
// append letter
current += Letters[choice % NumLetters];
// still valid ?
auto number = roman2number(current);
auto verify = number2roman(number);
// not valid or not optimal, remove last letter
if (current != verify)
current.pop_back();
}
}
return result / iterations;
}
// return expected value of current number and all its potential continuations
double search(unsigned int current)
{
// impossible to add any letter and get another valid, optimal number ? => terminal state
if (next[current].empty())
return current;
// there's a 2% chance that the current number is the final number
auto result = Terminal * current;
auto percentages = Terminal;
// and a 14% chance for each letter 'I', 'V', ...
for (auto x : next[current])
{
result += AnyLetter * search(x);
percentages += AnyLetter;
}
// in almost all cases, only a few letters actually yield a valid continuation
// so that those percentages don't add to 100%, need to adjust for that deficit
result /= percentages;
return result;
}
int main()
{
// store each number's Roman representation (0..999)
std::vector<std::string> n2r(1000);
// map each Roman representation to a number (0..999)
std::map<std::string, unsigned int> r2n;
// generate all Roman numbers from 0 to 999
const unsigned int Thousand = 1000;
for (unsigned int i = 0; i < Thousand; i++)
{
auto roman = number2roman(i);
n2r[i] = roman;
r2n[roman] = i;
}
// for each Roman number between 0 and 999:
// analyze which numbers they can transition into by adding a single letter (e.g. 50 + 'X' => 60)
for (unsigned int i = 0; i < Thousand; i++)
{
auto current = n2r[i];
// add a dummy letter (will be replaced in the next loop)
current += ' ';
// try to append every possible letter
for (auto add : Letters)
{
current.back() = add;
// is it a valid number (and optimal) ?
if (r2n.count(current) == 1)
next[i].push_back(r2n[current]);
}
}
// process all Roman numbers that DON'T start with an M (it's 0..999)
auto upTo1000 = 0.0;
upTo1000 += AnyLetter * search( 1); // I
upTo1000 += AnyLetter * search( 5); // V
upTo1000 += AnyLetter * search( 10); // X
upTo1000 += AnyLetter * search( 50); // L
upTo1000 += AnyLetter * search(100); // C
upTo1000 += AnyLetter * search(500); // D
// stop if adding one more M's doesn't significantly affect the result anymore
auto Precision = 0.000000001; // 10^-9
// count M's => the "thousands"
auto numM = 1;
auto result = upTo1000;
while (true)
{
// "weight" of the M's
auto manyM = numM * 1000 * (1 - AnyLetter);
// add the following letters
auto increment = manyM + upTo1000;
// and the whole thing because less likely the more M's we have ...
result += increment * pow(AnyLetter, numM);
// enough precision ?
if (increment < Precision)
break;
// next iteration
numM++;
}
std::cout << std::fixed << std::setprecision(8)
<< result << std::endl;
// Monte-Carlo simulation
//while (true)
//std::cout << monteCarlo(100000) << std::endl;
return 0;
}
This solution contains 37 empty lines, 52 comments and 6 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.24 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
October 9, 2017 submitted solution
October 9, 2017 added comments
Similar problems at Project Euler
Problem 89: Roman numerals
Note: I'm not even close to solving all problems at Project Euler. Chances are that similar problems do exist and I just haven't looked at them.
Links
projecteuler.net/thread=610 - the best forum on the subject (note: you have to submit the correct solution first)
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
the flashing problem is the one I solved most recently |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |
76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |
126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |
151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |
176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |
201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 |
I scored 13,486 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 607 - Marsh Crossing |