Binary codes correcting two deletions, lengths 16 to 18
Find larger binary codes of length 16, 17 and 18 that correct two deletions; the best known have 220, 349 and 567 words.
| 1 | # The checks and how to submit |
| 2 | |
| 3 | The checks run the judge in `checks/judge/` at the project's approved version, with your pushed commit as input, so a |
| 4 | route cannot change how it is judged. The judge is plain Python 3 with no dependencies: run it yourself before you push, |
| 5 | `python3 checks/judge/check.py routes/<branch>`, and rerun its own tests with `python3 -I checks/test_judge.py`. |
| 6 | |
| 7 | ## Files |
| 8 | |
| 9 | - `constructions/n16.json`: the record code of 220 words (EinsteinArena submission #2622). |
| 10 | - `constructions/n17.json`, `constructions/n18.json`: codes of 316 and 525 words from a lexicographic greedy computed |
| 11 | for this project (every word in increasing order, kept when it shares no descendant with a word kept before). They |
| 12 | are starting points, not records. |
| 13 | - `tools/check_format.py`: checks that files follow the submission format; it does not check the descendants. |
| 14 | |
| 15 | ## Submission format |
| 16 | |
| 17 | - **Files.** A candidate is a file whose name ends in `.json`, anywhere in your route's folder `routes/<branch>/`, whose |
| 18 | content is a JSON object with the keys `"n"` and `"words"`; other keys are ignored. A `.json` file whose content is |
| 19 | not an object with `"words"` is not a candidate and is ignored, but a `.json` file that is not valid JSON fails the |
| 20 | check. Keep each file under 1 MB. |
| 21 | - **`"n"`**: a JSON integer, 16, 17 or 18. |
| 22 | - **`"words"`**: a nonempty list of distinct strings, each of exactly `n` characters `0` and `1`, as EinsteinArena's |
| 23 | `"words"`. |
| 24 | - **Value.** The number of words, when no two words share a descendant. A candidate in which two words share one is |
| 25 | not a code: `verify` fails and names the two words and their common descendant. |
| 26 | - **Score.** For each length, the route's largest code divided by the record, where a length counts as its starting |
| 27 | code (220, 316 or 525 words) when the route has nothing larger. The score is the mean of the three ratios, higher is |
| 28 | better: `main` starts at $26680/28269\approx 0.9438$, and holding all three records scores 1. `verify` writes it to |
| 29 | `metrics.json` as `score` (a float) and `score_exact` (the exact fraction), with each length's largest code in |
| 30 | `subtasks` and the lengths above their records in `new_records`. |
| 31 | |
| 32 | ## How to check and submit |
| 33 | |
| 34 | - Check a folder before you push: `python3 tools/check_format.py routes/<branch>`. |
| 35 | - Push your work to your route. Two checks run on every push: |
| 36 | - **`verify`** checks every candidate in your route's folder exactly. It prints one line per candidate, |
| 37 | `<length>: <size> words (<file>), <difference> against the record`, ending `; a new record` when the code is larger |
| 38 | than the record, then the score and the new records. It fails if a `.json` file is unreadable or a candidate is |
| 39 | malformed or not a code; a route with no candidate passes with "no candidates to check". On `main` it also reads |
| 40 | `constructions/`. |
| 41 | - **`improves`** only informs: it never blocks a merge. For each length your route has a code for, it prints your |
| 42 | largest code against the largest `main` holds (in `constructions/` and `routes/`) and says whether it is a new |
| 43 | record. It passes when, for some length, your code has more words than `main`'s. |
| 44 | - Open a pull request into `main` when `improves` passes: the site's maintainer takes improvements in. Any other |
| 45 | result, such as a method that others can reuse or a negative result, is judged by review: say in your route's notes |
| 46 | exactly what you claim and how to check it. |
