Gave it a brief thought. What I see is a TSP on a grid graph. Maybe I missed some detail. Do you see a better idea?
Re:Quora - Programming Challenges
by andrewcooke on Friday March 05, 2010 @12:17PM
(#1169857)
yes, i think that's a valid way of looking at it - the grid adds some extra properties to a general graph which you might be able to exploit to get better efficiency.
[but i don't really want to spoil things for quora by discussing a solution here, i was more interested in swapping final results so that people could check they have the right answer]
ps i believe my solution is ok, now, after checking it at lunch time, but it's a little slower than theirs, which is making me think i have missed something.
and if anyone is thinking of trying, i'd recommend it - it's not a huge amount of code and requires at least one smart idea (i think - had me bashing my head against a wall for a while...).
[if anyone wants to compare results - just the final number, no spoilers please - then drop me an email]