<< problem 279 - Triangles with integral sides and an integral ... | Steady Squares - problem 284 >> |
Problem 280: Ant and seeds
(see projecteuler.net/problem=280)
A laborious ant walks randomly on a 5x5 grid. The walk starts from the central square.
At each step, the ant moves to an adjacent square at random, without leaving the grid; thus there are 2, 3 or 4 possible moves at each step depending on the ant's position.
At the start of the walk, a seed is placed on each square of the lower row. When the ant isn't carrying a seed and reaches a square of the lower row containing a seed,
it will start to carry the seed. The ant will drop the seed on the first empty square of the upper row it eventually reaches.
What's the expected number of steps until all seeds have been dropped in the top row?
Give your answer rounded to 6 decimal places.
My Algorithm
Wow, this turned out to be one of my solution with the most code written exclusively for a single problem (there are longer ones which copy stuff like Miller-Rabin test from my toolbox) !
But don't be afraid, it wasn't a hard problem, just lot's of laborous typing.
I created a struct named State
which contains:
- the position of the ant (5x5 grid → 25 positions)
- whether the ant currently carries a seed or not
- the seeds in the top row
- the seeds in the bottom row
- a hash function
State::getHash
to uniquely identify a state
Not all states are valid, e.g. if the ant still carries a seed, is in the top row and the current square is empty (because the ant should have dropped the seed).
A total of 10270 valid states remains (see
State::isValid
).A state is final, if the top row contains enough seeds (= 5 seeds).
My program determines how long it takes to reach a final state (there are 5 final states depending on where the last seed was dropped):
= 1 * p(1) + 2 * p(2) + 3 * p(3) + ... + n * p(n) + ...
p(n) is the probability that a final state is reached after exactly n moves.
After a certain number of moves the probability rapidly approaches zero and then I abort (e.g. ignoring ridicilously low values such as 10^99 * p(10^99) that are possible but extremely unlikely).
The first initialization phase enumerates all valid states and stores them in
states
.Then for each state I analyze whether it is final (stored in
final
) or find all possible moves (up, down, left, right) and store them in transitions
.The actual computation of all moves can be written in just a few lines of code (see below the
initialization is complete
marker'').All states are initialized with probability zero, except for the initial state with is 1 (=100%), i.e. ant in the middle of the grid.
Then do repeatedly:
- for each state
s
there are up to 4 transitions, all equally likely, so the chance for each is1 / transitions[s].size()
last[s]
contains the probability to be in states
after exactly the current number of steps (iteration
)- then
next[t]
will be the probability to be in statet
after one more step - so for each transition from
s
tot1
,t2
, etc.:next[t] += last[s] / transitions[s].size()
If the delta becomes very small, then I abort and print the current sum.
Note
My live test allows to specify the number of seeds in a final state. For example if the ant needs to move only one seed to the top row, then it takes about 55.6 moves.
However, my Epsilon
was fine-tuned for the default case (5 seeds), so the last digits of the result might be slightly off.
The transitions
container was a std::map
but memory allocations dominated execution time.
Since my hash values are pretty close to each other (maxHash = 49624
) I converted it to a sparse std::vector
and the code became about 2x faster.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 1 | ./280
Output:
Note: the original problem's input 5
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.
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <vector>
#include <bitset>
// 5x5 grid
const unsigned int gridSize = 5;
// how many seeds need to be transported from the bottom to the top row
unsigned int movedSeeds = 5;
// unique identifier of a state, generated by State::getHash()
typedef unsigned int Hash;
// note: all positions are zero-indexed, i.e. (0,0) to (4,4)
// top row can be identified by y=0
struct State
{
// ant's position
unsigned int x;
unsigned int y;
// true if ant is currently carrying a seed
bool carriesSeed;
// true if seed at (x, 0)
std::bitset<gridSize> seedsTopRow;
// true if seed at (x, 4)
std::bitset<gridSize> seedsBottomRow;
// dummy constructor
State() : x(0), y(0), carriesSeed(false), seedsTopRow(0), seedsBottomRow(0)
{}
// unique identifier
Hash getHash() const
{
// 17 bits: xxxyyyctttttbbbbb
Hash hash = carriesSeed ? 1 : 0;
hash = (hash << seedsTopRow .size()) + seedsTopRow .to_ulong();
hash = (hash << seedsBottomRow.size()) + seedsBottomRow.to_ulong();
hash = hash * gridSize + x;
hash = hash * gridSize + y;
return hash;
}
// true if all seeds moved to top row
bool isFinal() const
{
return seedsTopRow.count() == movedSeeds && !carriesSeed;
}
// return true if state has 5 seeds
bool isValid() const
{
// ant can't carry a seed in top row if current square is empty
if (y == 0 && carriesSeed && !seedsTopRow[x])
return false;
// ant can't be without a seed in bottom row if current square has seed
if (y == gridSize - 1 && !carriesSeed && seedsBottomRow[x])
return false;
// if all seeds are in top row (final state) then the ant must be in the top row, too
if (isFinal() && y != 0)
return false;
// a total of five seeds
auto seeds = seedsTopRow.count() + seedsBottomRow.count();
if (carriesSeed)
seeds++;
if (seeds != gridSize)
return false;
// all tests passed
return true;
}
// convert to string (for debugging purposes only, not needed anymore)
std::string toString() const
{
// position
auto result = std::to_string(x) + "," + std::to_string(y);
// flags
if (isFinal())
result += "!";
else if (carriesSeed)
result += "+";
else
result += " ";
// seeds on the ground
result += " ";
for (size_t i = 0; i < seedsTopRow.size(); i++)
result += std::to_string(seedsTopRow[i]);
result += " ";
for (size_t i = 0; i < seedsBottomRow.size(); i++)
result += std::to_string(seedsBottomRow[i]);
return result;
}
};
int main()
{
// how many seeds need to be transported from the bottom to the top row
std::cin >> movedSeeds;
std::cout << std::fixed << std::setprecision(6);
// manually tuned threshold - exit computation if sufficient precision has been reached
const double Epsilon = 0.0000000001;
const auto AllBits = (1 << gridSize) - 1;
// ant starts in the middle, all seeds in bottom row
State initial;
initial.x = 2;
initial.y = 2;
initial.carriesSeed = false;
initial.seedsTopRow = 0;
initial.seedsBottomRow = AllBits;
// generate all states
std::map<Hash, State> states;
for (unsigned int x = 0; x < gridSize; x++)
for (unsigned int y = 0; y < gridSize; y++)
for (auto carriesSeed = 0; carriesSeed <= 1; carriesSeed++)
for (auto maskTop = 0; maskTop <= AllBits; maskTop++)
for (auto maskBottom = 0; maskBottom <= AllBits; maskBottom++)
{
// generate state
State current;
current.x = x;
current.y = y;
current.carriesSeed = (carriesSeed == 1);
current.seedsTopRow = maskTop;
current.seedsBottomRow = maskBottom;
// only accept valid states
if (!current.isValid())
continue;
// add to container
states[current.getHash()] = current;
}
// find all transitions and identify final states
std::map<Hash, std::vector<Hash>> transitions;
std::vector<Hash> final;
for (auto i : states)
{
auto current = i.second;
// final state ?
if (current.isFinal())
{
final.push_back(i.first);
// no need to proceed after reaching a final state (no further moves of the ant)
continue;
}
// and now some boring and repetitive code ...
std::vector<State> candidates;
// move up
if (current.y > 0)
{
current.y--;
candidates.push_back(current);
current.y++; // restore
}
// move down
if (current.y < gridSize - 1)
{
current.y++;
candidates.push_back(current);
current.y--; // restore
}
// move left
if (current.x > 0)
{
current.x--;
candidates.push_back(current);
current.x++; // restore
}
// move right
if (current.x < gridSize - 1)
{
current.x++;
candidates.push_back(current);
current.x--; // restore
}
// drop or pick up seed
for (auto candidate : candidates)
{
// drop seed ?
if ( candidate.carriesSeed &&
candidate.y == 0 &&
!candidate.seedsTopRow[candidate.x])
{
candidate.carriesSeed = false;
candidate.seedsTopRow[candidate.x] = true;
}
// pick up seed ?
if (!candidate.carriesSeed &&
candidate.y == gridSize - 1 &&
candidate.seedsBottomRow[candidate.x])
{
candidate.carriesSeed = true;
candidate.seedsBottomRow[candidate.x] = false;
}
// found one more state transition
transitions[current.getHash()].push_back(candidate.getHash());
}
}
// no valid moves
if (final.empty() || transitions.empty())
return 1;
// get highest hash value
auto maxHash = transitions.rbegin()->first;
// ---------- initialization is complete, let's find the result ! ----------
// initially the ant is with 100% probability in the middle of the grid
std::vector<double> last(maxHash + 1, 0);
for (auto x : states)
last[x.first] = 0;
last[initial.getHash()] = 1;
// E = 1 * p(1) + 2 * p(2) + 3 * p(3) + ... + n * p(n)
// where p(n) is the probability that a final state was reached after n steps
double expected = 0;
// run this loop until the variable "expected" changes less than Epsilon
for (unsigned int iteration = 1; ; iteration++)
{
std::vector<double> next(last.size(), 0);
for (const auto& followup : transitions)
{
auto from = followup.first; // a hash
const auto& to = followup.second; // a container with hashes
// each step is equally likely
double probability = 1.0 / to.size();
probability *= last[from];
// add to each allowed follow-up state
for (auto move : to)
next[move] += probability;
}
// overwrite old probabilities with new values
last = std::move(next);
// add probabilities of reaching a final state
double add = 0;
for (auto x : final)
add += last[x];
// E = 1 * p(1) + 2 * p(2) + ...
add *= iteration;
expected += add;
// enough precision ?
if (add < Epsilon && expected > 1) // don't abort in the first iterations when add == 0 and expected == 0
break;
}
// print result
std::cout << expected << std::endl;
return 0;
}
This solution contains 46 empty lines, 56 comments and 6 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.4 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 5 MByte.
(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 25, 2017 submitted solution
August 25, 2017 added comments
Difficulty
Project Euler ranks this problem at 65% (out of 100%).
Links
projecteuler.net/thread=280 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p280.py (written by Nayuki)
Python github.com/roosephu/project-euler/blob/master/280.py (written by Yuping Luo)
Python github.com/smacke/project-euler/blob/master/python/280.py (written by Stephen Macke)
C++ github.com/evilmucedin/project-euler/blob/master/euler280/280.cpp (written by Den Raskovalov)
C github.com/LaurentMazare/ProjectEuler/blob/master/e280.c (written by Laurent Mazare)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p280.java (written by Nayuki)
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 |
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 |
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 279 - Triangles with integral sides and an integral ... | Steady Squares - problem 284 >> |