Zadanie

Napisz program, który odczytuje trzy liczby całkowite m , n albo ze STDIN, albo jako argumenty wiersza poleceń, drukuje wszystkie możliwe nachylenia prostokąta o wymiarach m × n przez domino 2 × 1 i 1 × 2, a na koniec liczbę prawidłowych przechyleń.

Domeny poszczególnych kafelków muszą być reprezentowane przez dwie kreski ( -) dla 2 × 1 i dwa pionowe słupki ( |) dla 1 × 2 dominów. Po każdym kafelku (w tym ostatnim) musi następować przesuw linii.

Do celów punktacji musisz również zaakceptować flagę ze STDIN lub jako argument wiersza poleceń, który powoduje, że Twój program wypisuje tylko liczbę prawidłowych nachyleń, ale nie same nachylenia.

Twój program nie może być dłuższy niż 1024 bajty. Musi działać dla wszystkich wejść, tak że m × n ≤ 64 .

(Zainspirowany przez Wydrukuj wszystkie domina z prostokątem 4x6 .)

Przykład

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

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Punktacja

Twój wynik zależy od czasu wykonania programu dla wejścia 8 8 z ustawioną flagą.

Aby ten kod był najszybszym, a nie najszybszym wyzwaniem komputerowym , uruchomię wszystkie zgłoszenia na własnym komputerze (Intel Core i7-3770, 16 GiB PC3-12800 RAM), aby ustalić oficjalny wynik.

Proszę zostawić szczegółowe instrukcje, jak skompilować i / lub wykonać swój kod. Jeśli potrzebujesz konkretnej wersji kompilatora / tłumacza swojego języka, złóż oświadczenie w tej sprawie.

Zastrzegam sobie prawo do pozostawienia zgłoszeń bez oceny, jeśli:

• Nie ma darmowego (jak w piwie) kompilatora / interpretera dla mojego systemu operacyjnego (Fedora 21, 64 bity).

• Pomimo naszych starań Twój kod nie działa i / lub generuje niepoprawne dane wyjściowe na moim komputerze.

• Kompilacja lub wykonanie trwa dłużej niż godzinę.

• Twój kod lub jedyny dostępny kompilator / interpreter zawiera wywołanie systemowe rm -rf ~lub coś równie podejrzanego.

Tabela liderów

Ponownie oceniłem wszystkie zgłoszenia, uruchamiając zarówno kompilacje, jak i wykonania w pętli z 10 000 iteracji do kompilacji i od 100 do 10 000 iteracji do wykonania (w zależności od szybkości kodu) i obliczając średnią.

Oto wyniki:

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.

do

Prosta implementacja ...

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

Wersja oszukująca

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

Wyjaśnienie szybszego algorytmu

Skanuje od lewej do prawej i utrzymuje stan d[i][j], w którym:

• ijest w [0,m), co oznacza bieżącą kolumnę.
• jjest bitowym wektorem wielkości n, gdzie bit wynosiłby 1, jeśli odpowiednia pozycja w kolumnie ijest już zajęta przed rozpoczęciem pracy nad tą kolumną. Tj. Jest zajęty przez prawą połowę --.
• d[i][j] to łączna liczba różnych przechyleń.

Następnie powiedz e[i][j]= suma, na d[i][k]której możesz umieścić pionowe podstawy domina, kaby utworzyć j. e[i][j]byłaby liczbą przechyleń, w której każdy 1 bit jjest zajęty przez cokolwiek poza lewą połową --. Wypełnij je, --a dostaniesz d[i+1][~j]= e[i][j]. e[m-1][every bit being 1]lub d[m][0]jest ostateczną odpowiedzią.

Naiwna implementacja zapewni Ci złożoność czasu gdzieś blisko g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)(już wystarczająco szybko, jeśli n = m = 8). Ale zamiast tego możesz najpierw wykonać pętlę dla każdego możliwego domina i spróbować dodać go do każdego kafelka, w którym można dodać to domino, i scalić wynik z oryginalną tablicą d(jak algorytm problemu Knapsack). I to staje się O (n * 2 ^ n). A wszystko inne to szczegóły implementacji. Cały kod działa w O (m * n * 2 ^ n).

do

Po rundzie optymalizacji i dostosowanej do zmodyfikowanych reguł:

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

Zacząłem wpadać na limit długości 1024 znaków, więc musiałem nieco zmniejszyć czytelność. Znacznie krótsze nazwy zmiennych itp.

Instrukcje budowania:

> gcc -O2 Code.c

Uruchom z włączonym wyjściem rozwiązania:

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

Uruchom tylko z liczbą rozwiązań:

> ./a.out 8 8 s

Niektóre komentarze:

