Сверхзвуковые домино

10

задача

Напишите программу, которая читает три целых числа m , n либо из STDIN, либо в качестве аргументов командной строки, печатает все возможные наклоны прямоугольника с размерами m × n с помощью домино 2 × 1 и 1 × 2 и, наконец, количество допустимых значений.

Домино отдельных листов должны быть представлены двумя штрихами ( -) для 2 × 1 и двумя вертикальными чертами ( |) для 1 × 2 домино. После каждого тайлинга (включая последний) должен следовать перевод строки.

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

Ваша программа не может быть длиннее 1024 байта. Он должен работать для всех входов, таких что m × n ≤ 64 .

(Вдохновлено печатью всех элементов домино прямоугольника 4x6 .)

пример

$ sdt 4 2
----
----

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

счет

Ваша оценка определяется временем выполнения вашей программы для ввода 8 8 с установленным флагом.

Чтобы сделать этот код быстрейшим, а не самым быстрым компьютерным испытанием, я буду запускать все представления на своем собственном компьютере (Intel Core i7-3770, 16 ГБ ОЗУ PC3-12800), чтобы определить официальный результат.

Пожалуйста, оставьте подробные инструкции о том, как скомпилировать и / или выполнить ваш код. Если вам требуется конкретная версия компилятора / интерпретатора вашего языка, сделайте заявление об этом.

Я оставляю за собой право оставлять материалы без оценки, если:

  • Для моей операционной системы нет бесплатного (как в пиве) компилятора / интерпретатора (Fedora 21, 64 бита).

  • Несмотря на наши усилия, ваш код не работает и / или выдает неправильные результаты на моем компьютере.

  • Компиляция или выполнение занимает больше часа.

  • Ваш код или единственный доступный компилятор / интерпретатор содержат системный вызов rm -rf ~или что-то такое же подозрительное.

Leaderboard

Я переоценил все представления, выполняя как компиляции, так и выполнения в цикле с 10 000 итераций для компиляции и от 100 до 10000 итераций для выполнения (в зависимости от скорости кода) и вычисления среднего значения.

Это были результаты:

User          Compiler   Score                              Approach

