fundo

Esta é uma continuação do meu desafio anterior , em que a tarefa era calcular a forma de uma escultura obtida pela queda de ímãs em uma pilha enorme.

Boas notícias: o artista excêntrico gostou do seu trabalho e tem outro projeto para você. Ele ainda trabalha com esculturas magnéticas, mas decidiu expandir seu estúdio de arte - para o espaço ! Seu método atual é lançar um único ímã em forma de cubo na órbita e disparar outros ímãs para criar um enorme satélite magnético.

Entrada

Sua entrada é uma lista finita de 0s e1 s, fornecida no formato de lista nativa do seu idioma ou em uma string. É interpretado como um "modelo" de uma obra de arte e é processado da esquerda para a direita, da seguinte maneira.

Você começa com um único ímã flutuando em alguma coordenada inteira do plano 2D e continua adicionando mais ímãs conforme as diretivas. A diretiva 0gira a escultura inteira 90 graus no sentido anti-horário. No caso da diretiva 1, o artista encontra a coluna mais à esquerda da escultura e lança um novo ímã por baixo. O novo ímã adere ao ímã mais baixo existente na coluna e se torna parte da escultura. Observe que o ímã não adere a outros ímãs na coluna vizinha, ao contrário do desafio anterior; sua velocidade agora é astronômica!

Resultado

O artista quer saber se a escultura completa caberá em sua garagem (como ele será retirado da órbita ainda não está claro). Assim, sua saída é a largura e a altura da escultura, ordenadas de menor para maior. Eles podem ser fornecidos como uma lista de dois elementos, um par ou como uma sequência separada por vírgula.

Exemplo

Considere a sequência de entrada

[1,0,1,1,0,1,0,0,1,1]

Para processá-lo, começamos com um ímã flutuando no espaço:

#

A primeira diretiva é 1, então filmamos um novo ímã a partir de baixo:

#
#

A próxima diretiva é 0, então giramos a escultura:

##

As próximas duas diretrizes são 1,1, o que significa que atiraremos dois ímãs na coluna mais à esquerda:

##
#
#

Em seguida, giramos novamente e disparamos uma vez, conforme indicado por 0,1:

#
###
#

Finalmente, giramos duas vezes e filmamos duas vezes:

  #
###
# #
#

A escultura resultante tem largura 3e altura 4, então produzimos [3,4].

Regras

Você pode atribuir uma função ou um programa completo. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

[1,0,1] -> [2,2]
[1,0,1,1,0,1,0,0,1,1] -> [3,4]
[1,1,0,1,1,0,1,0,1,1] -> [4,5]
[1,1,0,1,1,0,1,0,1,1,0] -> [4,5]
[1,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1] -> [3,3]
[0,1,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,1] -> [5,7]
[1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,0,1,0,1,1,0,0,0,1,0,1,1,0,0,1,0,1,1,0] -> [11,12]

Pitão : 34 33 bytes

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ

Entrada é uma lista de uns e zeros, como na pergunta. Experimente online: Pyth Compiler / Executor

Explicação:

É uma tradução individual dos seguintes código Python 2 ( 126 bytes ).

print sorted(map(len,map(set,zip(*reduce(lambda s,i:([[-b,a]for a,b in s],s+[[min(s)[0],min(s)[1]-1]])[i],input(),[[0,0]])))))

Eu crio uma lista de coordenadas dos ímãs únicos. Isso é inicializado com o ímã [0,0]. Então, para cada um dos números inteiros do blueprint, manipulo a lista da seguinte maneira. Se o próximo número inteiro for 0, eu giro a escultura alterando as coordenadas de cada ímã[a,b] para [-b,a](basicamente multiplicando por uma matriz de rotação). Se o próximo número inteiro for a 1, procuro a peça mínima [a,b](que é automaticamente o ímã mais baixo da coluna mais à esquerda) e anexo o ímã [a,b-1]à lista.

Depois que toda a entrada é processada, crio 2 conjuntos (para remover duplicatas), um para os valores x e outro para os valores y, e imprimo os tamanhos deles na ordem de classificação.

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
                             ],ZZ  starting list G=[(0,0)]
      u                     Q],ZZ  for H in input(): manipulate G
       S                              Sort G after each manipulation
        ?          H                  G = ... if H==1 else ...
                    m,_ekhkG            [(-b,a) for a,b in G)] (rotate)
         +G,hhGtehG                     G+[(G[0][0],G[0][1]-1)]
                                        (G[0] is the lowest magnet in the leftmost column)
     C                             Zip the coords together
                                    (creates 2 lists, x- and y-coords)
 ml{d                              for each of those list compute number of unique values
S                                  sort and print

Uma idéia para aperfeiçoar : Usar números complexos como cordas para os ímãs. Uma rotação é apenas uma multiplicação je subtração jdo ímã mais baixo na coluna mais à esquerda. Infelizmente, encontrar esse ímã mais baixo à esquerda exige muitos caracteres em Python, nem mesmo falar em encontrar o retângulo.

CJam, 48 bytes

S]l~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

Teste aqui.

