<< problem 204 - Generalised Hamming Numbers | Concealed Square - problem 206 >> |
Problem 205: Dice Game
(see projecteuler.net/problem=205)
Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2, 3, 4.
Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4, 5, 6.
Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.
What is the probability that Pyramidal Pete beats Cubic Colin? Give your answer rounded to seven decimal places in the form 0.abcdefg
My Algorithm
The function roll
counts all possible outcomes when rolling a number of dices.
In main
I iterate over all possible totals and count how often Peter wins against Colin:
beats_i = dfrac{ sum_{1..i-1}{six_i}}{ sum_{1..36}{six_i}}
beats_i has to be multiplied by the probability that Peter rolls i, which is:
roll_i = dfrac{four_i}{ sum_{1..36}{four_i}}
Note
I wasn't sure how to submit my solution: whether I should type in the leading zero and the decimal dot - or not.
Turns out you should enter your result the way it is printed by the program, including both zero and dot.
An interactive live test is available for this problem.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "4 6 6 4" | ./205
Output:
Note: the original problem's input 6 6 9 4
cannot be entered
because just copying results is a soft skill reserved for idiots.
(this interactive test is still under development, computations will be aborted after one second)
My code
… was written in C++ and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.
#include <iostream>
#include <iomanip>
#include <vector>
// roll dices, store at count[x] how often the sum of all dices was exactly x
void roll(unsigned int dices, unsigned int sides, std::vector<unsigned int>& count, unsigned int sum = 0)
{
// rolled all dices, increment the sum's counter
if (dices == 0)
{
count[sum]++;
return;
}
// all combinations of a dice ...
for (unsigned int i = 1; i <= sides; i++)
roll(dices - 1, sides, count, sum + i);
}
int main()
{
unsigned int dicesPeter, sidesPeter;
std::cin >> dicesPeter >> sidesPeter; // 6 6
unsigned int dicesColin, sidesColin;
std::cin >> dicesColin >> sidesColin; // 9 4
// "high score", by default 9*4 = 6*6 = 36
unsigned int maxTotal = std::max(dicesPeter * sidesPeter, dicesColin * sidesColin);
// roll all 6x6 dices (Colin)
std::vector<unsigned int> colin(maxTotal + 1, 0);
roll(dicesPeter, sidesPeter, colin);
unsigned int sumColin = 0; // will be 46656 for 6,6
for (auto x : colin)
sumColin += x;
// roll all 9x4 dices (Peter)
std::vector<unsigned int> peter(maxTotal + 1, 0);
roll(dicesColin, sidesColin, peter);
unsigned int sumPeter = 0; // will be 262144 for 9,4
for (auto x : peter)
sumPeter += x;
// for each of Peter's potential dice sums, find how often it wins against Colin
double winPeter = 0;
for (unsigned int sum = 1; sum <= maxTotal; sum++)
{
// win if total is higher
unsigned int numWins = 0;
// => add all combinations of Colin that are smaller
for (unsigned int j = 1; j < sum; j++)
numWins += colin[j];
// compute percentage that current sum (Peter) wins against Colin
double beats = numWins / double(sumColin);
// add all of them ...
winPeter += beats * peter[sum] / sumPeter;
}
// done !
std::cout << std::fixed << std::setprecision(7) << winPeter << std::endl;
return 0;
}
This solution contains 9 empty lines, 12 comments and 3 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in less than 0.01 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
May 26, 2017 submitted solution
May 26, 2017 added comments
Difficulty
Project Euler ranks this problem at 15% (out of 100%).
Links
projecteuler.net/thread=205 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/hughdbrown/Project-Euler/blob/master/euler-205.py (written by Hugh Brown)
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p205.py (written by Nayuki)
Python github.com/sefakilic/euler/blob/master/python/euler205.py (written by Sefa Kilic)
C++ github.com/Meng-Gen/ProjectEuler/blob/master/205.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/205.cpp (written by Yuping Luo)
C github.com/LaurentMazare/ProjectEuler/blob/master/e205.c (written by Laurent Mazare)
C github.com/zmwangx/Project-Euler/blob/master/205/205.c (written by Zhiming Wang)
Java github.com/HaochenLiu/My-Project-Euler/blob/master/205.java (written by Haochen Liu)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p205.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem205.java (written by Magnus Solheim Thrap)
Go github.com/frrad/project-euler/blob/master/golang/Problem205.go (written by Frederick Robinson)
Mathematica github.com/nayuki/Project-Euler-solutions/blob/master/mathematica/p205.mathematica (written by Nayuki)
Haskell github.com/nayuki/Project-Euler-solutions/blob/master/haskell/p205.hs (written by Nayuki)
Clojure github.com/rm-hull/project-euler/blob/master/src/euler205.clj (written by Richard Hull)
Perl github.com/gustafe/projecteuler/blob/master/205-Dice-game.pl (written by Gustaf Erikson)
Perl github.com/shlomif/project-euler/blob/master/project-euler/205/euler-205.pl (written by Shlomi Fish)
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own.
Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
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 | |
[new] | the flashing problem is the one I solved most recently |
I stopped working on Project Euler problems around the time they released 617.
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 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 | 634 | 635 | 636 | 637 | 638 | 639 | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 | 648 | 649 | 650 |
651 | 652 | 653 | 654 | 655 | 656 | 657 | 658 | 659 | 660 | 661 | 662 | 663 | 664 | 665 | 666 | 667 | 668 | 669 | 670 | 671 | 672 | 673 | 674 | 675 |
676 | 677 | 678 | 679 | 680 | 681 | 682 | 683 | 684 | 685 | 686 | 687 | 688 | 689 | 690 | 691 | 692 | 693 | 694 | 695 | 696 | 697 | 698 | 699 | 700 |
701 | 702 | 703 | 704 | 705 | 706 | 707 | 708 | 709 |
I scored 13526 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 204 - Generalised Hamming Numbers | Concealed Square - problem 206 >> |