How far from the exterior?

Question

Take a 2D region of space divided into axis aligned unit square elements with their centers aligned at integer intervals. An edge is said to be internal if it is shared by two elements, otherwise it is an external edge.

Your goal is to find the minimum number of neighboring elements which must be traversed to reach an exterior edge starting from the center of each element, known as the traversal distance, or distance for short. You may only traverse through an edge (i.e. no corner cutting/diagonal movement). Note that "exterior elements" (elements which have at least one external edge) are considered to need to traverse 0 neighboring elements to reach an exterior edge..

Input

The input is a list of non-negative integer pair coordinates denoting the (x,y) of the center of all elements. It is assumed there are no overlapping elements (i.e. an x/y pair uniquely identifies an element). You may not assume anything about the element input order.

You are welcome to transform the origin of the input to any location (e.g. 0,0 or 1,1, etc.).

You may assume that all input elements are connected, or in other words it is possible to travel from any one element to any other element using the rules above. Note that this does not mean that the 2D region is simply connected; it may have holes inside of it.

Example: the following is an invalid input.

0,0
2,0

error checking is not required.

The input may be from any source (file, stdio, function parameter, etc.)

Output

The output should be a list of coordinates identifying each element, and the corresponding integer distance traversed to get to an edge. The output may be in any element order desired (e.g. you need not output elements in the same order received as inputs).

The output may be to any source (file, stdio, function return value, etc.)

Any output which matches the coordinate of the element with it's exterior distance is fine, e.g. all of these are fine:

x,y: distance
...

[((x,y), distance), ...]

[(x,y,distance), ...]

Examples

Text example inputs are in the form x,y, with one element per line; you are welcome to reshape this into a convenient input format (see input format rules).

Text example outputs are in the format x,y: distance, with one element per line; again, you are welcome to reshape this into a convenient ouput format (see output format rules).

Graphical figures have the lower-left bound as (0,0), and the numbers inside represent the expected minimum distance traveled to reach an exterior edge. Note that these figures are purely for demonstration purposes only; your program does not need to output these.

Example 1

input:

1,0
3,0
0,1
1,2
1,1
2,1
4,3
3,1
2,2
2,3
3,2
3,3

Output:

1,0: 0
3,0: 0
0,1: 0
1,2: 0
1,1: 1
2,1: 0
4,3: 0
3,1: 0
2,2: 1
2,3: 0
3,2: 0
3,3: 0

graphical representation:

Example 2

input:

4,0
1,1
3,1
4,1
5,1
6,1
0,2
1,2
2,2
3,2
4,2
5,2
6,2
7,2
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
2,4
3,4
4,4
5,4
6,4
3,5
4,5
5,5

output:

4,0: 0
1,1: 0
3,1: 0
4,1: 1
5,1: 0
6,1: 0
0,2: 0
1,2: 1
2,2: 0
3,2: 1
4,2: 2
5,2: 1
6,2: 1
7,2: 0
1,3: 0
2,3: 1
3,3: 2
4,3: 2
5,3: 2
6,3: 1
7,3: 0
8,3: 0
2,4: 0
3,4: 1
4,4: 1
5,4: 1
6,4: 0
3,5: 0
4,5: 0
5,5: 0

graphical representation:

Example 3

input:

4,0
4,1
1,2
3,2
4,2
5,2
6,2
8,2
0,3
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
9,3
1,4
2,4
3,4
4,4
5,4
6,4
7,4
8,4
9,4
2,5
3,5
4,5
5,5
6,5
9,5
10,5
11,5
3,6
4,6
5,6
9,6
10,6
11,6
6,7
7,7
8,7
9,7
10,7
11,7

output:

4,0: 0
4,1: 0
1,2: 0
3,2: 0
4,2: 1
5,2: 0
6,2: 0
8,2: 0
0,3: 0
1,3: 1
2,3: 0
3,3: 1
4,3: 2
5,3: 1
6,3: 1
7,3: 0
8,3: 1
9,3: 0
1,4: 0
2,4: 1
3,4: 2
4,4: 2
5,4: 2
6,4: 1
7,4: 0
8,4: 0
9,4: 0
2,5: 0
3,5: 1
4,5: 1
5,5: 1
6,5: 0
9,5: 0
10,5: 0
11,5: 0
3,6: 0
4,6: 0
5,6: 0
9,6: 0
10,6: 1
11,6: 0
6,7: 0
7,7: 0
8,7: 0
9,7: 0
10,7: 0
11,7: 0

graphical representation:

Scoring

This is code golf. Shortest code in bytes wins. Standard loopholes apply. Any built-ins other than those specifically designed to solve this problem are allowed.

Answer 1

MATLAB/Octave, 143 bytes

function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);

Ungolfed

function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);

Explanation

Create Source and Result matrices of appropriate size, filled with zeros.

R=S=zeros(max(y+3),max(x+3));

Calculate the linear indices that correspond to the xy-pairs, with one element padding at the borders.

i=sub2ind(size(S),y+2,x+2);

Draw the structure.

S(i)=1;

S is shown here for Example 2:

0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   0   0   0
0   0   1   0   1   1   1   1   0   0   0
0   1   1   1   1   1   1   1   1   0   0
0   0   1   1   1   1   1   1   1   1   0
0   0   0   1   1   1   1   1   0   0   0
0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0

Remove all border elements by image erosion

