Problem 336: Maximix Arrangements

Project Euler Problem 336 Solution

EulerSolve provides an optimized solution for Project Euler Problem 336, Maximix Arrangements, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We have a train of $n$ distinct carriages labelled $A,B,C,\dots$. Simon sorts it using only suffix reversals: at stage $i$ (using 0-based indexing, as in the code), he takes the next required letter in sorted order, moves it to the tail if necessary, and then reverses the suffix starting at $i$ so that this letter lands permanently at position $i$. A starting permutation is called maximix if Simon is forced to use the largest possible total number of moves. For Project Euler 336, the task is to list all maximix arrangements for $n=11$, sort them lexicographically, and select the requested rank without hard-coding the answer. Mathematical Approach Let $R_i$ denote the operation “reverse the suffix beginning at index $i$”. Because a reversal is an involution, $R_i^{-1}=R_i$; this observation is what makes it possible to construct all maximix states backwards instead of testing every permutation forwards. Simon's Sorting Procedure Fix a stage $i\in\{0,\dots,n-2\}$. The target symbol is the $i$-th symbol of the sorted word $A_1A_2\cdots A_n$. If that symbol is already at index $i$, Simon does nothing. Otherwise, if it is at an interior position $p\in\{i+1,\dots,n-2\}$, Simon first applies $R_p$ to move it to the tail, and then applies $R_i$ to bring it from the tail back to index $i$....

Detailed mathematical approach

Problem Summary

A train collects $n$ carriages that should stand behind the engine in alphabetical order, $\mathtt{A}$, $\mathtt{B}$, $\mathtt{C}$ and so on, but they wait in some other order. The row is pushed onto a turntable and uncoupled at one chosen place, the engine pulls the front block away, the block left behind is turned through $180^{\circ}$, and all are coupled up again — so, writing the row as a word whose first letter is the carriage nearest the engine, one use of the turntable reverses one suffix. Simple Simon works from the front, bringing $\mathtt{A}$ to its place, then $\mathtt{B}$, and so on, each with as few uses as he can manage and without disturbing the carriages already placed. An arrangement is a maximix arrangement when it forces him to use the turntable as often as $n$ carriages ever can: for four carriages $\mathtt{DACB}$ and $\mathtt{DBAC}$, five uses each although three would suffice, whereas $\mathtt{ADCB}$ needs one. For six carriages there are $24$, the tenth in lexicographic order being $\mathtt{DFAECB}$. We want the $2011$th, in that same order, for eleven carriages. ^[1]

The whole solution in one sentence: every stage of Simon's routine has exactly one most expensive case, so we start from the finished train and undo those expensive stages one after another, which builds all $(n-2)!$ maximix arrangements and nothing else; sorting that list and reading off the requested position answers the question.

Mathematical Approach

First we settle what one stage of Simon's routine costs; that bounds his total and gives a stage-by-stage condition for reaching the bound. Since reversing a suffix twice restores the word, the condition can then be run backwards from the sorted train.

1. The turntable reverses a suffix

Throughout, $n\ge2$. Number the places $0,1,\dots,n-1$, place $0$ nearest the engine, and let $w=w_0w_1\cdots w_{n-1}$ be the word of carriage letters. Uncoupling in front of place $i$ and turning the rear block round defines $R_i$: it leaves $w_0,\dots,w_{i-1}$ alone and writes the rest in the opposite order, sending the letter in place $j\ge i$ to place $i+(n-1)-j$. So $R_i$ exchanges the places $i$ and $n-1$, while $R_{n-1}$ changes nothing, and a real use of the turntable is an $R_i$ with $i\le n-2$. Two facts matter throughout: $R_i(R_i(w))=w$, since reversing the same block twice restores it, and $R_i$ never disturbs the places before $i$. The easy case of the statement is now one symbol:

$$R_1(\mathtt{ADCB})=\mathtt{ABCD}.$$

2. What one stage costs Simon

Suppose the places $0,\dots,i-1$ already hold the right carriages and Simon now wants the carriage $t_i$ belonging in place $i$, which stands in some place $p\ge i$. He may only use reversals $R_j$ with $j\ge i$, as any other would disturb a carriage already placed. The stage costs exactly

