Vigenere Best Key Length

Problem

Estimate a Vigenere key length from a ciphertext. For each candidate length k, split the text into k columns with text[start::k], average the index of coincidence of the columns, and return the candidate with the largest average. Ties go to the smaller candidate. Assume candidates are positive and ascending.

Hint

Correctly aligned columns mix text from a single Caesar shift, raising their IC.

Test cases

case 1

in: ["ATTACKATDAWNATTACKATDAWN",[1,2,3,4,5]]

expected: 3

case 2

in: ["ABCABCABCABCABCABC",[1,2,3,4]]

expected: 3

case 3

in: ["AABAABAABAAB",[1,2,3,4]]

expected: 3

Starter codePython

def vigenere_best_key_length(text, candidates):
    # Your code here
    pass

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