Różnica prostokątna

20

W tym wyzwaniu otrzymujesz dwa nakładające się prostokąty i musisz obliczyć prostokąty utworzone przez usunięcie jednego z drugiego.

Na przykład, jeśli usuniesz czerwony prostokąt z czarnego:

prostokąty

Otrzymasz jeden z następujących dwóch zestawów prostokątów:

split-one podzielone na dwa

Będziesz także musiał wykonać następujące czynności:

Wszystkie przypadki testowe

Mówiąc dokładniej:

  • Podasz współrzędne dwóch prostokątów, A i B.
  • Musisz wygenerować jak najmniej nie nakładających się prostokątów, które pokrywają cały obszar A bez B. Dozwolone jest jakiekolwiek możliwe pokrycie
  • Współrzędne prostokątne są przekazywane jako 4 liczby całkowite. Możesz przekazać je w dwóch parach (reprezentujących dwa punkty narożne) lub jako krotkę / listę 4 liczb całkowitych. Twoje dane wejściowe i wyjściowe muszą być spójne.
  • A i B niekoniecznie będą się nakładać lub dotykać, a każdy z nich będzie miał powierzchnię co najmniej 1

Przypadki testowe:

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

To jest gra w , więc ustaw swój kod tak krótko, jak to możliwe!

Nathan Merrill
źródło
3
Związane z.
Martin Ender,
1
czy możemy założyć, że dane wejściowe są {(x1, y1), (x2, y2)}wstrzymane x1 < x2i y1 < y2?
tsh
Tak. Prostokąt będzie miał powierzchnię 1 i możesz uporządkować współrzędne w dowolnej kolejności.
Nathan Merrill,
Czy krawędź jest gruba? Kiedy zdefiniowany prostokąt zawiera krawędź?
Евгений Новиков
Krawędź ma grubość 0.
Nathan Merrill,

Odpowiedzi:

3

Python 2 , 375 360 345 343 bajtów

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

Wypróbuj online!

EDYCJE: -15 z sugestii @notjagan; kolejny -15 przez ponowne kodowanie tablicy prostokątów rozwiązania do formatu int36 i krótkiej tabeli odnośników; kolejne -2, zamieniając produkt na p zgodnie z @musicman.

Funkcja, która przyjmuje dwa prostokąty, z których każdy jest krotką ((lewy, górny), (prawy, dolny)); zwraca listę wynikowych prostokątów.

Podstawowa strategia:

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

Na powyższym schemacie punkty A i B są odpowiednio górną lewą i dolną prawą prostokątem „Źródła” (pierwszy prostokąt).

Znajdujemy położenie każdego górnego lewego (u,v)i dolnego prawego (x,y)prostokąta „Maska” w tej siatce.

Jeśli oba te punkty znajdują się w pierwszej lub ostatniej kolumnie; lub pierwszy lub ostatni rząd; wtedy nie ma nakładania się; i możemy zwrócić tylko źródło Source.

W przeciwnym razie pozostało 16 przypadków; na przykład pierwszym przykładem PO jest przypadek, który możemy oznaczyć (1,1),(2,2). Każdy przypadek można odwzorować na zbiór wynikowych prostokątów, których narożniki są zawsze współrzędne z wartościami poziomymi w prostokątach źródłowych po lewej, prawej stronie lub prostokątach maski po lewej, prawej stronie; i podobnie dla wartości pionowych, góry, dołu lub masek źródła.

Na przykład w tym (1,1),(2,2)przypadku prostokąty będą, ((l,t),(T,r))a ((l,T),(R,b))gdzie l,t,r,bi L,T,R,Bsą odpowiednio lewą, górną, prawą i dolną prostokątami Źródło i Maska.

Możemy więc utworzyć tabelę przeglądową, która odwzorowuje współrzędne na zbiór wszystkich takich możliwych kombinacji (o co chodzi w tym product(product(*zip(*)))bicie) na zbiór prostokątów, które powinny być zapewnione dla każdego z przypadków (które po pewnym dekompresji golfa , dotyczy reszty rzeczy na liście).

Chas Brown
źródło
-15 bajtów , wprowadzając różne ulepszenia gry w golfa, lub -18 bajtów przy użyciu łańcuchów w Pythonie 3.
notjagan
Można odciąć dwóch kolejnych bajtów wykonując p=producti zastąpienie product(productzp(p
musicman523
3

JavaScript, 115 bajtów

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)

nakładająca się wersja:

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)

Wprowadź w następującym formacie: f([1,1,8,8])([0,6,9,9])


Oznacz dane wejściowe jako ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

Jeśli którykolwiek z poniższych warunków jest spełniony, zwróć pierwszy prostokąt bez zmian:

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

Inaczej

  • Jeśli x1 <x3 <x2, wówczas generujemy prostokąt ((x1, y1), (x3, y2)); i ustaw x1: = x3
  • Jeśli x1 <x4 <x2, wówczas generujemy prostokąt ((x4, y1), (x2, y2)); i ustaw x2: = x4
  • Jeśli y1 <y3 <y2 to generujemy prostokąt ((x1, y1), (x2, y3)); i ustaw y1: = y3
  • Jeśli y1 <y4 <y2 to generujemy prostokąt ((x1, y4), (x2, y2)); i ustaw y2: = y4
tsh
źródło
To obiecujące podejście; ale obecnie czasami zawodzi, np. gdy prostokąt maski nie pokrywa się z prostokątem źródłowym; np. f([0, 30, 10, 40])([5, 1, 6, 2])powinien wrócić, [[0, 30, 10, 40]]ale zamiast tego powraca[[0,30,5,40],[6,30,10,40]]
Chas Brown,
@NathanMerrill ok, edytowane.
tsh
@tsh wygląda dobrze!
Nathan Merrill,
1

Java, 268 bajtów

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

Nie golfił

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

Przekaż dane wejściowe jako argumenty. Przykład

java -jar W.jar 0 0 5 5 3 4 8 7
Евгений Новиков
źródło
0

Python 2 , 272 bajty

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]

Wypróbuj online!

Działa to poprzez przetestowanie każdej komórki w pierwszym prostokącie pod kątem lewości = 1, aboveness = 4, prawości = 2 i belowness = 8 w / r względem drugiej i ORing wyniku. Jeśli drugi nie przecina = 0 z pierwszym, wówczas oryginał jest zwracany, w przeciwnym razie zwracana jest kombinacja lewego plasterka, prawego plasterka, górnego plasterka i dolnego plasterka, z zakwaterowaniem dla nakładania się.

SmileAndNod
źródło