$0$ when $p=i$, as there is nothing to do;
$1$ when $p=n-1$, namely $R_i$, which brings the last carriage to place $i$;
$2$ when $i\lt p\lt n-1$, namely $R_p$ then $R_i$: the first sends $t_i$ to place $n-1$, the second from there to $i$.

Only the last line needs an argument. A reversal $R_j$ with $j\gt p$ leaves $t_i$ in place $p\ne i$; if $j\le p$, Section 1 puts it in place $j+(n-1)-p$, and $j+(n-1)-p=i$ forces $j=i+p-(n-1)\le i$, hence $j=i$ and $p=n-1$. One use is therefore never enough for an interior target, and two always are. Those two are forced as well: only $R_i$ can land $t_i$ in place $i$, collecting it from place $n-1$, so the earlier reversal must carry $t_i$ from $p$ to $n-1$, which only $R_p$ does. Simon's run is thus determined, and his total is the sum of the stage costs for $i=0,\dots,n-2$; afterwards the last carriage has nowhere else to be.

3. Worked example: Simon on $\mathtt{DACB}$

This is the process drawn in the statement. The sorted word is $\mathtt{ABCD}$, so $t_0=\mathtt{A}$, $t_1=\mathtt{B}$ and $t_2=\mathtt{C}$.

Stage $0$: $\mathtt{A}$ is in place $1$, interior, so two uses — $R_1$ gives $\mathtt{DBCA}$, then $R_0$ gives $\mathtt{ACBD}$.
Stage $1$: $\mathtt{B}$ is in place $2$, interior again — $R_2$ gives $\mathtt{ACDB}$, then $R_1$ gives $\mathtt{ABDC}$.
Stage $2$: $\mathtt{C}$ is in place $3=n-1$, so one use — $R_2$ gives $\mathtt{ABCD}$.

That is $2+2+1=5$ uses, the figure quoted in the statement; $\mathtt{DBAC}$ is checked the same way.

4. The maximum is $2n-3$

Each stage $i=0,\dots,n-3$ costs at most $2$. At the last stage $i=n-2$ only the places $n-2$ and $n-1$ are free, so $t_{n-2}$ is either already right, costing $0$, or at the back, costing $1$; the interior case cannot occur, as no place lies strictly between them. Simon's total is therefore at most

$$2(n-2)+1=2n-3,$$

with equality only when every stage up to $n-3$ costs $2$ and the last costs $1$. Section 6 builds arrangements that meet all those conditions at once, so the bound is attained. For $n=4$ it is $5$, as the statement says; for $n=6$ it is $9$ and for $n=11$ it is $19$.

5. A stage-by-stage description

Write $w^{(0)}$ for the starting arrangement and $w^{(i+1)}$ for the word after stage $i$; by Section 2 these words are determined. By Sections 2 and 4, an arrangement is maximix exactly when

for every $i$ with $0\le i\le n-3$ the carriage $t_i$ stands in $w^{(i)}$ in a place $p_i$ with $i+1\le p_i\le n-2$, so that $w^{(i+1)}=R_i\bigl(R_{p_i}(w^{(i)})\bigr)$;
in $w^{(n-2)}$ the carriage $t_{n-2}$ stands in place $n-1$, so that $w^{(n-1)}$ is the sorted word.

This names the place the next carriage must occupy at every stage, which makes the arrangements constructible rather than merely testable.

6. Undoing the stages

Because $R_i$ is its own inverse, the first line above reads from right to left as

$$w^{(i)}=R_{p_i}\bigl(R_i(w^{(i+1)})\bigr).$$

The end of the chain is known: $w^{(n-1)}$ is the sorted word and the last stage is forced, so the only word that can enter it is $w^{(n-2)}=R_{n-2}(w^{(n-1)})$. From there we walk backwards through $i=n-3,\dots,0$, free at each step to pick any $p_i$ in $\{i+1,\dots,n-2\}$; every choice sequence $(p_0,\dots,p_{n-3})$ yields one starting word.

