Diferença retangular

20

Nesse desafio, você recebe dois retângulos sobrepostos e precisa calcular os retângulos criados removendo um do outro.

Por exemplo, se você remover o retângulo vermelho do preto:

retângulos

Você acaba com um dos dois conjuntos de retângulos a seguir:

split-one split-two

Você também precisará lidar com o seguinte:

Todos os casos de teste

Para ser mais explícito:

  • Você introduzirá as coordenadas de dois retângulos, A e B.
  • Você precisa produzir o menor número de retângulos sem sobreposição que cubram toda a área de A sem B. Qualquer cobertura possível é permitida
  • As coordenadas retangulares são passadas como 4 números inteiros. Você pode passá-los em dois pares (representando os dois pontos de canto) ou como uma tupla / lista de 4 números inteiros. Suas entradas e saídas precisam ser consistentes.
  • A e B não necessariamente se sobrepõem ou se tocam, e cada um terá uma área de pelo menos 1

Casos de teste:

[(0 0) (5 5)] [(3 4) (8 7)]   -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)]  -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)]    #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)]   ->    #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)]   -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)]  #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)]   -> [(1 5) (7 8)]  #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)]   -> [(4 1) (10 5)] [(4 7) (10 9)]  #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)]     -> [(1 1) (8 6)]   #Only possible output

Este é um , portanto, faça seu código o mais curto possível!

Nathan Merrill
fonte
3
Relacionado.
Martin Ender
1
podemos assumir que a entrada fornecida {(x1, y1), (x2, y2)}é válida x1 < x2e y1 < y2?
tsh
Sim. O retângulo terá uma área de 1 e você poderá ordenar as coordenadas na ordem que desejar.
Nathan Merrill
A borda é grossa? Quando o retângulo definido está incluído a aresta?
228176 #: 217176 #:
A aresta tem 0 espessura.
Nathan Merrill

Respostas:

3

Python 2 , 375 360 345 343 bytes

from itertools import*;P=product
def f(S,M):(l,t),(r,b)=S;(L,T),(R,B)=M;u,v,x,y=(L>=r)+(l<L),(T>=b)+(t<T),(R>=r)+(l<R),(B>=b)+(t<B);return[S]if v==y!=1or u==x!=1else[list(p(p(*zip(*(S+M))),repeat=2))[[43,197,6,199,9,231,142,229,53,189,134,181][int(i,36)]]for i in '38,491,258,2058,8,4B,28,208,7,41,27,461,,4,2,4A'.split(',')[u+2*v+4*x+8*y-12]]

Experimente online!

EDITS: -15 de sugestões de @notjagan; outro -15 recodificando a matriz de retângulos da solução para o formato int36 e uma tabela de pesquisa curta; outro -2 substituindo o produto por p conforme @musicman.

Uma função que usa dois retângulos, cada um sendo uma tupla de ((esquerda, superior), (direita, inferior)); retorna uma lista dos retângulos resultantes.

A estratégia básica:

     |     |
 0,0 | 1,0 | 2,0
-----A-----+-----
     |     |
 0,1 | 1,1 | 2,1
-----+-----B-----
     |     |
 0,2 | 1,2 | 2,2
     |     |

No diagrama acima, os pontos A e B são o canto superior esquerdo e o canto inferior direito, respectivamente, do retângulo 'Fonte' (o primeiro ret).

Encontramos o posicionamento de cada um dos cantos superior esquerdo (u,v)e inferior direito (x,y)do retângulo 'Mask' nessa grade.

Se esses dois pontos estiverem na primeira ou na última coluna; ou primeira ou última linha; então não há sobreposição; e podemos retornar apenas a fonte correta.

Caso contrário, restam 16 casos; por exemplo, o primeiro exemplo do OP é o caso que podemos rotular (1,1),(2,2). Cada caso pode ser mapeado para um conjunto de retângulos resultantes cujos cantos são sempre coordenadas com valores horizontais nos retângulos de origem à esquerda, à direita ou nos retângulos da máscara à esquerda, à direita; e da mesma forma para os valores verticais, superior, inferior ou máscaras da fonte.