jimmy23013    GCC (-O0)    46.11 ms =   1.46 ms + 44.65 ms  O(m*n*2^n) algorithm.
steveverrill  GCC (-O0)    51.76 ms =   5.09 ms + 46.67 ms  Enumeration over 8 x 4.
jimmy23013    GCC (-O1)   208.99 ms = 150.18 ms + 58.81 ms  Enumeration over 8 x 8.
Reto Koradi   GCC (-O2)   271.38 ms = 214.85 ms + 56.53 ms  Enumeration over 8 x 8.
Деннис
источник
Почему бы не сделать это соревнованием в гольф? :(
orlp
2
Если бы вы предложили это в песочнице, я мог бы. Это спасло бы мой процессор и мне большую работу ...
Деннис
3
@ kirbyfan64sos Насколько я понимаю, есть только один тип домино, который вы можете вращать. Если это горизонтальное, это выглядит следующим образом : --. Если это вертикально, это два |, один под другим.
Рето Коради
1
Ваш вызов не плохой. Проблема в том, что наши топ-кодеры слишком сильны. Мое решение, которое проверяет правильность строк и столбцов, остается около 1 минуты для 6x8.
edc65
1
Я думаю, что лучшей стратегией сейчас является использование ассемблера и попытка получить двоичный файл размером менее 1024 байт, чтобы избавиться от времени усложнения.
jimmy23013

Ответы:

5

С

Простая реализация ...

#include<stdio.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0;
char r[100130];
void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j)
        if(countonly)
            m++;
        else{
            if(c==b)
                for(k=0;k<b;r[k++,l++]=10)
                    for(j=0;j<a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
            else
                for(j=0;j<a;r[j++,l++]=10)
                    for(k=0;k<b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
            r[l++]=10;
            if(l>=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    w(0,0,1);
    if(countonly)
        printf("%llu\n",m);
    else if(l)
        fwrite(r,l,1,stdout);
}

Читерская версия

#include<stdio.h>
#include<string.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0,d[256];
char r[100130];
void w2(){
    int i,j,k,x;
    memset(d,0,sizeof d);
    d[0]=1;
    j=0;
    for(i=0;i<a-1;i++){
        for(k=1;k<(1<<(b-1));k*=2)
            for(x=0;x<(1<<(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1<<b)-1;
    }
    for(x=0;x<(1<<b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1<<b)-1)^j];
    printf("%llu\n",m);
}

void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j){
        if(c==b)
            for(k=0;k<b;r[k++,l++]=10)
                for(j=0;j<a;j++)
                    r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
        else
            for(j=0;j<a;r[j++,l++]=10)
                for(k=0;k<b;k++)
                    r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
        r[l++]=10;
        if(l>=100000){
            fwrite(r,l,1,stdout);
            l=0;
        }
    }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    if(countonly)
        w2();
    else{
        w(0,0,1);
        if(l)
            fwrite(r,l,1,stdout);
    }
}

Объяснение более быстрого алгоритма

Сканирует слева направо и сохраняет состояние d[i][j], в котором:

  • iнаходится в [0,m), что означает текущий столбец.
  • jбитовый вектор размера n, где бит будет равен 1, если соответствующая позиция в столбце iуже занята до начала работы с этим столбцом. Т.е. он занят правой половиной --.
  • d[i][j] общее количество различных элементов мозаичного изображения.

Затем скажите e[i][j]= сумма, d[i][k]где вы можете положить вертикальную основу домино, kчтобы сформировать j. e[i][j]будет количеством углов, где каждый 1 бит jзанят чем-либо, кроме левой половины a --. Заполните их, --и вы получите d[i+1][~j]= e[i][j]. e[m-1][every bit being 1]или d[m][0]это окончательный ответ.

Наивная реализация даст вам временную сложность где-то рядом g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)(уже достаточно быстро, если n = m = 8). Но вместо этого вы можете сначала выполнить цикл для каждого возможного домино и попытаться добавить его в каждый лист, в который можно добавить это домино, и объединить результат с исходным массивом d(как алгоритм для задачи о рюкзаке). И это становится O (n * 2 ^ n). А все остальное - детали реализации. Весь код работает в O (m * n * 2 ^ n).

jimmy23013
источник
@ Денис Вы, вероятно, хотите начать опрос, чтобы изменить его.
jimmy23013
@ Денис Не уверен, что увеличение размера очень помогло бы. Хотя это существенно увеличивает время вычислений, оно также дает примерно в 100 раз больше выходных данных. Условно говоря, объем производства на самом деле больше.
Рето Коради
1-я версия Выполнение: 0,286 с Компиляция: 0,053 с Сумма: 0,339 с 2-я версия Выполнение: 0,002 с Компиляция: 0,061 с Сумма: 0,063 с (Что здесь только что произошло?)
Деннис
@Dennis Он использовал другой алгоритм в O (m * n * 2 ^ n), если флаг установлен.
jimmy23013
1
Выполнение: 190 мс Компиляция: 68 мс Сумма: 258 мс ( -O1кажется, самое приятное место. Я перепробовал все уровни оптимизации.)
Деннис
3

С

После раунда оптимизаций, адаптированных к измененным правилам:

typedef unsigned long u64;

static int W, H, S;
static u64 RM, DM, NSol;
static char Out[64 * 2 + 1];

static void place(u64 cM, u64 vM, int n) {
  if (n) {
    u64 m = 1ul << __builtin_ctzl(cM); cM -= m;

    if (m & RM) {
      u64 nM = m << 1;
      if (cM & nM) place(cM - nM, vM, n - 1);
    }

    if (m & DM) {
      u64 nM = m << W;
      vM |= m; vM |= nM; place(cM - nM, vM, n - 1);
    }
  } else if (S) {
    ++NSol;
  } else {
    char* p = Out;
    for (int y = 0; y < H; ++y) {
      for (int x = 0; x < W; ++x) { *p++ = vM & 1 ? '|' : '-'; vM >>= 1; }
      *p++ = '\n';
    }
    *p++ = '\0';
    puts(Out);
    ++NSol;
  }
}

int main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);

  int n = W * H;
  if (n & 1) return 0;

  for (int y = 0; y < H; ++y) {
    RM <<= W; RM |= (1ul << (W - 1)) - 1;
  }
  DM = (1ul << (W * (H - 1))) - 1;

  place(-1, 0, n >> 1);
  printf("%lu\n", NSol);

  return 0;
}

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

