Tarefa

Escreva um programa que leia três números inteiros m , n de STDIN ou como argumentos da linha de comando, imprima todas as inclinações possíveis de um retângulo de dimensões m × n pelos dominós 2 × 1 e 1 × 2 e, finalmente, o número de inclinações válidas.

Os dominós de uma peça individual devem ser representados por dois traços ( -) para 2 × 1 e duas barras verticais ( |) para 1 × 2 dominós. Cada lado a lado (incluindo o último) deve ser seguido por um avanço de linha.

Para fins de pontuação, você também deve aceitar um sinalizador do STDIN ou como argumento da linha de comando que faz com que o programa imprima apenas o número de inclinações válidas, mas não as inclinações em si.

Seu programa não pode ter mais de 1024 bytes. Ele deve funcionar para todas as entradas, de modo que m × n ≤ 64 .

(Inspirado em Imprimir todas as inclinações de dominó do retângulo 4x6 .)

Exemplo

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

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Pontuação

Sua pontuação é determinada pelo tempo de execução do seu programa para a entrada 8 8 com o sinalizador definido.

Para tornar esse código mais rápido do que um desafio mais rápido para o computador , executarei todos os envios em meu próprio computador (Intel Core i7-3770, 16 GiB PC3-12800 RAM) para determinar a pontuação oficial.

Deixe instruções detalhadas sobre como compilar e / ou executar seu código. Se você precisar de uma versão específica do compilador / intérprete do seu idioma, faça uma declaração nesse sentido.

Reservo-me o direito de deixar os envios sem pontuação se:

• Não há compilador / intérprete gratuito (como na cerveja) para o meu sistema operacional (Fedora 21, 64 bits).

• Apesar dos nossos esforços, seu código não funciona e / ou produz resultados incorretos no meu computador.

• A compilação ou execução leva mais de uma hora.

• Seu código ou o único compilador / intérprete disponível contém uma chamada do sistema rm -rf ~ou algo igualmente suspeito.

Entre os melhores

Marquei todas as submissões, executando as compilações e as execuções em um loop com 10.000 iterações para compilação e entre 100 e 10.000 iterações para execução (dependendo da velocidade do código) e calculando a média.

Estes foram os resultados:

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.

C

Uma implementação direta ...

#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);
}

A versão de trapaça

#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);
    }
}

Explicação do algoritmo mais rápido

Ele digitaliza da esquerda para a direita e mantém o estado d[i][j], onde:

• iestá em [0,m), o que significa a coluna atual.
• j é um pequeno vetor de tamanho n , em que o bit seria 1 se a posição correspondente na coluna ijá estiver ocupada antes de começar a trabalhar nessa coluna. Ou seja, é ocupado pela metade direita de um --.
• d[i][j] é o número total de diferentes inclinações.

Então diga e[i][j]= a soma de d[i][k]onde você pode colocar a base de dominó vertical kpara formar a j. e[i][j]seria o número de inclinações em que cada 1 bit jé ocupado por qualquer coisa, menos a metade esquerda de a --. Encha-os com --e você terá d[i+1][~j]= e[i][j].e[m-1][every bit being 1]ou d[m][0]é a resposta final.

Uma implementação ingênua fornecerá a complexidade do tempo em algum lugar próximo g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)(já rápido o suficiente se n = m = 8). Mas você pode primeiro fazer um loop para cada dominó possível e tentar adicioná-lo a todos os mosaicos que podem ter esse dominó adicionado e mesclar o resultado à matriz original d(como o algoritmo para o problema da mochila). E isso se torna O (n * 2 ^ n). E tudo o resto são detalhes de implementação. O código inteiro é executado em O (m * n * 2 ^ n).

C

Após uma rodada de otimizações, e adaptado às regras modificadas:

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

Comecei a esbarrar no limite de 1024 caracteres, então tive que reduzir um pouco a legibilidade. Nomes de variáveis ​​muito mais curtos etc.

Instruções de construção:

> gcc -O2 Code.c

Execute com a saída da solução ativada:

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

Execute apenas com a contagem de soluções:

> ./a.out 8 8 s

