<< problem 327 - Rooms of Doom | Special partitions - problem 333 >> |
Problem 329: Prime Frog
(see projecteuler.net/problem=329)
Susan has a prime frog.
Her frog is jumping around over 500 squares numbered 1 to 500. He can only jump one square to the left or to the right, with equal probability,
and he cannot jump outside the range [1;500].
(if it lands at either end, it automatically jumps to the only available square on the next move.)
When he is on a square with a prime number on it, he croaks 'P' (PRIME) with probability 2/3 or 'N' (NOT PRIME) with probability 1/3 just before jumping to the next square.
When he is on a square with a number on it that is not a prime he croaks 'P' with probability 1/3 or 'N' with probability 2/3 just before jumping to the next square.
Given that the frog's starting position is random with the same probability for every square, and given that she listens to his first 15 croaks,
what is the probability that she hears the sequence PPPPNNPPPNPPNPN?
Give your answer as a fraction p/q in reduced form.
My Algorithm
A simple prime sieve finds all 95 primes between 1 and 500 in less than a millisecond.
The probability of reaching a square is 1/2 and it has the "right prime label" in 1/2 or 2/3 of all cases.
That means that there are 14 jumps and 15 "croak decisions". The denominator is always 500 * 2^14 * 3^15 (before reducing the fraction).
My program calculates the numerator recursively:
- each step checks whether the frog croaks in 1/3 or 2/3 of all cases (
chance = 1
orchance = 2
) - then the frog jumps right or left (respecting the borders of square 1 and 500)
- memoization speeds up the whole process
gcd
function from my toolbox (this time I changed it to a template - only for the fun of it).The result is displayed after dividing numerator and denominator by their
gcd
.
Alternative Approaches
There is no need to have the gcd
function/template. The denominator has only prime factors 2, 3 and 5.
I could repeatedly divide the numerator and denominator by those numbers.
Note
Sequence
has a dummy whitespace at position 0 because that position is unused.
Depth x
queries Sequence[x]
where x
starts at 1 and finished at 15.
Memoization isn't strictly necessary because the result will be found without it in less than a second.
There are just 2^15 * 500 = 16384000 final states.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "10 3" | ./329
Output:
Note: the original problem's input 500 15
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++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.
#include <iostream>
#include <vector>
// find greatest common divisor
template <typename T>
T gcd(T a, T b)
{
while (a != 0)
{
T c = a;
a = b % a;
b = c;
}
return b;
}
// croaked sequence
const char* Sequence = " PPPPNNPPPNPPNPN";
// length of croaked sequence
unsigned int maxDepth = 15;
// number of different starting positions
unsigned int limit = 500;
// prime numbers <= limit
static std::vector<char> isPrime; // I started with vector<bool> but vector<char> is a bit faster
// memoize intermediate results
static std::vector<unsigned int> cache;
// return only numerator, the denominator will be (2*3)^depth (before reducing)
unsigned int probability(unsigned int square, unsigned int depth = 1)
{
// either 1/3 or 2/3, discard the constant denominator 3 for now
unsigned int chance = 1;
if (isPrime[square] ^ (Sequence[depth] == 'N'))
chance = 2;
// done ?
if (depth == maxDepth)
return chance;
// memoize
auto id = square * maxDepth + depth;
if (cache.empty())
cache.resize((maxDepth + 1) * (limit + 1), 0);
if (cache[id] != 0)
return cache[id];
auto left = square - 1;
if (left < 1) // avoid left border
left = 1 + 1;
auto right = square + 1;
if (right > limit) // avoid right border
right = limit - 1;
// jump to next square with equal probability
auto result = chance * (probability(left, depth + 1) + probability(right, depth + 1));
cache[id] = result;
return result;
}
int main()
{
std::cin >> limit >> maxDepth;
// prime sieve
isPrime.resize(limit + 1, true);
isPrime[1] = false;
for (unsigned int i = 2; i*i <= limit; i++)
if (isPrime[i])
for (unsigned int j = i*i; j <= limit; j += i)
isPrime[j] = false;
// let's croak !
unsigned long long sum = 0;
for (unsigned int i = 1; i <= limit; i++)
sum += probability(i);
// 500 * 3^15 * 2^14
unsigned long long denominator = limit;
for (unsigned int i = 1; i < maxDepth; i++)
denominator *= 3 * 2; // 3^14 * 2^14
denominator *= 3;
// reduce fraction
auto divide = gcd(sum, denominator);
std::cout << sum / divide << "/" << denominator / divide << std::endl;
return 0;
}
This solution contains 14 empty lines, 15 comments and 2 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
August 13, 2017 submitted solution
August 13, 2017 added comments
Difficulty
Project Euler ranks this problem at 25% (out of 100%).
Links
projecteuler.net/thread=329 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/LaurentMazare/ProjectEuler/blob/master/e329.py (written by Laurent Mazare)
Python github.com/Meng-Gen/ProjectEuler/blob/master/329.py (written by Meng-Gen Tsai)
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p329.py (written by Nayuki)
Python github.com/smacke/project-euler/blob/master/python/329.py (written by Stephen Macke)
C++ github.com/roosephu/project-euler/blob/master/329.cpp (written by Yuping Luo)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p329.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem329.java (written by Magnus Solheim Thrap)
Perl github.com/shlomif/project-euler/blob/master/project-euler/329/euler-329-v1.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 |
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 327 - Rooms of Doom | Special partitions - problem 333 >> |