Espera entrada como uma matriz no estilo CJam (ou seja, espaços em vez de vírgulas) e apresentará a saída da mesma forma. Se você deseja usar os casos de teste da pergunta diretamente, copie-os diretamente para o campo de entrada (inclua os ->resultados e) e use este equipamento de teste, que converte as linhas no formato de entrada correto (e descarta os resultados):

qN/{S/0=","Ser}%{[

S]\~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

}/

Explicação

Estou apenas implementando as regras literalmente. Estou mantendo uma grade com a escultura atual (como uma matriz de seqüências de caracteres) e, em seguida, para cada instrução eu giro a grade ou adiciono um novo bloco. Os principais truques para salvar bytes são:

• Adicione à linha inferior da direita . Isto é completamente equivalente. Estou apenas uma rotação à frente e, como a grade começa rotativamente invariável, isso não importa.
• Use um espaço para representar blocos ocupados e um caractere de nova linha para representar blocos vazios. Portanto, se você realmente imprimisse a grade, não veria muito e nem pareceria retangular. Estou fazendo isso, porque a maioria dos operadores baseados em matriz só faz o que você deseja se o elemento de grade em questão estiver agrupado em uma matriz. E com Se Neu tenho acesso a strings contendo o espaço e o caractere de nova linha (ou seja, o caractere envolvido em uma matriz), em vez de ter que usar, digamos, 1ae 0aobter uma matriz contendo um número.

Vamos analisar o código:

"Overall program structure:";
S]l~{{...}{...}?}/_,\z,]$p
S]                         "Push a string with a space and wrap it in an array.
                            This is the initial grid containing a single block.";
  l~                       "Read the input and evaluate it.";
    {           }/         "For each instruction in the input...";
     {...}{...}?           "Execute the first block if it's 1, the second if it's 0.";
                  _,       "Duplicate the resulting grid and get its length. This
                            is one of the dimensions.";
                    \      "Swap with the other copy of the grid.";
                     z,    "Zip/transpose it and get its length. This is the other
                            dimension of the grid.";
                       ]$p "Wrap both in an array, sort them, and print the result.";

"The rotation block is simple. A rotation is equivalent to two reflection operations
 along different axes. The simplest ones available are to transpose the grid (which
 is a reflection about the diagonal) and reversing the rows (which is a reflection
 about the horizontal). In CJam these are z for zip/tranpose and W% for reversing
 an array. So I simply put these together in the right order to get a counter-
 clockwise rotation:";
zW%

"Now the interesting part, adding new blocks and growing the grid. This part consists
 of two steps: appending a block to the rightmost block in the bottom row (allowing
 for empty blocks after it). And then potentially padding the rest of the grid with
 new empty cells if the bottom row got longer.";
)S/);Sa+S*a+_z,f{_N*@\+<}
)                         "Split off the bottom row.";
 S/                       "Split the row on occupied blocks.";
   );                     "Split off the final substring - this discards trailing
                           empty cells.";
     Sa+                  "Add a new substring containing an occupied block to the row.";
        S*                "Join all substrings together with spaces, putting back in
                           all the occupied blocks.";
          a+              "Wrap it in an array to add the row back onto the grid.";

 "At this point we need to make sure the grid is still rectangular. The easiest way
  (I found) is to find the maximum row length, add that many empty blocks to each 
  line and then truncate the lines to that length.";

            _             "Duplicate the grid.";
             z,           "Zip/transpose it and get the length. This is the length
                           of the longest row in a ragged array.";
               f{       } "Map this block onto each row, passing in the target length.";
                 _N*      "Duplicate the target length and get a string of that many
                           empty cells.";
                    @\    "Pull up the row and then swap it with those empty cells.";
                      +   "Add the empty cells to the end of the row.";
                       <  "Truncate to the target length.";

Matlab (92)

S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))

Entrada padrão é usada. Os dados devem ser introduzidos no formulário [1,0,1,1,0,1,0,0,1,1].

Ungolfed:

S = 1; %// initial magnet
for d = input('') %// get directives, and pick them sequentially
    if d %// if directive is 1
        S(find(S(:,1),1,'last')+1,1) = 1; %// add 1 after lowest 1 in column 1. Grow if needed
    else %// if directive is 0
        S = rot90(S); %// rotate counterclockwise. Handy Matlab built-in function
    end
end
sort(size(S)) %// display size sorted

Exemplo de execução:

>> clear all
>> S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))
[1,0,1,1,0,1,0,0,1,1]
ans =
     3     4

Python - 211

import numpy as n
p=input()
q=len(p)
a=n.zeros([2*q+1]*2)
a[q,q]=1
for i in p:
 if i:x=a[:,n.where(a.any(0))[0][0]];x[len(x)-n.where(x[::-1])[0][0]+1]=1
 else:a=n.rot90(a)
z=a[:,a.any(1)]
print z[a.any(0)].shape

CJam, 47 bytes

1]]q~{{0f+(W%_1#(1tW%a\+z{1b},}{W%}?z}/),\,)]$p

Isso recebe a entrada de matriz com estilo CJam (espaço separado em vez de vírgula) de STDIN e imprime o resultado em STDOUT.

Exemplo:

[1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1]

dá

[3 3]

resultado.

Explicações a seguir depois que estou convencido de que isso não pode ser jogado mais.

Experimente online aqui