Intermediate Solutions

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

 I have been thinking for a while about a strategy that I call "The Intermediate Step".  The above link illustrates an example of the idea. By arranging the data in a different way that emphasised a property that was useful for the final solution, they found an efficient way to return a result from what is essentially a list searching problem.

Basically, for problems with no obvious solution, I find its often useful to look for ways to re-state the problem elements before being able to "see" a solution.   This may be (as above) organising the data into a structure that emphasises particular properties of the data that were either in-obvious or poorly structured in the initial presentation of the problem.

These "intermediate" steps are often of no immediate value for solving the problem, but help to explore the problem space.  Sometimes simply by re-stating the problem elements, you can jump to a single step solution, but usually, one or more of these intermediate steps can be composed to form the final solution.

The basic tools that I see recurring for this sort of exercise are:

* Sorting
* Partitioning and Grouping
* Meta data and Indexing (decorating)
* Deriving and Summarizing (reducing)
* Mapping, Translating and Transforming
* Adding edge case data ( Extreme data values, nulls, etc)
* Relating data (Identify implicit relationships, structures or sequences)

By playing with the properties of the data, especially implicit properties, and looking for different ways to re-state the data without damaging it, one of the variants will usually present a much simpler path to a final solution.

Does this mean that "hardness" of a problem may be related to arrangement of data? (I would suggest that this is often the case in the data sets I work with)

I would suggest that any problem where I cannot re-state the data set in a couple of different ways is one that I just do not understand well enough to play with.

Lets see how many seconds before I think up enough examples to undermine this whole post completely.....