Encontrando simetrias em quadrados

14

Escreva um programa ou função que inclua uma lista de números inteiros positivos. Cada um desses números inteiros representa o comprimento lateral de um quadrado em um plano 2D. Cada quadrado pode ser movido para quaisquer coordenadas inteiras no plano, mas não pode girar e não pode se sobrepor a outros quadrados.

Usando um caractere ASCII imprimível diferente para cada quadrado (excluindo o espaço usado para o vazio), seu programa / função precisa imprimir qualquer arranjo único dos quadrados que possua uma linha horizontal ou vertical de simetria reflexiva. Se não existir esse arranjo, nada deverá ser impresso.

Os quadrados são caracteres diferentes, apenas para que possam ser separados. Somente a forma feita pela união de todos os quadrados precisa ser simétrica. Você pode assumir que a lista não conterá mais de 94 elementos (pois existem 94 caracteres).

Por exemplo, se a entrada foi [2, 1, 2, 2, 2], uma saída possível é:

DD--
DD--
Z
FFPP
FFPP

Essa forma tem uma linha horizontal de simetria reflexiva; suas metades superior e inferior são imagens espelhadas. Aqui estão algumas outras possibilidades: (Observe que os quadrados não precisam ser tocados e que qualquer caractere pode ser usado, desde que não sejam feitos dois quadrados do mesmo caractere.)

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

     11 33
     11 33

    22   44
    22   44

A linha de simetria também pode ser o limite entre os caracteres, por exemplo, para [2, 4]:

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

Alguns conjuntos de quadrados são impossíveis de organizar simetricamente, por exemplo [1, 2, 3]:

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

E lembre-se de que a forma geral pode ser simétrica, mesmo que os limites quadrados não sejam. por exemplo, uma saída válida para [2, 1, 1, 1, 1, 4]é:

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

Da mesma forma, uma saída válida para [1, 1, 2, 3, 5]é:

44444
44444
44444
44444
44444
33301
33322
33322

Notas

  • A lista de entrada sempre terá de 1 a 94 elementos.
  • Tome entrada de qualquer maneira razoável: stdin, linha de comando, arquivo de texto, função arg. Pode ser ligeiramente formatado para atender às suas necessidades, por exemplo, {1, 2, 3, 4}ou [1 2 3 4].
  • Saída para stdout ou similar. Quaisquer quantidades de espaços à esquerda / à direita ou novas linhas são boas, desde que a forma resultante tenha a linha de simetria.
  • Uma linha diagonal de simetria não conta (caso contrário, isso seria super fácil). Além disso, tem que ser simetria reflexiva, não rotacional ou transitória.
  • Sinceramente, não tenho certeza do quão computacionalmente difícil essa tarefa é. Você pode postar respostas parciais que resolvem algum subconjunto do problema (especialmente se você quiser exibir um algoritmo particularmente inteligente). Estes não são elegíveis para ganhar.
    • Por exemplo, você pode supor que a entrada sempre tenha pelo menos um arranjo simétrico (portanto, listas como [1, 2, 3]nunca são inseridas).
    • Ou, por exemplo, você pode considerar apenas arranjos em que os limites quadrados, bem como a forma geral, são simétricos. Nesse caso, [1, 1, 2, 3, 5]não teria saída.
    • Se você quiser enlouquecer, pode estender a idéia para retângulos ou até poliaminos .

Pontuação

Sua pontuação é o tamanho do seu programa em bytes . A pontuação mais baixa vence. O desempatador segue a resposta postada primeiro.

Passatempos de Calvin
fonte
2
Pontos de bônus para resolver [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], embora, como a pergunta dê muito mais liberdade, provavelmente haja outras soluções.
Sp3000

Respostas:

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)

Apenas um pouco de golfe por enquanto, mas aqui está algo para começar. Tentei usar execpara as linhas 10 e 12, mas por algum motivo isso não me deixou.

Insira a lista Lvia STDIN, por exemplo [2, 1, 2, 2, 2]. O programa simplesmente tenta todas as possibilidades de colocar quadrados em uma sum(L) x sum(L)grade.

Saída de amostra (linhas em branco removidas para compactação):

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

Versão um pouco 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
fonte
@ Calvin'sHobbies Acabei de perceber que esqueci de remover linhas e colunas vazias (o que significaria que a configuração também teria que ser simétrica em relação ao quadro ). [1, 1, 2, 3, 5]agora corre bem.
Sp3000 17/03/2015
Ah Eu pensei que a força bruta estava demorando para sempre.
Hobbies de Calvin
@ Calvin'sHobbies É bom para pranchas maiores, mas colocar restrições adicionais só piora as coisas: P
Sp3000 17/15/15
Eu acho que você pode salvar alguns caracteres usando o truque de indentação .
Passatempos de Calvin