Número de inclinação de dominó

9

Escreva um programa ou função que, dado positivo n e m, calcule o número de inclinações de dominó distintas válidas que você pode ajustar em um retângulo n por m . Essa é a sequência A099390 na Enciclopédia on - line de sequências inteiras . Você pode inserir dados como argumento (s) de função, CLA ou stdin, em qualquer formato razoável. Você deve retornar ou imprimir um único número inteiro como saída.

Cada lado a lado não deve deixar nenhum espaço, e todos os lado a lado são contados, incluindo rotações, reflexões, etc. Por exemplo, as inclinações para 2x3 são:

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

Exemplos de entradas / saídas:

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

Seu programa deve, teoricamente, trabalhar para qualquer n e m , mas se o seu programa requer muita memória ou o seu tipo de dados transborda ele está dispensado. Seu programa deve funcionar corretamente para qualquer n, m <= 8 no entanto.


O menor código em bytes vence.

orlp
fonte
Você poderia ter tornado nossa vida muito mais fácil se você tivesse permitido áreas de 2n x 2m , bom desafio!
flawr
Assim como esta questão codegolf.stackexchange.com/q/51067/15599 apenas mais curta e mais lenta #
Level River St
@ edc65 Damnit = / Parece que não consigo pensar em nada novo ... Quase todos os desafios que penso já foram feitos de alguma forma. De qualquer forma, os desafios não são exatamente os mesmos, pois minha pergunta é um código de golfe e você não precisa encontrar as inclinações - apenas a quantidade delas. Talvez as pessoas possam usar boas fórmulas em vez de escrever um bruteforcer.
orlp
Concordou - indo para remover o outro comentário
edc65
Comentário copiado do bilbo (que ele postou como resposta devido a 1 representante): "Este problema é um desafio do SPOJ abreviado: spoj.com/problems/MNTILE O código mais curto do SPOJ é de 98 bytes no awk." . Parece que eu sou duplamente sem originalidade - eu não sabia.
orlp

Respostas:

3

Pitão, 30 29 bytes

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

Experimente on-line: Demonstration / Test Suite

Todas as entradas de exemplo são executadas no compilador online. O último leva alguns segundos.

Explicação:

No meu código, definirei uma função recursiva y. A função ypega uma lista de coordenadas 2D e retorna o número de diferentes inclinação do dominó usando essas coordenadas. Por exemplo y([[0,0], [0,1]]) = 1(um dominó horizontal), y([[0,0], [1,1]]) = 0(as coordenadas não são adjacentes) e y([[0,0], [0,1], [1,0], [1,1]]) = 2(dois dominós horizontais ou dois verticais). Depois de definir a função, chamarei com todas as coordenadas [x,y]com x in [0, 1, m-1], y in [0, 1, n-1].

Como funciona a função recursiva? É bem simples Se a lista de cordas estiver vazia, haverá exatamente um lado a lado e yretornos válidos 1.

Caso contrário, pego a primeira coordenada da lista b[0]e busco as demais coordenadas por vizinhos. Se não houver vizinho b[0], então não será possível colocar lado a lado, portanto, retornarei 0. Se houver um ou mais vizinhos, o número de inclinações será (o número de inclinações em que eu me conecto b[0]com o primeiro vizinho através de uma domina, mais o número de inclinações em que eu me conecto b[0]com o segundo vizinho, mais ...) Então chamo a função recursivamente para cada vizinho com a lista abreviada (removendo as duas cordas b[0]e o vizinho). Depois, resumi todos os resultados e os devolvo.

Por causa da ordem dos cabos, sempre existem apenas dois vizinhos possíveis, o do lado direito e o abaixo. Mas meu algoritmo não se importa com isso.

                          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  
Jakube
fonte
Você pode nos contar um pouco mais sobre como seu programa funciona? Não consegui descobrir seu algoritmo a partir dos comentários.
flawr
@ flawr Adicionei uma explicação do meu algoritmo.
Jakube 26/08/15
@ Jaketube Obrigado pela explicação, eu realmente gosto da abordagem recursiva!
flawr
3

Matlab, 292

Estou certo de que isso pode ser muito reduzido, apenas portando-o para outro idioma.

A idéia básica é a brutalidade: criei uma espécie de enumeração de todas as maneiras de como colocar m*n/2tijolos de dominó em uma m*nplaca. Mas essa enumeração também inclui muitas inclinações inválidas (tijolos que se sobrepõem ou ficam fora do quadro). Portanto, o programa constrói todas essas inclinações e conta apenas as válidas. A complexidade do tempo de execução é sobre O(2^(m*n/2) * m*n). A memória não é um problema para o sistema 8x8, pois apenas precisa de O(m*n)memória. Mas o tempo necessário 8x8é de cerca de 20 dias.

Aqui a versão totalmente comentada que explica o que está acontecendo.

PS: Se alguém souber como fazer o destaque da sintaxe do Matlab funcionar, inclua a tag correspondente nesta resposta!

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

Aqui o totalmente golfe:

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
flawr
fonte
2

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

Para facilitar a leitura, envolvi manualmente esta resposta - todas as novas linhas podem ser removidas com segurança para obter 230 bytes.

Define uma função int g(int n, int m)que retorna o número de inclinações. Ele usa uma função auxiliar fque itera sobre todas as inclinações válidas, colocando um dominó, recorrendo e removendo o dominó em uma placa compartilhada.

orlp
fonte
0

Python 243

Optei por uma abordagem de força bruta:

  • gerar m * n / 2 direções;
  • tente encaixar o dominó na placa m * n.

Se todos eles se ajustarem e não houver espaço, teremos uma entrada válida.

Aqui está o código:

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
Willem
fonte