Tarea

Escriba un programa que lea tres enteros m , n desde STDIN o como argumentos de línea de comandos, imprima todas las posibles inclinaciones de un rectángulo de dimensiones m × n por dominó 2 × 1 y 1 × 2 y finalmente el número de inclinaciones válidas.

Las fichas de dominó de un mosaico individual se deben representar con dos guiones ( -) para 2 × 1 y dos barras verticales ( |) para fichas de 1 × 2 . Cada mosaico (incluido el último) debe ir seguido de un salto de línea.

Para fines de puntuación, también debe aceptar un indicador de STDIN o como argumento de línea de comando que haga que su programa imprima solo el número de inclinaciones válidas, pero no las inclinaciones en sí.

Su programa no puede tener más de 1024 bytes. Tiene que funcionar para todas las entradas de modo que m × n ≤ 64 .

(Inspirado en Imprimir todas las inclinaciones de dominó del rectángulo 4x6 ).

Ejemplo

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

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Puntuación

Su puntaje está determinado por el tiempo de ejecución de su programa para la entrada 8 8 con el indicador establecido.

Para hacer de este un código más rápido en lugar de un desafío informático más rápido , ejecutaré todas las presentaciones en mi propia computadora (Intel Core i7-3770, 16 GiB PC3-12800 RAM) para determinar el puntaje oficial.

Deje instrucciones detalladas sobre cómo compilar y / o ejecutar su código. Si necesita una versión específica del compilador / intérprete de su idioma, haga una declaración al respecto.

Me reservo el derecho de dejar las presentaciones sin puntaje si:

• No hay un compilador / intérprete gratuito (como en cerveza) para mi sistema operativo (Fedora 21, 64 bits).

• A pesar de nuestros esfuerzos, su código no funciona y / o produce resultados incorrectos en mi computadora.

• La compilación o ejecución lleva más de una hora.

• Su código o el único compilador / intérprete disponible contiene una llamada al sistema rm -rf ~o algo igualmente sospechoso.

Tabla de clasificación

He vuelto a calificar todas las presentaciones, ejecutando compilaciones y ejecuciones en un bucle con 10,000 iteraciones para la compilación y entre 100 y 10,000 iteraciones para la ejecución (dependiendo de la velocidad del código) y calculando la media.

Estos fueron los 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

Una implementación sencilla ...

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

La versión trampa

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

Explicación del algoritmo más rápido.

Escanea de izquierda a derecha y mantiene el estado d[i][j], donde:

• iestá en [0,m), lo que significa la columna actual.
• jes un vector de tamaño de bit n, donde el bit sería 1 si la posición correspondiente en la columna iya está ocupada antes de comenzar a trabajar en esta columna. Es decir, está ocupado por la mitad derecha de a --.
• d[i][j] es el número total de diferentes inclinaciones.

Luego diga e[i][j]= la suma de d[i][k]dónde puede colocar la base de dominó vertical kpara formar a j. e[i][j]sería el número de inclinaciones donde cada 1 bit jestá ocupado por cualquier cosa que no sea la mitad izquierda de a --. Llénalos --y obtendrás d[i+1][~j]= e[i][j]. e[m-1][every bit being 1]o d[m][0]es la respuesta final.

Una implementación ingenua le dará la complejidad del tiempo en algún lugar cercano g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)(ya lo suficientemente rápido si n = m = 8). Pero en su lugar, puede hacer un bucle en primer lugar para cada dominó posible, e intentar agregarlo a cada mosaico que pueda tener este dominó agregado, y fusionar el resultado con la matriz original d(como el algoritmo para el problema Mochila). Y esto se convierte en O (n * 2 ^ n). Y todo lo demás son detalles de implementación. Todo el código se ejecuta en O (m * n * 2 ^ n).

C

Después de una ronda de optimizaciones, y adaptadas para las reglas 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;
}

Comencé a toparme con el límite de longitud de 1024 caracteres, así que tuve que reducir un poco la legibilidad. Nombres de variables mucho más cortos, etc.

Instrucciones de construcción:

> gcc -O2 Code.c

Ejecutar con salida de solución habilitada:

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

Ejecutar con solo recuento de soluciones:

> ./a.out 8 8 s

Algunos comentarios:

• Con el ejemplo de prueba más grande, quiero optimización ahora. Si bien mi sistema es diferente (Mac), -O2parece ser bueno.
• El código se ha vuelto más lento para el caso donde se genera la salida. Este fue un sacrificio consciente para optimizar el modo "solo contar" y para reducir la longitud del código.
• Habrá algunas advertencias del compilador debido a la falta de inclusiones y declaraciones externas para las funciones del sistema. Fue la forma más fácil de llegar a menos de 1024 caracteres al final sin hacer que el código sea totalmente ilegible.

También tenga en cuenta que el código aún genera las soluciones reales, incluso en el modo "contar solo". Cada vez que se encuentra una solución, la vMmáscara de bits contiene una 1para las posiciones que tienen una barra vertical y una 0para las posiciones con una barra horizontal. Solo se omite la conversión de esta máscara de bits en formato ASCII y la salida real.

C

El concepto es encontrar primero todos los arreglos posibles de dominó horizontal en una fila, almacenarlos r[]y luego organizarlos para dar todos los arreglos posibles de dominó vertical.

El código para colocar las fichas de dominó horizontales en una fila se modifica a partir de esta respuesta mía: https://codegolf.stackexchange.com/a/37888/15599 . Es lento para las cuadrículas más anchas, pero eso no es un problema para el caso de 8x8.

La innovación está en la forma en que se ensamblan las filas. Si el tablero tiene un número impar de filas, se gira 90 grados en el análisis de entrada, por lo que ahora tiene un número par de filas. Ahora coloco algunas fichas de dominó verticales en la línea central. Debido a la simetría, si hay cformas de organizar las fichas de dominó restantes en la mitad inferior, también debe haber cformas de organizar las fichas de dominó restantes en la mitad superior, lo que significa que para una disposición dada de fichas de dominó verticales en la línea central, hay c*cposibles soluciones. . Por lo tanto, solo se analiza la línea central más la mitad del tablero cuando se requiere que el programa imprima solo el número de soluciones.

f()construye la tabla de posibles arreglos de fichas de dominó horizontales y explora las posibles disposiciones de fichas de dominó verticales en la línea central. luego llama a la función recursiva g()que llena las filas. Si se requiere imprimir, h()se llama a la función para hacer esto.

g()Se llama con 3 parámetros. yes la fila actual y des la dirección (arriba o abajo) en la que estamos llenando el tablero desde el centro hacia afuera. xcontiene un mapa de bits que indica las fichas de dominó verticales que están incompletas de la fila anterior. Se intentan todos los arreglos posibles de dominó en una fila desde r []. En esta matriz, un 1 representa un dominó vertical y un par de ceros un dominó horizontal. Una entrada válida en la matriz debe tener por lo menos lo suficiente como para terminar 1 de los dominós verticales incompletas desde la última fila: (x&r[j])==x. Puede tener más 1, lo que indica que se están comenzando nuevas fichas de dominó verticales. Para la siguiente fila, entonces, solo necesitamos las nuevas fichas de dominó, así que llamamos al procedimiento nuevamente con x^r[j].

Si se ha alcanzado una fila final y no hay dominó vertical incompleto colgando de la parte superior o inferior del tablero, x^r[j]==0entonces la mitad se ha completado con éxito. Si no estamos imprimiendo, es suficiente completar la mitad inferior y usar c*cpara calcular el número total de arreglos. Si estamos imprimiendo, será necesario completar también la mitad superior y luego llamar a la función de impresión 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");

}

Tenga en cuenta que la entrada con un número impar de filas y un número par de columnas se gira 90 grados en la fase de análisis. Si esto es inaceptable, la función de impresión h()se puede cambiar para acomodarlo. (EDITAR: no es obligatorio, ver comentarios).

EDITAR: Se e()ha utilizado una nueva función para verificar la paridad de i(es decir, el número de fichas de dominó que se ubican en la línea central). La paridad de i(la cantidad de medias fichas de dominó en la línea central que sobresale en cada mitad del tablero) debe ser la misma que la rareza del número total de espacios en cada mitad (dado por n/2) porque solo entonces las fichas de dominó pueden llenar todo el espacio disponible. Esta edición elimina la mitad de los valores de i y, por lo tanto, hace que mi programa sea aproximadamente el doble de rápido.