Input

Your input in this challenge is a list of integer pairs. They represent the southwest corners of unit squares on the plane, and the list represents their union as a subset of the plane. For example, the list

[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]


represents the red-colored set in this picture:

Output

Yor output is a list of integer quadruples, representing rectangular subsets of the plane. More explicitly, a quadruple (x,y,w,h) reperents a rectangle of width w > 0 and height h > 0 whose southwest corner is at (x,y). The rectangles must form an exact covering of the input region, in the sense that each of the unit squares is a subset of some rectangle, each rectangle is a subset of the region, and two rectangles may overlap only at their borders. To forbid trivial solutions, the covering must not contain two rectangles that could be merged into a larger rectangle.

For example, the list

[(0,0,2,1),(0,1,3,1),(1,2,2,1)]


represents the legal covering

of the above region, whereas the covering given by

[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]


is illegal, since the neighboring 1-by-1 squares could be merged:

Rules

You can give a full program or a function. The precise formatting of the input and output is not important, within reason. The shortest byte count wins, and standard loopholes are disallowed. You are encouraged to provide an explanation of your algorithm, and some example outputs.

Test Cases

A U-shaped region:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]


A large triangle:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]


A square with holes:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]


Disconnected regions:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]


Verifier

Use this Python 2 program to verify your solution. It takes from STDIN a list of tuples (the input) and a list of quadruples (your output), separated by a comma.

I also wrote this Python 2 program to generate the pictures, and you can use it too. It takes from STDIN a list of either tuples or quadruples, and produces a file named out.png. It requires the PIL library. You can change the size of the grid cells and the width of the gird lines too, if you want.

Python - 272261258251 224

I think I can golf this more. I'm pretty sure this works, but I haven't finished testing it on all of the test cases yet. I finished testing it. It works for all of the test cases.

a=sorted(input())
b=[]
r=range
for i in a:
c=set(a)-set(b);w=h=1;x,y=i
if i in b:continue
while not{(x,y+h)}-c:h+=1
while all((x+w,y+j)in c for j in r(h)):w+=1
for j in r(w):
for k in r(h):b+=(j+x,k+y),
print x,y,w,h


I'm working on adding images of the results. Edit: Here are the results from the example and the test cases:

I'm trying to write this in Perl, but I can't figure out how to get multidimensional arrays from stdin without a huge number of characters. Does anyone have any suggestions?

• Two things: (i[0]+w,i[1]+j)not in c to {(i[0]+w,i[1]+j)}-c and you can move w=h=1 to the c=set(a)-set(b) line Jan 18, 2015 at 14:07
• A few more: b+=[(j+i[0],k+i[1])] to b+=(j+i[0],k+i[1]), and you use range three times so it's shorter to assign r=range Jan 18, 2015 at 14:09
• Also I'm not sure, but is it possible to do x,y=i then using x and y instead of i[0] and i[1]? That would save a lot of bytes. Jan 18, 2015 at 14:16
• Haven't tested this, but I think it works: Instead of while not[j for j in r(h)if(x+w,y+j)not in c]:w+=1 use while all((x+w,y+j)in c for j in r(h)):w+=1. Jan 18, 2015 at 14:52
• @Sp3000/Jakube I've used all of your suggestions.
– KSFT
Jan 18, 2015 at 14:59

Python: 196193 182 character

def g(r):
for p in r:
for q in r:
for h in 0,1:
if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
return r
f=lambda P:g([x+[1,1]for x in P])


My first solution used the exact same algorithm as KSFT, therefore I experimented with other methods.

First I do some preprocessing, I convert all points into small 1x1 rectangles {x+(1,1)for x in P}. With these rectangles, I call the function g. g iterates over each combination of rectangles. If it finds 2 rectangles, that can be merged into a bigger one, it deletes both and append the new one. Afterwards it calls itself with the new set of rectangles.

Usage

f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])


Results

Here are the visualization of the results. Note that they may be a bit different in the current version. The idea is though, that there is no kind of noticeable pattern.

A U-shaped region:

A large triangle

A square with holes:

Disconnected regions:

Just for fun: Pyth: 73 69 character

D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q


Works only in the offline version. Bug in the online version is fixed now. Try it here: Pyth Compiler/Executor. Expects a list of lists, not a list of tuples.

edit: Used an idea from @edc65: Instead of deleting both rectangles and creating a new one, I manipulate one and only delete one. In the Python solution I could get ride of the sets and the tuple-list-tuple casts. -11 chars in Python / -4 chars in Pyth

• Python3: Smiley faces are now valid code. Jan 17, 2015 at 20:02
• I might be wrong, but I think you can change 3-h to ~h? Jan 18, 2015 at 12:54
• Accepted for the Pyth version. Feb 4, 2015 at 8:30

Python 2, 139

The program accepts lists of ordered pairs surrounded by curly braces on standard input. E.g., {(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)}

s=input()
while s:x,y=min(s);w=h=0;exec"while(x+w,y)in s:w+=1\nwhile%s<=s:s-=%s;h+=1"%(("{(X,y+h)for X in range(x,x+w)}",)*2);print x,y,w,h


It's often irritating (not only in golf) that Python does not allow an assignment inside of a loop test. To work around this, I used string formatting operations.

• That's impressive. The same algorithm as KSFT, 'only' 85 (!!!) chars shorter. Jan 19, 2015 at 9:27

Mathematica - 315 285 267 bytes

f=(r={};For[m=MemberQ;t=Table;s=Sort@#,s!={},For[{x,y,w,h}=#~Join~{1,1}&@@s;i=j=0,i<1||j<1,If[s~m~{x+w,y+a-1}~t~{a,h}==True~t~{h},w++,i++];If[s~m~{x+a-1,y+h}~t~{a,w}==True~t~{w},h++,j++]];s=s~Cases~_?(!m[Join@@t[{x+a,y+b}-1,{a,w},{b,h}],#]&);r~AppendTo~{x,y,w,h}];r)&


With some help from @MartinBüttner.

Ungolfed:

f = (
rectangles = {};
For[squares = Sort[#], squares != {},
For[{x, y, w, h} = Join[squares[[1]], {1, 1}]; i = j = 0, i < 1 || j < 1,
If[Table[MemberQ[squares, {x + w, y + a - 1}], {a, h}] == Table[True, {h}], w++, i++];
If[Table[MemberQ[squares, {x + a - 1, y + h}], {a, w}] == Table[True, {w}], h++, j++];
];
squares = Cases[squares, _ ? (!MemberQ[Join@@Table[{x + a - 1, y + b - 1}, {a, w}, {b, h}], #] &)];
AppendTo[rectangles, {x, y, w, h}]
];
rectangles
)&


Usage:

In: f @ {{0,0},{1,0},{0,1},{1,1},{2,1},{1,2},{2,2}}
Out: {{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}


Test Cases

A U-shaped region

{{0, 0, 6, 2}, {0, 2, 2, 4}, {4, 2, 2, 4}}


A large triangle

{{0, 0, 6, 5}, {0, 5, 3, 3}, {0, 8, 2, 1}, {0, 9, 1, 1}, {3, 5, 2, 1}, {3, 6, 1, 1}, {6, 0, 3, 2}, {6, 2, 2, 1}, {6, 3, 1, 1}, {9, 0, 1, 1}}


A square with holes

{{0, 0, 6, 3}, {0, 3, 3, 6}, {1, 9, 9, 1}, {3, 4, 3, 2}, {3, 6, 2, 3}, {4, 3, 6, 1}, {5, 7, 5, 2}, {6, 1, 4, 2}, {6, 5, 4, 2}, {7, 0, 3, 1}, {7, 4, 3, 1}}


Disconnected regions

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


f[]=[]
f s@((x,y):_)=(x,y,w-x,h-y):f[r|r@(a,b)<-s,a<x||a>=w||b<y||b>=h]where w=[i|i<-[x..],notElem(i,y)s]!!0;h=[i|i<-[y..],not$all(\x->elem(x,i)s)[x..w-1]]!!0  test cases and images will be here shortly. Algorithm: Take the first square. Reach as far right without encountering a square not in the input. Then reach as far up as possible without having a square not on the input. We now have a rectangle without a missing square. Add it to the output, remove all of its squares from the input and call recursively. • You can save 1 byte by replacing not$all(\x->elem(x,i)s) with any(\x->notElem(x,i)s).
– nimi
Jan 19, 2015 at 16:14

JavaScript (ES6) 148 155 199

Edit2 Some more tuning
Edit Some golfing + rewrite using recursion. Did not expect such a reduction. Now it's a little difficult to follow, but the algorithm is the same.

The algorithm is similar to @jakube answer.

1. Each point becomes a 1x1 square (preprocessing)
2. For each element, check if it can be merged with another
Yes? First element grows, second element erased, start again at step 2
Else, proceed to next element
F=l=>
(l.map(x=>x.push(1,1)),R=f=>
l.some(u=>
(l=l.filter(t=>
[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))
),f)
)?R():l
)()


Test in snippet

F=l=>(l.map(x=>x.push(1,1)),R=f=>l.some(u=>(l=l.filter(t=>[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))),f))?R():l)()

// Test
MyCanvas.width= 600;
MyCanvas.height = 220;
var ctx = MyCanvas.getContext("2d");
ctx.fillStyle="#f23";

Draw=(x,y,f,l)=>l.forEach(p=>ctx.fillRect(x+p[0]*f,y+p[1]*f,p[2]*f-1||f-1,p[3]*f-1||f-1));

test=[
[[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,0],[2,1],[3,0],[3,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[6,0],[6,1],[6,2],[6,3],[7,0],[7,1],[7,2],[8,0],[8,1],[9,0]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,7],[5,8],[5,9],[6,1],[6,2],[6,3],[6,5],[6,6],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,6],[1,7],[1,8],[1,9],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[4,0],[4,1],[4,2],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,7],[9,8],[9,9],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]
]

Draw(0,0,10,test[0]),Draw(0,110,10,F(test[0]))
Draw(50,0,10,test[1]),Draw(50,110,10,F(test[1]))
Draw(130,0,10,test[2]),Draw(130,110,10,F(test[2]))
Draw(250,0,10,test[3]),Draw(250,110,10,F(test[3]))
Draw(370,0,10,test[4]),Draw(370,110,10,F(test[4]))
<canvas id=MyCanvas></canvas>

Mathematica, 153 151 144 136 133

Sort[{##,1,1}&@@@Input[]]//.{a___,r:{x_,y_,__},b___,{X_,Y_,W_,H_},c___}/;r=={x,Y,X-x,H}||r=={X,y,W,Y-y}:>{a,r+Sign@{0,0,X-x,Y-y},b,c}


Example:

Input:

{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 1}, {1, 2}, {2, 2}}


Output:

{{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}


Input:

{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 7}, {5, 8}, {5, 9}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {6, 9}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}, {8, 9}, {9, 0}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {9, 6}, {9, 7}, {9, 8}, {9, 9}}


Output:

{{0, 0, 3, 9}, {1, 9, 9, 1}, {3, 0, 3, 3}, {3, 4, 1, 5}, {4, 3, 1, 6}, {5, 3, 1, 3}, {5, 7, 1, 2}, {6, 1, 1, 3}, {6, 5, 1, 4}, {7, 0, 3, 9}}


Algorithm:

Cover the region with unit squares, then merge them.