Tenho certeza que todo mundo já viu antes que os copos possam ser empilhados em pirâmides (e outras formas):

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

^{Sim, Aé definitivamente um personagem adequado para representar um copo.}

Novos copos podem ser adicionados no chão, à direita da estrutura ou em cima de dois copos adjacentes. Aqui está a estrutura acima novamente, mas todos os locais disponíveis para novos copos estão marcados com _:

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

Digamos que queremos construir um robô que possa montar essas pilhas de copos. O robô entenderá duas instruções simples para manipular essa estrutura:

a: Adicione um copo novo no primeiro local disponível na ordem de leitura da esquerda para a direita (ou seja, digitalize as linhas de cima para baixo, da esquerda para a direita até encontrar um local disponível e coloque o copo ali). O exemplo acima se tornaria:
```
         A A   
        A A A  
 A     A A A A 
A A A A A A A A
```
r: Remova o primeiro copo na ordem de leitura da esquerda para a direita. O exemplo acima se tornaria:
```
        A A A  
 A     A A A A 
A A A A A A A A
```

Acontece que qualquer estrutura pode ser construída do zero usando apenas essas duas operações. Por exemplo

      A
 A   A A
A A A A A

Pode ser construído com a sequência de instruções

aaaaaaaaaaaarrrrraa

O exemplo maior acima pode ser construído usando

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

Aqui está um ainda maior:

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

que pode ser construído com

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

Nota: Se os pontos no chão forem liberados pelas instruções de remoção, eles serão reutilizados antes de colocar os copos à direita de todos os copos existentes. Por exemplo

aaaarrra

vai render

A   A

não

A A

Você pode pensar no chão como estando em cima de uma fileira semi-infinita de xícaras.

O desafio

Dada uma estrutura de copos empilhados, retorne uma sequência representando as instruções para construir essa estrutura. Sua pontuação principal é a soma dos números de instruções para os casos de teste fornecidos na parte inferior. Em caso de empate (o que é provável, porque estou convencido de que uma solução ótima e eficiente é possível), a solução mais curta vence.

Aqui estão mais alguns detalhes sobre as regras:

Você pode assumir que não há espaços à esquerda na linha inferior da entrada; portanto, o ponto mais à esquerda do copo sempre deve ser usado.
Você pode assumir qualquer quantidade razoável de espaços à direita (sem espaços, um espaço, preenchido com um retângulo, preenchido com um retângulo com um único espaço à direita).
Opcionalmente, você pode esperar que a entrada termine em uma única nova linha à direita.
Você pode escolher dois caracteres ASCII imprimíveis distintos (0x20 a 0x7E, inclusive) em vez de Aespaços (as regras sobre espaços são transferidas para o caractere escolhido).
Sua saída deve conter apenas dois caracteres distintos que representam as operações (você pode escolher outros caracteres além de ae r). Opcionalmente, você pode imprimir uma única nova linha à direita.
Seu código deve ser capaz de resolver qualquer um dos casos de teste abaixo em menos de um minuto em um PC de mesa razoável (se levar dois minutos no meu, darei a você o benefício da dúvida, mas se levar dez, vencerei Acredito que seja possível um algoritmo ideal que resolva qualquer um deles em menos de um segundo).
Você não deve otimizar seu código para casos de teste individuais (por exemplo, codificando-os). Se eu suspeito que alguém o faça, reservo-me o direito de alterar os casos de teste.

Você pode usar este script CJam para a operação reversa: ele precisará de uma sequência de instruções de construção e imprimirá a pilha de copos resultante. (Agradecemos a Dennis por reescrever o trecho e acelerá-lo significativamente.)

O Sp3000 também gentilmente forneceu esse script Python alternativo para o mesmo objetivo.

Casos de teste

Após cada caso de teste, há um número indicando o número ideal de instruções conforme a resposta de 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

Isso significa que a melhor pontuação possível é 64.515 instruções.

metagolf hexagonal-grid Martin Ender
fonte

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

Resultados

# 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

Explicação

Começamos com uma "área de trabalho" vazia. Digitalizamos a entrada na ordem inversa de leitura, ou seja, da direita para a esquerda e de baixo para cima. Se houver uma incompatibilidade entre a entrada e a área de trabalho no local atual (ou seja, um copo está presente na entrada, mas não na área de trabalho, ou vice-versa), adicionamos ou removemos copos na área de trabalho, de acordo com até as regras, até que a incompatibilidade seja resolvida; nesse ponto, continuamos para o próximo local.

Correção

Para mostrar que esse método está correto, ou seja, que a sequência resultante gera a estrutura de entrada, basta mostrar que nunca modificamos (ou seja, adicionamos ou removemos xícaras em) locais que já visitamos (desde que, em cada local que visitamos) , garantimos que a área de trabalho corresponda à entrada.) Isso é uma consequência fácil do fato de trabalharmos na ordem inversa na qual os copos são adicionados e removidos:

Um copo na posição l sempre será removido antes de um copo em um local que sucede l , a fim de ler, e, portanto, que precede l , a fim de digitalização, portanto, não há perigo de remoção de um copo que já visitou.
Da mesma forma, um copo no local l sempre será adicionado antes de um copo que o preceda na ordem de varredura, já que já existem dois copos abaixo dele (ou que estão na parte inferior); no entanto, como já visitamos esses locais e, portanto, adicionamos os copos necessários, e como, como observado acima, não há perigo de removê-los posteriormente, essa condição é atendida e, portanto, não há perigo de adicionar um copo em um local que já visitamos.

Optimalidade

