# HG changeset patch # User Brian Neal # Date 1371933133 18000 # Node ID 502b6bbcfefb09aed63c52ec56a48c14f27a8137 # Parent c9cc6f9f3bad963e5f3208982a2409a4fc8b2b9e Can now generate key list for first time. The algorithm fails on certain selections from group B (the unit test catches this). I'm committing this anyway and will address this later. diff -r c9cc6f9f3bad -r 502b6bbcfefb m209/keylist/data.py --- a/m209/keylist/data.py Fri Jun 21 20:20:43 2013 -0500 +++ b/m209/keylist/data.py Sat Jun 22 15:32:13 2013 -0500 @@ -374,3 +374,92 @@ [1, 2, 4, 7, 12, 12], [1, 2, 3, 7, 13, 13], ] + + +# All possible inputs to the Drum.rotate() function. This is used to ensure lug +# settings can create all values between 1 - 27, inclusive. +# +# This list was generated as follows: +# >>> from itertools import permutations +# >>> cases = [ +# ... [True, True, True, True, True, True], +# ... [True, True, True, True, True, False], +# ... [True, True, True, True, False, False], +# ... [True, True, True, False, False, False], +# ... [True, True, False, False, False, False], +# ... [True, False, False, False, False, False], +# ... ] +# >>> +# >>> result = [] +# >>> for case in cases: +# ... result.extend(sorted(list(set(permutations(case))))) +# +# The code above could have been included directly but it seems wasteful to +# compute it every time the program is run. We'll trade some memory for CPU +# here. + +ALL_DRUM_ROTATE_INPUTS = [ + (True, True, True, True, True, True), + (False, True, True, True, True, True), + (True, False, True, True, True, True), + (True, True, False, True, True, True), + (True, True, True, False, True, True), + (True, True, True, True, False, True), + (True, True, True, True, True, False), + (False, False, True, True, True, True), + (False, True, False, True, True, True), + (False, True, True, False, True, True), + (False, True, True, True, False, True), + (False, True, True, True, True, False), + (True, False, False, True, True, True), + (True, False, True, False, True, True), + (True, False, True, True, False, True), + (True, False, True, True, True, False), + (True, True, False, False, True, True), + (True, True, False, True, False, True), + (True, True, False, True, True, False), + (True, True, True, False, False, True), + (True, True, True, False, True, False), + (True, True, True, True, False, False), + (False, False, False, True, True, True), + (False, False, True, False, True, True), + (False, False, True, True, False, True), + (False, False, True, True, True, False), + (False, True, False, False, True, True), + (False, True, False, True, False, True), + (False, True, False, True, True, False), + (False, True, True, False, False, True), + (False, True, True, False, True, False), + (False, True, True, True, False, False), + (True, False, False, False, True, True), + (True, False, False, True, False, True), + (True, False, False, True, True, False), + (True, False, True, False, False, True), + (True, False, True, False, True, False), + (True, False, True, True, False, False), + (True, True, False, False, False, True), + (True, True, False, False, True, False), + (True, True, False, True, False, False), + (True, True, True, False, False, False), + (False, False, False, False, True, True), + (False, False, False, True, False, True), + (False, False, False, True, True, False), + (False, False, True, False, False, True), + (False, False, True, False, True, False), + (False, False, True, True, False, False), + (False, True, False, False, False, True), + (False, True, False, False, True, False), + (False, True, False, True, False, False), + (False, True, True, False, False, False), + (True, False, False, False, False, True), + (True, False, False, False, True, False), + (True, False, False, True, False, False), + (True, False, True, False, False, False), + (True, True, False, False, False, False), + (False, False, False, False, False, True), + (False, False, False, False, True, False), + (False, False, False, True, False, False), + (False, False, True, False, False, False), + (False, True, False, False, False, False), + (True, False, False, False, False, False), +] diff -r c9cc6f9f3bad -r 502b6bbcfefb m209/keylist/generate.py --- a/m209/keylist/generate.py Fri Jun 21 20:20:43 2013 -0500 +++ b/m209/keylist/generate.py Sat Jun 22 15:32:13 2013 -0500 @@ -13,14 +13,15 @@ from ..converter import M209 from .. import M209Error from ..data import KEY_WHEEL_DATA -from .data import GROUP_A, GROUP_B +from .data import GROUP_A, GROUP_B, ALL_DRUM_ROTATE_INPUTS +from ..drum import Drum logger = logging.getLogger(__name__) # Maximum number of attempts to generate valid settings before giving up and # raising a M209Error: -MAX_ATTEMPTS = 128 +MAX_ATTEMPTS = 1024 # Total number of pins on all 6 wheels: TOTAL_PINS = sum(len(letters) for letters, _ in KEY_WHEEL_DATA) @@ -101,15 +102,20 @@ for n in range(MAX_ATTEMPTS): overlaps = distribute_overlaps(selection, overlap) if overlaps and check_overlaps(overlaps): - break + # So far this looks good. But now we need to determine if the drum + # can generate all numbers in the range 1-27. + # Build a drum from our setup: + drum = Drum(build_lug_list(selection, overlaps)) + logger.debug('Drum: %s', drum) + if check_lug_placement(drum): + break + else: + logger.debug("Failed lug placement check") else: - raise M209Error("generate_lugs: too many attempts") + raise M209Error("generate_lugs: too many attempts: %s" % sorted(selection)) logger.info("Lugs generated in %s iteration(s)", n + 1) - # Build lug string - # TODO - - return '' + return drum.to_key_list() def distribute_overlaps(selection, overlap): @@ -211,6 +217,47 @@ return True +def build_lug_list(selection, overlaps): + """Build a lug list given the current selection and overlaps list.""" + + remaining = list(selection) + + lug_list = [] + for x, y, n in overlaps: + lug_list.extend([(x, y)] * n) + remaining[x] -= n + remaining[y] -= n + + for n in range(6): + lug_list.extend([(n, )] * remaining[n]) + + return lug_list + + +def check_lug_placement(drum): + """Returns True if this drum is capable of generating all values in the + range 1-27, inclusive, and False otherwise. + + """ + values = set() + + # Loop over all possible inputs to Drum.rotate(), noting the answer each + # time by storing it in our values set. When the size of our set reaches 27 + # we know we have good settings. + + for pins in ALL_DRUM_ROTATE_INPUTS: + val = drum.rotate(pins) + assert(1 <= val <= 27) + values.add(val) + + if len(values) == 27: + break + else: + return False + + return True + + def generate_pin_list(): """Return a random pin list based on Army procedure.""" diff -r c9cc6f9f3bad -r 502b6bbcfefb m209/keylist/tests/test_generate.py --- a/m209/keylist/tests/test_generate.py Fri Jun 21 20:20:43 2013 -0500 +++ b/m209/keylist/tests/test_generate.py Sat Jun 22 15:32:13 2013 -0500 @@ -11,6 +11,8 @@ from ..generate import generate_key_list, pin_list_check, check_overlaps from m209.converter import M209 from m209.data import KEY_WHEEL_DATA +from m209.drum import Drum +from m209.keylist.data import ALL_DRUM_ROTATE_INPUTS def make_pin_list(eff_cnt): @@ -40,7 +42,7 @@ 'EFGHIJLMNP' ] - def test_generate_key_list(self): + def do_test_generate_key_list(self): key_list = generate_key_list('BN') self.assertEqual(key_list.indicator, 'BN') @@ -50,13 +52,36 @@ for i, pins in enumerate(key_list.pin_list): self.assertTrue(all(c in KEY_WHEEL_DATA[i][0] for c in pins)) - # TODO: add some lug asserts - m_209 = M209(lugs=key_list.lugs, pin_list=key_list.pin_list) m_209.set_key_wheels('AAAAAA') s = m_209.encrypt('A' * 26) self.assertEqual(s, key_list.letter_check) + def test_generate_key_list(self): + + for n in range(32): + self.do_test_generate_key_list() + + def do_test_lug_settings(self): + + key_list = generate_key_list('BN') + drum = Drum.from_key_list(key_list.lugs) + + vals = set() + for pins in ALL_DRUM_ROTATE_INPUTS: + val = drum.rotate(pins) + self.assertTrue(1 <= val <= 27) + vals.add(val) + if len(vals) == 27: + break + else: + self.fail('Invalid drum settings (1-27 check)') + + def test_lug_settings(self): + + for n in range(1024): + self.do_test_lug_settings() + def test_pin_list_check(self): # Effective pin ratio too high (100%)