4
\$\begingroup\$

You live in a rectangular neighborhood which is completely partitioned into N rectangular plots, i.e. there are no gaps or overlaps. Plots do not necessarily have the same width/height as other plots. All widths/heights are positive integers. Your goal is to output all shared edges between plots.

Inputs

The input may come from any source desired (stdio, file, function parameters, etc.). The input is a list-like sequence of rectangles. Inputs for rectangles may be any form desired, for example (min_x, max_x, min_y, max_y), (min_x, min_y, width, height), (min_x, min_y, max_x, max_y), etc.

The neighborhood is bounded by min_x = 0 and min_y = 0. You may assume max_x and max_y of the neighborhood both fit in your language's native integer type.

You may flatten the input data into a 1D sequence if desired.

The id of a plot is a sequentially incremented integer based on the order of input, where the first plot may have any id desired.

Outputs

The output may be to any desired target (stdio, file, return value, output parameter, etc.).

The output is a list of lists of neighbors for each plot. A neighbor is defined as the id of the neighboring plot and the min/max bounds of the shared corner/edge. Shared corners/edges with the corner/edge of the neighborhood are not considered a neighbor relation and should not be outputted.

When printing out make some distinction between each list, for example using a newline to separate the neighbors of plot i from the neighbors of plot i+1.

The order of the neighbors of plot i is not important.

Example Test Cases

All listed test case inputs are of the format min_x, max_x, min_y, max_y and plot IDs start with 0. Outputs are formatted as (id, min_x, max_x, min_y, max_y).

Input:

0, 1, 0, 1

Output:

no output, empty list, list containing a single empty list, or anything similar such as null

Input:

0, 1, 0, 1
0, 1, 1, 2

Output:

(1, 0, 1, 1, 1)
(0, 0, 1, 1, 1)

Input:

0, 2, 1, 2
0, 2, 0, 1

Output:

(1, 0, 2, 1, 1)
(0, 0, 2, 1, 1)

Input:

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

Output:

Regions with no neighbor relationships may be omitted.

(1, 0, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 0, 1, 2, 2)
(1, 0, 1, 2, 2)

It is also ok to output the id of the other region with some indication of "no shared boundary".

(1, 0, 1, 1, 1), (2)
(0, 0, 1, 1, 1), (2, 0, 1, 2, 2)
(1, 0, 1, 2, 2), (0, falsy)

Input:

0, 1, 0, 1
0, 1, 1, 2
1, 2, 0, 2

Output:

(1, 0, 1, 1, 1), (2, 1, 1, 0, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 2)

One possible alternative output (switched order of neighbors for plot 0):

(2, 1, 1, 0, 1), (1, 0, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 2)

Input:

You may have corner neighbors.

0, 1, 0, 1
0, 1, 1, 2
1, 2, 0, 1
1, 2, 1, 2

Output:

(1, 0, 1, 1, 1), (2, 1, 1, 0, 1), (3, 1, 1, 1, 1)
(0, 0, 1, 1, 1), (2, 1, 1, 1, 1), (3, 1, 1, 1, 2)
(0, 1, 1, 0, 1), (1, 1, 1, 1, 1), (3, 1, 2, 1, 1)
(0, 1, 1, 1, 1), (1, 1, 1, 1, 2), (2, 1, 2, 1, 1)

Scoring

This is code golf; shortest code wins.

edit clarification that corner neighbors should be outputted as well. Also clarified that if two regions don't share any corners/edges the relation may be completely omitted, or a relation with a falsy edge bounds may be outputted. Both have test cases added.

\$\endgroup\$
  • 1
    \$\begingroup\$ Wouldn't the output format be simpler if it was the two neighbours and their shared edge together, instead of repeating each shared edge twice? Also are plots considered touching across corners? \$\endgroup\$ – Martin Ender Jan 24 '16 at 10:20
  • \$\begingroup\$ @MartinBüttner Yes, corners count as neighbors. See edit for new test case. I had considered outputting a single neighbor relation instead of duplicating them, but at the time for the larger problem I was solving it was much more convenient to have them separate so this is what you get as well. \$\endgroup\$ – helloworld922 Jan 24 '16 at 20:32
2
\$\begingroup\$

Mathematica, 179 171 bytes