• Przy większym przykładzie testowym chcę teraz optymalizacji. Podczas gdy mój system jest inny (Mac), wszystko -O2wydaje się być dobre.
• Kod zwolnił w przypadku generowania danych wyjściowych. Było to świadome poświęcenie dla optymalizacji trybu „tylko zliczanie” i dla zmniejszenia długości kodu.
• Pojawi się kilka ostrzeżeń kompilatora z powodu braku dołączeń i deklaracji zewnętrznych dla funkcji systemowych. To był najłatwiejszy sposób, aby uzyskać w końcu mniej niż 1024 znaki bez powodowania, że ​​kod byłby całkowicie nieczytelny.

Zauważ też, że kod nadal generuje rzeczywiste rozwiązania, nawet w trybie „tylko zliczanie”. Ilekroć znaleziono rozwiązanie, vMmaska ​​bitowa zawiera 1dla pozycji, które mają pionowy pasek, oraz 0dla pozycji z poziomym paskiem. Pomijana jest tylko konwersja tej maski bitowej do formatu ASCII i rzeczywiste wyjście.

do

Chodzi o to, aby najpierw znaleźć wszystkie możliwe układy poziomych domino w rzędzie, przechowywać je, r[]a następnie uporządkować, aby uzyskać wszystkie możliwe układy pionowych domino.

Kod do pozycjonowania poziomych domino w rzędzie został zmodyfikowany z tej mojej odpowiedzi: https://codegolf.stackexchange.com/a/37888/15599 . Jest wolniejszy w przypadku szerszych siatek, ale nie jest to problemem w przypadku 8x8.

Innowacja polega na sposobie montażu rzędów. Jeśli tablica ma nieparzystą liczbę rzędów, podczas analizy wejściowej jest obracana o 90 stopni, więc ma teraz parzystą liczbę rzędów. Teraz umieszczam pionowe domino wzdłuż linii środkowej. Ze względu na symetrię, jeśli istnieją csposoby ułożenia pozostałych domino w dolnej połowie, muszą istnieć również csposoby ułożenia pozostałych domino w górnej połowie, co oznacza, że ​​dla danego ułożenia pionowych domino na linii środkowej istnieją c*cmożliwe rozwiązania . Dlatego analizowana jest tylko linia środkowa plus połowa płytki, gdy program musi wydrukować tylko liczbę rozwiązań.

f()buduje tabelę możliwych ustawień domina poziomego i skanuje możliwe ustawienia pionu domina na linii środkowej. następnie wywołuje funkcję rekurencyjną, g()która wypełnia wiersze. Jeśli wymagane jest drukowanie, h()wywoływana jest funkcja, aby to zrobić.

g()jest wywoływany z 3 parametrami. yto bieżący rząd i dkierunek (w górę lub w dół), w którym wypełniamy planszę od środka na zewnątrz. xzawiera bitmapę, która wskazuje pionowe domino, które są niekompletne z poprzedniego rzędu. Wypróbowywane są wszystkie możliwe układy domino w rzędzie od r []. W tej tablicy 1 oznacza pionowy domino, a para zer poziomy domino. Ważny wpis w tablicy musi mieć co najmniej 1 na tyle, aby zakończyć niekompletne domina pionowy z ostatni wiersz (x&r[j])==x. Może zawierać więcej 1, co oznacza, że ​​uruchamiane są nowe domino pionowe. Do następnego wiersza potrzebujemy tylko nowych domino, więc ponownie wywołujemy procedurę za pomocą x^r[j].

Jeśli osiągnięto ostatni rząd i nie ma niekompletnych pionowych domino wiszących na górze lub na dole planszy, x^r[j]==0wówczas połowa została pomyślnie ukończona. Jeśli nie drukujemy, wystarczy wypełnić dolną połowę i użyć, c*caby obliczyć całkowitą liczbę aranżacji. Jeśli drukujemy, konieczne będzie uzupełnienie górnej połowy, a następnie wywołanie funkcji drukowania h().

KOD

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

}

Zauważ, że dane wejściowe z nieparzystą liczbą wierszy i parzystą liczbą kolumn są obracane o 90 stopni w fazie analizy. Jeśli jest to niedopuszczalne, funkcję drukowania h()można zmienić, aby ją dostosować. (EDYCJA: nie wymagane, patrz komentarze.)

EDYCJA: Nowa funkcja e()została użyta do sprawdzenia parzystości i(tj. Liczby domino okalających linię środkową). Parzystość i(liczba pół-domino na linii środkowej wystających do każdej połowy planszy) musi być taka sama jak dziwność całkowitej liczby spacji w każdej połowie (podana przez n/2), ponieważ tylko wtedy domina mogą wypełnić całą dostępną przestrzeń. Ta edycja eliminuje połowę wartości i, dzięki czemu mój program jest około dwa razy szybszy.