Alguns comentários:

• Com o exemplo de teste maior, quero otimização agora. Enquanto meu sistema é diferente (Mac), cerca de-O2 parece bom.
• O código ficou mais lento para o caso em que a saída é gerada. Este foi um sacrifício consciente por otimizar o modo "contar apenas" e por reduzir o comprimento do código.
• Haverá alguns avisos do compilador devido à falta de inclusões e declarações externas para funções do sistema. Foi a maneira mais fácil de obter abaixo de 1024 caracteres no final, sem tornar o código totalmente ilegível.

Observe também que o código ainda gera as soluções reais, mesmo no modo "contar apenas". Sempre que uma solução é encontrada, a vMmáscara de bits contém um 1para as posições que possuem uma barra vertical e um 0para posições com uma barra horizontal. Somente a conversão dessa máscara de bits no formato ASCII e a saída real são ignoradas.

C

O conceito é encontrar primeiro todos os arranjos possíveis de dominós horizontais em uma fileira, armazená-los em r[] e organizá-los para fornecer todos os arranjos possíveis de dominós verticais.

O código para posicionar os dominós horizontais em uma linha é modificado a partir desta resposta minha: https://codegolf.stackexchange.com/a/37888/15599 . É lento para as grades mais largas, mas isso não é um problema para o gabinete 8x8.

A inovação está na maneira como as linhas são montadas. Se o quadro tiver um número ímpar de linhas, ele será girado 90 graus na análise de entrada, portanto, agora ele terá um número par de linhas. Agora, coloco alguns dominós verticais na linha central. Por causa da simetria, se existem cmaneiras de organizar os dominós restantes na metade inferior, também deve haver cmaneiras de organizar os dominós restantes na metade superior, o que significa que, para um determinado arranjo de dominós verticais na linha central, existemc*c soluções possíveis . Portanto, apenas a linha central e mais metade da placa é analisada quando o programa é obrigado a imprimir apenas o número de soluções.

f()constrói a tabela de possíveis arranjos de dominó horizontal e varre os possíveis arranjos de dominó vertical na linha central. em seguida, chama a função recursiva g()que preenche as linhas. Se for necessária impressão, a funçãoh() é chamada para fazer isso.

g()é chamado com 3 parâmetros. yé a linha atual e dé a direção (para cima ou para baixo) na qual estamos preenchendo o quadro do centro para o exterior. xcontém um bitmap indica os dominós verticais incompletos da linha anterior. Todos os arranjos possíveis de dominós seguidos de r [] são tentados. Nesta matriz, um 1 representa um dominó vertical e um par de zeros um dominó horizontal. A entrada válida na matriz deve ter pelo menos o suficiente 1s para terminar quaisquer dominó verticais incompletas a partir da última linha: (x&r[j])==x. Pode ter mais 1s, o que indica que novos dominós verticais estão sendo iniciados. Para a próxima linha, então, precisamos apenas dos novos dominós, então chamamos o procedimento novamente comx^r[j] .

Se uma linha final foi alcançada e não há dominós verticais incompletos pendurados na parte superior ou inferior do tabuleiro x^r[j]==0, a metade foi concluída com êxito. Se não estivermos imprimindo, é suficiente concluir a metade inferior e usá-la c*cpara calcular o número total de arranjos. Se estivermos imprimindo, será necessário concluir também a metade superior e chamar a função de impressão h().

CÓDIGO

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");

}

Observe que a entrada com um número ímpar de linhas e número par de colunas é girada em 90 graus na fase de análise. Se isso não for aceitável, a função de impressão h()pode ser alterada para acomodá-la. (EDIT: não é necessário, veja os comentários.)

EDIT: Uma nova função e()foi utilizado para verificar a paridade de i(ou seja, o número de dominó abrangendo a linha central). A paridade de i(o número de meias-dominó no eixo saliente em cada metade da placa) deve ser a mesma que a singularidade do número total de espaços em cada metade (dado por n/2), porque somente então os dominós podem preencher todo o espaço disponível. Essa edição elimina metade dos valores de i e, portanto, torna meu programa aproximadamente duas vezes mais rápido.