вход

Ваш вход в этот вызов представляет собой список целочисленных пар. Они представляют юго-западные углы единичных квадратов на плоскости, а список представляет их объединение как подмножество плоскости. Например, список

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

представляет красный набор на этой картинке:

Выход

Yor output - это список целочисленных четверок, представляющих прямоугольные подмножества плоскости. Более конкретно, четверка (x,y,w,h)повторяет прямоугольник ширины w > 0и высоты h > 0, юго-западный угол которого равен (x,y). Прямоугольники должны формировать точное покрытие входной области, в том смысле, что каждый из единичных квадратов является подмножеством некоторого прямоугольника, каждый прямоугольник является подмножеством области, и два прямоугольника могут перекрываться только на своих границах. Чтобы запретить тривиальные решения, покрытие не должно содержать два прямоугольника, которые можно объединить в больший прямоугольник.

Например, список

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

представляет собой юридическое покрытие

указанного региона, тогда как покрытие

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

является незаконным, поскольку соседние квадраты 1 на 1 могут быть объединены:

правила

Вы можете дать полную программу или функцию. Точное форматирование ввода и вывода не имеет значения, в пределах разумного. Самый короткий счет байтов побеждает, и стандартные лазейки запрещены. Вам предлагается предоставить объяснение вашего алгоритма и некоторые примеры выходных данных.

Тестовые случаи

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)]

Большой треугольник:

[(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)]

контрольник

Используйте эту программу Python 2, чтобы проверить ваше решение. Он берет из STDIN список кортежей (входные данные) и список четверок (ваши выходные данные), разделенные запятой.

Я также написал эту программу на Python 2 для генерации картинок, и вы тоже можете ее использовать. Он берет из STDIN список кортежей или четверок и создает файл с именем out.png. Требуется библиотека PIL. При желании вы можете изменить размер ячеек сетки и ширину линий опоясывания.

Питон: 196 193 182 персонажа

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])

Мое первое решение использовало тот же алгоритм, что и KSFT, поэтому я экспериментировал с другими методами.

Сначала я делаю некоторую предварительную обработку, я конвертирую все точки в маленькие прямоугольники 1x1 {x+(1,1)for x in P}. С этими прямоугольниками я вызываю функцию g. gперебирает каждую комбинацию прямоугольников. Если он находит 2 прямоугольника, которые могут быть объединены в больший, он удаляет оба и добавляет новый. После этого он вызывает себя с новым набором прямоугольников.

использование

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

Полученные результаты

Вот визуализация результатов. Обратите внимание, что они могут немного отличаться в текущей версии. Идея заключается в том, что нет никакой заметной картины.

U-образная область:

Большой треугольник

Квадрат с отверстиями:

Отключенные регионы:

Просто для удовольствия: Pyth: 73 69 персонажа

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

Работает только в автономном режиме. Исправлена ​​ошибка в онлайн-версии. Попробуйте это здесь: Pyth Compiler / Executor . Ожидается список списков, а не список кортежей.

edit: Использовал идею из @ edc65: вместо того, чтобы удалять оба прямоугольника и создавать новый, я манипулирую одним и только удаляю один. В решении Python я мог получить наборы и приведение tuple-list-tuple. -11 символов в Python / -4 символа в Pyth

Питон - 272 261 258 251 224

Я думаю, что я могу играть в гольф это больше. Я почти уверен, что это работает, но я еще не закончил тестировать его на всех тестах. Я закончил тестирование. Это работает для всех тестовых случаев.

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

Я работаю над добавлением изображений результатов. Изменить: Вот результаты из примера и тестовых случаев:

Я пытаюсь написать это на Perl, но я не могу понять, как получить многомерные массивы из stdin без огромного количества символов. У кого-нибудь есть предложения?

Python 2, 139

Программа принимает списки упорядоченных пар, окруженных фигурными скобками, на стандартный ввод. Например,{(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

Часто раздражает (не только в гольфе), что Python не позволяет выполнять задания внутри циклического теста. Чтобы обойти это, я использовал операции форматирования строки.

Mathematica - 315 285 267 байт

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)&

С некоторой помощью @ MartinBüttner.

Ungolfed:

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
)&

Использование:

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}}

Тестовые случаи

U-образная область

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

Большой треугольник

{{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}}

Квадрат с отверстиями

{{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}}

Отключенные регионы

{{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}}

Хаскелл, 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

тестовые случаи и изображения будут здесь в ближайшее время.

Алгоритм: возьмите первый квадрат. Доберитесь до крайнего правого угла, не встречая квадрата, отсутствующего на входе. Затем достигните как можно большего расстояния, не имея квадрата на входе. Теперь у нас есть прямоугольник без пропущенного квадрата. Добавьте его к выводу, удалите все его квадраты из ввода и вызовите рекурсивно.

JavaScript (ES6) 148 155 199

Edit2 Еще немного тюнинга
Edit Некоторые игры в гольф + переписать с помощью рекурсии. Не ожидал такого сокращения. Теперь немного сложно следовать, но алгоритм тот же.

Алгоритм похож на ответ @jakube.

1. Каждая точка становится квадратом 1x1 (предварительная обработка)
2. Для каждого элемента проверьте, можно ли его объединить с другим
   Да? Первый элемент растет, второй элемент стирается, начните снова с шага 2,
   иначе перейдите к следующему элементу

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
  )()

Тест во фрагменте

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}

Пример:

Входные данные:

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

Выход:

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

Входные данные:

{{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, 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}}

Алгоритм:

Покройте область единичными квадратами, затем объедините их.