Lo prometo, este será mi último desafío sobre las diamantaciones (por un tiempo, de todos modos). En el lado positivo, este desafío no tiene nada que ver con el arte ASCII, y tampoco es un código de golf, por lo que esto es realmente completamente diferente.

Así que solo como recordatorio, cada hexágono se puede titular con tres diamantes diferentes:

Una pregunta interesante es cuántas de estas inclinaciones existen para un tamaño de hexágono dado. Parece que estos números se han estudiado bastante a fondo y se pueden encontrar en OEIS A008793 .

Sin embargo, el problema se vuelve más complicado si preguntamos cuántas inclinaciones existen hasta la rotación y la reflexión . Por ejemplo, para la longitud del lado N = 2, existen las siguientes 20 inclinaciones:

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

Pero muchos de estos son idénticos bajo rotación y reflexión. Si tomamos en cuenta estas simetrías, solo quedan 6 inclinaciones distintas:

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

   2        2        6        6        1        3

donde los números indican la multiplicidad de cada mosaico. Tenga en cuenta que para hexágonos más grandes también hay inclinaciones con multiplicidades 4 y 12.

Parece que el número de inclinaciones hasta la simetría se ha estudiado menos a fondo. La entrada OEIS A066931 solo enumera los cinco términos:

1, 1, 6, 113, 20174

donde el primer término es para la longitud del lado N = 0y el último término para la longitud del lado N = 4.

¡Estoy seguro de que podemos hacerlo mejor que eso!

Su tarea es calcular el número de inclinaciones para una longitud lateral dada.

Este es el código más rápido . Su puntaje será la longitud lateral más alta Npara la cual su código produce el resultado correcto en 30 minutos en mi máquina. En caso de empate, voy a aceptar la presentación que produce el resultado de que N más rápido.

Como de costumbre, no debe codificar los resultados que ya sabe para ganar el desempate. El algoritmo que resuelve N = 3debe ser idéntico al que resuelve N = 5.

Su envío no debe usar más de 4 GB de memoria. Le daré un margen de maniobra a esto si está operando cerca de ese límite, pero si está constantemente por encima de ese límite, o si aumenta significativamente más allá, no lo tendré en cuenta Npara su presentación.

Probaré todos los envíos en mi máquina con Windows 8, así que asegúrese de que su idioma de elección esté disponible gratuitamente en Windows. La única excepción a esto es Mathematica (porque tengo una licencia para ello). Incluya instrucciones sobre cómo compilar / ejecutar su código.

Por supuesto, siéntase libre de calcular más términos en su propio tiempo (para la ciencia y para que otros verifiquen sus números), pero el puntaje de su respuesta se determinará en esos 30 minutos.

Álgebra, teoría de grafos, inversión de Möbius, investigación y Java

El grupo de simetría del hexágono es el grupo diédrico de orden 12, y se genera mediante una rotación de 60 grados y un giro de espejo a través de un diámetro. Tiene 16 subgrupos, pero algunos de ellos están en grupos conjugados no triviales (los que solo tienen reflejos tienen 3 opciones de eje), por lo que hay 10 simetrías fundamentalmente diferentes que puede tener un mosaico del hexágono:

El número de inclinaciones de diamante de un subconjunto de una red triangular se puede calcular como determinante , por lo que mi enfoque inicial fue establecer un determinante para cada una de las simetrías del hexágono, para calcular el número de inclinaciones que tienen al menos esas simetrías ; y luego use la inversión de Möbius en el álgebra de incidencia de su poset (básicamente una generalización del principio de inclusión-exclusión) para calcular el número de inclinaciones cuyo grupo de simetría es exactamente cada uno de los 10 casos. Sin embargo, algunas de las simetrías tienen condiciones de borde desagradables, por lo que me vi obligado a sumar exponencialmente muchos determinantes. Afortunadamente, los valores obtenidos paran < 10me dio suficientes datos para poder identificar secuencias relevantes en OEIS y armar una forma cerrada (por algún valor de "cerrado" que permite productos finitos). Hay un poco de discusión sobre las secuencias, y referencias a las pruebas, en el escrito formal que preparé para justificar las actualizaciones de la secuencia OEIS.

