Организация произвольных прямоугольников для заполнения пробела

26

Могут ли эти прямоугольники заполнить прямоугольное пространство?

Учитывая группу прямоугольников, вас спрашивают, могут ли они быть расположены так, чтобы заполнить прямоугольное пространство.

Спекуляции

Задано множество произвольных m x nпрямоугольников; 0 <= m, n <= 1000Определите, можно ли расположить их так, чтобы они точно покрывали прямоугольную область без каких-либо отверстий или перекрытий. Прямоугольники не могут быть повернуты, и каждый прямоугольник может быть размещен только один раз.

вход

Входные данные для этого очень гибкие, поскольку входные данные дают некоторый список двухмерных измерений. Например, оба из следующих допустимы:

Разделенный пробелом, возвращение

1 2
1 5
4 5
3 6

Список размеров

[[1, 2], [1, 5], [4, 5], [3, 6]]

Выход

Любые значения true / false, такие как true / false, 0/1, T / F, True / False и т. Д. Если вы собираетесь использовать метод вывода, который не очень очевиден, пожалуйста, укажите в своем ответе.

Примеры

Тестовый пример 1

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

1 1
1 5
2 6

Вывод: true(или что-то подобное)
Как это устроить:

XYYYYY
ZZZZZZ
ZZZZZZ

Тестовый пример 2

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

1 1
2 2

Вывод: false(или что-то похожее)
Объяснение: Становится очевидным, что вы не можете расположить два квадрата разных размеров и выровнять их края.

Тестовый пример 3

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

1 1
1 2
1 2
2 1
2 1

Вывод: true(или что-то подобное) Как это устроить:

AAB
DEB
DCC

Как указывало @ETHProductions, для всех остальных тестовых случаев вы можете продолжать комбинировать прямоугольники с общей длиной ребра, пока у вас не будет только одного прямоугольника, поэтому этот тестовый случай просто нарушает любой код, использующий эту идею.

Тестовый пример 4

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

3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1

Вывод: true(или что-то подобное)
Как это устроить:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Примечание : вам не нужно указывать, как это организовать, вам нужно только определить, можно ли это организовать.

Это код гольф, поэтому самый короткий ответ в байтах выигрывает! Я приму кратчайший ответ от 14 января, но не стесняйтесь отправлять ответы позже, так как я все еще могу отдать голоса! :)

Удачного игры в гольф!

~ AL

PS Если вы знаете, какой тег должен быть применен к этой проблеме, пожалуйста, добавьте его, я абсолютно не знаю, что поставить в качестве тега, кроме code-golf.

РЕДАКТИРОВАТЬ : Ваша программа должна быть способна обрабатывать до 25 прямоугольников, самое большее за 10 секунд на приличном компьютере (я буду достаточно гибок в этом правиле).

РЕДАКТИРОВАТЬ : я продлил срок приема заявок до последнего дня года, но я сомневаюсь, что получу ответ к тому времени ...

РЕДАКТИРОВАТЬ : я продлил срок приема заявок на 2 недели, поэтому, если к тому времени больше не будет ответов, текущий ответ C будет принят! :)

HyperNeutrino
источник
Я так понимаю, каждый входной прямоугольник будет использоваться только один раз?
xnor
7
Почему существует крайний срок? Можно сказать, что вы примете ответ в то время, но испытания должны быть открыты на неопределенный срок :)
Натан Меррилл
4
Можно ли повернуть прямоугольники?
xnor
3
Что ж, ваша проблема - это проблема разрешимости: «Можно ли расположить эти ориентированные прямоугольники, чтобы они образовали другой прямоугольник с нулевым отходом», что является NP-полной проблемой (Korf, 2003: pdfs.semanticscholar.org/90a5/… ). Алгоритм Корфа, по сути, является грубой силой с некоторыми оптимизациями для более эффективного устранения конфигураций без решения. Я сомневаюсь, что гольф этого будет менее 250 символов на большинстве языков.
Габриэль Бенами
1
Простой способ - определить, можно ли повторно комбинировать два прямоугольника одинаковой ширины или высоты, пока у вас не останется 1 прямоугольник. Этот алгоритм работает для всех текущих тестовых случаев; однако, это терпит неудачу для [[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]](который может быть устроен ABB ACD EED). Вы можете добавить этот простой контрольный пример.
ETHproductions

Ответы:

5

C 1135 1158 1231 1598 байт

Что ж, он прошел установленный срок, но, учитывая, что ответов пока нет, вот один (немного длинный) на C.