Инструкции по сборке:

> gcc -O2 Code.c

Запустить с включенным выводом решения:

> ./a.out 8 8 >/dev/null

Запустить только с подсчетом решений:

> ./a.out 8 8 s

Некоторые комментарии:

  • С большим тестовым примером я хочу оптимизации сейчас. Хотя моя система отличается (Mac), -O2кажется, что все хорошо.
  • Код стал медленнее для случая, когда генерируется вывод. Это была сознательная жертва за оптимизацию режима «только счет» и за уменьшение длины кода.
  • Будет несколько предупреждений компилятора из-за отсутствия включений и внешних объявлений для системных функций. Это был самый простой способ получить в итоге менее 1024 символов, не делая код полностью нечитаемым.

Также обратите внимание, что код все еще генерирует реальные решения, даже в режиме «только подсчет». Всякий раз, когда решение найдено, vMбитовая маска содержит 1для позиций с вертикальной чертой и 0для позиций с горизонтальной чертой. Пропускается только преобразование этой битовой маски в формат ASCII и фактический вывод.

Рето Коради
источник
@Dennis Новая версия. Выполнение должно быть неизменным, но компиляция быстрее. Если нам нужно оптимизировать время компиляции, нам не нужны системные заголовки!
Рето Коради
@Dennis Обновлено для нового скоринга и для раунда оптимизаций. Обратите внимание, что я хочу оптимизации сейчас, что-то вроде -O2должно быть хорошо.
Рето Коради
Выполнение: 256 мс Компиляция: 65 мс Сумма: 321 мс ( -O2кажется, самое приятное место. Я перепробовал все уровни оптимизации.)
Деннис
1

С

Идея состоит в том, чтобы сначала найти все возможные варианты расположения горизонтальных домино в ряд, сохранить их, r[]а затем упорядочить, чтобы получить все возможные варианты расположения вертикальных домино.

Код для позиционирования горизонтального домино в ряд изменен из моего ответа: https://codegolf.stackexchange.com/a/37888/15599 . Это медленно для более широких сеток, но это не проблема для случая 8x8.

Инновация заключается в способе сборки рядов. Если у платы нечетное количество строк, то при разборе ввода она поворачивается на 90 градусов, поэтому теперь она имеет четное количество строк. Теперь я размещаю несколько вертикальных домино по центральной линии. Из-за симметрии, если есть cспособы расположить оставшиеся домино в нижней половине, также должны быть cспособы расположить оставшиеся домино в верхней половине, что означает, что для данного расположения вертикальных домино на центральной линии, есть c*cвозможные решения , Поэтому анализируется только центральная линия плюс половина платы, когда программе требуется распечатать только количество решений.

f()строит таблицу возможных расположений горизонтальных домино и просматривает возможные размещения вертикальных домино на центральной линии. Затем он вызывает рекурсивную функцию, g()которая заполняет строки. Если требуется печать, для этого вызывается функция h().

g()вызывается с 3 параметрами. yтекущая строка и dнаправление (вверх или вниз), в котором мы заполняем доску от центра наружу. xсодержит растровое изображение, обозначающее вертикальные домино, которые являются неполными из предыдущего ряда. Все возможные размещения домино в ряд от r [] перепробованы. В этом массиве 1 представляет вертикальное домино, а пара нулей - горизонтальное домино. Действительный элемент массива должен иметь по крайней мере , достаточно 1, чтобы закончить все незавершенные вертикальные домино с последнего ряда: (x&r[j])==x. У него может быть больше 1, что указывает на то, что начинаются новые вертикальные домино. Тогда для следующей строки нам нужны только новые домино, поэтому мы снова вызываем процедуру с помощью x^r[j].