Una vez que se realiza el conteo doble, resulta que cuatro de los diez valores se cancelan de manera ordenada, por lo que solo tenemos que calcular los seis restantes y luego hacer una suma ponderada.

Este código tarda menos de 30 segundos N=1000en mi 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

Introducción

Como comentó David Carraher, la forma más simple de analizar el mosaico hexagonal parecía ser aprovechar su isomorfismo con el Diagrama joven tridimensional, esencialmente un cuadrado x, y lleno de barras de altura enteras cuyas alturas z deben permanecer iguales o aumentar a medida que se acerca el eje z.

Comencé con un algoritmo para encontrar los totales que es más susceptible de adaptación para el conteo de simetría que el algoritmo publicado, que se basa en un sesgo en uno de los tres ejes cartesianos.

Algoritmo

Comienzo rellenando las celdas de los planos x, y y z con 1, mientras que el resto del área contiene ceros. Una vez hecho esto, construyo el patrón capa por capa, con cada capa que contiene las celdas que tienen una distancia manhattan 3D común desde el origen. Una celda solo puede contener un 1 si las tres celdas debajo también contienen un 1. si alguna de ellas contiene un 0, entonces la celda debe ser un 0.

La ventaja de construir el patrón de esta manera es que cada capa es simétrica respecto a la línea x = y = z. Esto significa que cada capa se puede verificar independientemente para la simetría.

Comprobación de simetría

Las simetrías del sólido son las siguientes: rotación 3 veces alrededor de la línea x = y = z -> rotación 3 veces alrededor del centro del hexágono; y 3 x reflexiones sobre los 3 planos que contienen la línea x = y = z y cada uno de los ejes x, y, z -> reflexión sobre las líneas a través de las esquinas del hexágono.

Esto suma solo 6 simetrías. Para obtener la simetría completa del hexágono, se debe considerar otro tipo de simetría. Cada sólido (construido a partir de 1) tiene un sólido complementario (construido a partir de 0). Donde N es impar, el sólido complementario debe ser diferente del sólido original (porque no es posible que tengan el mismo número de cubos). Sin embargo, cuando el sólido complementario se da vuelta, se encontrará que su representación 2D como un mosaico de diamantes es idéntica (a excepción de una operación de simetría de 2 veces) al sólido original. Donde N es par, es posible que el sólido sea autoinverso.

Esto se puede ver en los ejemplos para N = 2 en la pregunta. Si se ve desde la izquierda, el primer hexágono se ve como un cubo sólido con 8 cubos pequeños, mientras que el último hexágono se ve como una cáscara vacía con 0 cubos pequeños. Si se ve desde la derecha, lo contrario es cierto. Los hexágonos 3º, 4º y 5º y los hexágonos 16º, 17º y 18º parecen contener 2 o 6 cubos y, por lo tanto, se complementan entre sí en 3 dimensiones. Se relacionan entre sí en 2 dimensiones mediante una operación de simetría de 2 veces (rotación de 2 veces o reflexión sobre un eje a través de los bordes del hexágono). Por otro lado, los 9º, 10º, 11º y 12º hexágonos muestran patrones 3D que son sus propios complementos y, por lo tanto, tienen una simetría más alta (por lo tanto, estos son los únicos patrones con multiplicidad extraña).

Tenga en cuenta que tener (N ^ 3) / 2 cubos es una condición necesaria para autocompletarse, pero en general no es una condición suficiente si N> 2. El resultado de todo esto es que para N impar, las inclinaciones siempre ocurren en pares (N ^ 3) / 2 cubos deben ser cuidadosamente inspeccionados.