Each word so produced is maximix, by downward induction. In $w^{(i+1)}$ the carriage $t_i$ has just been placed, so it stands in place $i$; $R_i$ moves it to place $n-1$, and $R_{p_i}$ with $p_i\le n-2$ moves it from there to $p_i$. Neither reversal touches the places before $i$, so in $w^{(i)}$ those still hold the carriages placed earlier while $t_i$ sits in the interior place $p_i$ — exactly the two-use case of Section 2, whose reversals rebuild $w^{(i+1)}$. Simon's routine run forwards on $w^{(0)}$ therefore repeats the chain, spending $2$ uses at every stage $i\le n-3$ and $1$ at the last: $2n-3$ in all.

7. There are exactly $(n-2)!$ of them

At stage $i$ there are $n-i-2$ admissible places, so by the rule of product ^[5] the choice sequences number

$$\begin{aligned}\prod_{i=0}^{n-3}(n-i-2)&=(n-2)(n-3)\cdots1\\&=(n-2)!.\end{aligned}$$

Different sequences give different words, since the word determines the sequence back again: running Simon forwards reveals $p_i$ as the place of $t_i$ in $w^{(i)}$. By Sections 5 and 6 every maximix arrangement comes from its own sequence, so the construction is a bijection and the count is exactly $(n-2)!$ — two for $n=4$ and $24$ for $n=6$, both quoted in the statement, and $9!=362880$ for $n=11$. Their share is

$$\frac{(n-2)!}{n!}=\frac{1}{n(n-1)},$$

one in $12$ for four carriages, one in $30$ for six and one in $110$ for eleven.

8. Worked example: the construction for $n=4$

Start from $w^{(3)}=\mathtt{ABCD}$. The forced last stage gives $w^{(2)}=R_2(\mathtt{ABCD})=\mathtt{ABDC}$. At stage $i=1$ the only admissible place is $p_1=2$, so

$$\begin{aligned}\mathtt{ABDC}&\ \xrightarrow{\ R_1\ }\ \mathtt{ACDB}\\ &\ \xrightarrow{\ R_2\ }\ \mathtt{ACBD}.\end{aligned}$$

At stage $i=0$ we apply $R_0$, obtaining $\mathtt{DBCA}$, and then branch over $p_0\in\{1,2\}$:

$$\begin{aligned}R_1(\mathtt{DBCA})&=\mathtt{DACB},\\ R_2(\mathtt{DBCA})&=\mathtt{DBAC}.\end{aligned}$$

So the maximix arrangements for four carriages are $\mathtt{DACB}$ and $\mathtt{DBAC}$, as the statement says, and there are $(4-2)!=2$ of them.

9. The six-carriage checkpoint

For $n=6$ the construction yields $24$ words, and sorting them puts $\mathtt{DFAECB}$ tenth, as the statement states. Simon's routine on it takes the predicted $9$ uses, two at each of the first four stages and one at the last:

$$\begin{aligned}&\mathtt{DFBCEA},\ \mathtt{AECBFD},\ \mathtt{AECDFB},\\ &\mathtt{ABFDCE},\ \mathtt{ABFDEC},\ \mathtt{ABCEDF},\\ &\mathtt{ABCEFD},\ \mathtt{ABCDFE},\ \mathtt{ABCDEF}.\end{aligned}$$

10. What the arrangements look like

For $n\ge3$ the place of carriage $\mathtt{A}$ in $w^{(0)}$ is $p_0$, which ranges over $1,\dots,n-2$: so $\mathtt{A}$ never stands at an end of a maximix arrangement, and since the later choices do not depend on $p_0$, each interior place carries exactly $(n-3)!$ of them — for $n=11$, $8!=40320$ in each of nine places. (For $n=2$ no stage has an interior target, and the lone maximix arrangement is $\mathtt{BA}$.)

The construction does not emit the words in lexicographic order ^[6] — for $n=6$ its fourth and fifth words are $\mathtt{ECFBAD}$ and $\mathtt{CADEBF}$, the smaller of the two coming second — because branching at an early stage changes letters far from the front. No ranking scheme is needed, though, since $(n-2)!$ is small here: the list is sorted and indexed.

11. How wasteful Simon really is

