In the previous article I mentioned how I found very hard to find a solution to the Graham Scan problem of “Real world Haskell” chapter 3. You will find a solution attached that actually seems to work. So, without further ado, here is my solution. It is really crude, and could probably be written in a much cleaner way. When compiled, it expects to get a list of points, one per line, represented as tab separated coordinates.
My solution is really crude, and could use a lot of polish. It should also be noted that it is very slow. However, here is how it performs compared “the Internet solution” :
For a a million points, here is the performance of the scan :
$ time ./mysolution < points.dat > solution1.dat real 10m32.346s user 10m28.670s sys 0m2.320s
This is really bad, and it doesn’t behave at all like O(n log n), which was to be expected due to the fact that I don’t know how to backtrack properly. But what’s even more funny is that the Internet solution behaves way worse, which means I did not analyze its complexity properly.