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
