# code/: the most sets among n cards

A card is a point of AG(4,3): four digits 0–2. Three cards are a set (a line)
when each digit position sums to a multiple of 3. Everything here is C99 or
Python 3 with numpy; nothing else to install.

- `third.c`: g(n), the most lines among n points of AG(3,3) (one 27-card third
  of the deck), exactly, for n = 0..27. It walks all 2^27 subsets in Gray-code
  order, about 3 seconds. Also prints one witness subset per n, recounted from
  scratch.

  ```
  cc -O2 -o third third.c && ./third > out/third.txt
  ```

- `bound.py`: the counting bound over the parallel classes of hyperplanes (the
  40 ways to cut the deck into three parallel thirds). Exact integers, a few
  seconds. For each n it prints the best layout found and the most lines the
  argument allows. `selftest` runs it one dimension down (AG(3,3) from the 3×3
  grid's maxima) to compare with `third.c`; `dims` runs it in 5 features and
  up, for n ≤ 27, by induction.

  ```
  python3 bound.py > out/bound.txt
  python3 bound.py selftest > out/bound-selftest.txt
  python3 bound.py dims > out/bound-dims.txt
  ```

- `witness.py`: explicit layouts for n = 3..60, each counted directly over all
  81 cards. Reads `out/third.txt`.

  ```
  python3 witness.py > out/witnesses.txt
  ```

- `anneal.c`: simulated annealing over the whole deck, a search for good
  layouts (lower bounds only). We ran it on 48–60 cards; the best layouts,
  recounted, are in `out/anneal.txt`.

  ```
  cc -O2 -o anneal anneal.c && ./anneal <n> <seconds> <seed>
  ```

- `alld.py`: the induction to five or more features, for 28 to 81 points,
  with one certificate per n valid for every deck size (`out/alld.txt`).

  ```
  python3 alld.py > out/alld.txt
  ```

- `certify.py` and `check.py`: an exact Farkas certificate for every case
  (one line T ≤ u + v·P above every allowed split), and a 45-line checker
  that imports nothing else from here, re-derives the allowed splits and
  verifies every certificate for every set count above the claimed maximum.

  ```
  python3 certify.py > out/certificates.json && python3 check.py
  ```

- `classify.py`: the argument at the maximum, with the splits that would show
  the expected shape forbidden. Every best layout of up to 27 cards lies in
  one third; for 28–40 and 45–47 cards every best layout contains a whole third.

  ```
  python3 classify.py > out/classify.txt
  ```

- `classes3.c`, `classes4.py`, `canon4.c`: how many different best layouts
  there are. Up to 27 cards: union-find over generators of AGL(3,3).
  28–47: candidates built from best subsets of the parallel thirds, counted by
  an exact canonical key from nauty.

- `orbits.c`: one layout per class of n-card layouts under the deck's
  symmetries, by McKay's canonical augmentation with nauty. With a max-sets
  argument it keeps only layouts with at most that many sets (0 gives the
  caps). Outputs: `out/orbits.txt` (every class through 14 cards, matching
  OEIS A182240), `out/caps.txt`, `out/few2.txt` (no 21 cards hold fewer than
  3 sets, and a 21-card layout with exactly 3), `out/few5.txt` (with a cheap
  invariant pruning children before nauty: the fewest sets among 22, 23 and
  24 cards are 4, 5 and 6).

nauty isn't in the repo. Build it in a temp folder:

```
curl -LO https://pallini.di.uniroma1.it/nauty2_8_8.tar.gz
tar xzf nauty2_8_8.tar.gz && cd nauty2_8_8 && ./configure && make nauty.a
NAUTY=$PWD   # then, back in code/:
cc -O2 -I$NAUTY -o orbits orbits.c $NAUTY/nauty.a
cc -O2 -I$NAUTY -o canon4 canon4.c $NAUTY/nauty.a
cc -O2 -o classes3 classes3.c && ./classes3 > out/classes3.txt
python3 classes4.py ./classes3 ./canon4 > out/classes4.txt
./orbits - L1.txt 0 1                      # then level by level:
./orbits L1.txt L2.txt 0 1                 # ... (split a level into parts:
./orbits L13.txt L14.part3 3 10            #  part 3 of 10)
./orbits L19.txt L20.txt 0 1 2             # at most 2 sets
```

`attack/` holds the 48–60 work (exact maxima for single cuts, cap extensions);
see its README. `out/` holds the outputs.