S=imerode(S,strel('disk',1,0))

using the structuring element disk with radius 1:

0   1   0
1   1   1
0   1   0

If diagonal movement was allowed, we would instead use the rectangle:

1   1   1
1   1   1
1   1   1

Then, increment the result for all non-border elements

R+=S;

and loop until the image is completely eroded.

while nnz(S)

Return the result for each xy-pair.

v=R(i);

Answer 2

Pyth, 26 bytes

V]MQNf>*4Nl=Nsmfq1.a,dYQN0

Example 2

The output format I used is:

[[4, 3]]
2

That is, a list containing the point, followed by the distance from the exterior.

The code works by using a currently reached set, for each point filtering the input for all points exactly distance 1 away from that point, and checking whether the resultant number of points is 4 times as many as the starting number, and repeating until it's not. When started at a given point, this gives how far that point is from the exterior.

Answer 3

MATL, 38 37 36 33 bytes

1Z?t"tX@<~5Bt!Z~2X53$Y+4=+]3#fqhh

This uses current version (15.0.0) of the language/compiler.

Input format is: one array with x values and one array with y values. Input and output are 1-based. So the test cases have the following inputs:

[2 4 1 2 2 3 5 4 3 3 4 4]
[1 1 2 3 2 2 4 2 3 4 3 4]

[5 2 4 5 6 7 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 4 5 6]
[1 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 6 6 6]

[5 5 2 4 5 6 7 9 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 3 4 5 6 7 10 11 12 4 5 6 10 11 12 7 8 9 10 11 12]
[1 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8]

Try it online!

Explanation

A matrix is initially built with 1 at the input positions and 0 otherwise. Then a convolution is applied with a "North, East, South, West" mask ([0 1 0; 1 0 1; 0 1 0]), and the result at each position is compared with 4. A result of 4 means that that position is surrounded by other points, and so has distance-to-exterior at least 1. The result (0 or 1 for each point) is added to the original matrix. Those positions now contain 2 (at the end of the process the matrix will be decremented by 1).

The convolution process is iterated. For the next iteration, the input of the convolution is the accumulated matrix thresholded with 2; that is, values lower than 2 are set to 0. The result of the convolution indicates which points have distance at least 2 (all their neighbours have distance 1).

The number of iterations is chosen, for convenience, as the number of columns of the input matrix. This is sufficient (in fact, the maximum required number of iterations is half the minimum matrix dimension). The last iterations may be useless, but do no harm (they do simply add 0 to all points).

At the end of the process, 1 is subtracted from the result, because positions with value k have distance k-1 to the exterior. The coordinates and values of all positions is extracted and displayed.

           % take x and y implicitly
1          % push 1
Z?         % build sparse matrix from that x, y indices with 1 as value
t          % duplicate
"          % for each column of that matrix
  t        %   duplicate
  X@       %   push iteration index
  <~       %   true for matrix entries that are >= iteration index
  5B       %   5 in binary: row vector [1 0 1]
  t!       %   duplicate and transpose into a column vector
  Z~       %   element-wise XOR with broadcast: gives desired mask,
           %   [0 1 0; 1 0 1; 0 1 0]
  2X53$Y+  %   2D convolution. Output has same size as input
  4=       %   compare with 4: are all neighbouring positions occupied?
  +        %   add to accumulated matrix from previous iteration
]          % end for each
3#f        % extract row index, column index and value for nonzero
           % entries. In this case all entries are nonzero
q          % subtract 1 to value to yield distance to exterior
hh         % concatenate vertically twice
           % display implicitly 

Answer 4

Python 3, 180 166 160 bytes

def f(l,d=0):
 l=set(l);
 if l:i={(a,b)for a,b in l if all([x in l for x in[(a+1,b),(a-1,b),(a,b+1),(a,b-1)]])};return{(c,d)for c in l-i}|f(i,d+1)
 return set()

We know that if a coordinate has less than four neighbours, it must be on the "exterior". Therefore, we can repeatedly strip the exterior cells and assign to them a distance equal the the number of iterations/depth of recursion in this case.

Definitely think there's room for improvement - What's the best way of checking of adjacent neighbours?

edit: I should be allowed to accept a list of pairs as tuples.

Answer 5

PHP, 316 Bytes

<?preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t);foreach($t[1]as$k=>$v)$a[$v][$t[2][$k]]=0;function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};for(;$z++<max($t[2]);$o=$s,$s="")foreach($a as$x=>$b)foreach($b as$y=>$c)$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1));echo$o;

Online Version

Breakdown

preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t); 
foreach($t[1]as$k=>$v) 
$a[$v][$t[2][$k]]=0;  # make a 2 D array
function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};# check the neighbours
for(;$z++<max($t[2]);$o=$s,$s="") # stored the last loop string first run make possible to 1 and so on
foreach($a as$x=>$b) # x values
foreach($b as$y=>$c) # y values
$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1)); # concanate array item x+y+value
echo$o; #Output

Visualize as Ascii chars

ksort($a); 
foreach($a as$x=>$b){
for($y=0;$y<=max($t[2]);$y++)
echo isset($a[$x][$y])?$a[$x][$y]:" ";
#The better way would be make a SVG and use the text element and use a factor
#echo '<text x="'.($x*$factor).'" y="'.($y*$factor).'">'.$a[$x][$y].'</text>';
echo"\n";}