Hintergrund

Ich möchte einen Zaun bauen. Dafür habe ich ein paar Stangen gesammelt und auf den Boden geklebt. Ich habe auch viele Bretter gesammelt, die ich an die Stangen nageln werde, um den eigentlichen Zaun herzustellen. Ich neige dazu, mich beim Bauen mitreißen zu lassen, und höchstwahrscheinlich werde ich die Bretter so lange an die Stangen nageln, bis es keinen Platz mehr gibt, an dem ich sie platzieren kann. Ich möchte, dass Sie die möglichen Zäune aufzählen, mit denen ich enden kann.

Eingang

Ihre Eingabe ist eine Liste zweidimensionaler ganzzahliger Koordinaten, die die Positionen der Pole in einem beliebigen geeigneten Format darstellen. Sie können davon ausgehen, dass es keine Duplikate enthält, aber Sie können nichts über die Reihenfolge annehmen.

Die Bretter werden durch gerade Linien zwischen den Polen dargestellt, und der Einfachheit halber betrachten wir nur horizontale und vertikale Bretter. Zwei Pole können durch ein Brett verbunden werden, wenn sich keine anderen Pole oder Bretter zwischen ihnen befinden, was bedeutet, dass sich die Bretter nicht kreuzen können. Eine Anordnung von Polen und Brettern ist maximal, wenn keine neuen Bretter hinzugefügt werden können (äquivalent dazu befindet sich zwischen zwei horizontal oder vertikal ausgerichteten Polen entweder ein Pol oder ein Brett).

Ausgabe

Ihre Ausgabe ist die Anzahl der maximalen Anordnungen, die unter Verwendung der Pole konstruiert werden können.

Beispiel

Betrachten Sie die Eingabeliste

[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]

Von oben gesehen sieht die entsprechende Anordnung der Pole ungefähr so ​​aus:

  o
 o o
o    o
 o o
  o

Es gibt genau drei maximale Anordnungen, die unter Verwendung dieser Pole konstruiert werden können:

  o        o        o
 o-o      o|o      o-o
o----o   o||| o   o| | o
 o-o      o|o      o-o
  o        o        o

Somit ist die korrekte Ausgabe 3.

Regeln

Sie können entweder eine Funktion oder ein vollständiges Programm schreiben. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Testfälle

