// g(n): the most lines (sets) among n points of AG(3,3), a 27-card third of
// the deck, for every n = 0..27, by visiting all 2^27 subsets in Gray-code
// order and updating the line count as each point goes in or out. For each
// n it also prints one subset that attains g(n) (a witness), as cards: four
// digits 0-2, the fourth fixed at 0, so the witness lies in one 27-card third.
//
//   cc -O2 -o third third.c && ./third
#include <stdio.h>
#include <stdint.h>

int main(void) {
  // points are 0..26, digits base 3; the third point of a line through a, b
  int third[27][27];
  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;
    }
  // the 13 lines through each point, as pairs of the other two points
  int through[27][13][2];
  for (int p = 0; p < 27; p++) {
    int k = 0;
    for (int q = 0; q < 27; q++) {
      int r = third[p][q];
      if (q != p && q < r) { through[p][k][0] = q; through[p][k][1] = r; k++; }
    }
    if (k != 13) { fprintf(stderr, "point %d is on %d lines\n", p, k); return 1; }
  }
  int best[28];
  long long ways[28];
  uint32_t witness[28] = {0};
  for (int n = 0; n <= 27; n++) { best[n] = -1; ways[n] = 0; }
  uint32_t set = 0;
  int lines = 0, n = 0;
  best[0] = 0; ways[0] = 1;
  for (uint32_t i = 1; i < (1u << 27); i++) {
    int p = __builtin_ctz(i);  // the Gray code flips point p
    int 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 > best[n]) { best[n] = lines; ways[n] = 1; witness[n] = set; }
    else if (lines == best[n]) ways[n]++;
  }
  printf("n  g(n)  subsets of AG(3,3) attaining it\n");
  for (int k = 0; k <= 27; k++) printf("%2d %4d  %lld\n", k, best[k], ways[k]);
  printf("\nwitnesses (n, lines, cards):\n");
  for (int k = 3; k <= 27; k++) {
    // recount the witness's lines from scratch, as a check on the Gray-code count
    int c = 0;
    for (int a = 0; a < 27; a++)
      for (int b = a + 1; b < 27; b++) {
        int r = third[a][b];
        if (r > b && (witness[k] >> a & 1) && (witness[k] >> b & 1) && (witness[k] >> r & 1)) c++;
      }
    if (c != best[k] || __builtin_popcount(witness[k]) != k) { fprintf(stderr, "witness %d is wrong\n", k); return 1; }
    printf("%2d %4d ", k, c);
    for (int p = 0; p < 27; p++)
      if (witness[k] >> p & 1) printf(" %d%d%d0", p % 3, p / 3 % 3, p / 9);
    printf("\n");
  }
  return 0;
}