Encontrar simetrías en cuadrados

14

Escriba un programa o función que tome una lista de enteros positivos. Cada uno de estos enteros representa la longitud lateral de un cuadrado en un plano 2D. Cada cuadrado se puede mover a cualquier coordenada entera en el plano, pero no puede rotar y no puede solaparse con otros cuadrados.

Usando un carácter ASCII imprimible diferente para cada cuadrado (excluyendo el espacio que se usa para el vacío) su programa / función necesita imprimir cualquier disposición individual de los cuadrados que tenga una línea de simetría de reflexión horizontal o vertical. Si no existe tal disposición, no se debe imprimir nada.

Los cuadrados son caracteres diferentes solo para poder distinguirlos. Solo la forma hecha por la unión de todos los cuadrados debe ser simétrica. Puede suponer que la lista no contendrá más de 94 elementos (ya que hay 94 caracteres).

Por ejemplo, si la entrada fue [2, 1, 2, 2, 2], una salida posible es:

DD--
DD--
Z
FFPP
FFPP

Esta forma tiene una línea horizontal de simetría reflexiva; Sus mitades superior e inferior son imágenes especulares. Aquí hay algunas otras posibilidades: (Tenga en cuenta que los cuadrados no necesitan tocarse y que se pueden usar los caracteres siempre que no haya dos cuadrados del mismo carácter).

  55
  55
  %%
  %%
@
  HH
  HH
  ((
  ((
       G

     11 33
     11 33

    22   44
    22   44

La línea de simetría también podría ser el límite entre caracteres, por ejemplo, para [2, 4]:

!!!!
!!!!  ++
!!!!  ++
!!!!

Algunos conjuntos de cuadrados son imposibles de organizar simétricamente, por ejemplo [1, 2, 3]:

AAA BB C
AAA BB         (these can't be vertically or horizontally symmetric => no output)
AAA

Y recuerde que la forma general puede ser simétrica incluso si los límites cuadrados no lo son. por ejemplo, una salida válida para [2, 1, 1, 1, 1, 4]es:

AA----
AA----
BC----
DE----

Del mismo modo, una salida válida para [1, 1, 2, 3, 5]es:

44444
44444
44444
44444
44444
33301
33322
33322

Notas

  • La lista de entrada siempre tendrá de 1 a 94 elementos.
  • Tome la entrada de cualquier manera razonable: stdin, línea de comando, archivo de texto, función arg. Se puede formatear ligeramente para satisfacer sus necesidades, por ejemplo, {1, 2, 3, 4}o [1 2 3 4].
  • Salida a stdout o similar. Cualquier cantidad de espacios iniciales / finales o nuevas líneas está bien siempre que la forma resultante tenga la línea de simetría.
  • Una línea diagonal de simetría no cuenta (de lo contrario, esto sería muy fácil). Además, tiene que ser simetría de reflexión, no rotacional o de transición.
  • Sinceramente, no estoy seguro de cuán difícil es esta tarea computacionalmente. Puede publicar respuestas parciales que resuelvan algún subconjunto del problema (especialmente si desea mostrar un algoritmo particularmente inteligente). Estos no son elegibles para ganar.
    • Por ejemplo, puede suponer que la entrada siempre tiene al menos una disposición simétrica (por lo que las listas como [1, 2, 3]nunca se ingresan).
    • O, por ejemplo, solo puede considerar arreglos donde los límites cuadrados, así como la forma general, sean simétricos. En este caso, [1, 1, 2, 3, 5]no tendría salida.
    • Si quieres volverte loco, puedes extender la idea a rectángulos o incluso a poliominós .

Puntuación

Su puntaje es el tamaño de su programa en bytes . El puntaje más bajo gana. Tiebreaker va la respuesta publicada primero.

Pasatiempos de Calvin
fuente
2
Puntos de bonificación por resolver [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], aunque dado que la pregunta da mucha más libertad, probablemente haya otras soluciones.
Sp3000

Respuestas:

4

Python 2, 460 452 437 bytes

exec"""def f(L):
 if[]==L:
  X{2}[map(" ".__lt__,q)for q in G]);Z{2}zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x)
 for n in range(T*T):
  i=n%T;j=n/T
  if all({1}=" "{0}):
{0}:{1}chr(32+len(L))
   r=f(L[:-1])
{0}:{1}" "
   if r:return r""".format("   for a,b in[(a,b)for a in R for b in R]","G[i+a][j+b]=","=filter(sum,")
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

Solo un poco de golf por ahora, pero aquí hay algo para comenzar las cosas. Intenté usar execpara las líneas 10 y 12, pero por alguna razón no me lo permitió.

Ingrese la lista a Ltravés de STDIN, por ejemplo [2, 1, 2, 2, 2]. El programa simplemente prueba todas las posibilidades de colocar cuadrados en una sum(L) x sum(L)cuadrícula.

Salida de muestra (líneas en blanco eliminadas para compacidad):

[2, 1, 2, 2, 2]

%%       
%%       
$$       
$$       
"        
##       
##       
!!       
!!      

[2, 4]

""""  
""""  
""""  
""""  
 !!   
 !!   

[2, 1, 1, 1]

$!!  
#!!  
 "   

[1, 1, 2, 3, 5]

%%%%%       
%%%%%       
%%%%%       
%%%%%       
%%%%%       
$$$##       
$$$##       
$$$"!       

[1, 4, 1, 8]

$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
$$$$$$$$      
# """" !      
  """"        
  """"        
  """"        

[8, 1, 4, 1]

$   !!!!!!!!  
    !!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
####!!!!!!!!  
    !!!!!!!!  
"   !!!!!!!!  

(The algorithm starts placing from the last square first, prioritising left then up)

Versión ligeramente menos confusa (452 ​​bytes):

def f(L):
 if[]==L:
  X=filter(sum,[map(" ".__lt__,q)for q in G]);Z=filter(sum,zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x);V=[(a,b)for a in R for b in R]
 for n in range(T*T):
  i=n%T;j=n/T
  if all(G[i+a][j+b]<"!"for a,b in V):
   for a,b in V:G[i+a][j+b]=chr(32+len(L))
   r=f(L[:-1])
   for a,b in V:G[i+a][j+b]=" "
   if r:return r
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)
Sp3000
fuente
@Hobbies de Calvin Me acabo de dar cuenta de que olvidé quitar las filas y columnas vacías (lo que habría significado que la configuración también tuviera que ser simétrica con respecto al tablero ). [1, 1, 2, 3, 5]Ahora corre bien.
Sp3000
Ah Pensé que la fuerza bruta solo tardaba una eternidad.
Calvin's Hobbies
@ Calvin'sHobbies Lo hace para tableros más grandes, pero poner restricciones adicionales solo empeora: P
Sp3000
Creo que puedes guardar algunos caracteres usando el truco de sangría .
Calvin's Hobbies