<< 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.

# My code

… was written in C++ and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#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.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "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)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++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:

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p205.java (written by Nayuki)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

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 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# 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 >> |