// How many best layouts there are for each n <= 27, up to symmetry. Every best
// layout lies in a 27-card third (classify.py), and two layouts in a third are
// equivalent in the deck exactly when an affine map of the third (AGL(3,3),
// 303,264 maps) takes one to the other. So: list every subset of AG(3,3) with
// g(n) lines (as third.c does), and join each to its images under generators
// of AGL(3,3) with union-find. The classes are what's left.
//
//   cc -O2 -o classes3 classes3.c && ./classes3 > out/classes3.txt
//   ./classes3 dump k     # every best k-subset, then one per class (as 27-bit numbers)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

static const int G[28] = {0, 0, 0, 1, 1, 2, 3, 5, 8, 12, 12, 13, 14, 16, 19, 23, 26, 30, 36, 41,
                          47, 54, 62, 71, 81, 92, 104, 117};
static uint32_t* best[28];
static int nbest[28], cap[28];
static int par[300000];
static int find(int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; }
static int cmp(const void* a, const void* b) { uint32_t x = *(uint32_t*)a, y = *(uint32_t*)b; return x < y ? -1 : x > y; }

int main(int argc, char** argv) {
  int dump = argc > 2 ? atoi(argv[2]) : -1;
  int third[27][27], through[27][13][2];
  for (int a = 0; a < 27; a++)
    for (int b = 0; b < 27; b++) {
      int c = 0, pa = a, pb = b, w = 1;
      for (int i = 0; i < 3; i++, pa /= 3, pb /= 3, w *= 3) c += ((6 - pa % 3 - pb % 3) % 3) * w;
      third[a][b] = c;
    }
  for (int p = 0; p < 27; p++) {
    int k = 0;
    for (int q = 0; q < 27; q++) if (q != p && q < third[p][q]) { through[p][k][0] = q; through[p][k][1] = third[p][q]; k++; }
  }
  for (int n = 0; n <= 27; n++) { cap[n] = 1024; best[n] = malloc(cap[n] * sizeof(uint32_t)); }
  uint32_t set = 0;
  int lines = 0, n = 0;
  for (uint32_t i = 1; i < (1u << 27); i++) {
    int p = __builtin_ctz(i), d = 0;
    for (int k = 0; k < 13; k++) if ((set >> through[p][k][0] & 1) && (set >> through[p][k][1] & 1)) d++;
    if (set >> p & 1) { set &= ~(1u << p); lines -= d; n--; } else { set |= 1u << p; lines += d; n++; }
    if (lines == G[n] && n >= 3) {
      if (nbest[n] == cap[n]) best[n] = realloc(best[n], (cap[n] *= 2) * sizeof(uint32_t));
      best[n][nbest[n]++] = set;
    }
  }
  // generators of AGL(3,3) as permutations of the 27 points: a translation,
  // and matrices that generate GL(3,3): a transvection, a 3-cycle of
  // coordinates, a swap of two coordinates, and doubling one coordinate
  int gen[5][27];
  for (int p = 0; p < 27; p++) {
    int x[3] = {p % 3, p / 3 % 3, p / 9}, y[3];
    #define PT(v) ((v)[0] + 3 * (v)[1] + 9 * (v)[2])
    y[0] = (x[0] + 1) % 3; y[1] = x[1]; y[2] = x[2]; gen[0][p] = PT(y);
    y[0] = (x[0] + x[1]) % 3; y[1] = x[1]; y[2] = x[2]; gen[1][p] = PT(y);
    y[0] = x[2]; y[1] = x[0]; y[2] = x[1]; gen[2][p] = PT(y);
    y[0] = x[1]; y[1] = x[0]; y[2] = x[2]; gen[3][p] = PT(y);
    y[0] = 2 * x[0] % 3; y[1] = x[1]; y[2] = x[2]; gen[4][p] = PT(y);
  }
  if (dump < 0) printf("n  g(n)  best subsets of a third  classes  (subsets per class)\n");
  for (int k = 3; k <= 27; k++) {
    qsort(best[k], nbest[k], sizeof(uint32_t), cmp);
    for (int i = 0; i < nbest[k]; i++) par[i] = i;
    for (int i = 0; i < nbest[k]; i++)
      for (int t = 0; t < 5; t++) {
        uint32_t img = 0, s = best[k][i];
        for (int p = 0; p < 27; p++) if (s >> p & 1) img |= 1u << gen[t][p];
        uint32_t* hit = bsearch(&img, best[k], nbest[k], sizeof(uint32_t), cmp);
        if (!hit) { fprintf(stderr, "image of a best set isn't best: n=%d\n", k); return 1; }
        int a = find(i), b = find(hit - best[k]);
        if (a != b) par[a] = b;
      }
    int classes = 0;
    if (k == dump) {
      for (int i = 0; i < nbest[k]; i++) printf("all %u\n", best[k][i]);
      for (int i = 0; i < nbest[k]; i++) if (find(i) == i) printf("rep %u\n", best[k][i]);
    }
    if (dump >= 0) continue;
    printf("%2d %4d %7d", k, G[k], nbest[k]);
    for (int i = 0; i < nbest[k]; i++) classes += find(i) == i;
    printf(" %3d  (", classes);
    int first = 1;
    for (int i = 0; i < nbest[k]; i++) if (find(i) == i) {
      int sz = 0;
      for (int j = 0; j < nbest[k]; j++) sz += find(j) == i;
      printf("%s%d", first ? "" : " ", sz); first = 0;
    }
    printf(")\n");
  }
  return 0;
}