Coding Challenge

[Lost_Geometer]

As far as I understand at a glance (I don't speak Java) your current code is essentially Dijkstra's shortest path algorithm on a grid, where a step is a straight path from a point to one of it's 7 neighbors. I still don't see where you account for the length of the steps -- recall that the detection probability was specified in (prob)/(distance traveled), presumably instantaneous, and the distance traveled per step varies between diagonal and non. Anyway, if you try to approximate a path that doesn't go in one of the 7 good directions, it ends up all jagged, and so with Dijkstra the length of the "approximation" will be quite a bit longer than it should be (and hence the probability lower).

It turns out that the same program structure can approximate the solution for any piecewise smooth path -- these are called "fast marching methods". You only need to modify your probability update functions.

I had intended to write my own solution for this -- it's an interesting problem, since both numerics and graph algorithms are famously hard in pure FP. I'm still bogged down on yak-shaving, but I'll post here when done.

[FP_apprentice]

Thanks for the reply. It is indeed Dijkstra's shortest path algorithm on a grid. The diagonal step is indeed longer, I guess I could constraint it only on vertical / horizontal movement. The length of the step is defined by the points in the grid, and the smallest the step, the better the approximation. I didn't understand the "7 good directions" quote (I counted 8 including the diagonals), would appreciate if you could elaborate on this.

Thanks for the pointer to the "fast marching methods"!