On Tue, 2005-06-28 at 12:11 +0300, Radu Grigore wrote:

On 6/27/05, Arjun Guha wrote:

...

It's the all-pairs shortest paths data for a map of the Hyde Park area of Chicago (no real reason, really).

I wonder: is there really no way to do Floyd-Warshall in Haskell?

Indeed I understand from a colleague who implemented an all-pairs shortest paths algorithm in Haskell over the weekend for a map of the Hyde Park area of Chicago (no real reason, really!), that it takes about 0.1 seconds to execute (if you compile with -O), which is well within the 5 second limit... I wonder why everyone is so interested in the distances between intersections in the Hyde Park area of Chicago all of a sudden... http://icfpc.plt-scheme.org/ Duncan

On Tue, 2005-06-28 at 20:13 -0400, Arjun Guha wrote:

As a self-taught Haskell programmer of about a year, I'm really interested in seeing your colleague's code. I'd like to know what I did wrong. How about after two weeks? I think that's reasonable!

I'm sure we'll publish our entry after the end of the second round, we did last year (http://urchin.earth.li/icfpcontest/2004/). However I would not expect it to be something beautiful to behold; code written in haste seldom is. In the meantime, try looking up the standard algorithms for all-pairs shortest paths. Duncan

On 6/29/05, Duncan Coutts wrote:

Indeed I understand from a colleague who implemented an all-pairs shortest paths algorithm in Haskell over the weekend for a map of the Hyde Park area of Chicago (no real reason, really!), that it takes about 0.1 seconds to execute (if you compile with -O), which is well within the 5 second limit...

Well, that is about two times slower than c++ code :p ... I mean: it's way faster that what I would have expected :) Anyway, I am interested in how DP-like algorithms are implemented in Haskell (with the same complexities), not in this particular problem. A week ago I tried LCS, now the ICFP contest fed me with another algorithm that isn't trivial to implement in this language. For ICFPC you could use some other solution than Floyd-Warshall but, again, I am asking about _this_ particular algorithm.

I wonder why everyone is so interested in the distances between intersections in the Hyde Park area of Chicago all of a sudden...

You are right: I'll ask again in 2 weeks. So please don't answer to this post :) -- regards, radu http://rgrig.blogspot.com/