Обещаю, это будет моим последним испытанием о плитах алмаза (какое-то время, во всяком случае). С другой стороны, этот вызов не имеет ничего общего с искусством ASCII, и он также не является гольф-кодом, так что это на самом деле совершенно другое.

Напоминаем, что каждый шестиугольник может быть назван тремя разными бриллиантами:

Интересный вопрос, который нужно задать, состоит в том, сколько таких плиток существует для данного размера шестиугольника. Кажется, что эти цифры были изучены довольно тщательно и могут быть найдены в OEIS A008793 .

Однако проблема усложняется, если мы спросим, ​​сколько существует наклонов до поворота и отражения . Например, для длины стороны N = 2 существуют следующие 20 углов:

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

Но многие из них идентичны при вращении и отражении. Если мы примем во внимание эти симметрии, останется только 6 различных элементов мозаичного изображения:

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

   2        2        6        6        1        3

где числа указывают на кратность каждой плитки. Обратите внимание, что для больших шестиугольников также есть мозаики с кратностями 4 и 12.

Похоже, что число наклона до симметрии изучено менее тщательно. Запись OEIS A066931 содержит только пять терминов:

1, 1, 6, 113, 20174

где первый член для длины стороны N = 0и последний член для длины стороны N = 4.

Я уверен, что мы можем сделать лучше, чем это!

Ваша задача - вычислить количество плиток для заданной длины стороны.

Это самый быстрый код . Ваша оценка будет наибольшей длиной сторон, Nдля которой ваш код дает правильный результат в течение 30 минут на моей машине. В случае ничьей я приму представление, которое даст результат для этого N самого быстрого.

Как обычно, вы не должны жестко кодировать результаты, которые вы уже знаете, чтобы выиграть тай-брейк. Решающий алгоритм N = 3должен быть идентичен решающему N = 5.

Ваша заявка не должна использовать более 4 ГБ памяти. Я дам некоторую свободу в этом, если вы работаете близко к этому пределу, но если вы постоянно превышаете этот предел, или если вы значительно превысили его, я не буду считать это Nдля вашего представления.

Я протестирую все заявки на моем компьютере с Windows 8, поэтому убедитесь, что ваш язык свободно доступен в Windows. Единственное исключение - Mathematica (потому что у меня есть лицензия на него). Пожалуйста, включите инструкции о том, как скомпилировать / запустить ваш код.

Конечно, не стесняйтесь вычислять больше терминов в свое время (для науки и для других, чтобы сравнить их числа), но оценка вашего ответа будет определена через эти 30 минут.

Алгебра, теория графов, инверсия Мёбиуса, исследования и Java

Группа симметрии шестиугольника является диэдральной группой порядка 12 и создается поворотом на 60 градусов и зеркальным отражением поперек диаметра. У него 16 подгрупп, но некоторые из них находятся в нетривиальных группах сопряженности (те, которые имеют только отражения, имеют 3 варианта выбора оси), поэтому существует 10 принципиально различных симметрий, которые может иметь мозаика шестиугольника:

Количество алмазных мозаичных элементов в подмножестве треугольной решетки можно рассчитать как определитель , поэтому мой первоначальный подход заключался в том, чтобы установить один определитель для каждой из симметрий шестиугольника, чтобы рассчитать количество мозаичных элементов, которые имеют хотя бы эти симметрии. ; а затем с помощью инверсии Мёбиуса в алгебре инцидентности их множества (в основном, это обобщение принципа включения-исключения), чтобы вычислить число тайлингов, группа симметрии которых точно равна каждому из 10 случаев. Однако некоторые симметрии имеют неприятные граничные условия, поэтому я был вынужден суммировать по экспоненциальному множеству определителей. К счастью, значения, полученные дляn < 10дал мне достаточно данных, чтобы иметь возможность идентифицировать соответствующие последовательности в OEIS и собрать воедино закрытую форму (для некоторого значения «закрытая», которая допускает конечные продукты). В формальной рецензии есть небольшая дискуссия о последовательностях и ссылки на доказательства, которые я подготовил, чтобы оправдать обновления последовательностей OEIS.

Как только двойной счет учтен, получается, что четыре из десяти значений аккуратно удаляются, поэтому нам нужно только вычислить оставшиеся шесть и затем сделать взвешенную сумму.

Этот код занимает менее 30 секунд N=1000на моей машине.

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

С

Введение

Как прокомментировал Дэвид Каррахер, простейший способ анализа мозаики шестиугольника, по-видимому, заключается в том, чтобы воспользоваться его изоморфизмом с трехмерной диаграммой Юнга, по существу, квадратом x, y, заполненным целочисленными столбцами высоты, высота которых z должна оставаться неизменной или увеличиваться по мере приближения к оси Z.

Я начал с алгоритма нахождения итогов, который более приспособлен к адаптации для подсчета симметрии, чем опубликованный алгоритм, который основан на смещении к одной из трех декартовых осей.

Алгоритм

Я начинаю с заполнения ячеек плоскостей x, y и z единицами, а остальная часть области содержит нули. Как только это будет сделано, я создаю шаблон слой за слоем, где каждый слой содержит ячейки, которые имеют общее трехмерное манхэттенское расстояние от начала координат. Ячейка может содержать только 1, если три ячейки под ней также содержат 1. Если любая из них содержит 0, то ячейка должна быть 0.

Преимущество построения шаблона таким образом состоит в том, что каждый слой является симметричным относительно линии x = y = z. Это означает, что каждый слой можно проверить независимо на симметрию.

Проверка симметрии

