<< problem 243 - Resilience | Squares under a hyperbola - problem 247 >> |
Problem 244: Sliders
(see projecteuler.net/problem=244)
You probably know the game Fifteen Puzzle. Here, instead of numbered tiles, we have seven red tiles and eight blue tiles.
A move is denoted by the uppercase initial of the direction (Left, Right, Up, Down) in which the tile is slid,
e.g. starting from configuration (S), by the sequence LULUR we reach the configuration (E):
(S)(E)
For each path, its checksum is calculated by (pseudocode):
checksum = 0
checksum = (checksum * 243 + m_1) mod 100000007
checksum = (checksum * 243 + m_2) mod 100000007
...
checksum = (checksum * 243 + m_n) mod 100000007
where m_k is the ASCII value of the k-th letter in the move sequence and the ASCII values for the moves are:
L76
R82
U85
D68
For the sequence LULUR given above, the checksum would be 19761398.
Now, starting from configuration (S), find all shortest ways to reach configuration (T).
(S)(T)
What is the sum of all checksums for the paths having the minimal length?
My Algorithm
I run a breadth-first search without any "tricks" or "specific optimizations" (see en.wikipedia.org/wiki/Breadth-first_search):
- encode a board as an
std::string
, concatenate all rows to get a single line (initial board is".rbbrrbbrrbbrrbb"
) - store the checksum of all moves in a board, too
- avoid visiting a board already seen before (my
history
container keeps track of that)
Therefore my variables
fromX
, toX
, etc. in Board::move
refer to the empty square - but then the actual moves look strange (Left
→ increment toX
).
Alternative Approaches
There are many opportunities to speed up the program or save some memory.
For example, there is only one shortest path so I could abort search()
as soon as I encounter it.
Nevertheless, my live test "forces" me to look at all paths of the last iteration in case the user enters a board with multiple shortest paths.
Note
It's a classic computer science problem and therefore I found it to be pretty easy (I studied software engineering).
Project Euler awarded it a high difficulty rating because mathematicians are probably not that familiar with typical IT algorithms.
On the contrary, I've seen enough "easy" problems that were actually quite hard for me.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho "rrbbrbbbr.rbrrbb" | ./244
Output:
Note: the original problem's input .brbbrbrrbrbbrbr
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 <string>
#include <map>
#include <set>
#include <vector>
// encode the board by ASCII characters, too
enum Piece
{
Red = 'r',
Blue = 'b',
Empty = '.'
};
// moves as defined by the problem statement
enum Move
{
Up = 85, // 'U'
Left = 76, // 'L'
Down = 68, // 'D'
Right = 82 // 'R'
};
// represent a board (with moves needed to get there from the initial board)
struct Board
{
// the whole board as a one-line string, initial value is ".rbbrrbbrrbbrrbb"; (see enum Piece)
std::string pieces;
// checksum of executed moves
unsigned int checksum;
// 4x4 board
static const unsigned int Size = 4;
// create a new board
Board(const std::string& pieces_ = std::string(), unsigned int checksum_ = 0)
: pieces(pieces_), checksum(checksum_)
{}
// return true if pieces contains 16 characters (very basic check, will accept many invalid boards !)
bool isValid() const
{
return pieces.size() == Size * Size;
}
// return true if equal
bool operator==(const Board& other) const
{
return pieces == other.pieces;
}
// "move" the empty square, return an empty string if impossible
Board move(Move move) const
{
if (pieces.empty())
return Board();
// find the empty square
auto index = 0;
while (pieces[index] != Empty)
index++;
// from 1D to 2D
auto fromX = index % Size;
auto fromY = index / Size;
// new location of the empty square
auto toX = fromX;
auto toY = fromY;
// note: the moves are based on the movement of the red/blue square whereas
// I actually move the empty square, so everything's "reversed"
switch (move)
{
case Up:
if (fromY == Size - 1)
return Board();
toY++;
break;
case Down:
if (fromY == 0)
return Board();
toY--;
break;
case Left:
if (fromX == Size - 1)
return Board();
toX++;
break;
case Right:
if (fromX == 0)
return Board();
toX--;
break;
}
// from 2D to 1D ...
auto next = toY * Size + toX;
auto newPieces = pieces;
std::swap(newPieces[index], newPieces[next]);
// update checksum
auto newChecksum = (checksum * 243ULL + move) % 100000007;
return Board(std::move(newPieces), newChecksum);
}
};
// breadth search for a certain board, add all checksums
unsigned int search(const Board& finalBoard)
{
// initial configuration
std::vector<Board> todo = { Board(".rbbrrbbrrbbrrbb") };
// keep track of all boards already visited
std::set<std::string> history;
// sum of all checksums
unsigned int result = 0;
// look for the shortest path (there may be multiple !)
bool lastIteration = false;
while (!lastIteration)
{
std::vector<Board> next;
next.reserve(10000); // actually about 6500 is sufficient
for (auto current : todo)
{
// final position found ?
if (current == finalBoard)
{
lastIteration = true;
result += current.checksum;
}
// try all four movements:
// verify that the move is legal and avoid already visited positions
// L => left
auto left = current.move(Left);
if (left.isValid() && history.count(left.pieces) == 0)
{
next.push_back(left);
history.insert(left.pieces);
}
// R => right
auto right = current.move(Right);
if (right.isValid() && history.count(right.pieces) == 0)
{
next.push_back(right);
history.insert(right.pieces);
}
// U => up
auto up = current.move(Up);
if (up.isValid() && history.count(up.pieces) == 0)
{
next.push_back(up);
history.insert(up.pieces);
}
// D => down
auto down = current.move(Down);
if (down.isValid() && history.count(down.pieces) == 0)
{
next.push_back(down);
history.insert(down.pieces);
}
}
// prepare next iteration
todo = std::move(next);
}
return result;
}
int main()
{
std::string finalPosition = ".brbbrbrrbrbbrbr"; // example LULUR => "rrbbrbbbr.rbrrbb"
std::cin >> finalPosition;
// simple validation (for live test only)
auto numRed = 0;
auto numBlue = 0;
auto numEmpty = 0;
auto numInvalid = 0;
for (auto c : finalPosition)
{
switch (c)
{
case 'r': numRed++; break;
case 'b': numBlue++; break;
case '.': numEmpty++; break;
default: numInvalid++; break;
}
}
// reject invalid input
if (numRed != 7 || numBlue != 8 || numEmpty != 1 || numInvalid != 0)
return 1;
// let's go !
std::cout << search(Board(finalPosition)) << std::endl;
return 0;
}
This solution contains 24 empty lines, 33 comments and 5 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.15 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 11 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
September 25, 2017 submitted solution
September 25, 2017 added comments
Difficulty
Project Euler ranks this problem at 70% (out of 100%).
Links
projecteuler.net/thread=244 - 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/e244.py (written by Laurent Mazare)
C++ github.com/Meng-Gen/ProjectEuler/blob/master/244.cc (written by Meng-Gen Tsai)
C++ github.com/roosephu/project-euler/blob/master/244.cpp (written by Yuping Luo)
C++ github.com/smacke/project-euler/blob/master/cpp/244.cpp (written by Stephen Macke)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem244.java (written by Magnus Solheim Thrap)
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 243 - Resilience | Squares under a hyperbola - problem 247 >> |