Eu prometo, este será o meu último desafio sobre inclinações de diamong (por um tempo, pelo menos). Pelo lado positivo, esse desafio não tem nada a ver com arte ASCII e também não é um código de golfe, portanto, na verdade, é completamente diferente.

Assim, como lembrete, todo hexágono pode ser intitulado com três diamantes diferentes:

Uma pergunta interessante a ser feita é quantas dessas inclinações existem para um determinado tamanho de hexágono. Parece que esses números foram estudados minuciosamente e podem ser encontrados no OEIS A008793 .

No entanto, o problema fica mais complicado se perguntarmos quantas inclinações existem até a rotação e a reflexão . Por exemplo, para o comprimento lateral N = 2, existem as 20 inclinações a seguir:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Mas muitos deles são idênticos sob rotação e reflexão. Se levarmos em conta essas simetrias, restam apenas 6 inclinações distintas:

   ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\_\/_/\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/\_\_\/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/ 

   2        2        6        6        1        3

onde os números indicam a multiplicidade de cada lado a lado. Observe que para hexágonos maiores também existem inclinações com multiplicidades 4 e 12.

Parece que o número de inclinações até simetria foi estudado menos minuciosamente. A entrada OEIS A066931 lista apenas os cinco termos:

1, 1, 6, 113, 20174

onde o primeiro termo é para comprimento lateral N = 0e o último termo para comprimento lateral N = 4.

Tenho certeza que podemos fazer melhor que isso!

Sua tarefa é calcular o número de inclinações para um determinado comprimento lateral.

Este é o código mais rápido . Sua pontuação terá o maior comprimento lateral Npara o qual seu código produzirá o resultado correto em 30 minutos na minha máquina. Em caso de empate, vou aceitar a submissão que produz o resultado para que N mais rápido.

Como de costume, você não deve codificar os resultados que já conhece para vencer o desempate. O algoritmo que resolve N = 3deve ser idêntico ao que resolve N = 5.

Seu envio não deve usar mais de 4 GB de memória. Vou dar uma margem de manobra se você estiver operando próximo a esse limite, mas se você estiver consistentemente acima desse limite ou se atingir um pico significativamente além dele, não contarei isso Npara sua apresentação.

Testarei todos os envios na minha máquina com Windows 8, para garantir que seu idioma preferido esteja disponível gratuitamente no Windows. A única exceção é o Mathematica (porque, por acaso, tenho uma licença). Por favor, inclua instruções sobre como compilar / executar seu código.

Obviamente, sinta-se à vontade para calcular mais termos em seu próprio tempo (para a ciência e para outros verificarem seus números), mas a pontuação da sua resposta será determinada nesses 30 minutos.

Álgebra, teoria dos grafos, inversão de Möbius, pesquisa e Java

O grupo de simetria do hexágono é o grupo diédrico da ordem 12 e é gerado por uma rotação de 60 graus e um espelho girar através de um diâmetro. Ele possui 16 subgrupos, mas alguns deles estão em grupos de conjugação não triviais (os que têm apenas reflexões têm 3 opções de eixo); portanto, existem 10 simetrias fundamentalmente diferentes que um lado a lado do hexágono pode ter:

O número de inclinações de diamante de um subconjunto de uma rede triangular pode ser calculado como um determinante . Portanto, minha abordagem inicial foi estabelecer um determinante para cada uma das simetrias do hexágono, para calcular o número de inclinações que possuem pelo menos essas simetrias. ; e então use a inversão de Möbius na álgebra de incidência de seu poset (basicamente uma generalização do princípio de inclusão-exclusão) para calcular o número de inclinações cujo grupo de simetria é exatamente cada um dos 10 casos. No entanto, algumas das simetrias têm condições de borda desagradáveis, então fui forçado a somar exponencialmente muitos determinantes. Felizmente, os valores obtidos paran < 10forneceu dados suficientes para poder identificar sequências relevantes no OEIS e reunir um formulário fechado (para algum valor de "fechado", que permite produtos finitos). Há um pouco de discussão sobre as seqüências e referências a provas na redação formal que eu preparei para justificar as atualizações da sequência OEIS.

Uma vez que a contagem dupla é resolvida, quatro dos dez valores são cancelados ordenadamente; portanto, precisamos apenas calcular os seis restantes e fazer uma soma ponderada.

Esse código leva menos de 30 segundos para N=1000na minha máquina.

import java.math.BigInteger;

