[Tutor] locations

[Alan Gauld]

I should have added that this solution quickly explodes for large matrixes.
There are tweaks such as factoring in the distance between subsequent
zeros etc to keep the calculation size down. But for 4x4 sizes it should
be adequate in its simple state.

Alan G.


----- Original Message ----- 
From: "Alan Gauld" <alan.gauld at freenet.co.uk>
To: "linda.s" <samrobertsmith at gmail.com>; "Pujo Aji" <ajikoe at gmail.com>
Cc: <tutor at python.org>
Sent: Friday, April 21, 2006 4:49 PM
Subject: Re: [Tutor] locations


>> ---------------------
> I have a question. in the LIST M=
> [[1,1,1,1],
> [0,1,1,1],
> [1,1,0,1],
> [1,1,1,1]]
> If treat them as the locations of 16 points, I want to generate another 
> list
> N to hold the corresponding value for each point to its nearest 0.
>> ------------------
>
> Your explanation of the problem is clear up to this point, but...
>
>> -----------------------
> For example:
> the nearest 0 point to M[0][0] is M[1][0], so N[0][0]=1;
>> ----------------------
>
> You lost me there, how do you calculate the 1?
> Is it the linear distance? The number of hops?
> related to the index numbering? I'm confused.
>
>> M[0][1]'s nearest 0 is also at M[1][0], so N[0][1]=2;
>
> Linearly this is root 2 in distance not 2 so I assume you
> are counting hops?
>
>> but N[0][3]=3 because 0 at M[2][2] is much nearer;
>
> If you are counting hops then 3 is valid but its only one hop
> nearer not *much* nearer!
>
>> -------------------
> N should be
> [[1,2,2,3],
> [0,1,1,2],
> [1,1,0,1],
> [2,2,1,2]]
>> -------------------
>
> Assuming you mean hops... (and there probably is a proper
> mathematical algorithm for this.) I would do this:
>
> Locate the first zero(1,1) in this case.
> Mark all boxes with their distance to it.
> N looks like this (forget the python syntax
> for now, focus on the problem):
>
> 1234
> 0123
> 1234
> 2345
>
> Can you figure out the algorithm for doing that?
>
> Now find the next zero in M and do the same, except you
> only overwrite values where the new value is less than
> previously. Thus the values:
>
> 4323
> 3212
> 2101
> 3212
>
> becomes
>
> 1223
> 0112
> 1101
> 2212
>
> when overlaid on the previous matrix.
>
> Which is your required matrix N - QED.
>
> Does that help?
>
> Alan G
> Author of the learn to program web tutor
> http://www.freenetpages.co.uk/hp/alan.gauld
>
>