// ////////////////////////////////////////////////////////
// # Title
// Maximix Arrangements
//
// # URL
// https://projecteuler.net/problem=336
// http://euler.stephan-brumme.com/336/
//
// # Problem
// 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.
//
// ![train](p336_maximix.gif)
//
// 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.
//
// # Solved by
// Stephan Brumme
// July 2017
//
// # 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').
//
// # Note
// There are tons of further performance optimizations but the solution is found in less than 0.1 seconds - fast enough for me.
//
// # Alternative
// I looks like you can solve this recursively with Dynamic Programming.
#include
#include
#include
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;
}