public class OptimisedCounter {
    private static int[] minp = new int[2];

    public static void main(String[] args) {
        if (args.length > 0) {
            for (String arg : args) System.out.println(count(Integer.parseInt(arg)));
        }
        else {
            for (int n = 0; n < 16; n++) {
                System.out.format("%d\t%s\n", n, count(n));
            }
        }
    }

    private static BigInteger count(int n) {
        if (n == 0) return BigInteger.ONE;

        if (minp.length < 3*n) {
            int[] wider = new int[3*n];
            System.arraycopy(minp, 0, wider, 0, minp.length);
            for (int x = minp.length; x < wider.length; x++) {
                // Find the smallest prime which divides x
                for (wider[x] = 2; x % wider[x] != 0; wider[x]++) { /* Do nothing */ }
            }
            minp = wider;
        }

        BigInteger E = countE(n), R2 = countR2(n), F = countF(n), R3 = countR3(n), R = countR(n), FR = countFR(n);
        BigInteger sum = E.add(R3);
        sum = sum.add(R2.add(R).multiply(BigInteger.valueOf(2)));
        sum = sum.add(F.add(FR).multiply(BigInteger.valueOf(3)));
        return sum.divide(BigInteger.valueOf(12));
    }

    private static BigInteger countE(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR2(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            w[3*i+2]++;
            for (int j = 3*i + 1; j <= 2*i + n + 1; j++) w[j]--;
            for (int j = 2*i + n + 1; j <= i + n + n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countF(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = 2*i + 1; j <= 2*i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR3(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        return countE(n / 2).pow(2);
    }

    private static BigInteger countR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*m-1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= 3*i+1; j++) w[j] += 2;
            for (int j = 1; j <= i + m; j++) w[j] -= 2;
        }
        return powerProd(w);
    }

    private static BigInteger countFR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*n-2];
        for (int j = 1; j <= m; j++) w[j]--;
        for (int j = 2*m; j <= 3*m-1; j++) w[j]++;
        for (int i = 0; i <= 2*m-3; i++) {
            for (int j = i + 2*m + 1; j <= i + 4*m; j++) w[j]++;
            for (int j = 2*i + 3; j <= 2*i + 2*m + 2; j++) w[j]--;
        }
        return powerProd(w);
    }

    private static BigInteger powerProd(int[] w) {
        BigInteger result = BigInteger.ONE;
        for (int x = w.length - 1; x > 1; x--) {
            if (w[x] == 0) continue;

            int p = minp[x];
            if (p == x) result = result.multiply(BigInteger.valueOf(p).pow(w[p]));
            else {
                // Redistribute it. This should ensure we avoid negatives.
                w[p] += w[x];
                w[x / p] += w[x];
            }
        }

        return result;
    }
}

C

Introdução

Como comentado por David Carraher, a maneira mais simples de analisar o lado a lado do hexágono parecia ser tirar proveito de seu isomorfismo com o Diagrama Jovem tridimensional, essencialmente um quadrado x, y preenchido com barras de altura inteiras cujas alturas z devem permanecer iguais ou aumentar à medida que o eixo z é aproximado.

Comecei com um algoritmo para encontrar os totais que são mais passíveis de adaptação para contagem de simetria do que o algoritmo publicado, que é baseado em um viés para um dos três eixos cartesianos.

Algoritmo

Começo preenchendo as células dos planos x, ye z com 1's, enquanto o restante da área contém zeros. Feito isso, construo o padrão camada por camada, com cada camada contendo as células que têm uma distância de Manhattan em 3D comum da origem. Uma célula pode conter apenas 1 se as três células abaixo também contiverem um 1. Se alguma delas contiver 0, a célula deverá ser 0.

A vantagem de construir o padrão dessa maneira é que cada camada é simétrica em relação à linha x = y = z. Isso significa que cada camada pode ser verificada independentemente para simetria.

Verificação de simetria

As simetrias do sólido são as seguintes: rotação de 3 vezes em torno da linha x = y = z -> rotação de 3 vezes em torno do centro do hexágono; e 3 x reflexões sobre os 3 planos que contêm a linha x = y = z e cada um dos eixos x, y, z -> reflexão sobre as linhas através dos cantos do hexágono.