Reversing a suffix is the same operation as reversing a prefix, read from the other end of the row, so the unrestricted puzzle is pancake sorting and the least possible number of uses is the pancake distance. ^[2] A breadth-first search from the sorted word finds it for small $n$: it visits the arrangements in layers, and as every reversal is its own inverse, the layer where a word first appears is the number of uses needed to sort it. $\mathtt{DACB}$ appears in layer three, confirming the statement's remark that three suffice, by $R_2$, $R_1$, $R_0$,

$$\mathtt{DACB}\to\mathtt{DABC}\to\mathtt{DCBA}\to\mathtt{ABCD},$$

and no four-carriage arrangement needs more than four. Computing that minimum is NP-hard in general, ^[4] whereas Simon's cost is read off stage by stage in $O(n^2)$ time — which is why the problem asks about his routine.

How the Code Works

All three programs are one helper plus one generator; the C++ file adds a forward check and the statement's checkpoints. ^[8] The helper, reverse_suffix(s, idx) in C++ and Python and reverseSuffix in Java, implements $R_{idx}$: C++ reverses the tail in place with std::reverse from s.begin() + idx to s.end(); Python returns s[:idx] + s[idx:][::-1], reversing the tail with a slice of step $-1$; Java appends the reversed s.substring(idx) to a StringBuilder. ^[7]

In C++, generate_maximix_arrangements(n) is Section 6 as a loop. It builds the sorted word from the characters 'A' + i, which keeps the letters inside the capital alphabet for $n\le26$, and applies reverse_suffix(s, n - 2) to it: the forced inversion of the last stage. Then i runs from n - 3 down to 0, and for each word of the current generation it computes the $R_i$ image after_ri once, pushing one copy per p from i + 1 to n - 2, reversed at p, into a vector next reserved to the exact size. states.swap(next) keeps only two generations alive, and std::sort finally orders the words by character code, which is lexicographic order.

simon_moves(s) is the forward routine of Section 2, used only for checking: it sorts a copy for the targets $t_i$, then for each i up to n - 2 finds the target from place i onwards — the earlier places already hold their final carriages — and applies the three cases of that section. run_checkpoints() demands the four-carriage list be exactly DACB, DBAC, the six-carriage list have $24$ entries with DFAECB tenth, and simon_moves return 2 * 6 - 3 for all $24$. main takes only --skip-checkpoints, exits with status $1$ on any other argument and $2$ on a failed checkpoint, and prints mm11[2010], rank $2011$ in a list counted from zero.

Python's generate_maximix_arrangements and Java's generateMaximixArrangements follow the same recursion, but grow each generation by appending to a list and sort with states.sort() and Collections.sort, the latter ordering by String.compareTo and so by the same character order. ^[7] Both omit the checkpoints and guard the lookup with len(mm11) > 2010 and mm11.size() > 2010, which always holds since $9!=362880$. Nothing counts beyond a few hundred thousand, so the integer widths of the three languages play no role; the real differences are that only C++ reserves the next generation in advance and reverses inside a mutable copy, while Python and Java build a fresh word each time.

Complexity and Verification

Backward stage $i$ turns $(n-3-i)!$ words into $(n-2-i)!$ words, so the stage loop creates $\sum_{k=1}^{n-2}k!$ words besides the one it starts from; each factorial is at most half the next, so that stays below $2(n-2)!$. For $n=11$ it is $409113$ words, built with $455347$ suffix reversals of at most $n$ letters. The construction thus runs in $\Theta\bigl(n\,(n-2)!\bigr)$ time, optimal up to the constant since the output alone has that size, and sorting $362880$ words adds about $362880\log_2 362880\approx6.7$ million comparisons of at most eleven characters, in general $O\bigl(n\,(n-2)!\log (n-2)!\bigr)$. Memory is $\Theta\bigl(n\,(n-2)!\bigr)$, as the whole list must exist before sorting, with a library-dependent constant: in the build measured here a $32$-byte std::string holds an eleven-letter word inside the object, for a peak of about $15$ MB, whereas Python, giving every word its own object, peaked at about $68$ MB. Running times on that machine were $0.05$ s for C++, $0.10$ s for Python and $0.11$ s for Java.