Если достигнут конечный ряд и нет незавершенных вертикальных домино, висящих сверху или снизу доски, x^r[j]==0то половина была успешно завершена. Если мы не печатаем, достаточно заполнить нижнюю половину и использовать c*cдля выработки общего количества аранжировок. Если мы печатаем, необходимо также заполнить верхнюю половину и затем вызвать функцию печати h().

КОД

unsigned int W,H,S,n,k,t,r[1<<22],p,q[64];
long long int i,c,C;


//output: ascii 45 - for 0, ascii 45+79=124 | for 1
h(){int a;
  for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);
  puts("");
}

g(y,d,x){int j;
  for(j=0;j<p;j++)if((x&r[j])==x){
    q[y]=r[j];
    if(y%(H-1)==0){
       (x^r[j])==0?
        y?c++,S||g(H/2-1,-1,i):h() 
       :0;
    }else{
      g(y+d,d,x^r[j]);
    }

  }    
}

e(z){int d;
  for(d=0;z;d++)z&=z-1;return n/2+1+d&1; 
}

f(){
  //k=a row full of 1's
  k=(1ULL<<W)-1;

  //build table of possible arrangements of horizontal dominoes in a row;
  //flip bits so that 1=a vertical domino and save to r[]
  for(i=0;i<=k;i++)(i/3|i/3<<1)==i?r[p++]=i^k:0;

  //for each arrangement of vertical dominoes on the centreline, call g()
  for(i=0;i<=k;i++)e(i)?c=0,g(H/2,1,i),C+=c*c:0;
  printf("%llu",C);
}


main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);
  1-(n=W*H)%2?
      H%2?W^=H,H^=W,W^=H,t=1:0,f()
    :puts("0");

}

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

РЕДАКТИРОВАТЬ: новая функция e()была использована для проверки четности i(т.е. количество домино, охватывающих центральную линию.) Четность i(количество полдомино на центральной линии, выступающей в каждую половину доски) должно быть таким же, как нечетность общего количества пробелов в каждой половине (определяемых как n/2), потому что только тогда домино может заполнить все доступное пространство. Это редактирование устраняет половину значений i и, следовательно, делает мою программу примерно в два раза быстрее.

Уровень реки St
источник
Выполнение: 18 мс. Компиляция: 50 мс. Сумма: 68 мс ( -O0было приятное место для итога. Другие варианты замедлили компиляцию.)
Деннис
Это либо никогда не завершается, либо, по крайней мере, занимает очень много времени для ввода 32 2 s. Я остановил это примерно через 15 минут.
Рето Коради
@RetoKoradi действительно, но 2 32 sработает почти мгновенно. Сканирование всех возможных вертикальных домино чрезвычайно расточительно для этого H=2случая, потому что на самом деле у нас уже есть вся необходимая информация r[]. Я очень доволен официальным временем для 8 8 sВот пример патча для случая, о котором вы упомянули: if(H==2){C=p;if(!S)for(i=0;i<p;i++)q[0]=q[1]=r[i],h();}else for(i=0;i<=k;i++)c=0,g(H/2,1,i),C+=c*c;Как вы можете видеть, этот фрагмент будет работать мгновенно H=2 с установленным флагом. Общее время выполнения ограничено тем, что здание, r[]безусловно, имеет место для улучшения.
Уровень Река St
Для полноты здесь приведен патч для правильного увеличения выходного значения, если это необходимо: if(t)for(a=n;a--;a%H||puts(""))putchar(124-(q[a%H]>>a/H)%2*79);else for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);длина кода все еще значительно ниже 1000 байтов, и влияние на время компиляции должно быть минимальным. Я не включал эти патчи прошлой ночью, так как был слишком уставшим.
Уровень Река St
Я хотел прокомментировать это прошлой ночью, но я забыл. Так как выигрыш делается на квадрате, я не собираюсь настаивать на конкретном заказе.
Деннис