Henry, Why in your example answer for D aren't the rightmost 2 atoms *s, since they have not changed from 20 and 3? Does that suggest that the "new" 20 and 3 are calculated but that you are not giving their calculations?
Also you say, "An atom of D indicates the minimum number of penalty points that must be incurred to reach that position." This suggests to me that atoms of D are penalties, not distances. Is that true and does that matter? On Mon, Feb 22, 2016 at 1:28 PM, Henry Rich <[email protected]> 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 > -- (B=) ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