Por exemplo, para o (1,1),(2,2)caso, os retângulos seriam ((l,t),(T,r))e ((l,T),(R,b)), onde l,t,r,be L,T,R,Bestão à esquerda, superior, direita e inferior dos retângulos Origem e Máscara, respectivamente.

Assim, podemos criar uma tabela de pesquisa que mapeie as coordenadas para o conjunto de todas essas combinações possíveis (que é o que é o product(product(*zip(*)))bit) para um conjunto de retângulos que devem ser fornecidos para cada um dos casos (que, após algumas descompressões de golfe) , é disso que trata o restante do material da lista).

Chas Brown
fonte
-15 bytes por fazer várias melhorias de golfe, ou -18 bytes usando cordas em Python 3.
notjagan
Você pode cortar fora mais dois bytes fazendo p=producte substituindo product(productcomp(p
musicman523
3

JavaScript, 115 bytes

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=a[i]=n,p)).filter(x=>x)

versão sobreposta:

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=n,p)).filter(x=>x)

Entrada no seguinte formato: f([1,1,8,8])([0,6,9,9])


Indique entrada como ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

Se qualquer uma das seguintes condições for atendida, retorne o primeiro retângulo como está:

  • x3> x2
  • x4 <x1
  • y3> y2
  • y4 <y1

de outra forma

  • Se x1 <x3 <x2, geramos um retângulo ((x1, y1), (x3, y2)); e defina x1: = x3
  • Se x1 <x4 <x2, geramos um retângulo ((x4, y1), (x2, y2)); e defina x2: = x4
  • Se y1 <y3 <y2, geramos um retângulo ((x1, y1), (x2, y3)); e defina y1: = y3
  • Se y1 <y4 <y2, geramos um retângulo ((x1, y4), (x2, y2)); e defina y2: = y4
tsh
fonte
Esta é uma abordagem promissora; mas atualmente falha algumas vezes, por exemplo, quando o retângulo da máscara não se sobrepõe ao retângulo de origem; por exemplo, f([0, 30, 10, 40])([5, 1, 6, 2])deve retornar, [[0, 30, 10, 40]]mas retorna[[0,30,5,40],[6,30,10,40]]
Chas Brown
@NathanMerrill ok, editado.
tsh
@tsh parece ser bom!
Nathan Merrill
1

Java, 268 bytes

class W{public static void main(String[]z) {int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};for(i=0;i<4;i+=1){for(j=0;j<4;j+=1){a[j]=Integer.parseInt(z[y[i*4+j]]);}if(a[0]<a[2] && a[1]<a[3]){for(j=0;j<4;j+=1){System.out.println(String.valueOf(a[j]));}}}}}

Ungolfed

class W{
    public static void main(String[]z) {
        int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};

        for(i=0;i<4;i+=1){
            for(j=0;j<4;j+=1){
                a[j]=Integer.parseInt(z[y[i*4+j]]);
            }
            if(a[0]<a[2] && a[1]<a[3]){
                for(j=0;j<4;j+=1){
                    System.out.println(String.valueOf(a[j]));
                }
            }
        }
    }
}

Passe entrada como argumentos. Exemplo

java -jar W.jar 0 0 5 5 3 4 8 7
Евгений Новиков
fonte
0

Python 2 , 272 bytes

lambda((a,b),(c,d)),((e,f),(g,h)):[([([[(a,b),(e,min(h,d))]]+[[(g,max(b,f)),(c,d)]]*2+[[(max(a,e),b),(c,f)]]*4+[[(a,h),(min(c,g),d)]])[m-1]for m in M&{1,2,4,8}]if M&{0}else[(a,b),(c,d)])for M in[{(x<e)*1+(x>g)*2+(y<f)*4+(y>h)*8 for x in range(a,c)for y in range(b,d)}]][0]

Experimente online!

Isso funciona testando todas as células dentro do primeiro retângulo quanto à esquerda = 1, acima = 4, direita = 2 e abaixo = 8 w / r para a outra e ORing como resultado. Se o outro não cruzar = 0 com o primeiro, o original será retornado; caso contrário, será retornada alguma combinação de uma fatia esquerda, direita, superior e inferior, com acomodação para sobreposição.

SmileAndNod
fonte