Симметрии тела следующие: 3-кратное вращение вокруг линии x = y = z -> 3-кратное вращение вокруг центра шестиугольника; и 3 отражения по 3 плоскостям, содержащим линию x = y = z и каждую из осей x, y, z -> отражение по линиям через углы шестиугольника.

Это добавляет только 6-кратную симметрию. Чтобы получить полную симметрию шестиугольника, необходимо рассмотреть другой вид симметрии. Каждое тело (построено из 1) имеет дополнительное тело (построено из 0). Там, где N нечетно, дополнительное тело должно отличаться от исходного тела (потому что они не могут иметь одинаковое количество кубов). Тем не менее, когда дополнительное тело поворачивается, обнаруживается, что его двумерное представление в виде ромбовидной мозаики идентично (за исключением операции симметрии в 2 раза) исходному телу. Если N четное, тело может быть самообращенным.

Это можно увидеть в примерах для N = 2 в вопросе. Если смотреть слева, первый шестиугольник выглядит как сплошной куб с 8 маленькими кубиками, а последний шестиугольник выглядит как пустая оболочка с 0 маленькими кубиками. Если смотреть справа, обратное верно. 3-й, 4-й и 5-й шестиугольники и 16-й, 17-й и 18-й шестиугольники выглядят так, как будто они содержат либо 2, либо 6 кубов, и, таким образом, они дополняют друг друга в 3 измерениях. Они связаны друг с другом в двух измерениях с помощью операции симметрии в 2 раза (2-кратное вращение или отражение вокруг оси через края шестиугольника.) С другой стороны, 9-й, 10-й, 11-й и 12-й шестиугольники показывают трехмерные структуры, которые являются их собственными дополнениями и, следовательно, имеют более высокую симметрию (следовательно, это единственные модели с нечетной кратностью).

Обратите внимание, что наличие (N ^ 3) / 2 кубов является необходимым условием для самодополнения, но в целом оно не является достаточным условием, если N> 2. Результатом всего этого является то, что для нечетных N мозаики всегда происходят в парах (N ^ 3) / 2 куба должны быть тщательно проверены.

Текущий код (генерирует правильную сумму для N = 1,2,3,5. Ошибка, как обсуждалось для 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]);    
}

Выход

Программа генерирует выходную таблицу из 8 записей в соответствии с 8 симметриями тела. Твердое тело может иметь любую из 4 симметрий следующим образом (обозначение 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)

Кроме того, когда тело имеет ровно половину ячеек с 1 и половину с 0, существует возможность перевернуть все 1 и 0, а затем инвертировать координаты через центр пространства куба. Это то, что я называю самодополнением, но более математический термин будет «антисимметричным по отношению к центру инверсии».

Эта операция симметрии дает 2-кратную ось вращения в шестиугольной плитке.

Шаблоны с такой симметрией перечислены в отдельном столбце. Они встречаются только там, где N четно.

Мой счет, кажется, немного для N = 4. В разговоре с Питером Тейлором выясняется, что я не обнаруживаю наклоны, которые имеют симметрию только линии, проходящей через ребра шестиугольника. Вероятно, это связано с тем, что я не проверял самодополнение (антисимметрию) для операций, отличных от (инверсия) x (тождество.) ) может раскрыть недостающие симметрии. Тогда я бы ожидал, что первая строка данных для N = 4 будет выглядеть следующим образом (на 16 меньше в c1 и еще 32 в C1):

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

Это приведет итоги в соответствие с ответом Питера и https://oeis.org/A066931/a066931.txt.

Токовый выход выглядит следующим образом.

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

Список дел (обновлено)

Уберите текущий код.

Готово, более или менее

Реализуйте проверку симметрии для текущего слоя и передайте параметр для симметрии предыдущего слоя (нет смысла проверять, был ли последний слой асимметричным).

Готово, результаты для нечетного N согласуются с опубликованными данными

Добавить опцию, чтобы подавить подсчет асимметричных фигур (должен работать намного быстрее)

Это можно сделать, добавив к рекурсивному вызову еще одно условие: if(s1 && m<n*3-2)f(m + 1,e+d,s1)оно сокращает время выполнения для N = 5 с 5 минут до примерно секунды. В результате первая строка выходных данных становится общим мусором (как и общие итоги), но если итог уже известен из OEIS, число асимметричных значений может быть восстановлено, по крайней мере, для нечетного N.

Но даже для N число асимметричных (в соответствии с c3v-симметриями) тел, которые являются самодополняемыми, будет потеряно. Для этого случая может быть полезна отдельная программа, посвященная твердым телам с точно (N ** 3) / 2 ячейками с 1. Имея это в наличии (и считая правильно), можно попробовать N = 6, но для запуска потребуется много времени.

Реализовать подсчет ячеек, чтобы сократить количество запросов до (N ^ 3) / 2 кубов.

Не сделано, сбережения, как ожидается, будут незначительными

Реализуйте проверку симметрии (дополняющее тело) для шаблонов, содержащих ровно (N ^ 3) / 2 куба.

Готово, но, похоже, есть пропуски, см. N = 4.

Найдите способ выбрать лексически низкую фигуру из асимметричной.

Ожидается, что сбережения не будут такими большими. Подавление асимметричных фигур устраняет большинство из этого. Единственное отражение, которое проверяется, - это плоскость, проходящая через ось y (x и z вычисляются позже путем умножения на 3.) Фигуры только с симметрией вращения учитываются в обеих их энантиомерных формах. Возможно, он будет работать почти вдвое быстрее, если считать только один.

Чтобы облегчить это, возможно, улучшите способ перечисления координат в каждом слое (они образуют вырожденные группы из 6 или 3, возможно, с группой 1 в точном центре слоя).

Интересно, но, вероятно, есть другие вопросы на сайте для изучения.