Jestem pewien, że wszyscy widzieli wcześniej, że kubki można układać w piramidy (i inne kształty):

           A    
        A A A   
 A     A A A A  
A A A A A A A A

^{Tak, Ajest zdecydowanie odpowiednią postacią do reprezentowania filiżanki.}

Nowe kubki można dodawać albo na ziemi, po prawej stronie konstrukcji, albo na dwóch sąsiadujących kubkach. Oto ponownie powyższa struktura, ale wszystkie dostępne miejsca na nowe kubki są oznaczone _:

         _ A         
        A A A        
 A _ _ A A A A       
A A A A A A A A _ _ _

Powiedzmy, że chcemy zbudować robota, który może łączyć te stosy kubków. Robot zrozumie dwie proste instrukcje dotyczące manipulowania taką strukturą:

a: Dodaj nowy kubek w pierwszym dostępnym miejscu w kolejności czytania od lewej do prawej (tzn. Zeskanuj rzędy od góry do dołu, od lewej do prawej, aż znajdziesz wolne miejsce, a następnie umieść tam kubek). Powyższy przykład wyglądałby następująco:
```
         A A   
        A A A  
 A     A A A A 
A A A A A A A A
```
r: Wyjmij pierwszy kubek w kolejności czytania od lewej do prawej. Powyższy przykład wyglądałby następująco:
```
        A A A  
 A     A A A A 
A A A A A A A A
```

Okazuje się, że dowolną strukturę można zbudować od zera przy użyciu tylko tych dwóch operacji. Na przykład

      A
 A   A A
A A A A A

Może być zbudowany z sekwencji instrukcji

aaaaaaaaaaaarrrrraa

Większy przykład powyżej można zbudować za pomocą

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

Oto jeszcze większy:

    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A

które można zbudować

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

Uwaga: Jeśli miejsca na ziemi zostaną zwolnione dzięki instrukcjom usuwania, zostaną one ponownie wykorzystane przed umieszczeniem filiżanek po prawej stronie wszystkich istniejących filiżanek. Na przykład

aaaarrra

ustąpi

A   A

nie

A A

Możesz myśleć o ziemi jako o pół-nieskończonym rzędzie filiżanek.

Wyzwanie

Biorąc pod uwagę strukturę stosów kubków, zwróć sekwencję przedstawiającą instrukcje dotyczące budowy tej struktury. Twój wynik główny to suma liczb instrukcji dla przypadków testowych podanych na dole. W przypadku remisu (co jest prawdopodobne, ponieważ jestem przekonany, że możliwe jest skuteczne i optymalne rozwiązanie), najkrótsze rozwiązanie wygrywa.

Oto kilka szczegółów na temat zasad:

Możesz założyć, że w dolnym rzędzie wejścia nie ma żadnych spacji wiodących, więc zawsze używaj lewego skrajnego miejsca na filiżankę.
Możesz założyć dowolną rozsądną liczbę końcowych spacji (bez spacji, jedna spacja, dopełniona do prostokąta, dopełniona do prostokąta z jedną spacją końcową).
Opcjonalnie możesz oczekiwać, że dane wejściowe zakończą się jednym końcowym znakiem nowej linii.
Możesz wybrać dowolne dwa odrębne drukowalne znaki ASCII (0x20 do 0x7E włącznie) zamiast Aspacji (reguły dotyczące spacji przenoszą się na wybraną postać).
Twój wynik powinien zawierać tylko dwa różne znaki reprezentujące operacje (możesz wybrać inne znaki niż ai r). Możesz opcjonalnie wydrukować jedną końcową linię nowego wiersza.
Twój kod musi być w stanie rozwiązać dowolny z poniższych przypadków testowych w ciągu niecałej minuty na rozsądnym komputerze stacjonarnym (jeśli zajmie to dwie minuty w moim przypadku, dam ci korzyść z wątpliwości, ale jeśli zajmie to dziesięć, wygrałem 't - Uważam, że możliwy jest optymalny algorytm, który rozwiąże którykolwiek z nich w mniej niż sekundę).
Nie wolno optymalizować kodu pod kątem indywidualnych przypadków testowych (np. Poprzez ich kodowanie na stałe). Jeśli podejrzewam, że ktoś to robi, zastrzegam sobie prawo do zmiany przypadków testowych.

Możesz użyć tego skryptu CJam do operacji odwrotnej: zajmie ciąg instrukcji budowania i wydrukuje powstały stos kubków. (Podziękowania dla Dennisa za przepisanie fragmentu i znaczne przyspieszenie).

Sp3000 również uprzejmie dostarczył ten alternatywny skrypt Pythona do tego samego celu.

Przypadki testowe

Po każdym przypadku testowym znajduje się liczba wskazująca optymalną liczbę instrukcji zgodnie z odpowiedzią Ell.

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

Oznacza to, że najlepszy możliwy wynik to 64 515 instrukcji.

metagolf hexagonal-grid

— Martin Ender
źródło

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()

Wyniki

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

Razem 64.515

Wyjaśnienie

Zaczynamy od pustego „obszaru roboczego”. Skanujemy dane wejściowe w odwrotnej kolejności odczytu, tj. Od prawej do lewej i od dołu do góry. Jeśli istnieje niezgodność między wejściem a obszarem roboczym w bieżącej lokalizacji (tj. Kubek jest obecny na wejściu, ale nie w obszarze roboczym, lub odwrotnie), dodajemy lub usuwamy kubki do obszaru roboczego, zgodnie z do zasad, do momentu usunięcia niezgodności, w tym momencie przechodzimy do następnej lokalizacji.

Poprawność

Aby pokazać, że ta metoda jest poprawna, tj. Że wynikowa sekwencja generuje strukturę wejściową, wystarczy pokazać, że nigdy nie modyfikujemy (tj. Dodajemy lub usuwamy misek w) miejscach, które już odwiedziliśmy (ponieważ w każdej lokalizacji, którą odwiedzamy , upewniamy się, że obszar roboczy pasuje do danych wejściowych.) Jest to prosta konsekwencja faktu, że pracujemy w odwrotnej kolejności, w której kubki są dodawane i usuwane:

Kubek w miejscu l zawsze będzie usuwany przed kubkiem w miejscu, w którym udaje się l w kolejności odczytu, a zatem poprzedza l w kolejności skanowania, dlatego nie ma niebezpieczeństwa usunięcia kubka, który już odwiedziliśmy.
Podobnie kubek w miejscu l zawsze będzie dodawany przed kubkiem, który poprzedza go w kolejności skanowania, biorąc pod uwagę, że pod nim znajdują się już dwa kubki (lub że jest on na dole); ponieważ jednak odwiedziliśmy już te lokalizacje i dlatego dodaliśmy niezbędne kubki, a ponieważ, jak wspomniano powyżej, nie ma niebezpieczeństwa późniejszego usunięcia tych filiżanek, warunek ten jest spełniony, a zatem nie ma niebezpieczeństwa dodania filiżanki w lokalizacja, którą już odwiedziliśmy.

Optymalność

Zauważ, że efekt dodania lub usunięcia kubka ze struktury nie zależy od sekwencji operacji użytych do wygenerowania struktury, tylko od jej bieżącej konfiguracji. W rezultacie, biorąc pod uwagę optymalną sekwencję S _n = { s ₁ , ..., s _n } operacji, które generują określoną strukturę, każdy początkowy segment S _n , tj. Dowolna sekwencja S _m = { s ₁ , .. ., s _m }, gdzie m ≤ n , jest również optymalną sekwencją, dla odpowiedniej struktury, którą generuje, w przeciwnym razie byłaby krótsza sekwencja niż S _n, generując tę samą strukturę.

Możemy wykazać, że nasza metoda jest optymalna poprzez indukcję długości optymalnej sekwencji generującej: Nasza metoda wyraźnie generuje optymalną sekwencję dla dowolnej struktury, której optymalna sekwencja generująca jest pusta (istnieje tylko jedna taka struktura - pusta struktura). Załóżmy, że nasza Sposób generuje sekwencję optymalną dla wszystkich struktur, których optymalną sekwencję (lub sekwencje) ma długość n i rozważyć struktury sekwencji generowanych przez optymalny S _{n +1} . Chcemy wskazują, że ze względu na strukturę generowane przez S _{n +1} jako wejście, sposób według wynalazku zapewnia taką samą sekwencję (lub przynajmniej sekwencję o tej samej długości).

Jak wspomniano powyżej, S _n jest sekwencją optymalna, a więc z założenia, sposób według wynalazku daje sekwencję optymalny ze względu na wytwarzane przez strukturę S _n jako wejście. Załóżmy, bez utraty ogólności, że S _n jest sekwencją utworzoną przez naszą metodę (jeśli nie jest, zawsze możemy zastąpić pierwsze n elementów S _{n +1} tą sekwencją i otrzymać sekwencję o długości n + 1, który generuje tę samą strukturę.) Niech l będzie lokalizacją zmodyfikowaną przez ostatnią operację w S _{n +1} (a mianowicie s _{n +1} ) i niechS _m jest początkowym segmentem S _n , który nasz program wytworzy, gdy osiągnie l (ale przed przetworzeniem l ). Należy zauważyć, że ponieważ struktury wytworzone przez S _n i S _{n +1} zgadza się we wszystkich miejscach, które następują l , w stanie odczytu, S _m jest taki sam biorąc pod uwagę zarówno konstrukcja, jak dane wejściowe.

Jeżeli s _{n +1} to a(tj. Dodanie kielicha), to nie może być żadnego miejsca poprzedzającego l , w kolejności odczytu, w którym kielich można dodać do struktury generowanej przez S _n . W rezultacie podsekwencja S _n po S _m musi być wszystkim a(ponieważ roznaczałoby to, że albo jest pusta przestrzeń przed l , albo że S _n nie jest optymalna.) Kiedy dojdziemy do przetworzenia l , będziemy musieli dodaj dokładnie n - m kubków, zanim będziemy mogli dodać filiżankę w l , stąd sekwencją wynikową będzie S_m , po których następuje n - m + 1aelementów, co równa się S _{n +1} (po tym punkcie nie będzie żadnego niedopasowania, stąd jest to wytworzona pełna sekwencja).

Podobnie, jeśli s _{n +1} jest r, to nie może być żadnego kubka w miejscu poprzedzającym l , w kolejności odczytu, w strukturze generowanej przez S _n . W rezultacie podsekwencja S _n po S _m musi być wszystkim r. Kiedy dojdziemy do przetworzenia l , będziemy musieli usunąć dokładnie n - m kubków, zanim będziemy mogli usunąć kielich w l , stąd powstałą sekwencją będzie S _m , a następnie n - m + 1 relementów, co ponownie jest równe S _{n +1} .

Innymi słowy, nasza metoda zapewnia optymalną sekwencję dla wspomnianej struktury wejściowej, a zatem, przez indukcję, dla dowolnej struktury wejściowej.

Pamiętaj, że nie oznacza to, że ta implementacja jest najbardziej wydajna. Zdecydowanie można na przykład obliczyć liczbę kubków, które należy dodać lub usunąć bezpośrednio w każdym punkcie, zamiast faktycznie wykonywać te operacje.

Wyjątkowość

Możemy wykorzystać optymalność naszej metody, aby pokazać, że optymalne sekwencje są w rzeczywistości unikalne (to znaczy, że żadne dwie odrębne optymalne sekwencje nie generują tej samej struktury.) Ponownie używamy indukcji wielkości optymalnej sekwencji generującej: Pusta sekwencja jest oczywiście unikalną optymalną sekwencją generującą pustą strukturę. Załóżmy, że wszystkie sekwencje optymalne generowanie długości n są unikalne i rozważyć struktury, Ď generowanego przez te dwie sekwencje optymalne S _{n +1} i T _{n +1} .

Przypomnij sobie, że S _n i T _n same w sobie są optymalne, a zatem, hipotetycznie, niepowtarzalne. Ponieważ sposób według wynalazku daje optymalne sekwencje S _n i T _n mogą być traktowane jako wytwarzane przez nasz sposób. Niech l _S i l _T będą lokalizacjami zmodyfikowanymi przez ostatnią operację odpowiednio w S _{n +1} i T _{n +1} , i załóżmy, bez utraty ogólności, że l _S podąża lub równa się l _T w kolejności odczytu. Ponieważ struktury generowane przez S _ni T _n zgadza się we wszystkich miejscach po l _S , w celu, sekwencję wytwarzanego przez naszej metody odczytu, podawano Struktura danych wejściowych, po osiągnięciu l _S (ale przed jego przetwarzanie), jest taki sam dla obu; nazwać sekwencję U .

Ponieważ ostatnie działanie S _{n +1} modyfikuje l _S , jeśli Σ ma kubek przy l _S, to nie może być wolnego miejsca przed l _S , a jeśli Σ nie ma kubka przy l _S, nie może być żadnego kubek przed l _S. w kolejności czytania. Dlatego też reszta generowania sekwencji Ď po U musi składać się z powtarzających się stosowanie tej samej instrukcji, dyktowane przez obecność lub nieobecność kubka w l _S (lub w innym wypadku nie byłoby optymalne). Innymi słowy, S _{n +1} i T _{n +1}są równe (oba zaczynają się od U i kończą wspomnianą sekwencją powtarzanych instrukcji), to znaczy optymalna sekwencja generująca Σ jest unikalna, a zatem, poprzez indukcję, wszystkie optymalne sekwencje generujące są unikalne.

— Łokieć
źródło

Zaprogramuj robota układającego kubki

Wyzwanie

Przypadki testowe

Python 2, 64,515

Wyniki

Wyjaśnienie