Esculturas magnéticas ... en el espacio!

8

Antecedentes

Esta es una continuación de mi desafío anterior , donde la tarea era calcular la forma de una escultura obtenida colocando imanes en una enorme pila.

Buenas noticias: al artista excéntrico le gustó tu trabajo y tiene otro proyecto para ti. Todavía trabaja con esculturas magnéticas, pero ha decidido expandir su estudio de arte al espacio . Su método actual es disparar un solo imán en forma de cubo en la órbita y dispararle a otros imanes para crear un enorme satélite magnético.

Entrada

Su entrada es una lista finita de 0sys 1, dada en el formato de lista nativa de su idioma, o una cadena. Se interpreta como un "plano" de una obra de arte, y se procesa de izquierda a derecha de la siguiente manera.

Comienza con un solo imán flotando en alguna coordenada entera del plano 2D, y sigue agregando más imanes según las directivas. La directiva 0gira toda la escultura 90 grados en sentido antihorario. En el caso de la directiva 1, el artista encuentra la columna más a la izquierda de la escultura y le dispara un nuevo imán desde abajo. El nuevo imán se adhiere al imán más inferior existente en la columna y se convierte en parte de la escultura. Tenga en cuenta que el imán no se adhiere a otros imanes en la columna vecina, a diferencia del desafío anterior; ¡su velocidad ahora es astronómica!

Salida

El artista quiere saber si la escultura completa cabe en su garaje (no está claro cómo la bajará de la órbita). Por lo tanto, su salida es el ancho y la altura de la escultura, ordenada de menor a mayor. Se pueden dar como una lista de dos elementos, un par o como una cadena separada por una coma.

Ejemplo

Considere la secuencia de entrada

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

Para procesarlo, comenzamos con un imán flotando en el espacio:

#

La primera directiva es 1, así que disparamos un nuevo imán desde abajo:

#
#

La siguiente directiva es 0, así que rotamos la escultura:

##

Las siguientes dos directivas son 1,1, lo que significa que dispararemos dos imanes a la columna más a la izquierda:

##
#
#

Luego, giramos nuevamente y disparamos una vez, como lo indica 0,1:

#
###
#

Finalmente, giramos dos veces y disparamos dos veces:

  #
###
# #
#

La escultura resultante tiene ancho 3y alto 4, por lo que sacamos [3,4].

Reglas

Puede dar una función o un programa completo. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

[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]
Zgarb
fuente
¿No debería [1,1,0,1,1,0,1,0,1,1,0]volver [5,4]y no [4,5]? La escultura se gira al final.
algorithmshark
@algorithmshark Cometí el mismo error. La sección Salida especifica que se debe ordenar el resultado.
Martin Ender
1
@ MartinBüttner tiene razón. La justificación es que la orientación no importa cuando estás en el espacio . : P
Zgarb

Respuestas:

8

Pyth : 34 33 bytes

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

La entrada es una lista de unos y ceros, como en la pregunta. Pruébelo en línea: Pyth Compiler / Executor

Explicación:

Es una traducción uno a uno del siguiente código de 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]])))))

Creo una lista de coordenadas de los imanes individuales. Esto se inicializa con el imán [0,0]. Luego, para cada uno de los enteros del plano, manipulo la lista de la siguiente manera. Si el siguiente número entero es 0, puedo rotar la escultura cambiando las coordenadas para cada imán [a,b]a [-b,a](básicamente multiplicando con una matriz de rotación). Si el siguiente entero es un 1, busco la pieza mínima [a,b](que es automáticamente el imán más bajo de la columna más a la izquierda) y agrego el imán [a,b-1]a la lista.

Después de procesar toda la entrada, creo 2 conjuntos (para eliminar duplicados), uno para los valores xy otro para los valores y, e imprimo los tamaños de ellos en orden ordenado.

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

Una idea para mejorar : usar números complejos como coordenadas para los imanes. Una rotación es solo una multiplicación jy resta jdel imán más bajo en la columna más a la izquierda. Lamentablemente, encontrar este imán más bajo a la izquierda requiere demasiados caracteres en Python, ni siquiera hablar de encontrar el rectángulo.

Jakube
fuente
7

CJam, 48 bytes

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

Pruébalo aquí.

Espera la entrada como una matriz de estilo CJam (es decir, espacios en lugar de comas) y presentará la salida de manera similar. Si desea utilizar los casos de prueba de la pregunta directamente, cópielos directamente en el campo de entrada (incluya los ->resultados y) y use este arnés de prueba, que convierte las líneas al formato de entrada correcto (y descarta los resultados):

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

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

}/

Explicación

Solo estoy implementando las reglas muy literalmente. Mantengo una cuadrícula con la escultura actual (como un conjunto de cadenas), y luego, para cada instrucción, giro la cuadrícula o agrego un nuevo bloque. Los principales trucos para guardar bytes son:

  • Agregue a la fila inferior desde la derecha . Esto es completamente equivalente. Solo tengo una rotación por delante, y dado que la cuadrícula comienza rotacionalmente invariante, eso no importa.
  • Use un espacio para representar bloques ocupados y un carácter de nueva línea para representar bloques vacíos. Entonces, si realmente imprimiste la cuadrícula, no verías mucho y ni siquiera se vería rectangular. Estoy haciendo esto, porque la mayoría de los operadores basados ​​en matrices solo hacen lo que quieres si el elemento de la cuadrícula en cuestión está envuelto en una matriz. Y con Sy Ntengo acceso a cadenas que contienen el espacio y el carácter de nueva línea (es decir, el carácter envuelto en una matriz), en lugar de tener que usar, por ejemplo, 1ay 0aobtener una matriz que contenga un número.

Veamos el 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.";
Martin Ender
fuente
No tengo idea de cómo funciona, ¡pero lo hace!
Luis Mendo
@LuisMendo Se agregó una explicación. Si algo no está claro y le interesa, no dude en enviarme otro comentario. ;)
Martin Ender
No tengo idea sobre CJam, y no parece ser un lenguaje fácil precisamente. Ya tenías mi +1 :-)
Luis Mendo
4

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

Se utiliza la entrada estándar. Los datos deben introducirse en el formulario [1,0,1,1,0,1,0,0,1,1].

Sin golf:

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

Ejemplo de ejecución:

>> 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
Luis Mendo
fuente
1

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
KSFT
fuente
¡La salida se debe ordenar de menor a mayor! También su programa se rompe para la entrada [1].
Jakube
0

CJam, 47 bytes

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

Esto toma la entrada de matriz con estilo CJam (espacio separado en lugar de coma) de STDIN e imprime el resultado en STDOUT.

Ejemplo:

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

da

[3 3]

salida.

Explicación a seguir después de que estoy convencido de que esto no se puede jugar más.

Pruébalo en línea aquí

Optimizador
fuente