Diese Herausforderung basiert auf einer anderen ähnlichen Herausforderung. Da das Finden der effizientesten Packung von Rechtecken NP-schwer ist (dh die Lösung ist leicht zu überprüfen, aber schwer zu finden), ist diese Herausforderung viel einfacher als diese hier

Diese Herausforderung

Stellen Sie anhand einer Reihe von Rechtecken fest, ob sie einen rechteckigen Raum ohne Lücken oder Überlappungen ausfüllen.

Eingang

Die Eingabe kann in zwei Formen erfolgen, von denen eine mit einer Strafstrafe verbunden ist.

Das erste: Es enthält eine Liste von Unterlisten mit einer Länge von jeweils 4. Diese Liste enthält 4 Ganzzahlen, die die Koordinaten entgegengesetzter Scheitelpunkte sind. Da alle Rechtecke horizontal / vertikal sind, gibt es keine Unklarheit darüber, wo sich das Rechteck befindet. Jede Unterliste enthält vier Ganzzahlen, die der Reihe nach die x-Koordinate des ersten Scheitelpunkts, die y-Koordinate des ersten Scheitelpunkts, die x-Koordinate des zweiten Scheitelpunkts und die y-Koordinate des zweiten Scheitelpunkts sind.

Das zweite: Es enthält vier Listen von Ganzzahlen mit derselben Länge. Die vier Listen repräsentieren die verschiedenen Koordinaten. Wenn Sie sich die Eingabeoption 1 als Matrix vorstellen, ist die Eingabe hier nur die Transponierte der Matrix. Diese Eingabe trägt eine +20%Byte-Strafe.

Ausgabe

Einfache Wahrheits- / Falschausgabe.

Spezifikationen

Wenn es ein Rechteck mit dem Bereich 0 gibt (dh x1 == x2 || y1 == y2), ignorieren Sie dieses Rechteck ( [0 0 1 1], [2 2 3 2]ist also gültig). Diese Spezifikation soll es den Menschen erschweren, einfach die min / max x / y-Werte zu erhalten.

x1 <= x2und y1 <= y2sind nicht immer wahr. Wenn x1 > x2 || y1 > y2das Rechteck kein Nullbereichsrechteck ist; Vielmehr nimmt es den rechteckigen Raum zwischen (x1, y1)und ein (x2, y2).
Koordinaten können negativ sein. In diesem Fall belegen sie immer noch den Raum zwischen den Koordinaten.
Das Rechteck ganz links befindet sich nicht immer bei (0, 0). Daher muss der rechteckige Raum, der ausgefüllt wird, nicht unbedingt in der oberen linken Ecke liegen (0, 0).
(Vielen Dank an @xnor für den Hinweis auf diese Unklarheiten)

Bitte geben Sie an, wie Sie Ihre Eingabe wünschen und wie Ihre Ausgabe dargestellt wird.

Wertung

Die Punktzahl ist die Größe des Codes in Bytes zuzüglich einer Byte-Strafe, falls zutreffend. Die niedrigste Punktzahl am 15. Dezember gewinnt.

Testfälle

0 0 1 2
1 0 3 1 ==> true
1 1 3 2

0 0 2 2
0 0 1 1 ==> false
0 0 0 0

0 0 1 1
2 2 2 2 ==> true
0 1 2 1

Viel Glück, viel Spaß beim Golfen!

JavaScript (ES6), 249 Byte

with(Math)a=>!(a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]).filter(g=([l,t,r,b])=>(r-l)*(b-t))).reduce((s,b)=>s-g(b),g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))

Hinweis: Um dies zu verwenden, werten Sie es entweder als Zeichenfolge aus und weisen Sie das Ergebnis einer Variablen zu, oder fügen Sie die Zuweisung nach dem ein with(Math). Erläuterung:

with(Math)a=>!(Bringen Sie minund maxin den Geltungsbereich.
a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b])Koordinieren der Koordinaten
.filter(g=([l,t,r,b])=>(r-l)*(b-t)))Entfernen Sie leere Rechtecke und definieren Sie eine Funktion zur Berechnung der Fläche.
.reduce((s,b)=>s-g(b),Subtrahieren Sie die Flächen aller Rechtecke
g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))vom Bereich des Begrenzungsrahmens
>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))und stellen Sie sicher, dass sich keine Rechtecke überlappen.

Mathematica, 194 Bytes

(r=Select[#,(#-#3)(#2-#4)&@@#>0&];m={#~Min~#3,#2~Min~#4,#~Max~#3,#2~Max~#4}&@@Transpose@r;b=Boole[(x-#)(x-#3)<0&&(y-#2)(y-#4)<0]&;Integrate[(Plus@@(b@@@r)-b@@m)^2,{x,#,#3}&@@m,{y,#2,#4}&@@m]<1)&

Eine ungolfed Version:

1  (r = Select[#1, (#1 - #3) (#2 - #4) & @@ #1 > 0 &]; 
2   m = {Min[#1, #3], Min[#2, #4], Max[#1, #3], Max[#2, #4]} & @@ Transpose[r]; 
3   b = Boole[(x - #1) (x - #3) < 0 && (y - #2) (y - #4) < 0] &;
4   Integrate[
5     (Plus @@ (b @@@ r) - b @@ m)^2 ,
6     {x, #1, #3} & @@ m ,
7     {y, #2, #4} & @@ m
8   ] < 1
9  ) &

Zeile 1 definiert rals die Menge nichttrivialer Rechtecke aus der angegebenen Eingabe. ( & @@In diesem Code ist viel los; nur damit wir ihn #1,#2,#3,#4für die vier Elemente einer Liste verwenden können #[[1]],#[[2]],#[[3]],#[[4]].) Dann definiert Zeile 2 mdie Koordinaten des kleinsten Rechtecks, das alle in aufgelisteten begrenzt r. Wenn die Eingaberechtecke ein großes Rechteck kacheln, muss dieses große Rechteck sein m.

Zeile 3 definiert eine Funktion, bdie bei Anwendung auf ein Vierfach, das ein Rechteck darstellt, eine Funktion aus zwei Variablen erzeugt xund ygleich 1 ist, wenn sich der Punkt (x,y)innerhalb des Rechtecks ​​befindet, und 0, wenn dies nicht der Fall ist. Zeile 5 erzeugt viele dieser Funktionen, eine für jedes Rechteck in r(alle addiert) und eine letzte für das große Rechteck m(subtrahiert); Diese komplizierte Zwei-Variablen-Funktion wird dann quadriert.

Der Schlüssel an dieser Stelle ist, dass diese Funktion mit zwei Variablen identisch 0 ist, wenn die kleinen Rechtecke das große Rechteck kacheln, aber einige positive Werte hat, wenn sich zwei kleine Rechtecke überlappen, oder einige negative Werte (vor dem Quadrieren), wenn ein Teil des großen Rechtecks ​​wird nicht abgedeckt. Wir erkennen dies, indem wir die Zwei-Variablen-Funktion buchstäblich über das große Rechteck integrieren (!) (Die Integrationsgrenzen sind in den Zeilen 6-7 angegeben): Wenn wir 0 erhalten, war die Kachelung perfekt, und wenn wir einen positiven Wert erhalten Dann gab es irgendwo ein Problem. Da alles in Sichtweite eine Ganzzahl ist, speichern wir ein letztes Byte < 1anstelle von == 0in Zeile 8.

(Ich denke, es macht ziemlich Spaß, dass wir Mathematicas Fähigkeit nutzen können, Kalkül zu machen, um dieses kombinatorische Problem zu lösen.)