[Question]
  [
I'm sure everyone has seen before that cups can be stacked into pyramids (and other shapes):
```
           A    
        A A A   
 A     A A A A  
A A A A A A A A
```
Yes, `A` is definitely an adequate character to represent a cup.
New cups could be added either on the ground, to the right of the structure, or on top of two adjacent cups. Here is the above structure again, but all available spots for new cups are marked with `_`:
```
         _ A         
        A A A        
 A _ _ A A A A       
A A A A A A A A _ _ _
```
Let's say we want to build a robot which can assemble these cup stacks. The robot will understand two simple instructions to manipulate such a structure:
* `a`: Add a new cup in the first available spot in left-to-right *reading* order (that is, scan the rows from top to bottom, left to right until you find an available spot, then place the cup there). The above example would become:
```
         A A   
        A A A  
 A     A A A A 
A A A A A A A A
```
* `r`: Remove the first cup in left-to-right reading order. The above example would become:
```
        A A A  
 A     A A A A 
A A A A A A A A
```
It turns out that *any* structure can be constructed from scratch using only these two operations. E.g.
```
      A
 A   A A
A A A A A
```
Can be built with the sequence of instructions
```
aaaaaaaaaaaarrrrraa
```
The larger example above can be built using
```
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr
```
Here is an even bigger one:
```
    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A
```
which can be built with
```
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa
```
**Note:** If spots on the ground are freed up by removal instructions they will be reused *before* placing cups to the right of all existing cups. E.g.
```
aaaarrra
```
will yield
```
A   A
```
not
```
    A A
```
You can think of the ground as being on top of a semi-infinite row of cups.
## The Challenge
Given a structure of stacked cups, return a sequence representing the instructions to build this structure. Your primary score is the sum of the numbers of instructions for the test cases provided at the bottom. In the event of a tie (which is likely, because I'm convinced that an efficient optimal solution is possible), the shortest solution wins.
Here are some more details about the rules:
* You may assume that there are no leading spaces on the bottom row of the input, so the left-most ground spot for a cup with always be used.
* You may assume any reasonable amount of trailing spaces (no spaces, one space, padded to a rectangle, padded to a rectangle with a single trailing space).
* You may optionally expect the input to end in a single trailing newline.
* You may choose any two distinct printable ASCII characters (0x20 to 0x7E, inclusive) instead of `A` and spaces (the rules about spaces then transfer to your chosen character).
* Your output should contain only two distinct characters representing the operations (you may choose other characters than `a` and `r`). You may optionally print a single trailing newline.
* Your code must be able to solve **any of the test cases below in less than a minute** on a reasonable desktop PC (if it takes two minutes on mine, I'll give you the benefit of the doubt, but if it takes ten I won't - I believe an optimal algorithm is possible which solves any of them in less than a second).
* You must not optimise your code towards individual test cases (e.g. by hardcoding them). If I suspect anyone of doing so, I reserve the right to change the test cases.
You can use [this CJam script](http://cjam.aditsu.net/#code=r_e%600%5C%7B~'a%3D2*(*1%24%2B%7D%25%24_%40%3DW%3E%0A%7B%0A%20%20W%3D2*mQ2%2B%3ALS*aL(*'_L*a%2BN*%5C%0A%20%20%7B%0A%20%20%20%20'a%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20_'_%23%3AI'At_I(%3D'A%3D%7BI(L)-'_t%7D%26_I)%3D'A%3D%7BIL)-'_t%7D%26%0A%20%20%20%20%7D%7B%0A%20%20%20%20%20%20_'A%23%3AI'_t_I(L)-%3D'_%3D%7BI(L)-'%20t%7D%26_IL)-%3D'_%3D%7BIL)-'%20t%7D%26%0A%20%20%20%20%7D%3F%0A%20%20%7D%2F%0A%20%20N%2F%7BS-%7D%2CW%25ee%7B~S*%5CS*%5C%2B%7D%25_0%3D%2Cf%3CW%25N*'_'%20er%0A%7D%7B%0A%20%20%26%0A%7D%3F&input=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa) for the reverse operation: it will take a string of building instructions and print the resulting stack of cups. (Thanks to Dennis for rewriting the snippet and significantly speeding it up.)
Sp3000 also kindly provided [this alternative Python script](http://ideone.com/kNh1Y2) for the same purpose.
## Test Cases
After each test case, there's a number indicating the optimal number of instructions as per Ell's answer.
```
                                       A
                                      A A
                                     A A A
                                    A A A A
                                   A A A A A
                                  A A A A A A
                                 A A A A A A A
                                A A A A A A A A
                               A A A A A A A A A
                              A A A A A A A A A A
                             A A A A A A A A A A A
                            A A A A A A A A A A A A
                           A A A A A A A A A A A A A
                          A A A A A A A A A A A A A A
                         A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A
                       A A A A A A A A A A A A A A A A A
                      A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A
                    A A A A A A A A A A A A A A A A A A A A
                   A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A
                 A A A A A A A A A A A A A A A A A A A A A A A
                A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A
              A A A A A A A A A A A A A A A A A A A A A A A A A A
             A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
820
                                             A
                                            A A
                                           A A A
                                          A A A A
                                         A A A A A
                                        A A A A A A
                                       A A A A A A A
                                      A A A A A A A A
                     A               A A A A A A A A A
                    A A             A A A A A A A A A A
                   A A A           A A A A A A A A A A A
                  A A A A         A A A A A A A A A A A A
         A       A A A A A       A A A A A A A A A A A A A
        A A     A A A A A A     A A A A A A A A A A A A A A
   A   A A A   A A A A A A A   A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
1946
               A
              A A
             A A A
            A A A A
           A A A A A
          A A A A A A
         A A A A A A A
        A A A A A A A A
       A A A A A A A A A               A
      A A A A A A A A A A             A A
     A A A A A A A A A A A           A A A
    A A A A A A A A A A A A         A A A A
   A A A A A A A A A A A A A       A A A A A       A
  A A A A A A A A A A A A A A     A A A A A A     A A
 A A A A A A A A A A A A A A A   A A A A A A A   A A A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
2252
                                                         A A
                                                      A A A A
                                                   A A A A A A
                                                A A A A A A A A
                                             A A A A A A A A A A
                                          A A A A A A A A A A A A
                                       A A A A A A A A A A A A A A
                                    A A A A A A A A A A A A A A A A
                                 A A A A A A A A A A A A A A A A A A
                              A A A A A A A A A A A A A A A A A A A A
                           A A A A A A A A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
9958
                   A A
                  A A A A
                 A A A A A A
                A A A A A A A A
               A A A A A A A A A A
              A A A A A A A A A A A A
             A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5540
A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
10280
 A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
10320
   A       A       A       A       A       A       A       A       A       A
  A A     A A     A A     A A     A A     A A     A A     A A     A A     A A
 A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
5794
              A
             A A
            A A A
           A A A A                                               A
          A A A A A                                             A A
         A A A A A A A                                         A A A
        A A A A A A A A               A                       A A A A
       A A A A A A A A A             A A             A       A A A A A   A
      A A A A A A A A A A           A A A           A A     A A A A A A A A
     A A A A A A A A A A A         A A A A         A A A   A A A A A A A A A
    A A A A A A A A A A A A       A A A A A       A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A     A A A A A A     A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A   A A A A A A A   A A A A A A A A A A A A A A A A
3297
                                                   A A
                                                  A A A
                                                 A A A A
                                                A A A A A
                                               A A A A A A
                                              A A A A A A A
                                             A A A A A A A A
                                            A A A A A A A A A
                                           A A A A A A A A A A     A
                                          A A A A A A A A A A A   A A
                                       A A A A A A A A A A A A A A A A
                                      A A A A A A A A A A A A A A A A A
                                     A A A A A A A A A A A A A A A A A A
      A                             A A A A A A A A A A A A A A A A A A A
     A A                           A A A A A A A A A A A A A A A A A A A A
    A A A             A A         A A A A A A A A A A A A A A A A A A A A A
   A A A A           A A A       A A A A A A A A A A A A A A A A A A A A A A
  A A A A A         A A A A     A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A     A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
4081
                      A
                     A A       A                     A
                    A A A     A A                   A A A                 A
             A     A A A A   A A A A               A A A A     A         A A
  A         A A   A A A A A A A A A A         A   A A A A A   A A       A A A
 A A       A A A A A A A A A A A A A A       A A A A A A A A A A A     A A A A
A A A   A A A A A A A A A A A A A A A A     A A A A A A A A A A A A   A A A A A
4475
                                                             A              
      A           A                       A                 A A A   A       A
     A A         A A   A         A A     A A A   A         A A A A A A     A A
A   A A A A A   A A A A A   A   A A A   A A A A A A   A   A A A A A A A   A A A
5752
```
That means, the best possible score is **64,515** instructions.
  
[Answer]
# Python 2, 64,515
```
import sys
input = map(str.rstrip, sys.stdin.readlines())
width = (len(input[-1]) + 1) / 2
for i in range(len(input)):
    indent = len(input) - i - 1
    input[i] = [c != " " for c in input[i][indent::2]]
    input[i] += [False] * (width - indent - len(input[i]))
input = [[False] * n for n in range(width - len(input) + 1)] + input
working_area = [[False] * n for n in range(width + 1)]
def add():
    sys.stdout.write("a")
    for row in range(width + 1):
        for i in range(row):
            if not working_area[row][i] and (
                row == width or
                (working_area[row + 1][i] and working_area[row + 1][i + 1])
            ):
                working_area[row][i] = True
                return
def remove():
    sys.stdout.write("r")
    for row in range(width + 1):
        if True in working_area[row]:
            working_area[row][working_area[row].index(True)] = False
            return
for row in range(width, -1, -1):
    r = input[row]; R = working_area[row]
    for i in range(len(r) - 1, -1, -1):
        if r[i]:
            while not R[i]: add()
        else:
            while R[i]: remove()
```
## Results
[![Test 1](https://i.stack.imgur.com/FGBsZ.gif)](https://i.stack.imgur.com/M6xZO.gif) **#1** - [820](https://gist.githubusercontent.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test1) 
[![Test 2](https://i.stack.imgur.com/LbqwF.gif)](https://i.stack.imgur.com/LufCh.gif) **#2** - [1,946](https://gist.githubusercontent.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test2) 
[![Test 3](https://i.stack.imgur.com/PES2L.gif)](https://i.stack.imgur.com/T3gKA.gif) **#3** - [2,252](https://gist.githubusercontent.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test3)
  
[![Test 4](https://i.stack.imgur.com/T7f6f.gif)](https://i.stack.imgur.com/rKkkV.gif) **#4** - [9,958](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test4) 
[![Test 5](https://i.stack.imgur.com/fELhA.gif)](https://i.stack.imgur.com/czBFQ.gif) **#5** - [5,540](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test5) 
[![Test 6](https://i.stack.imgur.com/TQW4i.gif)](https://i.stack.imgur.com/T4LyW.gif) **#6** - [10,280](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test6)
  
[![Test 7](https://i.stack.imgur.com/SWpvk.gif)](https://i.stack.imgur.com/osCj1.gif) **#7** - [10,320](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test7) 
[![Test 8](https://i.stack.imgur.com/TNFBi.gif)](https://i.stack.imgur.com/pIlXQ.gif) **#8** - [5,794](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test8) 
[![Test 9](https://i.stack.imgur.com/JRj0E.gif)](https://i.stack.imgur.com/eMGsQ.gif) **#9** - [3,297](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test9)
  
[![Test 10](https://i.stack.imgur.com/vfOGr.gif)](https://i.stack.imgur.com/cMfoZ.gif) **#10** - [4,081](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test10) 
[![Test 11](https://i.stack.imgur.com/8sPpa.gif)](https://i.stack.imgur.com/YhC8j.gif) **#11** - [4,475](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test11) 
[![Test 12](https://i.stack.imgur.com/yjCuH.gif)](https://i.stack.imgur.com/DF6xV.gif) **#12** - [5,752](https://gist.github.com/anonymous/bee1a2949430e04d9b6e/raw/ff6ad031168259f43f3d33be5459d1529e5d3fb0/test12)
**Total** 64,515
## Explanation
We start with an empty "working area".
We scan the input in *reverse* reading order, i.e., right-to-left and bottom-to-top.
If there's a mismatch between the input and the working area at the current location (i.e., a cup is present in the input but not in the working area, or vice versa,) we add, or remove, cups to the working area, according to the rules, until the mismatch is resolved, at which point we continue to the next location.
**Correctness**
To show that this method is correct, i.e., that the resulting sequence generates the input structure, it's enough to show that we never modify (i.e., add or remove cups at) locations we've already visited (since, at each location we visit, we make sure that the working area matches the input.)
This is an easy consequence of the fact that we work in the reverse order in which cups are added and removed:
* A cup at location *l* will always be removed before a cup at a location that succeeds *l* in reading order, and therefore, that precedes *l* in scan order, hence there's no danger of removing a cup we've already visited.
* Similarly, a cup at location *l* will always be added before a cup that precedes it in scan order, **given that** there are already two cups below it (or that it's at the bottom);
however, since we will have already visited these locations, and hence added the necessary cups, and since, as noted above, there's no danger of later having removed those cups, this condition is met, and so there's no danger of adding a cup at a location we've already visited.
**Optimality**
Note that the effect of adding, or removing, a cup from a structure doesn't depend on the sequence of operations used to generate the structure, only on its current configuration.
As a result, given an optimal sequence *Sn* = {*s*1, ..., *sn*} of operations that generate a certain structure, every initial segment of *Sn*, i.e., any sequence *Sm* = {*s*1, ..., *sm*}, where *m* ≤ *n*, is also an optimal sequence, for the corresponding structure it generates, or else there would be a shorter sequence than *Sn*, generating the same structure.
We can show that our method is optimal by induction on the length of the optimal generating sequence:
Our method clearly generates an optimal sequence for any structure whose optimal generating sequence is empty (there's only one such structure—the empty structure.)
Suppose that our method generates an optimal sequence for all structures whose optimal sequence (or sequences) is of length *n*, and consider a structure generated by an optimal sequence *S**n*+1.
We want to show that, given the structure generated by *S**n*+1 as input, our method produces the same sequence (or, at least, a sequence of the same length.)
As noted above, *Sn* is also an optimal sequence, and so, by hypothesis, our method produces an optimal sequence given the structure generated by *Sn* as input.
Suppose, without loss of generality, that *Sn* is the sequence produced by our method (if it isn't, we can always replace the first *n* elements of *S**n*+1 with the said sequence, and get a sequence of length *n* + 1 that generates the same structure.)
Let *l* be the location modified by the last operation in *S**n*+1 (namely, *s**n*+1), and let *Sm* be the initial segment of *Sn*, that our program will have produced once it reaches *l* (but before processing *l*).
Note that, since the structures generated by *Sn* and *S**n*+1 agree in all locations that follow *l*, in reading order, *Sm* is the same given either structure as input.
If *s**n*+1 is `a` (i.e., cup addition), then there must not be any location preceding *l*, in reading order, where a cup can be added to the structure generated by *Sn*. As a result, the subsequence of *Sn* following *Sm* must be all `a` (since an `r` would imply that either there's an empty space before *l*, or that *Sn* is not optimal.)
When we come to process *l*, we'll need to add exactly *n - m* cups before we can add a cup at *l*, hence the resulting sequence will be *Sm*, followed by *n - m* + 1 `a` elements, which equals *S**n*+1 (there won't be any mismatch after this point, hence this is the complete sequence produced.)
Likewise, if *s**n*+1 is `r`, then there must not be any cup at a location preceding *l*, in reading order, in the structure generated by *Sn*. As a result, the subsequence of *Sn* following *Sm* must be all `r`.
When we come to process *l*, we'll need to remove exactly *n - m* cups before we can remove the cup at *l*, hence the resulting sequence will be *Sm*, followed by *n - m* + 1 `r` elements, which again equals *S**n*+1.
In other words, our method produces an optimal sequence for the said input structure, and therefore, by induction, for any input structure.
Note that this doesn't mean that this implementation is the most efficient one.
It's definitely possible, for example, to calculate the number of cups that has to be added, or removed, at each point directly, instead of actually performing these operations.
**Uniqueness**
We can use the optimality of our method to show that optimal sequences are, in fact, unique (that is, that no two distinct optimal sequences generate the same structure.)
We use, again, induction on the size of the optimal generating sequence:
The empty sequence is obviously the unique optimal generating sequence of the empty structure.
Suppose that all optimal generating sequences of length *n* are unique, and consider a structure, Σ, generated by the two optimal sequences *S**n*+1 and *T**n*+1.
Recall that *Sn* and *Tn* are themselves optimal, and therefore, by hypothesis, unique.
Since our method produces optimal sequences, *Sn* and *Tn* can be thought of as generated by our method.
Let *lS* and *lT* be the locations modified by the last operation in *S**n*+1 and *T**n*+1, respectively, and suppose, without loss of generality, that *lS* follows, or equals, *lT* in reading order.
Since the structures generated by *Sn* and *Tn* agree in all locations following *lS*, in reading order, the sequence produced by our method, given either structure as input, once it reaches *lS* (but before processing it), is the same for both; call this sequence *U*.
Since the last action of *S**n*+1 modifies *lS*, if Σ has a cup at *lS* then there must not be any vacancy before *lS*, and if Σ doesn't have a cup at *lS* then there must not be any cup before *lS*, in reading order.
Therefore, the rest of the sequence generating Σ, following *U*, must consist of repeated application of the same instruction, dictated by the presence or absence of a cup at *lS* (or else it wouldn't be optimal).
In other words, *S**n*+1 and *T**n*+1 are equal (they both start with *U*, and end with the said sequence of repeated instructions,) that is, the optimal generating sequence of Σ is unique, and so, by induction, all optimal generating sequences are unique.
]