Isso adiciona apenas 6 vezes a simetria. Para obter a simetria completa do hexágono, outro tipo de simetria deve ser considerado. Cada sólido (construído a partir de 1s) possui um sólido complementar (construído a partir de 0s). Onde N é ímpar, o sólido complementar deve ser diferente do sólido original (porque não é possível que eles tenham o mesmo número de cubos). No entanto, quando o sólido complementar é girado em volta, verifica-se que sua representação 2D como um diamante é idêntica (exceto para uma operação de simetria 2 vezes) ao sólido original. Onde N é par, é possível que o sólido seja auto-inverso.

Isso pode ser visto nos exemplos de N = 2 na pergunta. Se visto da esquerda, o primeiro hexágono parece um cubo sólido com 8 cubos pequenos, enquanto o último hexágono parece uma concha vazia com 0 cubos pequenos. Se visto da direita, o inverso é verdadeiro. O 3º, 4º e 5º hexágonos e os 16º, 17º e 18º hexágonos parecem conter 2 ou 6 cubos e, portanto, se complementam em 3 dimensões. Eles estão relacionados entre si em duas dimensões por uma operação de simetria de duas vezes (rotação de duas vezes ou reflexão sobre um eixo através das bordas do hexágono). Por outro lado, os hexágonos 9, 10, 11 e 12 mostram padrões 3D que são seus próprios complementos e, portanto, têm uma simetria mais alta (esses são, portanto, os únicos padrões com multiplicidade ímpar).

Observe que ter (N ^ 3) / 2 cubos é uma condição necessária para o auto-complemento, mas, em geral, não é uma condição suficiente se N> 2. O resultado de tudo isso é que, para N ímpar, as inclinações sempre ocorrem em pares (N ^ 3) / 2 cubos devem ser cuidadosamente inspecionados.

Código atual (gera o total correto para N = 1,2,3,5. Erro conforme discutido para N = 4).

int n;                     //side length

char t[11][11][11];        //grid sized for N up to 10

int q[29][192], r[29];     //tables of coordinates for up to 10*3-2=28 layers 

int c[9];                  //counts arrangements found by symmetry class. c[8] contains total.


//recursive layer counting function. m= manhattan distance, e= number of cells in previous layers, s=symmetry class.
void f(int m,int e,int s){

  int u[64], v[64], w[64]; //shortlists for x,y,z coordinates of cells in this layer
  int j=0;                 
  int x,y,z;

  for (int i=r[m]*3; i; i-=3){
    // get a set of coordinates for a cell in the current layer.
    x=q[m][i-3]; y= q[m][i-2]; z= q[m][i-1];
    // if the three cells in the previous layer are filled, add it to the shortlist u[],v[],w[]. j indicates the length of the shortlist.
    if (t[x][y][z-1] && t[x][y-1][z] && t[x-1][y][z]) u[j]=x, v[j]=y, w[j++]=z ;
  }


  // there are 1<<j possible arrangements for this layer.   
  for (int i = 1 << j; i--;) {

    int d = 0;

    // for each value of i, set the 1's bits of t[] to the 1's bits of i. Count the number of 1's into d as we go.
    for (int k = j; k--;) d+=(t[u[k]][v[k]][w[k]]=(i>>k)&1);

    // we have no interest in i=0 as it is the empty layer and therefore the same as the previous recursion step. 
    // Still we loop through it to ensure t[] is properly cleared.      

    if(i>0){
      int s1=s;    //local copy of symmetry class. 1's bit for 3 fold rotation, 2's bit for reflection in y axis.
      int sc=0;    //symmetry of self-complement.

      //if previous layers were symmetrical, test if the symmetry has been reduced by the current layer 
      if (s1) for (int k = j; k--;) s1 &= (t[u[k]][v[k]][w[k]]==t[w[k]][u[k]][v[k]]) | (t[u[k]][v[k]][w[k]]==t[w[k]][v[k]][u[k]])<<1;

      //if exactly half the cells are filled, test for self complement
      if ((e+d)*2==n*n*n){
        sc=1;
        for(int A=1; A<=(n>>1); A++)for(int B=1; B<=n; B++)for(int C=1; C<=n; C++) sc&=t[A][B][C]^t[n+1-A][n+1-B][n+1-C];
      }

      //increment counters for total and for symmetry class.
      c[8]++; c[s1+(sc<<2)]++;

      //uncomment for graphic display of each block stacking with metadata. not recommended for n>3.
      //printf("m=%d  j=%d  i=%d c1=%d-2*%d=%d c3=%d cy=%d(cs=%d) c3v=%d ctot=%d\n",m,j,i,c[0],c[2],c[0]-2*c[2],c[1],c[2],c[2]*3,c[3],c[8]);
      //printf("m=%d  j=%d  i=%d C1=%d-2*%d=%d C3=%d CY=%d(CS=%d) C3V=%d ctot=%d\n",m,j,i,c[4],c[6],c[4]-2*c[6],c[5],c[6],c[6]*3,c[7],c[8]);
      //for (int A = 0; A<4; A++, puts(""))for (int B = 0; B<4; B++, printf(" "))for (int C = 0; C<4; C++) printf("%c",34+t[A][B][C]);

      //recurse to next level.
      if(m<n*3-2)f(m + 1,e+d,s1);

    }
  } 
}

