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.
README.md
The checks and how to submit
The checks run the judge in checks/judge/ at the project's approved version, with your pushed commit as input, so a
route cannot change how it is judged. The judge is plain Python 3 with no dependencies: run it yourself before you push,
python3 checks/judge/check.py routes/<branch>, and rerun its own tests with python3 -I checks/test_judge.py.
Files
constructions/n16.json: the record code of 220 words (EinsteinArena submission #2622).constructions/n17.json,constructions/n18.json: codes of 316 and 525 words from a lexicographic greedy computed for this project (every word in increasing order, kept when it shares no descendant with a word kept before). They are starting points, not records.tools/check_format.py: checks that files follow the submission format; it does not check the descendants.
Submission format
- Files. A candidate is a file whose name ends in
.json, anywhere in your route's folderroutes/<branch>/, whose content is a JSON object with the keys"n"and"words"; other keys are ignored. A.jsonfile whose content is not an object with"words"is not a candidate and is ignored, but a.jsonfile that is not valid JSON fails the check. Keep each file under 1 MB. "n": a JSON integer, 16, 17 or 18."words": a nonempty list of distinct strings, each of exactlyncharacters0and1, as EinsteinArena's"words".- Value. The number of words, when no two words share a descendant. A candidate in which two words share one is
not a code:
verifyfails and names the two words and their common descendant. - Score. For each length, the route's largest code divided by the record, where a length counts as its starting
code (220, 316 or 525 words) when the route has nothing larger. The score is the mean of the three ratios, higher is
better:
mainstarts at , and holding all three records scores 1.verifywrites it tometrics.jsonasscore(a float) andscore_exact(the exact fraction), with each length's largest code insubtasksand the lengths above their records innew_records.
How to check and submit
- Check a folder before you push:
python3 tools/check_format.py routes/<branch>. - Push your work to your route. Two checks run on every push:
verifychecks every candidate in your route's folder exactly. It prints one line per candidate,<length>: <size> words (<file>), <difference> against the record, ending; a new recordwhen the code is larger than the record, then the score and the new records. It fails if a.jsonfile is unreadable or a candidate is malformed or not a code; a route with no candidate passes with "no candidates to check". Onmainit also readsconstructions/.improvesonly informs: it never blocks a merge. For each length your route has a code for, it prints your largest code against the largestmainholds (inconstructions/androutes/) and says whether it is a new record. It passes when, for some length, your code has more words thanmain's.
- Open a pull request into
mainwhenimprovespasses: the site's maintainer takes improvements in. Any other result, such as a method that others can reuse or a negative result, is judged by review: say in your route's notes exactly what you claim and how to check it.
