I was recently asked to solve this problem in the programming language of my choice. Naturally, I chose Ruby. Although I only arrived at a partial solution ( details are available here), I came pretty close for 90% of use cases.
Let me know what you think, and feel free to fork the Source code on Github..