#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""Search for small codes with some minimal Hamming distance.

For example, can I make a (6, 4) code with minimal Hamming distance 3?
That’s just a set of 16 6-bit codewords whose pairwise XORs always
have at least 3 bits set.

So this attempts to find such a code by using backtracking.  Obviously
that isn’t going to be feasible for a lot of bits, but maybe it can
work for small codes.

(In particular it finds no (6, 4) code with minimal Hamming distance
3, so no (6, 4) code can detect all 2-bit errors, unless this code is
buggy.)

"""
from __future__ import print_function
import sys

def find(codebits=6, databits=4, distance=3):
    codemax = 2**codebits
    datamax = 2**databits
    weight = {i: sum(1 if i & (1 << j) else 0 for j in range(codebits))
              for i in range(codemax)}

    # It is fine to try adding candidates to the code in increasing
    # order, since the minimal Hamming distance of the code doesn’t
    # depend on the decoded data, just the set of codewords.

    code = []
    possibilities = [range(codemax)]
    def find_acceptable(start):
        # Prune early if there aren’t enough possibilities left.
        if len(possibilities[-1]) + len(code) < datamax:
            return None

        for possibility in possibilities[-1]:
            if possibility >= start:
                return possibility

    # There are two moves we can make from a given situation, if the
    # code is not yet complete.  First, we can try adding a new
    # codeword; we must search to find one that doesn’t violate the
    # distance constraint.  If we can’t find one, we must backtrack,
    # which involves doing the same search for each remaining item in
    # the code until we find one that has a remaining alternative.
    i = 0
    while len(code) < datamax:
        i += 1
        if not i % 100000:
            print("trying", code, "remaining", possibilities[-1])
        next = find_acceptable(code[-1] + 1 if code else 0)
        while code and next is None:
            possibilities.pop()
            next = find_acceptable(code.pop() + 1)
        if not code and next is None:
            return None

        code.append(next)

        # Maintaining the set of possibilities incrementally in this
        # way is about 1000× faster than pairwise testing each
        # candidate against each existing codeword.  Note also that
        # using PyPy gets about a 4× speedup.
        possibilities.append([item for item in possibilities[-1]
                              if item > next
                              and weight[item ^ next] >= distance])

    return code

if __name__ == '__main__':
    print(find(*(int(arg) for arg in sys.argv[1:])))