Rechteckkreuzungen zählen

8

Die Herausforderung

Geben Sie bei einer beliebigen Anzahl von Rechtecken die Gesamtzahl der Schnittpunkte dieser Rechtecke aus, wenn diese in einer 2D-Ebene gezeichnet werden.

Ein Schnittpunkt ist hier definiert als ein Punkt, Pder von zwei Linien gekreuzt wird, die orthogonal zueinander sind und beide nicht enden P.

Beispiel

Jedes Rechteck wird hier durch ein 2-Tupel gekennzeichnet, wobei die Koordinaten der oberen linken Ecke zuerst und die Koordinaten der unteren rechten Ecke an zweiter Stelle stehen.

[(-8,6), (-4, -2)]
[(-4,9), (4,3)]
[(2,10), (14,4)]
[(1,7), (10, -6)]
[(7,4), (10,2)]
[(5,2), (9, -4)]
[(-6, -4), (-2, -6)]

Geben Sie hier die Bildbeschreibung ein

Diese Rechtecke erzeugen 6 Schnittpunkte, die Ihre Ausgabe sein müssen.

  • Wie Sie im obigen Bild sehen können, werden durch Berühren von Rechtecken hier keine Schnittpunkte erstellt und nicht gezählt.
  • Sie können die Rechtecke in jedem gewünschten Format codieren. Machen Sie deutlich, welches Format Sie verwenden.
  • Wenn sich mehrere Rechtecke am selben Punkt schneiden, zählt dies nur als ein Schnittpunkt.
  • Die Koordinaten sind immer ganze Zahlen.
  • Die Eingabe enthält keine doppelten Rechtecke.
  • Sie erhalten immer mindestens ein Rechteck als Eingabe.
  • Sie dürfen keine integrierten Funktionen verwenden, die dieses Problem direkt lösen. Außerdem dürfen Sie keine integrierten Funktionen verwenden, die Gleichungen lösen. Alle anderen Einbauten sind erlaubt.
  • Die Ausgabe muss eine einzelne Ganzzahl sein, die die Anzahl der Schnittpunkte angibt.

Regeln

  • Funktion oder volles Programm erlaubt.
  • Standardregeln für die Eingabe / Ausgabe.
  • Es gelten Standardlücken .
  • Dies ist Code-Golf , also gewinnt die niedrigste Byte-Anzahl. Tiebreaker ist eine frühere Einreichung.

Testfälle

Gleiches Format wie im obigen Beispiel. Die Rechtecke werden in eine Liste eingeschlossen.

[[(-8,6), (-4, -2)], [(-4,9), (4,3)], [(2,10), (14,4)], [(1 , 7), (10, -6)], [(7,4), (10,2)], [(5,2), (9, -4)], [(-6, -4), (-2, -6)]] -> 6
[[(-2,2), (6, -4)]] -> 0
[[(-12,10), (- 8,6)], [(- 14,6), (- 10,2)], [(- 10,6), (- 6,2)]] - > 0
[[(-4,10), (6,2)], [(- 2,8), (4,3)], [(1,6), (8,4)], [(2,11 ), (5,5)]] -> 10
[[(8,2), (12, -2)], [(10,0), (14, -4)] -> 2
[[(0,2), (2,0)], [(0,1), (3,0)]] -> 1
[[(-10, -2), (-6, -6)], [(-6, -2), (-2, -6)], [(-8, -4), (-4, -8)]] -> 3

Viel Spaß beim Codieren!

code-golf math geometry grid Denker
quelle
Sie müssen definieren, was die Antworten zählen sollen, da laut Diagramm viele Punkte im Schnittpunkt von zwei oder mehr Rechtecken anscheinend ignoriert werden.
Feersum
1
Hätte [[(0,0),(1,2)],[(0,0),(2,1)]]ich also 1 Kreuzung?
Neil
@Neil Genau. Ich werde diesen Testfall hinzufügen, danke!
Denker
@feersum Ich denke, das Diagramm macht ziemlich klar, was zu zählen ist und was nicht. Aber eine formale Definition würde wohl nicht schaden, ich werde eine hinzufügen.
Denker
1
Wenn es N Rechteckpaare gibt, die sich bei (x, y) schneiden, wird der Punkt (x, y) einmal oder N-mal gezählt?
Feersum

Antworten:

2

JavaScript (ES6), 186 Bytes

a=>a.map(([a,b,c,d])=>h.push([b,a,c],[d,a,c])&v.push([a,b,d],[c,b,d]),h=[],v=[])|h.map(([d,a,e])=>v.map(([c,f,b])=>a<c&c<e&b<d&d<f&t.every(([a,b])=>a-c|b-d)&&t.push([c,d])),t=[])|t.length

Teilt jedes Rechteck in seine Komponentenlinien, schneidet dann die horizontalen und vertikalen Linien und erstellt eine Liste von Schnittpunkten, um Duplikate zu vermeiden.

Neil
quelle
Welches Eingabeformat verwenden Sie? Wenn ich das mit den Tastcases nenne, bekomme ich immer Null.
Denker
@DenkerAffe Sorry, ich hätte sagen sollen, ich erwarte ein Array von Arrays mit 4 Elementen, z [[-4,10,6,2],[-2,8,4,3],[1,6,8,4],[2,11,5,5]]. Da JavaScript keine Tupel enthält, hätten Sie, wenn Sie versucht hätten, Ihre Beispiele wörtlich zu verwenden, stattdessen den Kommaoperator ausgelöst und die Eingabe ungültig gemacht.
Neil
Gut, danke. Dies ergibt jedoch 4 statt 3 für den letzten Testfall, da Schnittpunkte mehrerer Rechtecke nur als ein Schnittpunkt zählen. Ich habe das geklärt, nachdem du deine Antwort gepostet hast, denke ich, also geht diese auf mich los. Ich hoffe, es ist nicht zu schwer, dies zu beheben. Entschuldigen Sie die Unannehmlichkeiten.
Denker
@DenkerAffe Ich habe es aktualisiert, um mit Ihrer neuen Spezifikation zu arbeiten.
Neil
0

Mathematica 138 Bytes

Nicht beendet! Dies funktioniert in allen Fällen außer[[(0,0),(1,2)],[(0,0),(2,1)]]

Length@Union[Join@@(Cases[RegionIntersection@@# &/@Subsets[Line[{{#,#2},{#3,#2},{#3,#4},{#,#4},{#,#2}}]&@@@Flatten/@#,{2}],Point@a__:> a])]

Beispiel

Length@Union[
Join @@ (Cases[RegionIntersection @@ # & /@ Subsets[
Line[{{#, #2}, {#3, #2}, {#3, #4}, {#, #4}, {#, #2}}] & @@@ Flatten /@ #, {2}], 
Point@a__ :> a])] &@{{{-8, 6}, {-4, -2}}, {{-4, 9}, {4, 3}}, {{2, 10}, {14, 4}}, 
{{1, 7}, {10, -6}}, {{7, 4}, {10, 2}}, {{5, 2}, {9, -4}}, {{-6, -4}, {-2, -6}}}

6

DavidC
quelle