MacWilliams Dual Distribution

Problem

Given the weight distribution weights[i] of a binary linear code (weights[i] = number of codewords of weight i) of length n, return the weight distribution of its dual using the MacWilliams identity:

B_j = (1 / 2^k) * sum_i A_i * K_j(i)

where K_j(i) = sum_t (-1)^t * C(i, t) * C(n - i, j - t). Find k from k = log2(sum of weights) and round each integer result.

Hint

Applying the transform twice returns the original distribution.

Test cases

case 1

in: [[1,0,0,1]]

expected: [1,0,3,0]

case 2

in: [[1,0,3,0]]

expected: [1,0,0,1]

case 3

in: [[1,0,0,7,7,0,0,1]]

expected: [1,0,0,0,7,0,0,0]

case 4

in: [[1,0,0,0]]

expected: [1,3,3,1]

Starter codePython

import math
def macwilliams_dual(weights):
    # Your code here
    pass

4 test cases · run your code against them in the editor