Rechteckiger Unterschied

20

In dieser Herausforderung erhalten Sie zwei überlappende Rechtecke und müssen die Rechtecke berechnen, die durch Entfernen der Rechtecke voneinander erstellt wurden.

Wenn Sie beispielsweise das rote Rechteck vom schwarzen entfernen:

Rechtecke

Am Ende haben Sie eine der folgenden beiden Rechteckmengen:

Split-One zwei Teile

Sie müssen auch Folgendes erledigen:

Alle Testfälle

Genauer gesagt:

  • Sie geben die Koordinaten der beiden Rechtecke A und B ein.
  • Sie müssen die wenigsten nicht überlappenden Rechtecke ausgeben, die den gesamten Bereich von A ohne B abdecken. Jede mögliche Abdeckung ist zulässig
  • Rechteckige Koordinaten werden als 4 Ganzzahlen übergeben. Sie können sie in zwei Paaren (die zwei Eckpunkte darstellen) oder als Tupel / Liste mit 4 ganzen Zahlen übergeben. Ihre Ein- und Ausgänge müssen konsistent sein.
  • A und B müssen sich nicht unbedingt überlappen oder berühren, und jeder hat eine Fläche von mindestens 1

Testfälle:

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

Dies ist ein , also mach deinen Code so kurz wie möglich!

Nathan Merrill
quelle
3
Verbunden.
Martin Ender
1
können wir davon ausgehen, dass die angegebene Eingabe {(x1, y1), (x2, y2)}gilt x1 < x2und y1 < y2?
tsh
Ja. Das Rechteck hat eine Fläche von 1 und Sie können die Koordinaten in beliebiger Reihenfolge anordnen.
Nathan Merrill
Ist die Kante dick? Wenn das definierte Rechteck die Kante enthält?
Евгений Новиков
Die Kante hat 0 Dicke.
Nathan Merrill

Antworten:

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

Probieren Sie es online!

EDITS: -15 von Vorschlägen von @notjagan; eine weitere -15 durch Neucodierung des Arrays von Lösungsrechtecken in das Int36-Format und eine kurze Nachschlagetabelle; ein weiteres -2 durch Ersetzen des Produkts durch p gemäß @musicman.

Eine Funktion, die zwei Rechtecke akzeptiert, wobei jedes Rect ein Tupel von ((links, oben), (rechts, unten)) ist. gibt eine Liste der resultierenden Rechtecke zurück.

Die Grundstrategie:

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

Im obigen Diagramm befinden sich die Punkte A und B oben links und unten rechts im Rechteck 'Source' (das erste Rechteck).

Wir finden die Position des oberen linken (u,v)und unteren rechten (x,y)Bereichs des 'Mask'-Rechtecks ​​in diesem Raster.

Wenn sich beide Punkte in der ersten oder letzten Spalte befinden; oder erste oder letzte Reihe; dann gibt es keine Überlappung; und wir können nur die Quelle rect zurückgeben.

Ansonsten verbleiben 16 Fälle. Das erste Beispiel des OP ist beispielsweise der Fall, den wir kennzeichnen können (1,1),(2,2). Jeder Fall kann einer Reihe von resultierenden Rechtecken zugeordnet werden, deren Ecken immer mit horizontalen Werten in den Quellrechtecken links, rechts oder den Maskenrechtecken links, rechts koordiniert sind. und in ähnlicher Weise für die vertikalen Werte, die oberen, unteren oder die Masken der Quelle.

Zum Beispiel für den (1,1),(2,2)Fall, würden die Rechtecken sein ((l,t),(T,r))und ((l,T),(R,b)), wo l,t,r,bund L,T,R,Bsind links, oben, rechts und unten auf der Quelle und Rechtecke Maske ist.

So können wir eine Nachschlagetabelle erstellen, die die Koordinaten der Menge aller möglichen Kombinationen (worum es bei dem product(product(*zip(*)))Bit geht) auf eine Menge von Rechtecken abbildet, die für jeden der Fälle (nach einer gewissen Golf-Dekomprimierung) bereitgestellt werden sollten , darum geht es im Rest der Liste).

Chas Brown
quelle
-15 Bytes durch verschiedene Verbesserungen beim Golfen oder -18 Bytes mit Strings in Python 3.
notjagan
Sie können aus zwei Bytes schnippeln , indem Sie p=productund Ersetzen product(productmitp(p
musicman523
3

JavaScript, 115 Byte

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)

überlappende Version:

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)

Eingabe in folgendem Format: f([1,1,8,8])([0,6,9,9])


Bezeichnen Sie die Eingabe als ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

Wenn eine der folgenden Bedingungen erfüllt ist, geben Sie das erste Rechteck wie folgt zurück:

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

Andernfalls

  • Wenn x1 <x3 <x2, dann erzeugen wir ein Rechteck ((x1, y1), (x3, y2)); und setze x1: = x3
  • Wenn x1 <x4 <x2, dann erzeugen wir ein Rechteck ((x4, y1), (x2, y2)); und setze x2: = x4
  • Wenn y1 <y3 <y2, dann erzeugen wir ein Rechteck ((x1, y1), (x2, y3)); und setze y1: = y3
  • Wenn y1 <y4 <y2, dann erzeugen wir ein Rechteck ((x1, y4), (x2, y2)); und setze y2: = y4
tsh
quelle
Dies ist ein vielversprechender Ansatz. Derzeit schlägt dies jedoch manchmal fehl, z. B. wenn das Maskenrechteck nicht mit dem Quellrechteck überlappt. zB f([0, 30, 10, 40])([5, 1, 6, 2])sollte zurückkehren, [[0, 30, 10, 40]]sondern kehrt zurück[[0,30,5,40],[6,30,10,40]]
Chas Brown
@ NathanMerrill ok, bearbeitet.
TSH
@tsh sieht gut aus!
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]));
                }
            }
        }
    }
}

Übergeben Sie die Eingabe als Argumente. Beispiel

java -jar W.jar 0 0 5 5 3 4 8 7
Евгений Новиков
quelle
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]

Probieren Sie es online!

Dies funktioniert, indem jede Zelle im ersten Rechteck auf leftness = 1, aboveness = 4, rightness = 2 und belowness = 8 w / r für die andere getestet und das Ergebnis einer OR-Verknüpfung unterzogen wird. Wenn das andere nicht = 0 mit dem ersten schneidet, wird das Original zurückgegeben, andernfalls wird eine Kombination aus einem linken Slice, einem rechten Slice, einem oberen Slice und einem unteren Slice mit Überlappungsmöglichkeit zurückgegeben.

SmileAndNod
quelle