[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8

Mathematica, 301 Bytes

(t~SetAttributes~Orderless;u=Subsets;c=Complement;l=Select;f=FreeQ;Count[s=List@@@l[t@@@u[Sort@l[Sort/@#~u~{2},!f[#-#2&@@#,0]&]//.{a___,{x_,y_},{x_,z_},b___,{y_,z_},c___}:>{a,{x,y},b,{y,z},c}],f[#,t[{{a_,b_},{a_,c_}},{{d_,e_},{f_,e_}},___]/;d<a<f&&b<e<c]&],l_/;f[s,k_List/;k~c~l!={}&&l~c~k=={},{1}]])&

Dies ist eine unbenannte Funktion, die die Koordinaten als verschachtelt verwendet Listund eine Ganzzahl zurückgibt. Das heißt, Sie können ihm entweder einen Namen geben und ihn nennen oder einfach anhängen

@ {{3, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}

Mit Einrückung:

(
  t~SetAttributes~Orderless;
  u = Subsets;
  c = Complement;
  l = Select;
  f = FreeQ;
  Count[
    s = List @@@ l[
      t @@@ u[
        Sort @ l[
          Sort /@ #~u~{2}, 
          !f[# - #2 & @@ #, 0] &
        ] //. {a___, {x_, y_}, {x_, z_}, b___, {y_, z_}, c___} :> 
              {a, {x, y}, b, {y, z}, c}
      ],
      f[
        #,
        t[{{a_, b_}, {a_, c_}}, {{d_, e_}, {f_, e_}}, ___] 
          /; d < a < f && b < e < c
      ] &
    ], 
    l_ /; f[
      s, 
      k_List /; k~c~l != {} && l~c~k == {}, 
      {1}
    ]
  ]
) &

Ich kann nicht einmal anfangen auszudrücken, wie naiv diese Implementierung ist ... es könnte definitiv nicht brutaler sein ...

• Holen Sie sich alle (ungeordneten) Polpaare.
• Sortieren Sie jedes Paar und alle Paare in einer kanonischen Reihenfolge.
• Verwerfen Sie Paare, die keine gemeinsame Koordinate haben (dh die nicht durch eine orthogonale Linie verbunden sind).
• Abwurfpaare können aus zwei kürzeren Paaren gebildet werden (so dass o--o--onur zwei statt drei Zäune entstehen).
• Holen Sie sich alle Teilmengen dieser Paare - dh alle möglichen Kombinationen von Zäunen.
• Filtern Sie Kombinationen heraus, bei denen sich Zäune kreuzen.
• Zählen Sie die Anzahl der resultierenden Zaunsätze, für die in der Liste keine strikte Obermenge gefunden werden kann.

Überraschenderweise werden alle Testfälle praktisch sofort gelöst.

Ein wirklich netter Trick, den ich dafür entdeckt habe, ist die Verwendung Orderless, um die Anzahl der Muster zu reduzieren, die ich anpassen muss. Wenn ich Zaunsets mit sich kreuzenden Zäunen abgraben möchte, muss ich im Wesentlichen ein Paar vertikaler und horizontaler Zäune finden und den Zustand auf ihnen überprüfen. Aber ich weiß nicht, in welcher Reihenfolge sie erscheinen werden. Da Listenmuster normalerweise auftragsabhängig sind, würde dies zu zwei wirklich langen Mustern führen. Also ersetze ich stattdessen die umgebende Liste durch eine Funktion tmit t @@@- die nicht definiert ist, so dass sie so gehalten wird, wie sie ist. Aber diese Funktion ist Orderless, so dass ich kann nur einen einzigen Auftrag in dem Muster überprüfen, und Mathematica prüft es gegen alle Permutationen. Danach habe ich die Listen wieder mit erstellt List @@@.

Ich wünschte, es gäbe eine integrierte Funktion, die a) Orderless, b) nicht Listable und c) nicht für 0 Argumente oder Listenargumente definiert ist. Dann könnte ich das ersetzen t. Aber es scheint keinen solchen Operator zu geben.

Haskell, 318 Bytes

import Data.List
s=subsequences
k[(_,a,b),(_,c,d)]|a==c=f(\w->(1,a,w))b d|1<2=f(\w->(2,w,b))a c
f t u v=[t x|x<-[min u v+1..max u v-1]]
q l=nub[x|x<-map(k=<<)$s[a|a@[(_,n,m),(_,o,p)]<-s l,n==o||m==p],x++l==nubBy(\(_,a,b)(_,c,d)->a==c&&b==d)(x++l)]
m=q.map(\(a,b)->(0,a,b))
p l=sum[1|x<-m l,all(\y->y==x||x\\y/=[])$m l]

Verwendung : p [(1,0),(0,1),(-1,0),(0,-1)]. Ausgabe:2

Wie es funktioniert:

• Erstellen Sie alle Unterlisten der Eingabeliste und behalten Sie diese mit zwei Elementen und entweder gleichen x- oder gleichen y-Koordinaten bei. Dies ist eine Liste aller Mastenpaare, zwischen denen ein Zaun gebaut werden kann.
• Erstellen Sie alle Unterlisten davon
• füge Boards für jede Liste hinzu
• Entfernen Sie Listen, in denen eine xy-Koordinate zweimal erscheint (Bretter und Pole).
• Entfernen Sie doppelte Listen (nur Bretter), um mehrere leere Listen zu verarbeiten, da direkt benachbarte Pole (z. B. (1,0) und (1,1))
• Behalten Sie diejenigen, die keine strikte Unterliste einer anderen Liste sind
• verbleibende Listen zählen