I implemented what I think is a scalar model of how this could work:
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
mdi=:dyad define
x+y
P=.x
r=. D=.y
for_j. }.i.#D do.
p=. j{P
d0=. (j-1){D
d1=. j{D
if. d0>_1 do.
D=. (d1 <. d0+p) j} D
end.
end.
D
)
P mdi D
1000000 1000000 1 3 5 7 8 9 10 _1 _1 1000000 1000000 20 3
That said, I'll note that Henry left a number of semi-wildcards in his
spec - perhaps for good reason.
That said, I don't have a good mental model of what's supposed to
happen here, I'm just working rotely, which limits my ability to think
about the problem. (Henry's description about how it's used didn't
hook into anything I understood.)
I hope this helps,
--
Raul
On Tue, Mar 1, 2016 at 3:21 PM, Joe Bogner <[email protected]> wrote:
> 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 <[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
>>
>>
>>
>>
>>
>>
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
