Aufgabe

Schreiben Sie ein Programm, das drei Ganzzahlen m , n entweder aus STDIN oder als Befehlszeilenargumente liest , alle möglichen Kacheln eines Rechtecks ​​der Dimensionen m × n mit 2 × 1 und 1 × 2 Dominos und schließlich die Anzahl der gültigen Kacheln druckt.

Dominos einer einzelnen Kachelung müssen durch zwei Striche ( -) für 2 × 1 und zwei vertikale Balken ( |) für 1 × 2 Dominos dargestellt werden. Auf jede Kachelung (einschließlich der letzten) muss ein Zeilenvorschub folgen.

Für Bewertungszwecke müssen Sie auch ein Flag von STDIN oder als Befehlszeilenargument akzeptieren, mit dem Ihr Programm nur die Anzahl der gültigen Kacheln druckt, nicht jedoch die Kacheln selbst.

Ihr Programm darf nicht länger als 1024 Byte sein. Es muss für alle Eingänge so funktionieren, dass m × n ≤ 64 ist .

(Inspiriert von Alle Domino-Kacheln des 4x6-Rechtecks ​​drucken .)

Beispiel

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

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Wertung

Ihre Punktzahl wird durch die Ausführungszeit Ihres Programms für die Eingabe 8 8 mit gesetztem Flag bestimmt.

Um dies zu einem schnellsten Code und nicht zu einer schnellsten Computerherausforderung zu machen , führe ich alle Einsendungen auf meinem eigenen Computer (Intel Core i7-3770, 16 GiB PC3-12800 RAM) aus, um die offizielle Punktzahl zu ermitteln.

Bitte hinterlassen Sie detaillierte Anweisungen zum Kompilieren und / oder Ausführen Ihres Codes. Wenn Sie eine bestimmte Version des Compilers / Interpreters Ihrer Sprache benötigen, geben Sie eine entsprechende Erklärung ab.

Ich behalte mir das Recht vor, Einsendungen unbewertet zu lassen, wenn:

• Für mein Betriebssystem (Fedora 21, 64 Bit) gibt es keinen kostenlosen Compiler / Interpreter (wie bei Bier).

• Trotz unserer Bemühungen funktioniert Ihr Code nicht und / oder erzeugt auf meinem Computer eine falsche Ausgabe.

• Das Kompilieren oder Ausführen dauert länger als eine Stunde.

• Ihr Code oder der einzige verfügbare Compiler / Interpreter enthält einen Systemaufruf rm -rf ~oder etwas ähnlich fauliges.

Bestenliste

Ich habe alle Einsendungen neu bewertet, sowohl Kompilierungen als auch Ausführungen in einer Schleife mit 10.000 Iterationen für die Kompilierung und zwischen 100 und 10.000 Iterationen für die Ausführung (abhängig von der Geschwindigkeit des Codes) ausgeführt und den Mittelwert berechnet.

Dies waren die Ergebnisse:

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.

Eine unkomplizierte Implementierung ...

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

Die betrügerische Version

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

Erklärung des schnelleren Algorithmus

Es scannt von links nach rechts und behält den Zustand bei d[i][j], in dem:

• iist in [0,m), was bedeutet, die aktuelle Spalte.
• jist ein Bitvektor der Größe n, wobei das Bit 1 wäre, wenn die entsprechende Position in der Spalte ibereits belegt ist, bevor mit der Arbeit an dieser Spalte begonnen wird. Dh es ist von der rechten Hälfte eines besetzt --.
• d[i][j] ist die Gesamtzahl der verschiedenen Fliesen.

Sagen Sie dann e[i][j]= die Summe, d[i][k]auf die Sie vertikale Dominosteine ​​setzen können, um a kzu bilden j. e[i][j]wäre die Anzahl der Kacheln, bei denen jedes 1 Bit in jetwas anderem als der linken Hälfte von a belegt ist --. Füllen Sie sie mit --und Sie erhalten d[i+1][~j]= e[i][j]. e[m-1][every bit being 1]oder d[m][0]ist die endgültige Antwort.

Eine naive Implementierung bringt Ihnen die zeitliche Komplexität in die Nähe g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n)(bereits schnell genug, wenn n = m = 8). Sie können jedoch zunächst eine Schleife für jedes mögliche Domino erstellen und versuchen, es zu jeder Kachelung hinzuzufügen, zu der dieses Domino hinzugefügt werden kann, und das Ergebnis mit dem ursprünglichen Array zusammenführen d(wie der Algorithmus für das Knapsack-Problem). Und dies wird O (n * 2 ^ n). Und alles andere sind Implementierungsdetails. Der gesamte Code läuft in O (m * n * 2 ^ n).

C.

Nach einer Optimierungsrunde und angepasst an die geänderten Regeln:

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

Ich habe angefangen, die Längenbeschränkung von 1024 Zeichen zu überschreiten, daher musste ich die Lesbarkeit etwas verringern. Viel kürzere Variablennamen usw.

Bauanleitung:

> gcc -O2 Code.c

Mit aktivierter Lösungsausgabe ausführen:

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

Nur mit Lösungsanzahl ausführen:

> ./a.out 8 8 s

Einige Kommentare:

