Finding Symmetries in Squares

Question

Write a program or function that takes in a list of positive integers. Each of these integers represents the side length of a square on a 2D plane. Each square can be moved to any integer coordinates in the plane, but it can't rotate and it can't overlap other squares.

Using a different printable ASCII character for each square (excluding space which is used for emptiness) your program/function needs to print any single arrangement of the squares that has a horizontal or vertical line of reflectional symmetry. If no such arrangement exists then nothing should be printed.

The squares are different characters just so they can be told apart. Only the shape made by the union of all the squares needs to be symmetrical. You can assume the list will not contain more than 94 elements (as there are 94 characters).

For example, if the input was [2, 1, 2, 2, 2], a possible output is:

DD--
DD--
Z
FFPP
FFPP

This shape has a horizontal line of reflectional symmetry; its top and bottom halves are mirror images. Here are some other possibilities: (Note that the squares don't need to touch and any characters can be used as long as no two squares are made of the same character.)

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

       G

     11 33
     11 33

    22   44
    22   44

The line of symmetry could also be the boundary between characters, e.g. for [2, 4]:

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

Some sets of squares are impossible to arrange symmetrically, e.g. [1, 2, 3]:

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

And remember that the overall shape may be symmetric even if the square boundaries aren't. e.g. a valid output for [2, 1, 1, 1, 1, 4] is:

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

Similarly, a valid output for [1, 1, 2, 3, 5] is:

44444
44444
44444
44444
44444
33301
33322
33322

Notes

• The input list will always have from 1 to 94 elements.
• Take input in any reasonable way: stdin, command line, text file, function arg. It can be slightly formatted to suit your needs, e.g. {1, 2, 3, 4} or [1 2 3 4].
• Output to stdout or similar. Any amounts of leading/trailing spaces or newlines are fine as long as the resulting shape has the line of symmetry.
• A diagonal line of symmetry does not count (else this would be super easy). Also, it has to be reflectional symmetry, not rotational or transitional.
• I'm honestly not sure how computationally difficult this task is. You may post partial answers that solve some subset of the problem (especially if you want to show off a particularly clever algorithm). These are not eligible to win.
  • For example, you might assume that the input always has at least one symmetrical arrangement (so lists like [1, 2, 3] are never input).
  • Or, for example, you may only consider arrangements where the square boundaries, as well as the overall shape, are symmetrical. In this case, [1, 1, 2, 3, 5] would have no output.
  • If you want to go crazy, you could extend the idea to rectangles or even polyominoes.

Scoring

Your score is the size of your program in bytes. The lowest score wins. Tiebreaker goes the the answer posted first.

Answer 1

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)

Only mildly golfed for now, but here's something to get things started. I tried using exec for lines 10 and 12, but for some reason it didn't let me.

Input the list L via STDIN, e.g. [2, 1, 2, 2, 2]. The program simply tries every possibility of placing squares in a sum(L) x sum(L) grid.

Sample output (blank lines removed for compactness):

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

---

Slightly less confusing version (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)