Возвращает:

  • 0 (ноль) при неудаче (не подходит)
  • Полная подгонка матрицы на успех

Обновить:

Исходный код может застрять на некоторых матрицах, занимая намного больше времени, чем разрешенные 10 секунд. Текущая редакция должна завершить все матрицы до 1 с. Это достигается путем 1) сортировки входных прямоугольников и 2) пропуска повторяющихся размеров при подгонке.

Golfed:

#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct{int x,y,u,p;}r[25],*S;int A,M,N,U,V,X,Y;char *P;T(x,y,w,h){_(I,x+w,x)_(J,y+h,y)if(I/U|J/V|P[J*U+I])Z 0;Z 1;}L(x,y,w,h,c){_(I,x+w,x)_(J,y+h,y)P[J*U+I]=c;}F(){int x=0,y;while(++x<A)if(!P[x])break;if(x/A){_(i,V,0)printf("%*.*s\n",U,U,P+i*U);exit(0);}y=x/U;x-=y*U;_(i,N,0)if(!R.u&T(x,y,R.x,R.y))R.u=1,L(x,y,R.x,R.y,'A'+i),F(),R.u=0,L(x,y,R.x,R.y,0);}O(i,y){if(!R.u){if(!T(0,y,R.x,R.y))Z;R.u=1;R.p=0;L(0,y,R.x,R.y,'A'+i);y+=R.y;}if(y-V||F())_(j,N,0)if(j-i&!r[j].u){O(j,y);while(r[j].x-r[j+1].x|r[j].y-r[j+1].y)j++;}R.u=0;L(R.p,(y-=R.y),R.x,R.y,0);}Q(i,x){if(!R.u){if(R.x>U-x)Z;R.u=1;R.p=x;L(x,0,R.x,R.y,'A'+i);x+=R.x;}if(x-U||O(i,1))_(j,N,0)if(j-i&!r[j].u)Q(j,x);L(x-=R.x,0,R.x,R.y,0);R.u=0;}C(int*a,int*b){Z*a-*b?*a-*b:a[1]-b[1];}main(){_(i,25,0)if(++N&scanf("%d%d\n",&R.x,&R.y)-2)break;_(i,N,0){A+=R.x*R.y;if(R.x>X)X=R.x;if(R.y>Y)Y=R.y;}_(i,A+1,1)if(!(A%i)){if(i<Y|A/i<X)continue;M++;S=realloc(S,M*16);S[M-1].y=i;S[M-1].x=A/i;}qsort(S,M,16,C);P=calloc(A+1,1);_(j,M,0){U=S[j].x;V=S[j].y;_(i,N,0)R.u=1,L(0,0,R.x,R.y,'A'+i),Q(i,R.x),R.u=0;}printf("0\n");exit(1);}

UnGolfed:

#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct {
    int x,y,u,p;
} r[25],*S;
int A,M,N,U,V,X,Y;
char *P;

test_space(x,y,w,h) {
    _(I,x+w,x)
        _(J,y+h,y)
            if (    I >= U |
                    J >= V |
                    P[J*U+I]) Z 0;
    Z 1;
}
place_rect(x,y,w,h,c){
    _(I,x+w,x)
        _(J,y+h,y)P[J*U+I] = c;
}

fill_rest() {
    int x=0,y;
    while(++x<A) if (!P[x])break;
    if (x>=A) {
        _(i,V,0) printf("%*.*s\n", U,U, P+i*U);
        exit(0);
    }
    y = x / U; x -= y*U;

    _(i,N,0)
        if (!R.u & test_space(x, y, R.x, R.y))
                R.u = 1,
                place_rect(x, y, R.x, R.y, 'A'+i),
                fill_rest(),
                R.u = 0,
                place_rect(x, y, R.x, R.y, 0);

}

fill_y(i,y) {
    if (!R.u) {
        if (!test_space(0, y, R.x, R.y)) Z;
        R.u = 1;
        R.p = 0;
        place_rect(0, y, R.x, R.y, 'A'+i);
        y += R.y;
    }
    if (y == V) fill_rest();
    else _(j,N,0)
        if (j!=i && !r[j].u){ fill_y(j, y);
        while (r[j].x^r[j+1].x||r[j].y^r[j+1].y)j++;
        }
    R.u = 0;
    place_rect(R.p, (y -= R.y), R.x, R.y, 0);
}