Beyond those checkpoints, the following was verified for this article, outside the published solutions.

A brute force over all $n!$ arrangements for every $n$ from $2$ to $11$, which is $39916800$ words at $n=11$: the largest cost of Simon's routine is exactly $2n-3$, exactly $(n-2)!$ arrangements attain it, and that set is identical, word for word, to the one the backward construction produces.
A breadth-first search over the reachable positions, for every $n\le7$, every stage and every place of the target: the stage cost is the $0$, $1$ or $2$ of Section 2, and the two-reversal pair is unique.
A breadth-first search with unrestricted reversals for $n\le8$: the worst-case minima are $1,3,4,5,7,8,9$ for $n=2,\dots,8$ and the whole distributions agree with the published ones. ^[2] ^[3] In particular $\mathtt{DACB}$ needs three uses and $\mathtt{ADCB}$ one, the side remarks of the statement.
The distribution of Section 10, on the generated lists for $3\le n\le11$; and all three programs print the same word for eleven carriages.

Footnotes and References

The references below supply the background facts used above; the stage cost, the bound $2n-3$, the backward construction and its bijection with the choice sequences are derived explicitly here.

Project Euler 336 — Maximix Arrangements. The official statement describes the turntable, which turns the uncoupled rear block through 180 degrees, and Simple Simon, who puts carriage A in place first, then B, and so on. It names DACB and DBAC as the worst four-carriage cases at five rotations each although three suffice, notes that ADCB is solved by separating A from DCB, gives 24 maximix arrangements for six carriages with DFAECB tenth, and asks for the 2011th for eleven.
Wikipedia — Pancake sorting. The only allowed operation is the reversal of a prefix, and the pancake number is the smallest number of flips that always suffices for a given stack height. The page tabulates how many stacks of each height need each number of flips — its row for height 4 is 1, 3, 6, 11, 3 — and states that finding a shortest flip sequence is NP-hard.
OEIS A058986 — sorting by prefix reversal. The sequence gives the worst case, over all permutations of n letters, of the number of initial-segment reversals needed to sort one; its terms from n = 1 begin 0, 1, 3, 4, 5, 7, 8, 9, 10, 11.
Pancake Flipping is Hard. L. Bulteau, G. Fertin and I. Rusu, arXiv:1111.0434. The paper proves that sorting a stack of pancakes with the fewest prefix reversals is NP-hard, for the unburnt variant, the one here.
Wikipedia — Rule of product. If there are a ways of doing one thing and b ways of another, there are a·b ways of doing both, and the rule extends to any number of independent choices — here those of p_0, …, p_(n−3).
Wikipedia — Lexicographic order. Words over a totally ordered alphabet are compared at the first position where they differ — the order the problem asks for.
Library documentation for the reversals and the sorts. cppreference — std::reverse reverses in place the half-open range of two bidirectional iterators. Python — common sequence operations defines s[i:j:k] as the items with indices i, i+k, i+2k, … stopping before j, so a negative step walks backwards and s[::-1] reverses. Java — String documents that compareTo compares strings by the Unicode value of each character.
C++ — Euler336.cpp. The linked immutable revision contains reverse_suffix, simon_moves, generate_maximix_arrangements and run_checkpoints, and the option --skip-checkpoints; it is the implementation record here.

Problem 336 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

void reverse_suffix(std::string& s, const int idx) {
    std::reverse(s.begin() + idx, s.end());
}

int simon_moves(std::string s) {
    const std::string sorted = [&]() {
        std::string t = s;
        std::sort(t.begin(), t.end());
        return t;
    }();

    int moves = 0;
    const int n = static_cast<int>(s.size());

    for (int i = 0; i <= n - 2; ++i) {
        const char target = sorted[static_cast<std::size_t>(i)];
        int pos = -1;
        for (int j = i; j < n; ++j) {
            if (s[static_cast<std::size_t>(j)] == target) {
                pos = j;
                break;
            }
        }

        if (pos == i) {
            continue;
        }

        if (pos != n - 1) {
            reverse_suffix(s, pos);
            ++moves;
        }

        reverse_suffix(s, i);
        ++moves;
    }

    return moves;
}

