Solve a Tetris Puzzle (pack predefined shapes into optimal form)
Java - Theoretically Optimal Solution

I needed one of these anyway, so...

Code is viewable here.

The routine should theoretically produce an optimal solution for any input. It typically runs on the order of milliseconds or seconds for &lt; 100 shapes, and the complexity appears to be roughly O(n log2 n) for random inputs. Packing hundreds or even thousands of random shapes should complete in a reasonable amount of time.

The worst case performance grows as O(nn ww), where n is the number of shapes to pack and w is the packing width. Thus this program earns the dubious distinction of having the worst worst case performance of any (non-busy-beaver) algorithm I've ever programmed. :P

Sample I/O

java TetPack 10 J T Z I I J Z O O J T S S O I

IIIIJOOTTT
IIIIJOOSTI
OOSJJZTSSI
OOSSZZTTSI
OOJSZJTZZI
OOJJJJJJZZ

Displayed solution is optimal.

java TetPack 3 T

XTX
TTT

9 J S I O S T T I I I S

XIIIIIIII
TTTSSIIII
TTSSJJJOO
TTSSSSJOO
TSSSSIIII

java TetPack 15 L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J

JJJJLLLLJLJJJJJ
JJJJLLJJJLJJJJJ
LLLLLLJJJLLLJJJ
LLLLLLJJLLLLJJJ
LLLLJJJJLLJLLLL
LLLLJJJJJLJJJLL
LLJJJJJJJLLLLLL
LLJJJJJJJLLLLLL
LLJJJJJLJLLLLLL
JJJJJJLLJJJLJLL
JJJJJJLLLLLLJLL
JJJJJLLLJJLJJLL
LLLJJLLLJJLJJJJ
LLLLLLLLJJLLLJJ
JLLLLLJLJJLLJJJ
JJJLLLJJJLLLJJJ

Displayed solution is optimal.

java TetPack 4 Z T

XZXX
ZZTX
ZTTT

java TetPack 30 J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I

XXIIIIIIIIIIIIIIIIIIIIIIIIIIII
LIIIILIIIILIIIILIIIIJLIIIIJLOO
LIIIILJJJLLIIIILLLJJJLIIIIJLOO
LLJLJLLIJLLLZLJLLLJJJLLZZJJLLI
JJJLJJJILLLZZLJJJLJZZLLIZZZOOI
JJJLLILILZZZJLLSSOOIZZLILZZOOI
JJJJJILILLZZJSSSZOOIOOLILZTLLI
IJJJJILLSSZJJSSZZOOIOOTILLTTLI
IJJJJILSSZZSSZSZTOOIITTTOOTSLI
IJJJJLLZZZSSZZTTTTOOIIJJOOLSSI
ISSZILLLZZOOZTTTTJOOIIJLLLLTSI
SSZZILLOOJOOTZZTTJJJIIJLZZTTOO
LSZLIZZOOJJJTTZZTIIIIIJLLZZTOO
LSSLIJZZOOOOTSSSSSSTZZJJJLIIII
LLSLLJJJOOOOSSSSSSTTTZZLLLIIII