• Mit dem größeren Testbeispiel möchte ich jetzt eine Optimierung. Während mein System anders ist (Mac), -O2scheint es gut zu sein.
• Der Code ist für den Fall, dass eine Ausgabe generiert wird, langsamer geworden. Dies war ein bewusstes Opfer für die Optimierung des "Nur zählen" -Modus und für die Reduzierung der Codelänge.
• Es werden einige Compiler-Warnungen angezeigt, da Includes und externe Deklarationen für Systemfunktionen fehlen. Es war der einfachste Weg, mich am Ende auf unter 1024 Zeichen zu bringen, ohne den Code völlig unlesbar zu machen.

Beachten Sie auch, dass der Code auch im Modus "Nur zählen" die tatsächlichen Lösungen generiert. Immer wenn eine Lösung gefunden wird, vMenthält die Bitmaske a 1für Positionen mit vertikalem Balken und a 0für Positionen mit horizontalem Balken. Nur die Konvertierung dieser Bitmaske in das ASCII-Format und die tatsächliche Ausgabe werden übersprungen.

C.

Das Konzept besteht darin, zuerst alle möglichen Anordnungen horizontaler Dominosteine ​​in einer Reihe zu finden, sie darin zu speichern r[]und dann zu organisieren, um alle möglichen Anordnungen vertikaler Dominosteine ​​zu erhalten.

Der Code zum Positionieren der horizontalen Dominosteine ​​in einer Reihe wurde anhand meiner Antwort geändert: /codegolf//a/37888/15599 . Für die breiteren Gitter ist es langsam, aber für den 8x8-Fall ist das kein Problem.

Die Innovation liegt in der Art und Weise, wie die Reihen zusammengesetzt werden. Wenn die Karte eine ungerade Anzahl von Zeilen hat, wird sie beim Parsen der Eingabe um 90 Grad gedreht, sodass sie jetzt eine gerade Anzahl von Zeilen hat. Jetzt platziere ich einige vertikale Dominosteine ​​über der Mittellinie. Wenn es aufgrund der Symmetrie cMöglichkeiten gibt, die verbleibenden Dominosteine ​​in der unteren Hälfte anzuordnen, muss es auch cMöglichkeiten geben, die verbleibenden Dominosteine ​​in der oberen Hälfte anzuordnen, was bedeutet, dass es für eine bestimmte Anordnung vertikaler Dominosteine ​​auf der Mittellinie c*cmögliche Lösungen gibt . Daher wird nur die Mittellinie plus die Hälfte der Platine analysiert, wenn das Programm nur die Anzahl der Lösungen drucken muss.

f()Erstellt die Tabelle möglicher Anordnungen horizontaler Dominosteine ​​und durchsucht die möglichen Anordnungen vertikaler Dominosteine ​​auf der Mittellinie. es ruft dann eine rekursive Funktion auf, g()die die Zeilen ausfüllt. Wenn Drucken erforderlich ist, wird dazu die Funktion h()aufgerufen.

g()wird mit 3 Parametern aufgerufen. yist die aktuelle Zeile und dist die Richtung (nach oben oder unten), in der wir das Brett von der Mitte nach außen füllen. xenthält eine Bitmap, die die vertikalen Dominosteine ​​angibt, die aus der vorherigen Zeile unvollständig sind. Alle möglichen Anordnungen von Dominosteinen in einer Reihe von r [] werden versucht. In diesem Array repräsentiert eine 1 ein vertikales Domino und ein Nullpaar ein horizontales Domino. Ein gültiger Eintrag im Array muss mindestens genug Einsen enthalten, um unvollständige vertikale Dominosteine ​​aus der letzten Zeile zu beenden : (x&r[j])==x. Es kann mehr Einsen geben, was darauf hinweist, dass neue vertikale Dominosteine ​​gestartet werden. Für die nächste Reihe brauchen wir also nur die neuen Dominosteine, also rufen wir die Prozedur erneut mit auf x^r[j].

Wenn eine Endreihe erreicht wurde und keine unvollständigen vertikalen Dominosteine ​​oben oder unten auf dem Brett hängen, wurde x^r[j]==0die Hälfte erfolgreich abgeschlossen. Wenn wir nicht drucken, reicht es aus, die untere Hälfte zu vervollständigen und c*cdie Gesamtzahl der Arrangements zu berechnen. Wenn wir drucken, muss auch die obere Hälfte ausgefüllt und dann die Druckfunktion aufgerufen werden h().

CODE

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

}

Beachten Sie, dass die Eingabe mit einer ungeraden Anzahl von Zeilen und einer geraden Anzahl von Spalten in der Analysephase um 90 Grad gedreht wird. Wenn dies nicht akzeptabel ist, kann die Druckfunktion h()geändert werden, um sie aufzunehmen. (BEARBEITEN: nicht erforderlich, siehe Kommentare.)

BEARBEITEN: Eine neue Funktion e()wurde verwendet, um die Parität von i(dh die Anzahl der Dominos auf der Mittellinie) zu überprüfen . Die Parität von i(die Anzahl der halben Dominosteine ​​auf der Mittellinie, die in jede Hälfte des Bretts hineinragen) muss dieselbe sein wie die Seltsamkeit der Gesamtzahl der Felder in jeder Hälfte (gegeben durch n/2), weil nur dann die Dominosteine ​​den gesamten verfügbaren Raum ausfüllen können. Diese Bearbeitung eliminiert die Hälfte der Werte von i und macht mein Programm daher ungefähr doppelt so schnell.