fill_x(i,x) {
    if (!R.u) {
        if (R.x > U - x) Z;
        R.u = 1;
        R.p = x;
        place_rect(x, 0, R.x, R.y, 'A'+i);
        x += R.x;
    }
    if (x == U) fill_y(i, 1);
    else
        _(j,N,0)
            if (j!=i && !r[j].u) fill_x(j, x);
    place_rect((x -= R.x), 0, R.x, R.y, 0);
    R.u = 0;
}
C(int*a,int*b) {
    Z *a^*b?*a-*b:a[1]-b[1];
}


main() {
    _(i,25,0)
        if (++N&&scanf("%d %d\n", &R.x, &R.y)!=2) break;
    _(i,N,0){
        A+=R.x*R.y;
        if(R.x>X)X=R.x;
        if(R.y>Y)Y=R.y;
    }
    _(i,A+1,1)
        if (!(A%i)) {
            if (i < Y | A/i < X) continue;
            M++;
            S = realloc(S,M*16);
            S[M-1].y=i;
            S[M-1].x=A/i;
        }
    qsort(S, M, 16,C);
    P = calloc(A + 1,1);
    _(j,M,0){
        U = S[j].x; V = S[j].y;
        _(i,N,0)
            R.u = 1,
            place_rect(0, 0, R.x, R.y, 'A'+i),
            fill_x(i, R.x),
            R.u = 0;
    }
    printf("0\n");
    exit(1);
}

Объяснение: У нас есть 6 функций: main, O, Q, F, Lи T. T т эстов , чтобы увидеть , если есть пространство для прямоугольника в данном месте. Lфил л а м прямоугольник в выходной буфер или, альтернативно удаляет один путем перезаписи его. Oи Qсоздать левые и верхние стенки, соответственно , и F е бед оставшуюся часть прямоугольника путем итеративного поиска.

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

Сет
источник
Хорошая работа! Похоже, что работает ... Однако, вы могли бы указать свой выходной формат? Похоже, что это печатные материалы, если они работают, и сбой, если это не так, что я позволю, так как это единственный ответ в любом случае. Кроме того, вы можете сэкономить несколько байтов, напечатав «1» вместо «Все подходят!» (потому что это разрешено), а также довольно много байтов, не печатая, как они устроены. Хорошо, что это напечатано, но оно использует ненужные байты, и цель состоит в том, чтобы сэкономить на этом. В противном случае, хорошая работа! Я продляю крайний срок на полмесяца, но пока что есть повышенный голос. :)
HyperNeutrino
Спасибо. Я обновил, чтобы указать формат и исправил сбой (это было непреднамеренно). Я оставил матричный вывод (+ 30 байт), потому что он отличный, и если кто-то еще опубликует решение на языке гольфа, они не будут просто бить меня к 30 :)
Сет
-367 байт ... Возможно, самый большой гольф когда-либо? :-)
HyperNeutrino
:-) Ну, это помогает иметь хакерскую точку отсчета.
Сет
Конечно, делает! Мой самый большой гольф состоял из 337 символов на Java за несколько правок, и я начал с довольно ужасных идей (о, старые добрые времена, когда я создавал 50 миллионов переменных и мне нужно всего 2 ...). В любом случае, я буду ждать ответов, но, похоже, это единственный работающий!
HyperNeutrino
6

Haskell, 226 байт

((y,z):l)&(w,x)|x*y<1=(w+y,x+z):l
(q:l)&p=p:q:l
(p@(u,v):r@(y,z):l)%q@(w,x)=[((y-w,z):l)&q&(u,v-x)|w<=y,x<=v]++[p:m|m<-(r:l)%q]
_%_=[]
g m(p:n)l=any(g[]$m++n)(l%p)||g(p:m)n l
g[]_[_,_,_]=0<1
g _[]_=0<0
($[(0,9^9),(9^9,0)]).g[]

Попробуйте это на Ideone

Как это работает

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

Чтобы увидеть, что любая мозаика прямоугольника может быть построена следующим образом: в любой мозаике непустой диаграммы Юнга пусть R будет набором прямоугольников в мозаике, юго-западный угол которых не касается другого прямоугольника. Поскольку каждая вогнутая вершина диаграммы Юнга примыкает к ребру (а не только к углу) не более чем к одному прямоугольнику в R, а количество этих вогнутых вершин на один меньше, чем число прямоугольников в R, должно быть не менее один прямоугольник в R, примыкающий к ребру ни к одной из этих вогнутых вершин. Удаление его приводит к другой диаграмме Юнга, поэтому мы можем действовать по индукции.

Андерс Касеорг
источник
Хороший! Это фантастика. Отличная работа! :)
HyperNeutrino