CareerCup

Good question. Not sure what they would be looking for, apart from some heuristics and backtracking etc.

There are sets of geometrical forms for which the problem is NP-complete (easy reduction from tiling a square with Wang tiles). So if you have an efficient algorithm (polynomial time) for the question, you don't need the job :-)

I'd start with some greedy algorithm that basically simulates the decisions that a human Tetris player makes. Just iterate through the shapes, and drop them to the lowest level possible. Orient each shape so that it's longest side is on the bottom, then find the lowest level that provides a long enough platform for the whole bottom to sit on top.

Adding T-shapes and L-shapes to the mix creates the necessity of having handling "holes" and plugging holes. When you encounter a T-shape or L-shape, look for a way that it can snugly fill a hole; otherwise, push it to the end of the queue.

Consider shapes that fit nicely together. Two troublesome Ls can be joined together to make a rectangle. You can preprocess your list in advance to try to pair up Ls.

Eventually, you'll want some kind of backtracking scheme. You provisionally place a piece, but maybe subsequent pieces can't plug the holes it creates. If so, roll back and try another piece.

Definitely not a trivial problem.

One metaphor for this problem is that you have a mating game. You have a bunch of piece that want to mate. When two pieces mate, they create a child, and the parents die off. All pieces--single and combined--have a "survival fitness" tied to them. A piece's fitness is a measure of how well it mates with other pieces to form other nice shapes. At any stage of the mating game, you're trying to first mate off pieces with the lowest survival probability, so that you can kill them off and let their children prosper.

Before the game even starts, you can do some analysis on piece types, including small compound pieces, to create a compatibility graph, where the nodes are piece types, and the weight of the edges to other piece types indicates some sort of inclination for ideal mating.

A greedy algorithm would start with the most troublesome piece, and then iterate through the compatibility graph to find types to mate to, checking the actual bag of pieces to find out if there available mates for that type. Then marry the pieces, create the child, and kill the parents.