Oh, yes, that's a good point - with manhattan distance, if a point's region reaches the border, nothing can stop it from reaching infinity.
So my code could be simplified slightly, since I don't need that extra row of padding. (I am also wondering if I am guaranteed to have a conflicted region on the border. I am pretty sure that I am guaranteed that, but I haven't proven it to myself, and it was only a couple of characters to let me ignore that issue.) Thanks, -- Raul On Wed, Dec 12, 2018 at 3:51 PM Jimmy Gauvin <[email protected]> wrote: > > Hi, > > I went with the assumption that inner regions are characterized by an > absence of points on the border of the spanning box. > A region that has a point on the border can "escape" out of the box. > This might not be true for Euclidian distance but seems to hold for > Manhattan distance. > > On Wed, Dec 12, 2018 at 1:40 PM Raul Miller <[email protected]> wrote: > > > On Wed, Dec 12, 2018 at 1:25 PM 'Mike Day' via Programming > > <[email protected]> wrote: > > > It occurred to me yesterday, though I haven’t coded it, that you can > > work through twice, first for the minimum suitable spanning box, and second > > for that box extended one row up and down and one column left and right. > > The inner regions are those whose size doesn’t change. Probably pretty > > inefficient, but easier to understand? > > > > What I did was ensure my grid had at least one row of empty grid cells > > on the border. > > > > I am not sure that that's sufficient. Intuitively, I would think the > > grid should be twice times the size necessary to contain the named > > coordinates for the worst cases (with the named coordinates in the > > central part), but it worked for every example I've encountered, so > > far. (On the other hand, if that single extra grid coordinate is > > sufficient, for the worst case, it might be that I don't even need > > that single extra row.) > > > > "Fortunately", ... Advent of Code doesn't require you solve for the > > general case. > > > > FYI, > > > > -- > > Raul > > ---------------------------------------------------------------------- > > 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
