[Jprogramming] A practical problem: minimum distance with penalties

[Joe Bogner]

Henry, just curious, do you have a scalar solution to the problem? You
mentioned it'd be trivial to write so I was curious if there is one.
It'd be helpful to compare against. Is the pseudocode on wikipedia
what you had in mind?
https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode




On Mon, Feb 22, 2016 at 1:28 PM, Henry Rich <henryhrich at gmail.com> wrote:
> This task shows J in my hands at its best and its worst.  Best, because I
> found a good solution; worst, because it took me 4 hours to come up with
> something that would have been trivial in a scalar language.  See what you
> can do with it.
>
> The task is to write a REALLY FAST program to solve the problem.  Solving
> the problem correctly is not so hard, but this is the innermost loop of many
> nested loops, and it must run at close to maximum machine speed.
>
> The problem arises in shortest-path-finding.  You are given two lists, the
> list of distances D and the list of penalties P.  D is to be thought of as
> ordered left-to-right.  An atom of D indicates the minimum number of penalty
> points that must be incurred to reach that position.
>
> At each step, new elements of D are created by external code, as new best
> ways to reach positions are discovered.  After the new elements of D have
> been installed, you come in.  You have to process D (and P) to propagate the
> new distances through D, leaving every atom of D showing the best distance.
> This best distance may be either the incumbent distance at that position, or
> a smaller value inherited from the position to its left.  If you inherit the
> distance from the left, you must add the value of the atom of P in the
> position being moved into.  The incumbent value in that position already
> includes the value of P.
>
> There is one more fillip.  Certain positions of D are blocked off.  A
> blocked-off atom must not be changed, and its value may not be inherited by
> the cell to its right.
>
> In the representation of D, empty cells are given a distance of HIGH-VALUE
> (=1e6), and blocked cells are given a distance of LOW-VALUE (=_1).
>
> Example:
>
> Given the setup
> H =. 1e6
> L =. _1
> D =. H, H, 1, H, 5, H, 8, H, 11, L, L, H, H, 20,3
> P =. 1, 1, 1, 2, 4, 2, 1, 1,  1, 1, 1, 1, 2, 1, 2
>
> you would produce
>
>
>      *  *  *  3  *  7  *  9  10  *  *  *  *  20 3
>
> 3 = 1+2-------|
> 7 = 5+2-------------|
>
> The * values indicate 'anything greater than or equal to the incumbent
> value' and indicate atoms that are unchanged by the process.  You are free
> to give them any value you like, as long as it is not less than the
> incumbent value.
>
> The numbered values are the inherited distances: the ones you must find.
>
> All the values can be integer and all are small compared with the range of
> an integer.  The length of the lists will not exceed 10,000, the values of D
> will not exceed 50,000, and the values of P will not exceed 20.
>
> Your code will be executed many times.  If you want to factor out
> computation by pre-computing any values, do so and do not count that as part
> of the execution time.
>
> Henry Rich
>
>
>
>
>
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm