Entrada

Su entrada en este desafío es una lista de pares enteros. Representan las esquinas sudoeste de cuadrados unitarios en el plano, y la lista representa su unión como un subconjunto del plano. Por ejemplo, la lista

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

representa el conjunto de color rojo en esta imagen:

Salida

Su salida es una lista de cuádruples enteros, que representan subconjuntos rectangulares del plano. Más explícitamente, un cuádruple (x,y,w,h)repite un rectángulo de ancho w > 0y alto h > 0cuya esquina suroeste está (x,y). Los rectángulos deben formar una cobertura exacta de la región de entrada, en el sentido de que cada uno de los cuadrados unitarios es un subconjunto de algún rectángulo, cada rectángulo es un subconjunto de la región y dos rectángulos pueden solaparse solo en sus bordes. Para prohibir soluciones triviales, la cubierta no debe contener dos rectángulos que puedan fusionarse en un rectángulo más grande.

Por ejemplo, la lista

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

representa la cobertura legal

de la región anterior, mientras que la cobertura dada por

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

es ilegal, ya que los cuadrados vecinos 1 por 1 podrían fusionarse:

Reglas

Puedes dar un programa completo o una función. El formato preciso de la entrada y salida no es importante, dentro de lo razonable. El conteo de bytes más corto gana, y las lagunas estándar no se permiten. Se le recomienda que proporcione una explicación de su algoritmo y algunos resultados de ejemplo.

Casos de prueba

Una región en forma de U:

[(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)]

Un gran triángulo:

[(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)]

Un cuadrado con agujeros:

[(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)]

Regiones desconectadas:

[(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)]

Verificador

Use este programa Python 2 para verificar su solución. Toma de STDIN una lista de tuplas (la entrada) y una lista de cuádruples (su salida), separadas por una coma.

También escribí este programa Python 2 para generar las imágenes, y también puedes usarlo. Toma de STDIN una lista de tuplas o cuádruples, y produce un archivo llamado out.png. Requiere la biblioteca PIL. También puede cambiar el tamaño de las celdas de la cuadrícula y el ancho de las líneas de ceñido, si lo desea.

Python: 196 193 182 caracteres

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])

Mi primera solución utilizó exactamente el mismo algoritmo que KSFT, por lo tanto, experimenté con otros métodos.

Primero hago un preprocesamiento, convierto todos los puntos en pequeños rectángulos de 1x1 {x+(1,1)for x in P}. Con estos rectángulos, llamo a la función g. gitera sobre cada combinación de rectángulos. Si encuentra 2 rectángulos, que se pueden fusionar en uno más grande, elimina ambos y agrega el nuevo. Luego se llama a sí mismo con el nuevo conjunto de rectángulos.

Uso

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

Resultados

Aquí están la visualización de los resultados. Tenga en cuenta que pueden ser un poco diferentes en la versión actual. Sin embargo, la idea es que no hay ningún tipo de patrón notable.

Una región en forma de U:

Un gran triangulo

Un cuadrado con agujeros:

Regiones desconectadas:

Solo por diversión: Pyth: 73 69 caracteres

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

Funciona solo en la versión sin conexión. El error en la versión en línea se ha solucionado ahora. Pruébelo aquí: Pyth Compiler / Executor . Espera una lista de listas, no una lista de tuplas.

editar: Usé una idea de @ edc65: en lugar de eliminar ambos rectángulos y crear uno nuevo, manipulo uno y solo elimino uno. En la solución Python pude obtener el paseo de los conjuntos y los moldes tuple-list-tuple. -11 caracteres en Python / -4 caracteres en Pyth

Python - 272 261 258 251 224

Creo que puedo jugar más al golf. Estoy bastante seguro de que esto funciona, pero aún no he terminado de probarlo en todos los casos de prueba. Terminé de probarlo. Funciona para todos los casos de prueba.

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

Estoy trabajando para agregar imágenes de los resultados. Editar: Aquí están los resultados del ejemplo y los casos de prueba:

Estoy tratando de escribir esto en Perl, pero no puedo entender cómo obtener matrices multidimensionales de stdin sin una gran cantidad de caracteres. ¿Alguien tiene alguna sugerencia?

Pitón 2, 139

El programa acepta listas de pares ordenados rodeados por llaves en la entrada estándar. P.ej,{(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

A menudo es irritante (no solo en el golf) que Python no permita una asignación dentro de una prueba de bucle. Para evitar esto, utilicé operaciones de formateo de cadenas.

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)&

Con algo de ayuda de @ MartinBüttner.

Sin golf:

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
)&

Uso:

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}}

Casos de prueba

Una región en forma de U

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

Un gran triangulo

{{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}}

Un cuadrado con agujeros

{{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}}

Regiones desconectadas

{{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}}

Haskell, 158

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

Los casos de prueba y las imágenes estarán aquí en breve.

Algoritmo: toma el primer cuadrado. Llegue a la derecha sin encontrar un cuadrado que no esté en la entrada. Luego llegue lo más arriba posible sin tener un cuadrado que no esté en la entrada. Ahora tenemos un rectángulo sin un cuadrado faltante. Agréguelo a la salida, elimine todos sus cuadrados de la entrada y llame de forma recursiva.

JavaScript (ES6) 148 155 199

Edit2 Un poco más de sintonía
Edit Some golfing + rewrite using recursion. No esperaba tal reducción. Ahora es un poco difícil de seguir, pero el algoritmo es el mismo.

El algoritmo es similar a la respuesta @jakube.

1. Cada punto se convierte en un cuadrado de 1x1 (preprocesamiento)
2. Para cada elemento, verifique si se puede combinar con otro
   Sí? El primer elemento crece, el segundo elemento se borra, comience de nuevo en el paso 2 De lo
   contrario, continúe con el siguiente elemento

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
  )()

Prueba en fragmento

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}

Ejemplo:

Entrada:

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

Salida:

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

Entrada:

{{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}}

Salida:

{{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}}

Algoritmo:

Cubra la región con cuadrados unitarios, luego combínelos.