Wkład

Twój wkład w to wyzwanie jest listą liczb całkowitych. Reprezentują południowo-zachodnie rogi kwadratów jednostek na płaszczyźnie, a lista przedstawia ich związek jako podzbiór płaszczyzny. Na przykład lista

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

przedstawia czerwony zestaw na tym obrazku:

Wydajność

Dane wyjściowe to lista poczwórnych liczb całkowitych reprezentujących prostokątne podzbiory płaszczyzny. Mówiąc (x,y,w,h)ściślej, czteroosobowy przedstawia prostokąt o szerokości w > 0i wysokości, h > 0którego południowo-zachodni róg jest (x,y). Prostokąty muszą tworzyć dokładne pokrycie obszaru wejściowego, w tym sensie, że każdy z kwadratów jednostkowych jest podzbiorem jakiegoś prostokąta, każdy prostokąt jest podzbiorem regionu, a dwa prostokąty mogą zachodzić na siebie tylko na swoich granicach. Aby zabronić trywialnych rozwiązań, pokrycie nie może zawierać dwóch prostokątów, które można połączyć w większy prostokąt.

Na przykład lista

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

reprezentuje ochronę prawną

z powyższego regionu, natomiast pokrycie udzielone przez

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

jest nielegalne, ponieważ sąsiednie kwadraty 1 na 1 można połączyć:

Zasady

Możesz podać pełny program lub funkcję. Dokładne formatowanie danych wejściowych i wyjściowych nie jest ważne z uzasadnionego powodu. Wygrywa najkrótsza liczba bajtów, a standardowe luki są niedozwolone. Zachęcamy do wyjaśnienia swojego algorytmu i kilku przykładowych wyników.

Przypadki testowe

Region w kształcie litery U:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]

Duży trójkąt:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]

Kwadrat z otworami:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]

Odłączone regiony:

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

Weryfikator

Użyj tego programu Python 2, aby zweryfikować swoje rozwiązanie. Pobiera ze STDIN listę krotek (dane wejściowe) i listę poczwórnych (dane wyjściowe), oddzielonych przecinkiem.

Napisałem również ten program w języku Python 2 do generowania zdjęć i możesz go również używać. Pobiera ze STDIN listę krotek lub poczwórnych i tworzy plik o nazwie out.png. Wymaga biblioteki PIL. Jeśli chcesz, możesz zmienić rozmiar komórek siatki i szerokość linii podpaskowych.

Python: 196 193 182 znaków

def g(r):
 for p in r:
  for q in r:
   for h in 0,1:
    if p[h::2]==q[h::2]and p[1-h]+p[~h]==q[1-h]:p[~h]+=q[~h];r.remove(q);return g(r)
 return r
f=lambda P:g([x+[1,1]for x in P])

Moje pierwsze rozwiązanie wykorzystywało dokładnie ten sam algorytm co KSFT, dlatego eksperymentowałem z innymi metodami.

Najpierw robię wstępne przetwarzanie, przekształcam wszystkie punkty w małe prostokąty 1x1 {x+(1,1)for x in P}. Z tymi prostokątami wywołuję funkcję g. giteruje każdą kombinację prostokątów. Jeśli znajdzie 2 prostokąty, które można połączyć w większy, usuwa oba i dołącza nowy. Następnie nazywa się nowym zestawem prostokątów.

Stosowanie

f([[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]])

Wyniki

Oto wizualizacja wyników. Pamiętaj, że mogą się one nieco różnić w bieżącej wersji. Chodzi o to, że nie ma żadnego zauważalnego wzoru.

Region w kształcie litery U:

Duży trójkąt

Kwadrat z otworami:

Odłączone regiony:

Dla zabawy: Pyth: 73 69 znaków

D!HFGHFZHV2I&q%2>GN%2>ZNqs%2>G-1N@Z-1N X-3NG@Z-3NR!-H]Z)))RH!m+d*2]1Q

Działa tylko w wersji offline. Błąd w wersji online został już naprawiony. Wypróbuj tutaj: Pyth Compiler / Executor . Oczekuje listy list, a nie listy krotek.

edit: Użyłem pomysłu z @ edc65: Zamiast usuwać oba prostokąty i tworzyć nowy, manipuluję jednym i tylko usuwam jeden. W rozwiązaniu Python mogłem uzyskać dostęp do zestawów i rzutów tuple-list-tuple. -11 znaków w Pythonie / -4 znaków w Pyth

Python - 272 261 258 251 224