main()
{
  scanf("%d",&n);

  int x,y,z;

  // Fill x,y and z planes of t[] with 1's
  for (int a=0; a<9; a++) for (int b=0; b<9; b++) t[a][b][0]= t[0][a][b]= t[b][0][a]= 1;

  // Build table of coordinates for each manhattan layer
  for (int m=1; m < n*3-1; m++){
    printf("m=%d : ",m);
    int j=0;
    for (x = 1; x <= n; x++) for (y = 1; y <= n; y++) {
      z=m+2-x-y;
      if (z>0 && z <= n) q[m][j++] = x, q[m][j++] = y, q[m][j++]=z, printf(" %d%d%d ",x,y,z);
      r[m]=j/3;
    }
    printf(" : r=%d\n",r[m]);
  }

  // Set count to 1 representing the empty box (symmetry c3v)
  c[8]=1; c[3]=1; 

  // Start searching at f=1, with 0 cells occupied and symmetry 3=c3v
  f(1,0,3); 

  // c[2 and 6] only contain reflections in y axis, therefore must be multiplied by 3.
  // Similarly the reflections in x and z axis must be subtracted from c[0] and c[4].
  c[0]-=c[2]*2; c[2]*=3; 
  c[4]-=c[6]*2; c[6]*=3;



  int cr[9];cr[8]=0;
  printf("non self-complement                   self-complement\n");
  printf("c1  %9d/12=%9d           C1  %9d/6=%9d\n",   c[0], cr[0]=c[0]/12,     c[4], cr[4]=c[4]/6);
  if(cr[0]*12!=c[0])puts("c1 division error");if(cr[4]*6!=c[4])puts("C1 division error");

  printf("c3  %9d/4 =%9d           C3  %9d/2=%9d\n",   c[1], cr[1]=c[1]/4,      c[5], cr[5]=c[5]/2);
  if(cr[1]*4!=c[1])puts("c3 division error");if(cr[5]*2!=c[5])puts("C3 division error");

  printf("cs  %9d/6 =%9d           CS  %9d/3=%9d\n",   c[2], cr[2]=c[2]/6,      c[6], cr[6]=c[6]/3);
  if(cr[2]*6!=c[2])puts("cs division error");if(cr[6]*3!=c[6])puts("CS division error");

  printf("c3v %9d/2 =%9d           C3V %9d/1=%9d\n",   c[3], cr[3]=c[3]/2,      c[7], cr[7]=c[7]);
  if(cr[3]*2!=c[3])puts("c3v division error");  

  for(int i=8;i--;)cr[8]+=cr[i]; 
  printf("total =%d unique =%d",c[8],cr[8]);    
}

Resultado

O programa gera uma tabela de saída com 8 entradas, de acordo com as 8 simetrias do sólido. O sólido pode ter qualquer uma das 4 simetrias da seguinte forma (notação Schoenflies)

c1: no symmetry
c3: 3-fold axis of rotation (produces 3-fold axis of rotation in hexagon tiling)
cs: plane of reflection (produces line of reflection in hexagon tiling)
c3v both of the above (produces 3-fold axis of rotation and three lines of reflection through the hexagon corners)

Além disso, quando o sólido possui exatamente metade das células com 1 e metade com 0, existe a possibilidade de inverter todos os 1 e 0, invertendo as coordenadas pelo centro do espaço do cubo. Isso é o que estou chamando de auto-complemento, mas um termo mais matemático seria "antissimétrico em relação a um centro de inversão".

Esta operação de simetria fornece um eixo de rotação 2 vezes no ladrilho hexagonal.

Os padrões que possuem essa simetria são listados em uma coluna separada. Eles ocorrem apenas onde N é par.