Código actual (genera el total correcto para N = 1,2,3,5. Error como se discutió 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]);    
}

Salida

El programa genera una tabla de salida de 8 entradas, de acuerdo con las 8 simetrías del sólido. El sólido puede tener cualquiera de las 4 simetrías siguientes (notación de 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)

Además, cuando el sólido tiene exactamente la mitad de las celdas con 1 y la otra mitad con 0, existe la posibilidad de voltear todos los 1 y 0, y luego invertir las coordenadas a través del centro del espacio del cubo. Esto es lo que yo llamo autocomplemento, pero un término más matemático sería "antisimétrico con respecto a un centro de inversión".

Esta operación de simetría proporciona un eje de rotación de 2 veces en el mosaico hexagonal.

Los patrones que tienen esta simetría se enumeran en una columna separada. Solo ocurren donde N es par.

Mi recuento parece estar ligeramente apagado para N = 4. En discusión con Peter Taylor, parece que no estoy detectando inclinaciones que solo tienen una simetría de una línea a través de los bordes del hexágono. Esto se debe presumiblemente a que no he realizado pruebas de autocomplemento (antisimetría) para operaciones que no sean (inversión) x (identidad). Prueba de autocomplemento para las operaciones (inversión) x (reflexión) y (inversión) x (rotación de 3 veces ) puede descubrir las simetrías faltantes. Entonces esperaría que la primera línea de datos para N = 4 se vea así (16 menos en c1 y 32 más en C1):

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

Esto pondría los totales en línea con la respuesta de Peter y https://oeis.org/A066931/a066931.txt

La salida actual es la siguiente.

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 tareas (actualizada)

Poner en orden el código actual.

Listo, más o menos

Implemente la comprobación de simetría para la capa actual y pase un parámetro para la simetría de la capa anterior (no tiene sentido comprobar si la última capa era asimétrica).

Hecho, los resultados para N impar coinciden con los datos publicados

Agregue una opción para suprimir el conteo de figuras asimétricas (debería ejecutarse mucho más rápido)

Esto se puede hacer agregando otra condición a la llamada de recursión: if(s1 && m<n*3-2)f(m + 1,e+d,s1)reduce el tiempo de ejecución para N = 5 de 5 minutos a aproximadamente un segundo. Como resultado, la primera línea de salida se convierte en basura total (al igual que los totales generales), pero si el OEIS ya conoce el total, el número de inclinaciones asimétricas se puede reconstituir, al menos para N.

Pero incluso para N, se perdería el número de sólidos asimétricos (según las simetrías c3v) que se autocomplementan. Para este caso, un programa separado dedicado a sólidos con exactamente (N ** 3) / 2 celdas con un 1 puede ser útil. Con esto disponible (y contando correctamente) puede ser posible probar N = 6, pero tomará mucho tiempo ejecutarlo.

Implemente el recuento de celdas para reducir la búsqueda a hasta (N ^ 3) / 2 cubos.

No hecho, se espera que los ahorros sean marginales

Implemente la comprobación de simetría (sólido complementario) para patrones que contengan exactamente (N ^ 3) / 2 cubos.

Hecho, pero parece tener omisiones, ver N = 4.

Encuentre una manera de elegir la figura léxicamente más baja de una figura asimétrica.

No se espera que los ahorros sean tan buenos. Suprimir figuras asimétricas elimina la mayor parte de esto. El único reflejo que se verifica es el plano a través del eje y (x y z se calculan luego multiplicando por 3.) Las figuras con simetría rotacional solo se cuentan en sus dos formas enantioméricas. Quizás correría casi el doble de rápido si solo se contara uno.

Para facilitar esto, posiblemente mejore la forma en que se enumeran las coordenadas en cada capa (forman grupos degenerados de 6 o 3, posiblemente con un grupo de 1 en el centro exacto de la capa).

Interesante pero probablemente hay otras preguntas en el sitio para explorar.