Myślę, że mogę bardziej golfa. Jestem pewien, że to działa, ale jeszcze nie skończyłem testowania na wszystkich testowych przypadkach. Skończyłem testować. Działa dla wszystkich przypadków testowych.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h

Pracuję nad dodaniem zdjęć wyników. Edycja: Oto wyniki z przykładu i przypadków testowych:

Próbuję napisać to w Perlu, ale nie potrafię wymyślić, jak uzyskać wielowymiarowe tablice ze standardowego wejścia bez ogromnej liczby znaków. Czy ktoś ma jakieś sugestie?

Python 2, 139

Program akceptuje listy uporządkowanych par otoczonych nawiasami klamrowymi na standardowym wejściu. Na przykład,{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)}

s=input()
while s:x,y=min(s);w=h=0;exec"while(x+w,y)in s:w+=1\nwhile%s<=s:s-=%s;h+=1"%(("{(X,y+h)for X in range(x,x+w)}",)*2);print x,y,w,h

Często denerwujące (nie tylko w golfie) jest to, że Python nie pozwala na przypisanie w teście pętli. Aby obejść ten problem, użyłem operacji formatowania łańcucha.

Mathematica - 315 285 267 bajtów

f=(r={};For[m=MemberQ;t=Table;s=Sort@#,s!={},For[{x,y,w,h}=#~Join~{1,1}&@@s;i=j=0,i<1||j<1,If[s~m~{x+w,y+a-1}~t~{a,h}==True~t~{h},w++,i++];If[s~m~{x+a-1,y+h}~t~{a,w}==True~t~{w},h++,j++]];s=s~Cases~_?(!m[Join@@t[{x+a,y+b}-1,{a,w},{b,h}],#]&);r~AppendTo~{x,y,w,h}];r)&

Z pewną pomocą @ MartinBüttner.

Nie golfowany:

f = (
    rectangles = {};
    For[squares = Sort[#], squares != {},
        For[{x, y, w, h} = Join[squares[[1]], {1, 1}]; i = j = 0, i < 1 || j < 1,
            If[Table[MemberQ[squares, {x + w, y + a - 1}], {a, h}] == Table[True, {h}], w++, i++];
            If[Table[MemberQ[squares, {x + a - 1, y + h}], {a, w}] == Table[True, {w}], h++, j++];
        ];
        squares = Cases[squares, _ ? (!MemberQ[Join@@Table[{x + a - 1, y + b - 1}, {a, w}, {b, h}], #] &)];
        AppendTo[rectangles, {x, y, w, h}]
    ];
    rectangles
)&

Stosowanie:

In: f @ {{0,0},{1,0},{0,1},{1,1},{2,1},{1,2},{2,2}}
Out: {{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Przypadki testowe

Region w kształcie litery U.

{{0, 0, 6, 2}, {0, 2, 2, 4}, {4, 2, 2, 4}}

Duży trójkąt

{{0, 0, 6, 5}, {0, 5, 3, 3}, {0, 8, 2, 1}, {0, 9, 1, 1}, {3, 5, 2, 1}, {3, 6, 1, 1}, {6, 0, 3, 2}, {6, 2, 2, 1}, {6, 3, 1, 1}, {9, 0, 1, 1}}

Kwadrat z dziurami

{{0, 0, 6, 3}, {0, 3, 3, 6}, {1, 9, 9, 1}, {3, 4, 3, 2}, {3, 6, 2, 3}, {4, 3, 6, 1}, {5, 7, 5, 2}, {6, 1, 4, 2}, {6, 5, 4, 2}, {7, 0, 3, 1}, {7, 4, 3, 1}}

Odłączone regiony

{{0, 0, 2, 5}, {0, 5, 1, 4}, {1, 6, 2, 4}, {2, 1, 1, 5}, {4, 0, 3, 3}, {4, 4, 3, 6}, {5, 3, 1, 1}, {8, 0, 3, 4}, {8, 4, 1, 6}, {9, 7, 2, 3}, {10, 4, 1, 3}}

Haskell, 158

f[]=[]
f s@((x,y):_)=(x,y,w-x,h-y):f[r|r@(a,b)<-s,a<x||a>=w||b<y||b>=h]where w=[i|i<-[x..],notElem(i,y)s]!!0;h=[i|i<-[y..],not$all(\x->elem(x,i)s)[x..w-1]]!!0

przypadki testowe i zdjęcia będą wkrótce dostępne.

Algorytm: weź pierwszy kwadrat. Dotrzyj jak najdalej w prawo, nie napotykając kwadratu poza wejściem. Następnie sięgnij tak daleko, jak to możliwe, bez kwadratu na wejściu. Teraz mamy prostokąt bez brakującego kwadratu. Dodaj go do wyjścia, usuń wszystkie jego kwadraty z wejścia i wywołaj rekurencyjnie.

JavaScript (ES6) 148 155 199

Edycja2 Jeszcze więcej tuningu
Edytuj Niektóre golfa + przepisz używając rekurencji. Nie spodziewałem się takiej redukcji. Teraz jest trochę trudny do naśladowania, ale algorytm jest taki sam.

Algorytm jest podobny do odpowiedzi @jakube.

1. Każdy punkt staje się kwadratem 1x1 (przetwarzanie wstępne)
2. Dla każdego elementu sprawdź, czy można go połączyć z innym
   Tak? Pierwszy element rośnie, drugi element jest usuwany, zacznij od kroku 2 W przeciwnym razie
   przejdź do następnego elementu

F=l=>
  (l.map(x=>x.push(1,1)),R=f=>
    l.some(u=>
      (l=l.filter(t=>
        [0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))
      ),f)
    )?R():l
  )()

Testuj we fragmencie

F=l=>(l.map(x=>x.push(1,1)),R=f=>l.some(u=>(l=l.filter(t=>[0,1].every(p=>u[p]-t[p]|u[p^=2]-t[p]|u[p^=3]-t[p]+u[p^=2]||!(f=u[p]+=t[p]))),f))?R():l)()

// Test
MyCanvas.width= 600;
MyCanvas.height = 220;
var ctx = MyCanvas.getContext("2d");
ctx.fillStyle="#f23";

Draw=(x,y,f,l)=>l.forEach(p=>ctx.fillRect(x+p[0]*f,y+p[1]*f,p[2]*f-1||f-1,p[3]*f-1||f-1));

test=[
[[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[2,0],[2,1],[3,0],[3,1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[5,0],[5,1],[5,2],[5,3],[5,4],[6,0],[6,1],[6,2],[6,3],[7,0],[7,1],[7,2],[8,0],[8,1],[9,0]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[3,0],[3,1],[3,2],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,7],[5,8],[5,9],[6,1],[6,2],[6,3],[6,5],[6,6],[6,7],[6,8],[6,9],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9]],
[[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[1,0],[1,1],[1,2],[1,3],[1,4],[1,6],[1,7],[1,8],[1,9],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[4,0],[4,1],[4,2],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[6,0],[6,1],[6,2],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[9,0],[9,1],[9,2],[9,3],[9,7],[9,8],[9,9],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]
]

Draw(0,0,10,test[0]),Draw(0,110,10,F(test[0]))
Draw(50,0,10,test[1]),Draw(50,110,10,F(test[1]))
Draw(130,0,10,test[2]),Draw(130,110,10,F(test[2]))
Draw(250,0,10,test[3]),Draw(250,110,10,F(test[3]))
Draw(370,0,10,test[4]),Draw(370,110,10,F(test[4]))

<canvas id=MyCanvas></canvas>

Mathematica, 153 151 144 136 133

Sort[{##,1,1}&@@@Input[]]//.{a___,r:{x_,y_,__},b___,{X_,Y_,W_,H_},c___}/;r=={x,Y,X-x,H}||r=={X,y,W,Y-y}:>{a,r+Sign@{0,0,X-x,Y-y},b,c}

Przykład:

Wkład:

{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 1}, {1, 2}, {2, 2}}

Wydajność:

{{0, 0, 2, 2}, {1, 2, 2, 1}, {2, 1, 1, 1}}

Wkład:

{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {2, 9}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {3, 9}, {4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 7}, {5, 8}, {5, 9}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {6, 9}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 5}, {8, 6}, {8, 7}, {8, 8}, {8, 9}, {9, 0}, {9, 1}, {9, 2}, {9, 3}, {9, 4}, {9, 5}, {9, 6}, {9, 7}, {9, 8}, {9, 9}}

Wydajność:

{{0, 0, 3, 9}, {1, 9, 9, 1}, {3, 0, 3, 3}, {3, 4, 1, 5}, {4, 3, 1, 6}, {5, 3, 1, 3}, {5, 7, 1, 2}, {6, 1, 1, 3}, {6, 5, 1, 4}, {7, 0, 3, 9}}

Algorytm:

Przykryj region kwadratami jednostek, a następnie scal je.