Observe que o efeito de adicionar ou remover um copo de uma estrutura não depende da sequência de operações usada para gerar a estrutura, apenas de sua configuração atual. Como resultado, dada uma sequência ideal S _n = { s ₁ , ..., s _n } de operações que geram uma certa estrutura, todo segmento inicial de S _n , ou seja, qualquer sequência S _m = { s ₁ , .. ., s _m }, onde m ≤ n , também é uma sequência ótima, para a estrutura correspondente que gera, ou então haveria uma sequência mais curta que S _n, gerando a mesma estrutura.

Podemos mostrar que nosso método é ideal por indução no comprimento da sequência geradora ideal: Nosso método gera claramente uma sequência ideal para qualquer estrutura cuja sequência geradora ideal esteja vazia (existe apenas uma dessas estruturas - a estrutura vazia). Suponha que nosso O método gera uma sequência ideal para todas as estruturas cuja sequência (ou sequências) ideal é de comprimento n e considera uma estrutura gerada por uma sequência ótima S _{n +1} . Queremos mostrar que, dada a estrutura gerada por S _{n +1} como entrada, nosso método produz a mesma sequência (ou, pelo menos, uma sequência do mesmo comprimento).

Como observado acima, S _n também é uma sequência ótima e, por hipótese, nosso método produz uma sequência ótima, dada a estrutura gerada por S _n como entrada. Suponha, sem perda de generalidade, que S _n é a sequência produzida por nosso método (se não for, sempre podemos substituir os primeiros n elementos de S _{n +1} pela referida sequência e obter uma sequência de comprimento n + 1 que gera a mesma estrutura.) Seja l o local modificado pela última operação em S _{n +1} (ou seja, s _{n +1} ), e sejaS _m é o segmento inicial de S _n , que nosso programa terá produzido quando atingir l (mas antes de processar l ). Observe que, como as estruturas geradas por S _n e S _{n +1} concordam em todos os locais que seguem l , na ordem de leitura, S _m é o mesmo dado tanto a estrutura como a entrada.

Se s _{n +1} for a(isto é, adição de xícara), não deverá haver nenhum local anterior a l , em ordem de leitura, em que uma xícara possa ser adicionada à estrutura gerada por S _n . Como resultado, a subsequência de S _n após S _m deve ser toda a(uma vez rque implica que há um espaço vazio antes de l ou que S _n não é ideal.) Quando chegamos ao processo l , precisamos adicione exatamente n - m xícaras antes que possamos adicionar uma xícara em l , portanto a sequência resultante será S_m , seguido por n - m + 1aelementos, que é igual a S _{n +1} (não haverá incompatibilidade após esse ponto, portanto, esta é a sequência completa produzida).

Da mesma forma, se s _{n +1} for r, então não deve haver nenhum copo em um local anterior a l , em ordem de leitura, na estrutura gerada por S _n . Como resultado, a subsequência de S _n após S _m deve ser toda r. Quando chegarmos ao processo l , precisaremos remover exatamente n - m xícaras antes de podermos remover a xícara em l ; portanto, a sequência resultante será S _m , seguida por n - m + 1 relementos, que novamente é igual a S _{n +1} .

Em outras palavras, nosso método produz uma sequência ótima para a referida estrutura de entrada e, portanto, por indução, para qualquer estrutura de entrada.

Observe que isso não significa que essa implementação seja a mais eficiente. É definitivamente possível, por exemplo, calcular o número de xícaras que devem ser adicionadas ou removidas diretamente em cada ponto, em vez de realmente executar essas operações.

Singularidade

Podemos usar a otimização de nosso método para mostrar que as seqüências ótimas são, de fato, únicas (ou seja, que não existem duas seqüências ótimas distintas gerando a mesma estrutura). Usamos, novamente, a indução do tamanho da sequência geradora ideal: A sequência vazia é obviamente a única sequência geradora ideal da estrutura vazia. Suponha que todas as seqüências ótimas de geração de comprimento n sejam únicas e considere uma estrutura, Σ, gerada pelas duas seqüências ótimas S _{n +1} e T _{n +1} .

Lembre-se de que S _n e T _n são eles próprios ótimos e, portanto, por hipótese, únicos. Como nosso método produz seqüências ótimas, S _n e T _n podem ser considerados gerados por nosso método. Vamos l _S e L _T ser os locais modificados pela última operação em S _{n +1} e T _{n +1} , respectivamente, e suponho, sem perda de generalidade, que l _S segue, ou iguais, l _T em ordem de leitura. Como as estruturas geradas por S _ne T _n concordam em todos os locais na sequência l _S , em ordem, a sequência produzida pelo nosso método de ler, dado qualquer estrutura como entrada, uma vez que atinge l _S (mas antes do seu processamento), é o mesmo para ambos; chamar essa sequência U .

Como a última ação de S _{n +1} modifica l _S , se Σ tem um copo em l _S, então não deve haver nenhuma vaga antes de l _S , e se Σ não tem um copo em l _S, então não deve haver nenhum copo antes l _S , na ordem de leitura. Por isso, o resto do gerador de Σ sequência, seguindo L , deve ser constituído por aplicação repetida da mesma instrução, ditada pela presença ou ausência de um copo em L _S (ou então não seria óptimo). Em outras palavras, S _{n +1} e T _{n +1}são iguais (ambos começam com U e terminam com a referida sequência de instruções repetidas), ou seja, a sequência geradora ideal de Σ é única e, por indução, todas as sequências geradoras ideais são únicas.

Ell
fonte

Programar o robô de empilhar copos

O desafio

Casos de teste

Respostas:

Python 2, 64.515

Resultados

Explicação