Schreiben Sie ein Programm oder eine Funktion , dass gegebene positive n und m die Anzahl der gültigen verschiedene Domino Pflasterungen berechnet Sie in einem passen n durch m Rechteck. Dies ist die Sequenz A099390 in der Online-Enzyklopädie der ganzzahligen Sequenzen . Sie können Eingaben als Funktionsargument (e), CLA oder auf stdin in einem beliebigen vernünftigen Format vornehmen. Sie müssen eine einzelne Ganzzahl als Ausgabe zurückgeben oder drucken.

Jede Kachelung darf keine Lücken hinterlassen, und jede einzelne Kachelung wird gezählt, einschließlich Rotationen, Reflexionen usw. Die Kacheln für 2x3 sind beispielsweise:

|--    |||    --| 
|--    |||    --|

Beispiel Ein- / Ausgänge:

1,  9 -> 0
2,  2 -> 2
2,  3 -> 3
4,  4 -> 36
4,  6 -> 281
6,  6 -> 6728
7, 10 -> 53175517

Ihr Programm sollte theoretisch für jedes n und m funktionieren , aber wenn Ihr Programm zu viel Speicher benötigt oder Ihr Datentyp überläuft, wird es entschuldigt. Ihr Programm muss jedoch für jedes n, m <= 8 korrekt funktionieren .

Der kürzeste Code in Bytes gewinnt.

Pyth, 30 29 Bytes

L?bsmy-tb]dfq1.a-VThbb1y*FUMQ

Probieren Sie es online aus: Demonstration / Test Suite

Alle Beispieleingaben werden im Online-Compiler ausgeführt. Der letzte dauert allerdings einige Sekunden.

Erläuterung:

In meinem Code werde ich eine rekursive Funktion definieren y. Die Funktion ynimmt eine Liste von 2D-Koordinaten und gibt anhand dieser Koordinaten die Anzahl der verschiedenen Domino-Kacheln zurück. ZB y([[0,0], [0,1]]) = 1(ein horizontaler Domino), y([[0,0], [1,1]]) = 0(Koordinaten sind nicht benachbart) und y([[0,0], [0,1], [1,0], [1,1]]) = 2(entweder zwei horizontale oder zwei vertikale Dominosteine). Nachdem ich die Funktion definiert habe, rufe ich sie mit allen Koordinaten [x,y]auf x in [0, 1, m-1], y in [0, 1, n-1].

Wie funktioniert die rekursive Funktion? Es ist ganz einfach. Wenn die Liste der Koordinaten leer ist, gibt es genau eine gültige Kachelung und ykehrt zurück 1.

Ansonsten nehme ich die erste Koordinate in der Liste b[0]und suche die verbleibenden Koordinaten nach einem Nachbarn. Wenn es keinen Nachbarn b[0]gibt, ist keine Kachelung möglich, daher gebe ich 0 zurück. Wenn es einen oder mehrere Nachbarn gibt, ist die Anzahl der Kacheln (die Anzahl der Kacheln, bei denen ich mich b[0]über eine Domina mit dem ersten Nachbarn verbinde, plus die Anzahl der Kacheln, bei denen ich mich b[0]mit dem zweiten Nachbarn verbinde, plus ...) Also rufe ich die Funktion rekursiv für jeden Nachbarn mit der verkürzten Liste auf (indem ich die beiden Koordinaten b[0]und den Nachbarn entferne ). Danach fasse ich alle Ergebnisse zusammen und gebe sie zurück.

Aufgrund der Reihenfolge der Koordinaten sind immer nur zwei Nachbarn möglich, der rechte und der untere. Aber mein Algorithmus kümmert sich nicht darum.

                          UMQ  convert the input numbers into ranges
                        *F     Cartesian product (coords of each square)
L                              define a function y(b):
 ?b                              if len(b) > 0:
           f         b             filter b for squares T, which satisfy:
              .a-VThb                Euclidean distance between T and b[0]
            q1                       is equal to 1 (direct neighbors)
    m                              map each neighbor d to:
      -tb]d                          remove d from b[1]
     y                               and call recursively y with the rest
   s                               sum all those values and return them
                                 else:
                      1            return 1 (valid domino tiling found)
                       y*FUMQ  Call y with all coords and print the result  

Matlab, 292

Ich bin sicher, dass dies sehr verkürzt werden kann, wenn man es einfach in eine andere Sprache portiert.

