<< problem 329 - Prime Frog | 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

→ after the second rotation 'A' will be the first and 'B' the last

→ 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.

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

# 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 "6 10" | ./336`

Output:

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.03 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(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

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)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

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 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# 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 329 - Prime Frog | Golomb's self-describing sequence - problem 341 >> |