I do not know how to describe the goal succinctly, which may be why I haven't been able to find an applicable algorithm despite ample searching, but a picture shows it clearly:

![Interlocking items](https://i.stack.imgur.com/TEsAD.png)

**Given the state of items in the grid at the left, does anyone know of an algorithm for efficiently finding the ending positions shown in the grid at right?** In this case all the items have "fallen" "down", but the direction of course is arbitrary. The point is just that:

* There are a collection of items of arbitrary shapes, but all composed of contiguous squares
* Items cannot overlap
* All items should move the maximum distance in a given direction until they are touching a wall, or they are touching another item which [...is touching another item ad infinitum...] is touching a wall.

This is not homework, I'm not a student. This is for my own interest in geometry and programming. I haven't mentioned the language because it doesn't matter. I can implement whatever algorithm in the language I'm using for the specific project I'm working on. A useful answer could be described in words or code; it's the ideas that matter.

This problem could probably be abstracted into some kind of graph (in the mathematical sense) of dependencies and slack space, so perhaps an algorithm aimed at minimizing lag time could be adapted.

If you don't know the answer but are about to try to make up an algorithm on the spot, just remember that there can be circular dependencies, such as with the interlocking pink (backwards) "C" and blue "T" shapes. Parts of T are below C, and parts of C are below T. This would be even more tricky if interlocking items were locked through a "loop" of several pieces. 

Some notes for an applicable algorithm: All the following are very easy and fast to do because of the way I've built the grid object management framework:

* Enumerate the individual squares within a piece
* Enumerate all pieces
* Find the piece, if any, occupying a specific square in the overall grid

**A note on the answer:**
maniek hinted it first, but bloops has provided a brilliant explanation. I think the absolute key is the insight that all pieces moving the same amount maintain their relationship to each other, and therefore *those relationships don't have to be considered*. 

An additional speed-up for a sparsely populated board would be to shift all pieces to eliminate rows that are completely empty. It is very easy to count empty rows and to identify pieces on one side ("above") an empty row. 

**Last note:** I did in fact implement the algorithm described by bloops, with a few implementation-specific modifications. It works beautifully.