If[Depth@#2>2,Flatten/@(Thread@{##}/.Line->List)]&~MapThread~{Range@Length@#~Subsets~{2}-1,RegionIntersection/@Subsets[Line@{{##3},{#,#4},{#,#2},{#3,#2},{##3}}&@@@#,{2}]}&

Test cases

Inputs and outputs are list of elements in form {x1, y1, x2, y2}.

%[{{0, 0, 1, 1}, {0, 1, 1, 2}, {1, 0, 2, 2}}]
(*
   {{{0, 0, 1, 1, 1}, {1, 0, 1, 1, 1}},
    {{0, 1, 0, 1, 1}, {2, 1, 0, 1, 1}},
    {{1, 1, 1, 1, 2}, {2, 1, 1, 1, 2}}}
 *)
\$\endgroup\$
  • \$\begingroup\$ Why the Nothing? \$\endgroup\$ – LegionMammal978 Jan 24 '16 at 11:39
  • \$\begingroup\$ @LegionMammal978 It is possible that two regions have no common boundary, in which case, Nothing instead of Null will not appear in the output list. \$\endgroup\$ – njpipeorgan Jan 24 '16 at 11:44
  • \$\begingroup\$ In that case, couldn't you use 1<0 to indicate a falsey value? \$\endgroup\$ – LegionMammal978 Jan 24 '16 at 11:51
  • \$\begingroup\$ @LegionMammal978 Expressions other than Nothing, like False or Null, will appear in the list as elements. \$\endgroup\$ – njpipeorgan Jan 24 '16 at 11:56
  • \$\begingroup\$ Is there also a problem with using None, then? \$\endgroup\$ – LegionMammal978 Jan 24 '16 at 12:02
1
\$\begingroup\$

Mathematica 123 134 bytes

g@d_:=Subsets[MapIndexed[List,Apply[Rectangle,d,1]],{2}]/.{{a_,{i_Integer}},
{b_,{j_}}}:>{{i-1,r=RegionIntersection[a,b][[1]]},{j-1,r}}

I prefer this version, at 123 bytes, which returns graphics objects instead of mere coordinates. It also avoids redundancy, using by MartinBüttner's suggestion, by listing two rectangle numbers followed by a Line[{{x1,y1},{x2,y2}}] in the case of a shared edge, and Point[{x,y}] in the case of a shared corner.

f@d_:=Subsets[MapIndexed[List,Apply[Rectangle,d,1]],{2}]/.
{{a_,{i_Integer}},{b_,{j_}}}:>{{i,j}-1,r=RegionIntersection[a,b]}

f[{{{0, 0}, {1, 1}}}]

{}


f[{{{0, 0}, {1, 1}}, {{0, 1}, {1, 2}}}]

{{{0, 1}, Line[{{0, 1}, {1, 1}}]}}


f[{{{0, 1}, {1, 2}}, {{0, 0}, {2, 1}}}]

{{{0, 1}, Line[{{0, 1}, {1, 1}}]}}


Shared edges, corners, areas, formatted to a grid for clarity.

f[{{{0, 0}, {1, 1}}, {{0, 1}, {1, 2}}, {{.5, .5}, {1.3, 1.5}}, {{1, 
 0}, {2, 1}}, {{1, 1}, {2, 2}}}] // Grid

image

\$\endgroup\$
0
\$\begingroup\$

Python, 189 characters

for p in i:
    for q in i:
        for t in 0,2:
            v,a,b=p[3-t],min(p[1+t],q[1+t]),max(p[t],q[t])
            w,z=[v,v],[b,a]
            if v==q[2-t]and a>b:
                for d in p,q:
                    print[i.index(d)]+(w+z,z+w)[t/2]

The input is given as a list like

i = [[0, 1, 0, 1], [0, 1, 1, 2], [1, 2, 0, 2]]
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 228

Input / output as an array of arrays. Format as in OP testcases:

  • inputs min_x, max_x, min_y, max_y.
  • outputs id (0 based), min_x, max_x, min_y, max_y.
l=>l.map(([x,r,y,s],i)=>l.map(([t,v,u,w],j)=>i-j&&(n=x-t&&x-v,m=r-t&&r-v,u>=s|w<=y||n&&m||q.push([j,z=m?x:r,z,y>u?y:u,s<w?s:w]),n=y-u&&y-w,m=s-u&&s-w,t>=r|v<=x||n&&m||q.push([j,x>t?x:t,r<v?r:v,z=m?y:s,z])),o.push(q=[])),o=[])&&o

This can probably be shortened merging the horizontal and vertical check

TEST

f=l=>
  l.map(([x,r,y,s],i)=>
    l.map(([t,v,u,w],j)=>
      i-j&&(
        n=x-t&&x-v,m=r-t&&r-v,u>=s|w<=y||n&&m||q.push([j,z=m?x:r,z,y>u?y:u,s<w?s:w]), // vertical
        n=y-u&&y-w,m=s-u&&s-w,t>=r|v<=x||n&&m||q.push([j,x>t?x:t,r<v?r:v,z=m?y:s,z])  // horizontal
      )
    ,o.push(q=[]))  
  ,o=[])&&o  

ArToStr=(a,s)=>a.map?(s?'[':'[\n ')+a.map(x=>ArToStr(x,1)).join(s?',':',\n ')+(s?']':'\n]\n'):a

console.log=x=>O.textContent+=x+'\n';

console.log(ArToStr(f([[0,1,0,1]])))
console.log(ArToStr(f([[0,1,0,1],[0,1,1,2]])))
console.log(ArToStr(f([[0, 2, 1, 2],[0, 2, 0, 1]])))
console.log(ArToStr(f([[0, 1, 0, 1],[0, 1, 1, 2],[1, 2, 0, 2]])))
<pre id=O></pre>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.