Program the Cup-Stacking Robot

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 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 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 1

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

#1 - 820  #2 - 1,946  #3 - 2,252
#4 - 9,958  #5 - 5,540  #6 - 10,280
#7 - 10,320  #8 - 5,794  #9 - 3,297
#10 - 4,081  #11 - 4,475  #12 - 5,752

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 S_n = {s₁, ..., s_n} of operations that generate a certain structure, every initial segment of S_n, i.e., any sequence S_m = {s₁, ..., s_m}, where m ≤ n, is also an optimal sequence, for the corresponding structure it generates, or else there would be a shorter sequence than S_n, 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, S_n is also an optimal sequence, and so, by hypothesis, our method produces an optimal sequence given the structure generated by S_n as input. Suppose, without loss of generality, that S_n 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 S_m be the initial segment of S_n, that our program will have produced once it reaches l (but before processing l). Note that, since the structures generated by S_n and S_n+1 agree in all locations that follow l, in reading order, S_m 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 S_n. As a result, the subsequence of S_n following S_m must be all a (since an r would imply that either there's an empty space before l, or that S_n 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 S_m, 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 S_n. As a result, the subsequence of S_n following S_m 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 S_m, 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 S_n and T_n are themselves optimal, and therefore, by hypothesis, unique. Since our method produces optimal sequences, S_n and T_n can be thought of as generated by our method. Let l_S and l_T be the locations modified by the last operation in S_n+1 and T_n+1, respectively, and suppose, without loss of generality, that l_S follows, or equals, l_T in reading order. Since the structures generated by S_n and T_n agree in all locations following l_S, in reading order, the sequence produced by our method, given either structure as input, once it reaches l_S (but before processing it), is the same for both; call this sequence U.

Since the last action of S_n+1 modifies l_S, if Σ has a cup at l_S then there must not be any vacancy before l_S, and if Σ doesn't have a cup at l_S then there must not be any cup before l_S, 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 l_S (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.