Minha contagem parece estar um pouco baixa para N = 4. Em discussão com Peter Taylor, parece que não estou detectando inclinações que têm apenas uma simetria de uma linha através das arestas do hexágono. Provavelmente, isso é porque eu não testei o auto-complemento (anti-simetria) para operações além de (inversão) x (identidade.) Teste de auto-complemento para as operações (inversão) x (reflexão) e (inversão) x (rotação de três vezes ) pode descobrir as simetrias ausentes. Eu esperaria que a primeira linha dos dados para N = 4 se parecesse com esta (16 menos em c1 e 32 mais em C1):

c1   224064/12=18672          C1  534/6=89

Isso alinharia os totais com a resposta de Peter e https://oeis.org/A066931/a066931.txt

saída atual é a seguinte.

N=1
non self-complement     self-complement
c1      0/12= 0           C1  0/6= 0
c3      0/4 = 0           C3  0/2= 0
cs      0/6 = 0           CS  0/3= 0
c3v     2/2 = 1           C3V 0/1= 0
total =2 unique =1

non self-complement     self-complement
N=2
c1      0/12= 0           C1  0/6= 0
c3      0/4 = 0           C3  0/2= 0
cs     12/6 = 2           CS  3/3= 1
c3v     4/2 = 2           C3V 1/1= 1
total =20 unique =6

N=3
non self-complement     self-complement
c1    672/12=56           C1  0/6= 0
c3      4/4 = 1           C3  0/2= 0
cs    288/6 =48           CS  0/3= 0
c3v    16/2 = 8           C3V 0/1= 0
total =980 unique =113

N=4 (errors as discussed)
non self-complement     self-complement
c1   224256/12=18688          C1  342/6=57
c3       64/4 =16             C3  2/2= 1
cs     8064/6 =1344           CS  54/3=18
c3v      64/2 =32             C3V 2/1= 2
total =232848 unique =20158

N=5
non self-complement     self-complement
c1  266774112/12=22231176        C1  0/6= 0
c3       1100/4 =275             C3  0/2= 0
cs     451968/6 =75328           CS  0/3= 0
c3v       352/2 =176             C3V 0/1= 0
total =267227532 unique =22306955

Lista de tarefas (atualizada)

Arrume o código atual.

Feito, mais ou menos

Implemente a verificação de simetria para a camada atual e passe um parâmetro para a simetria da camada anterior (não faz sentido verificar se a última camada era assimétrica).

Concluído, os resultados para N ímpares concordam com os dados publicados

Adicione uma opção para suprimir a contagem de figuras assimétricas (deve correr muito mais rápido)

Isso pode ser feito adicionando outra condição à chamada de recursão: if(s1 && m<n*3-2)f(m + 1,e+d,s1)reduz o tempo de execução para N = 5 de 5 minutos para cerca de um segundo. Como resultado, a primeira linha da saída se torna lixo total (assim como os totais totais), mas se o total já for conhecido da OEIS, o número de inclinações assimétricas pode ser reconstituído, pelo menos para N. ímpar.

Mas, mesmo para N, o número de sólidos assimétricos (de acordo com as simetrias c3v) que são autocomplemento seria perdido. Nesse caso, um programa separado dedicado a sólidos com exatamente (N ** 3) / 2 células com 1 pode ser útil. Com isso disponível (e contando corretamente), pode ser possível tentar N = 6, mas levará muito tempo para ser executado.

Implemente a contagem de células para reduzir a pesquisa em até (N ^ 3) / 2 cubos.

Não feito, a economia deve ser marginal

Implemente a verificação de simetria (sólido complementar) para padrões contendo exatamente (N ^ 3) / 2 cubos.

Feito, mas parece ter omissões, veja N = 4.

Encontre uma maneira de escolher a figura lexicamente mais baixa de uma assimétrica.

Não se espera que a economia seja tão boa. A supressão de números assimétricos elimina a maior parte disso. A única reflexão que é verificada é o plano através do eixo y (x e z são calculados posteriormente multiplicando por 3.) Figuras com apenas simetria rotacional são contadas em ambas as suas formas enantioméricas. Talvez fosse quase duas vezes mais rápido se apenas um fosse contado.

Para facilitar isso, possivelmente melhore a maneira como as coordenadas em cada camada são listadas (elas formam grupos degenerados de 6 ou 3, com possivelmente um grupo de 1 no centro exato da camada).

Interessante, mas provavelmente existem outras perguntas no site a serem exploradas.