<< problem 333 - Special partitions | Golomb's self-describing sequence - problem 341 >> |
Problem 336: Maximix Arrangements
(see projecteuler.net/problem=336)
A train is used to transport four carriages in the order: ABCD.
However, sometimes when the train arrives to collect the carriages they are not in the correct order.
To rearrange the carriages they are all shunted on to a large rotating turntable.
After the carriages are uncoupled at a specific point the train moves off the turntable pulling the carriages still attached with it.
The remaining carriages are rotated 180 degrees. All of the carriages are then rejoined and this process is repeated
as often as necessary in order to obtain the least number of uses of the turntable.
Some arrangements, such as ADCB, can be solved easily: the carriages are separated between A and D, and after DCB are rotated the correct order has been achieved.
However, Simple Simon, the train driver, is not known for his efficiency, so he always solves the problem by initially getting carriage A in the correct place,
then carriage B, and so on.
Using four carriages, the worst possible arrangements for Simon, which we shall call maximix arrangements, are DACB and DBAC; each requiring him five rotations
(although, using the most efficient approach, they could be solved using just three rotations).
The process he uses for DACB is shown below.
It can be verified that there are 24 maximix arrangements for six carriages, of which the tenth lexicographic maximix arrangement is DFAECB.
Find the 2011th lexicographic maximix arrangement for eleven carriages.
My Algorithm
Simple Simon works as follows:
1. find the next carriage (first is 'A', then 'B', etc.)
2. rotate all carriages from that position to the end
3. rotate all carriages from the final position to the end
4. continue with next carriage in step 1
STL's std::rotate
and std::next_permutation
are very efficient default implementations and used throughout my solution.
The maximum number of rotation is 2(n-1) - 1 because the last carriage needs no rotation and the
second-to-last needs only one rotation.
A few performance tweaks:
(a) if a carriage is already in its final position, then Simple Simon can proceed with the next carriage
→ saving two rotations - it can't be a maximix arrangement
(b) if a carriage is already at the end of the train, then Simple Simon needs only one rotation
→ it can't be a maximix arrangement, except when he is about to rearrange the last two carriages, then it's ok
These two "rules" lead to some conclusions:
- a maximix arrangement can't start with an 'A' because that violates rule (a)
- a maximix arrangement can't start with an 'B' because after the first rotation, 'A' will be the last carriage while 'B' is the first
→ only one rotation (the third) places 'B' in its correct slot (see rule (b) )
Therefore my initial train configuration is "CABDEFGHIJKLM" (the lexigraphic smallest that neither starts with 'A' nor 'B').
Alternative Approaches
I looks like you can solve this recursively with Dynamic Programming.
Note
There are tons of further performance optimizations but the solution is found in less than 0.1 seconds - fast enough 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 "6 10" | ./336
Output:
(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 <algorithm>
int main()
{
// can't start with an 'A' or 'B'
std::string train = "CABDEFGHIJKLM"; // up to 14 for live test
// look for the 2011th maximix train
auto stopWhenFound = 2011;
auto numFound = 0;
// shorter train
auto length = train.size();
std::cin >> length >> stopWhenFound;
train.erase(length);
// two for each carriage, except for the last two which require just one rotation
unsigned int maxRotations = (train.size() - 1) * 2 - 1;
do
{
auto current = train;
// move carriage 'A', then 'B', then 'C', ... to its correct position
auto expect = 'A';
// count rotations
unsigned int rotations = 0;
for (size_t i = 0; i < current.size() - 1; i++, expect++)
{
// carriage already in correct position ?
// => can't be a maximix arrangement
if (current[i] == expect)
break;
// carriage in last position ? only allowed for 'J' (the second-to-last carriage)
if (current[current.size() - 1] == expect && i != current.size() - 2)
break;
// find carriage
auto j = i + 1;
while (current[j] != expect)
j++;
// rotate carriage to the end of the train (unless it's already there)
if (j < current.size() - 1)
{
std::reverse(current.begin() + j, current.end());
rotations++;
}
// rotate carriage to its correct position
std::reverse(current.begin() + i, current.end());
rotations++;
}
// is it a maximix arrangement ?
if (rotations == maxRotations)
{
numFound++;
// found 2011th maximix ?
if (numFound == stopWhenFound)
break;
}
} while (std::next_permutation(train.begin(), train.end()));
std::cout << train << std::endl;
return 0;
}
This solution contains 11 empty lines, 14 comments and 3 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.03 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
July 15, 2017 submitted solution
July 15, 2017 added comments
Difficulty
Project Euler ranks this problem at 25% (out of 100%).
Links
projecteuler.net/thread=336 - 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/e336.py (written by Laurent Mazare)
Python github.com/Meng-Gen/ProjectEuler/blob/master/336.py (written by Meng-Gen Tsai)
Python github.com/roosephu/project-euler/blob/master/336.py (written by Yuping Luo)
C++ github.com/evilmucedin/project-euler/blob/master/euler336/336.cpp (written by Den Raskovalov)
C++ github.com/roosephu/project-euler/blob/master/336.cpp (written by Yuping Luo)
C++ github.com/smacke/project-euler/blob/master/cpp/336.cpp (written by Stephen Macke)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem336.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 a new problem is published | |
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 |
I scored 13,486 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 333 - Special partitions | Golomb's self-describing sequence - problem 341 >> |