tło

Chcę zbudować ogrodzenie. W tym celu zebrałem kilka tyczek i przyłożyłem je do ziemi. Zebrałem też wiele desek, które przykleję do słupów, aby zrobić prawdziwe ogrodzenie. Podczas budowania przedmiotów mam tendencję do uniesienia się i najprawdopodobniej po prostu przybijam deski do tyczek, dopóki nie będzie już miejsca na ich ułożenie. Chcę, żebyś wyliczył możliwe ogrodzenia, z którymi mogę skończyć.

Wejście

Twoje dane wejściowe to lista dwuwymiarowych współrzędnych całkowitych reprezentujących pozycje biegunów, w dowolnym dogodnym formacie. Możesz założyć, że nie zawiera duplikatów, ale nie możesz zakładać niczego o jego kolejności.

Deski są reprezentowane przez proste linie między biegunami, a dla uproszczenia rozważamy tylko poziome i pionowe deski. Deska może być połączona z dwoma biegunami, jeśli nie ma między nimi innych biegunów lub desek, co oznacza, że ​​deski nie mogą się przecinać. Rozmieszczenie biegunów i desek jest maksymalne, jeśli nie można do niego dodać żadnych nowych desek (równoważnie, między dowolnymi dwoma biegunami ustawionymi poziomo lub pionowo jest słup lub deska).

Wynik

Twój wynik to liczba maksymalnych układów, które można zbudować za pomocą biegunów.

Przykład

Rozważ listę danych wejściowych

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

Patrząc z góry odpowiedni układ biegunów wygląda mniej więcej tak:

  o
 o o
o    o
 o o
  o

Istnieją dokładnie trzy maksymalne układy, które można zbudować za pomocą tych biegunów:

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

Zatem prawidłowe wyjście to 3.

Zasady

Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

[] -> 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 bajtów

(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}]])&

Jest to funkcja bez nazwy, która przyjmuje współrzędne jako zagnieżdżone Listi zwraca liczbę całkowitą. Oznacza to, że możesz nadać mu nazwę i nazwać ją lub po prostu dołączyć

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

Z wcięciem:

(
  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}
    ]
  ]
) &

Nie potrafię nawet wyrazić, jak naiwna jest ta implementacja ... zdecydowanie nie może być bardziej brutalna ...

• Zbierz wszystkie (nieuporządkowane) pary biegunów.
• Posortuj każdą parę i wszystkie pary w kolejności kanonicznej.
• Odrzuć pary, które nie mają jednej współrzędnej (tj. Których nie można połączyć linią ortogonalną).
• Pary odrzucone można utworzyć z dwóch krótszych par (tak, że o--o--odają tylko dwa ogrodzenia zamiast trzech).
• Uzyskaj wszystkie podzbiory tych par - tj. Wszystkie możliwe kombinacje ogrodzeń.
• Odfiltruj kombinacje, które krzyżują się ze sobą.
• Policz liczbę wynikowych zestawów ogrodzenia, dla których nie można znaleźć ścisłego nadzorca na liście.

Zaskakująco rozwiązuje wszystkie przypadki testowe praktycznie natychmiast.

Naprawdę fajną sztuczką, którą odkryłem w tym celu, jest Orderlessograniczenie liczby wzorów, które muszę dopasować. Zasadniczo, gdy chcę porzucić zestawy ogrodzeń za pomocą ogrodzeń krzyżowych, muszę znaleźć parę ogrodzenia pionowego i poziomego i sprawdzić na nich stan. Ale nie wiem, w jakiej kolejności będą się pojawiać. Ponieważ wzorce list są zwykle zależne od kolejności, powstałyby dwa naprawdę długie wzorce. Zamiast tego zastępuję otaczającą listę funkcją tz t @@@- która nie jest zdefiniowana, więc jest utrzymywana bez zmian. Ale ta funkcja jest Orderlesstaka, że mogę po prostu sprawdzić pojedyncze zamówienie we wzorcu, a Mathematica sprawdzi je pod kątem wszystkich permutacji. Następnie ponownie umieszczam listy za pomocą List @@@.

Żałuję, że nie ma wbudowanej funkcji, która jest a) Orderless, b) nie Listable i c) nie zdefiniowana dla 0 argumentów lub listy argumentów. Wtedy mógłbym to zastąpić t. Ale wydaje się, że nie ma takiego operatora.

Haskell, 318 bajtów

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]

Zastosowanie: p [(1,0),(0,1),(-1,0),(0,-1)]. Wynik:2

Jak to działa:

• utwórz wszystkie listy podrzędne listy wejściowej i zachowaj te z dwoma elementami i równymi współrzędnymi x lub równymi y. To jest lista wszystkich par słupów, pomiędzy którymi można zbudować ogrodzenie.
• utwórz z niego wszystkie podlisty
• dodaj tablice do każdej listy
• usuń listy, w których współrzędna xy pojawia się dwukrotnie (tablice i bieguny)
• usuń zduplikowane listy (tylko tablice), aby obsłużyć wiele pustych list z powodu bezpośrednio sąsiadujących biegunów (np. (1,0) i (1,1))
• zachowaj te, które nie są ścisłą listą podrzędną innej listy
• policz pozostałe listy