std::vector<std::string> generate_maximix_arrangements(const int n) {
    std::string start;
    start.reserve(static_cast<std::size_t>(n));
    for (int i = 0; i < n; ++i) {
        start.push_back(static_cast<char>('A' + i));
    }

    std::vector<std::string> states{start};

    // Inverse of Simon's mandatory last move (for i = n-2).
    for (std::string& s : states) {
        reverse_suffix(s, n - 2);
    }

    // For i = n-3 ... 0, inverse of two moves: R(p) after R(i), with p in [i+1, n-2].
    for (int i = n - 3; i >= 0; --i) {
        std::vector<std::string> next;
        const std::size_t branch = static_cast<std::size_t>(n - i - 2);
        next.reserve(states.size() * branch);

        for (const std::string& after : states) {
            std::string after_ri = after;
            reverse_suffix(after_ri, i);

            for (int p = i + 1; p <= n - 2; ++p) {
                std::string before = after_ri;
                reverse_suffix(before, p);
                next.push_back(std::move(before));
            }
        }

        states.swap(next);
    }

    std::sort(states.begin(), states.end());
    return states;
}

bool run_checkpoints() {
    {
        const std::vector<std::string> mm4 = generate_maximix_arrangements(4);
        if (mm4.size() != 2 || mm4[0] != "DACB" || mm4[1] != "DBAC") {
            std::cerr << "Checkpoint failed: n=4 maximix set mismatch\n";
            return false;
        }
    }

    {
        const std::vector<std::string> mm6 = generate_maximix_arrangements(6);
        if (mm6.size() != 24 || mm6[9] != "DFAECB") {
            std::cerr << "Checkpoint failed: n=6 count or 10th lexicographic mismatch\n";
            return false;
        }

        const int max_moves = 2 * 6 - 3;
        for (const std::string& s : mm6) {
            if (simon_moves(s) != max_moves) {
                std::cerr << "Checkpoint failed: generated arrangement is not maximix for n=6\n";
                return false;
            }
        }
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const std::vector<std::string> mm11 = generate_maximix_arrangements(11);
    std::cout << mm11[2010] << '\n';
    return 0;
}

Python

def reverse_suffix(s, idx):
    return s[:idx] + s[idx:][::-1]

def generate_maximix_arrangements(n):
    start = "".join(chr(ord('A') + i) for i in range(n))
    states = [start]
    
    states = [reverse_suffix(s, n - 2) for s in states]
    
    for i in range(n - 3, -1, -1):
        nxt = []
        for after in states:
            after_ri = reverse_suffix(after, i)
            for p in range(i + 1, n - 1):
                before = reverse_suffix(after_ri, p)
                nxt.append(before)
        states = nxt
        
    states.sort()
    return states

def solve():
    mm11 = generate_maximix_arrangements(11)
    if len(mm11) > 2010:
        return mm11[2010]
    return ""

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler336 {

    static String reverseSuffix(String s, int idx) {
        StringBuilder sb = new StringBuilder(s.substring(0, idx));
        StringBuilder reversed = new StringBuilder(s.substring(idx)).reverse();
        return sb.append(reversed).toString();
    }

    static List<String> generateMaximixArrangements(int n) {
        StringBuilder startBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            startBuilder.append((char) ('A' + i));
        }
        String start = startBuilder.toString();

        List<String> states = new ArrayList<>();
        states.add(start);

        List<String> tempStates = new ArrayList<>();
        for (String s : states) {
            tempStates.add(reverseSuffix(s, n - 2));
        }
        states = tempStates;

        for (int i = n - 3; i >= 0; i--) {
            List<String> next = new ArrayList<>();
            for (String after : states) {
                String after_ri = reverseSuffix(after, i);
                for (int p = i + 1; p <= n - 2; p++) {
                    String before = reverseSuffix(after_ri, p);
                    next.add(before);
                }
            }
            states = next;
        }

        Collections.sort(states);
        return states;
    }

    public static String solve() {
        List<String> mm11 = generateMaximixArrangements(11);
        if (mm11.size() > 2010) {
            return mm11.get(2010);
        }
        return "";
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}