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
