<< problem 278 - Linear Combinations of Semiprimes | Scoring probabilities - problem 286 >> |

# 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

A state implies that the seed was already dropped or picked up on the current square if possible.

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 is `1 / transitions[s].size()`

- `last[s]`

contains the probability to be in state `s`

after exactly the current number of steps (`iteration`

)

- then `next[t]`

will be the probability to be in state `t`

after one more step

- so for each transition from `s`

to `t1`

, `t2`

, etc.: `next[t] += last[s] / transitions[s].size()`

After each iteration I add the probabilities that a final state was reached and add all of them.

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 to`echo 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 a 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=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

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)

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

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 |

I scored 13,386 points (out of 15600 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 278 - Linear Combinations of Semiprimes | Scoring probabilities - problem 286 >> |