Raul, yes, that helps. Thanks
I'm not entirely clear about the performance issues with any of the
approaches outlined. It would be useful to be able to simulate that I
think so any of the approaches outlined or new ones could be tested.
It sounds like the approach will be called multiple times per interval
as some external process is updating data? Running it once with the
parameters outlined seems to be fine:
timespacex '(? 10000#20) mdi ((? 10000#15) { D)'
0.0384976 926464
But I could see how that would be a problem if it needs to be run 100
times per second. It would be helpful to include the simulation in the
problem definition.
On Tue, Mar 1, 2016 at 3:25 PM, Raul Miller <[email protected]> wrote:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