Die Grundidee ist Bruteforcing: Ich habe mir eine Art Aufzählung aller Möglichkeiten ausgedacht, wie man m*n/2Dominosteine ​​auf ein m*nBrett legt . Diese Aufzählung enthält jedoch auch viele ungültige Kacheln (Steine, die sich überlappen oder außerhalb der Tafel liegen). Das Programm erstellt also alle diese Kacheln und zählt nur die gültigen. Die Laufzeitkomplexität ist ungefähr O(2^(m*n/2) * m*n). Speicher ist kein Problem für die, 8x8da er nur O(m*n)Speicher benötigt . Die dafür benötigte Zeit 8x8beträgt jedoch etwa 20 Tage.

Hier die vollständig kommentierte Version, die erklärt, was los ist.

PS: Wenn jemand weiß, wie die Hervorhebung der Matlab-Syntax funktioniert, fügen Sie bitte das entsprechende Tag in diese Antwort ein!

function C=f(m,n)
d = ceil(m*n/2);%number of dominoes
%enumeration: %the nth bit in the enumeration says whether the nth 
% domino pice is upright or not. we enumerate like this:
% firt piece goes top left:
% next piece goes to the left most column that has an empty spot, in the
% top most empty spot of that column
C=0;%counter of all valid tilings
for e=0:2^d-1 %go throu all enumerations
    %check whether each enumeration is valid
    A = ones(m,n);
    %empty spots are filled with 1
    %filled spots are 0 (or if overlapping <0) 
    v=1;%flag for the validity. hte grid is assumed to be valid until proven otherwise
    for i=1:d %go throu all pieces, place them in A
        %find the column where to place:
        c=find(sum(A)>0,1);
        %find the row where to place:
        r=find(A(:,c)>0,1);
        %find direction of piece:
        b=de2bi(e,d);
        if b(i)
            x=0;y=1;
        else
            x=1;y=0;
        end
        %fill in the piece:
        try
            A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;
        catch z
            v=0;break;
        end
        %check whether A has no overlapping pieces
        if any(A(:)<0)
            v=0;break;
        end
    end
    %if valid, count it as valid
    if v && ~norm(A(:))
        disp(A)
        C=C+1;
    end
end

Hier der voll Golf:

function C=f(m,n);m=4;n=6;d=ceil(m*n/2);C=0;for e=0:2^d-1;A=ones(m,n);v=1;for i=1:d;c=find(sum(A)>0,1);r=find(A(:,c)>0,1);b=de2bi(e,d);if b(i);x=0;y=1;else;x=1;y=0;end;try;A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;catch z;v=0;break;end;if any(A(:)<0);v=0;break;end;end;if v && ~norm(A(:));C=C+1;end;end

C89, 230 Bytes

f(n,m,b)int*b;{int s,i;s=i=0;
while(b[i])if(++i==n*m)return 1;
if(i/n<m-1){b[i]=b[i+n]=1;s+=f(n,m,b);b[i]=b[i+n]=0;}
if(i%n<n-1&&!(b[i]|b[i+1])){b[i]=b[i+1]=1;s+=f(n,m,b);b[i]=b[i+1]=0;}
return s;}
g(n,m){int b[99]={};return f(n,m,b);}

Zur besseren Lesbarkeit habe ich diese Antwort handverpackt - alle Zeilenumbrüche können sicher entfernt werden, um 230 Byte zu erreichen.

Definiert eine Funktion int g(int n, int m), die die Anzahl der Kacheln zurückgibt. Es verwendet eine fHilfsfunktion, die alle gültigen Kacheln durchläuft, indem ein Domino platziert, rekursiv und dann auf einer gemeinsam genutzten Karte entfernt wird.

Python 243

Ich habe mich für einen Brute-Force-Ansatz entschieden:

• m * n / 2 Richtungen erzeugen;
• Versuchen Sie, den Domino auf das m * n-Brett zu setzen.

Wenn sie alle passen und keine Leerzeichen mehr vorhanden sind, haben wir einen gültigen Eintrag.

Hier ist der Code:

import itertools as t
m,n=input()
c,u=0,m*n
for a in t.product([0,1],repeat=u/2):
 l,k,r,h=[' ',]*u,0,'-|',[1,m]
 for t in a:
  l[k]=r[t]
  k+=h[t]   
  if k%m<m and k/m<n and l[k]==' ':l[k]=r[t]
  k=''.join(l).find(' ',1)
 if k<0:c+=1
print c