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:

Input data (separated by spaces or newlines):
Note: Enter the number of seeds that need to be moved to the top row (there are always 5 seeds in the bottom row

This is equivalent to
echo 1 | ./280

Output:

(please click 'Go !')

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

65% Project Euler ranks this problem at 65% (out of 100%).

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
The 270 solved problems (level 10) had an average difficulty of 31.3% at Project Euler and
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.

more about me can be found on my homepage, especially in my coding blog.
some names mentioned on this site may be trademarks of their respective owners.
thanks to the KaTeX team for their great typesetting library !