<< problem 309 - Integer Ladders | Sliding game - problem 313 >> |
Problem 310: Nim Square
(see projecteuler.net/problem=310)
Alice and Bob play the game Nim Square.
Nim Square is just like ordinary three-heap normal play Nim, but the players may only remove a square number of stones from a heap.
The number of stones in the three heaps is represented by the ordered triple (a,b,c).
If 0 <= a <= b <= c <= 29 then the number of losing positions for the next player is 1160.
Find the number of losing positions for the next player if 0 <= a <= b <= c <= 100 000.
My Algorithm
Problem 301 introduced the Nim game and problem 306 re-used some of the knowledge gained and added the concept of a mex
function.
After reading the blog posting mathstrek.blog/2012/08/05/combinatorial-game-theory-iii/ I immediately realized that I already knew enough to solve the current problem -
but was way to stupid "to open my eyes".
Anyway, writing a quick'n'dirty bruteForce
solver is good idea because it takes just a few minutes and helps verifying that the "smart" solver is correct (for small values).
See the bruteForce
function and #define BRUTE_FORCE
.
The basic idea is to look at a single heap.
The mex-value of an empty heap is zero because then the game is lost.
Whenever I want to determine the mex-value of a heap with size
elements then I analyze all heaps size - i*i
.
For example, to compute the mex-value of 13 I need the mex-values of mex(13 - 1^2) = mex(12), mex(13 - 2^2) = mex(9) and mex(13 - 3^2) = mex(4).
The mex-value of 13 is the smallest number >= 0 which is not among these values.
Maybe it becomes a bit clearer when looking at the mex-values between 0 and 13:
heap size012345678910111213
mex01012010120101
Since mex(12) = 0, mex(9) = 2 and mex(4) = 2 the set of its "children mex-values" is \{ 0, 2 \}.
The smallest number >= 0 which is not part of that set is 1.
The first part of search
implements this straight-forward algorithm.
Looking at my logging output, the maximum mex-value for heaps smaller than 100000 is surprisingly small: just 74.
A simple std::bitset
instead of std::set
makes this process pretty fast.
However, the original problem was about three heaps - and not a single heap.
I could write three nested loops and check whether mex(a) ^ mex(b) ^ mex(c) is zero (= lost, same XOR idea like in problem 301).
But that's not very efficient: it would require approx 100000^3 iterations (actually a bit less, but still a huge number).
The following observations speed up the process (\oplus is the XOR-operation):
(1) x \oplus y is only zero if x = y
(2) x \oplus y \oplus z = x \oplus (y \oplus z)
To count the number of lost positions in a three heap Nim Square game:
- while analyzing triples (a,b,c) many pairs (b,c) are repeatedly encountered
- especially if a iterates backwards, that means from
limit
to0
, then all pairs (b,c) of the previous iteration will appears again - of course a few new pairs (b,c) will appear, too, where b = a and b <= c
- I count how often these pairs (b,c) produce
mex(b) ^ mex(c)
and store it in myfrequency
container such thatfrequency[mex[b] ^ mex[c]]++
- for each a the number in
frequency[mex[a]]
is the number of lost games because of equation (1)
Alternative Approaches
Clever use of combinatorics can eliminate the last step. I opted for the "programming" solution instead of the hairy "mathematical approach".
Interactive test
This feature is not available for the current problem.
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <vector>
#include <bitset>
#include <unordered_set>
#include <algorithm>
// needed to compute a unique ID for each position (bruteForce only)
const unsigned long long MaxValue = 100000;
// determine whether a single position is won (true) or lost (false)
// reasonably fast for small values but eats quite a good amount of memory (about 800 MByte to fully analyze a,b,c <= 500)
bool bruteForce(unsigned int a, unsigned int b, unsigned int c)
{
// game over ?
if (a == 0 && b == 0 && c == 0)
return false;
// sort them in ascending order: a <= b <= c
if (a > b)
std::swap(a, b);
if (b > c)
std::swap(b, c);
if (a > b)
std::swap(a, b);
// memoize
auto id = a * MaxValue * MaxValue + b * MaxValue + c;
// two separate caches
static std::unordered_set<unsigned long long> cacheWon;
if (cacheWon .count(id) != 0)
return true;
static std::unordered_set<unsigned long long> cacheLost;
if (cacheLost.count(id) != 0)
return false;
// try every possible move:
// take a square number of stones
for (unsigned int i = 1; i*i <= c; i++)
{
// take a square number of stones from the smallest stack
if (i*i <= a && !bruteForce(a - i*i, b, c))
{
cacheWon.insert(id);
return true;
}
// take a square number of stones from the stack in the middle
if (i*i <= b && !bruteForce(a, b - i*i, c))
{
cacheWon.insert(id);
return true;
}
// take a square number of stones from the largest stack
if (!bruteForce(a, b, c - i*i))
{
cacheWon.insert(id);
return true;
}
}
// no winning move ... meaning that the current player loses
cacheLost.insert(id);
return false;
}
// count all lost positions, just under 5 seconds for limit = 100000
unsigned long long search(unsigned int limit)
{
// based on this great posting: https://mathstrek.blog/2012/08/05/combinatorial-game-theory-iii/
// compute Nim values for a single pile
std::vector<unsigned int> mex(limit + 1, 0); // fill with zeros
for (unsigned int size = 0; size <= limit; size++)
{
// I saw in my experiments that Nim values are pretty small for limit <= 100000 (<= 74)
const size_t NimLimit = 80;
// collect all Nim values after each possible move
std::bitset<NimLimit> moves; // initialized with zeros
for (unsigned int i = 1; i*i <= size; i++)
// take i^2 stones from the heap
moves[mex[size - i*i]] = true;
// find the smallest non-negative number which is NOT part of the "moves" container
unsigned int available = 0;
while (moves[available])
available++;
mex[size] = available;
}
// the largest Nim value
auto maxNimValue = *std::max_element(mex.begin(), mex.end());
// find largest possible number when XORing two Nim values
unsigned int nextPowerOfTwo = 1; // it's 128
while (nextPowerOfTwo < maxNimValue)
nextPowerOfTwo *= 2;
// count how often value[b] ^ value[c] occurs where a <= b <= c <= limit
std::vector<unsigned int> frequency(nextPowerOfTwo, 0);
unsigned long long numLost = 0;
for (int a = limit; a >= 0; a--)
{
// modify the "frequency" container to cover new pairs (b,c), too
// it already contains all pairs (b+1,c), now a is one unit smaller so b can be one smaller, too
for (auto b = a; b == a; b++) // I know that it looks silly -
// but I want to make clear it's two nested loops
// where the outer needs only one iteration
for (auto c = b; c <= (int)limit; c++)
frequency[mex[b] ^ mex[c]]++;
// look at Nim value of a
// how many pairs (b,c) have to same Nim value such that value[a] ^ (value[b] ^ value[c]) = 0 => lost
numLost += frequency[mex[a]];
}
return numLost;
}
int main()
{
unsigned int limit = 100000;
std::cin >> limit;
//#define BRUTE_FORCE
#ifdef BRUTE_FORCE
// if limit is 500: => 21084251 positions, 2018811 lost => 800 MByte caches in bruteForce(), finish in about two minutes
// brute-force
unsigned long long numLost = 0;
// generate every possible position and count how many are lost
for (unsigned int a = 0; a <= limit; a++)
for (auto b = a; b <= limit; b++)
for (auto c = b; c <= limit; c++)
// lost ?
if (!bruteForce(a,b,c))
numLost++;
std::cout << numLost << std::endl;
#endif
std::cout << search(limit) << std::endl;
return 0;
}
This solution contains 22 empty lines, 34 comments and 7 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 4.6 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
December 12, 2017 submitted solution
December 12, 2017 added comments
Difficulty
Project Euler ranks this problem at 40% (out of 100%).
Links
projecteuler.net/thread=310 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/evilmucedin/project-euler/blob/master/euler310/euler310.py (written by Den Raskovalov)
Python github.com/Meng-Gen/ProjectEuler/blob/master/310.py (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/310.cpp (written by Yuping Luo)
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 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 |
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 309 - Integer Ladders | Sliding game - problem 313 >> |