36
\$\begingroup\$

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.

\$\endgroup\$
32
\$\begingroup\$

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 #1 - 820Test 2 #2 - 1,946Test 3 #3 - 2,252
Test 4 #4 - 9,958Test 5 #5 - 5,540Test 6 #6 - 10,280
Test 7 #7 - 10,320Test 8 #8 - 5,794Test 9 #9 - 3,297
Test 10 #10 - 4,081Test 11 #11 - 4,475Test 12 #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 Sn = {s1, ..., sn} of operations that generate a certain structure, every initial segment of Sn, i.e., any sequence Sm = {s1, ..., sm}, where mn, 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 Sn+1. We want to show that, given the structure generated by Sn+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 Sn+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 Sn+1 (namely, sn+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 Sn+1 agree in all locations that follow l, in reading order, Sm is the same given either structure as input.

If sn+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 Sn+1 (there won't be any mismatch after this point, hence this is the complete sequence produced.)

Likewise, if sn+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 Sn+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 Sn+1 and Tn+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 Sn+1 and Tn+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 Sn+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, Sn+1 and Tn+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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.