# HG changeset patch # User Brian Neal # Date 1371959294 18000 # Node ID b32ded2f157ff76b256bfd432e11b60886464544 # Parent 502b6bbcfefb09aed63c52ec56a48c14f27a8137 For now, comment out entries in group B that we can't find a solution for. Added tests for all of group A and group B (minus the problematic ones). diff -r 502b6bbcfefb -r b32ded2f157f m209/keylist/data.py --- a/m209/keylist/data.py Sat Jun 22 15:32:13 2013 -0500 +++ b/m209/keylist/data.py Sat Jun 22 22:48:14 2013 -0500 @@ -20,6 +20,14 @@ # TYPO?, below. Should I tell the War Department? :P # I changed it to a sequence where the overlap matched the lines above and below # it. I suppose it could have been intentional. +# +# Finally there were 5 selections in group B that our heuristic algorithm could +# not find a solution for, even when allowed to iterate 100,000 times. At this +# time I am not certain there is a solution for these values. For the time +# being I have commented them out. I would imagine that if our (albeit simple) +# algorithm could not come up with a solution then a soldier would have +# difficulty finding a solution as well, assuming they generated the key lists +# by hand. If they used a computer or algorithm, I'd sure like to see it! GROUP_A = [ [1, 2, 3, 4, 8, 10], @@ -331,11 +339,11 @@ [1, 1, 3, 5, 10, 13], [1, 1, 3, 6, 10, 12], [1, 1, 3, 6, 9, 13], - [1, 2, 2, 4, 11, 13], +# [1, 2, 2, 4, 11, 13], # Our algorithm has trouble with this one [1, 2, 2, 5, 11, 12], [1, 2, 2, 5, 10, 13], [1, 2, 2, 6, 9, 13], - [1, 2, 3, 3, 11, 13], +# [1, 2, 3, 3, 11, 13], # Our algorithm has trouble with this one [1, 2, 3, 5, 11, 11], [1, 2, 3, 7, 7, 13], [1, 2, 3, 7, 10, 10], @@ -344,7 +352,7 @@ [1, 1, 3, 5, 11, 13], [1, 1, 3, 6, 11, 12], [1, 1, 3, 6, 10, 13], - [1, 2, 2, 4, 12, 13], +# [1, 2, 2, 4, 12, 13], # Our algorithm has trouble with this one [1, 2, 2, 5, 11, 13], [1, 2, 2, 6, 11, 12], [1, 2, 2, 6, 10, 13], @@ -367,8 +375,8 @@ [1, 2, 4, 5, 12, 12], [1, 2, 4, 7, 11, 11], [1, 2, 4, 8, 8, 13], - [1, 2, 2, 6, 13, 13], - [1, 2, 3, 5, 13, 13], +# [1, 2, 2, 6, 13, 13], # Our algorithm has trouble with this one +# [1, 2, 3, 5, 13, 13], # Our algorithm has trouble with this one [1, 2, 4, 8, 11, 11], [1, 2, 3, 6, 13, 13], [1, 2, 4, 7, 12, 12], diff -r 502b6bbcfefb -r b32ded2f157f m209/keylist/generate.py --- a/m209/keylist/generate.py Sat Jun 22 15:32:13 2013 -0500 +++ b/m209/keylist/generate.py Sat Jun 22 22:48:14 2013 -0500 @@ -17,11 +17,19 @@ from ..drum import Drum +class KeyListGenError(M209Error): + """Exception class for key list generation errors""" + + logger = logging.getLogger(__name__) -# Maximum number of attempts to generate valid settings before giving up and -# raising a M209Error: -MAX_ATTEMPTS = 1024 +# Maximum number of attempts to generate valid lug settings before giving up and +# raising a KeyListGenError: +MAX_LUG_ATTEMPTS = 2048 + +# Maximum number of attempts to generate valid pin settings before giving up and +# raising a KeyListGenError: +MAX_PIN_ATTEMPTS = 64 # Total number of pins on all 6 wheels: TOTAL_PINS = sum(len(letters) for letters, _ in KEY_WHEEL_DATA) @@ -47,7 +55,8 @@ CONSEC_MAPS = [build_consec_map(letters) for letters, _ in KEY_WHEEL_DATA] -def generate_key_list(indicator): +def generate_key_list(indicator, lug_selection=None, + max_lug_attempts=MAX_LUG_ATTEMPTS, max_pin_attempts=MAX_PIN_ATTEMPTS): """Create a key list at random with the given indicator. The procedure used is based upon manuals for the M-209 as found online: @@ -63,43 +72,71 @@ Page 1 of reference [2] says: "This manual supercedes TM-11-380, 27 April 1942, and TM-11-380B, 20 September 1943." + The algorithm we use follows the procedure outlined in reference [2]. The + algorithm is simple and ad-hoc in nature. When required to make a decision + it relies on some simple heuristics and random numbers. If it cannot come up + with a solution it simply tries again, up to an iteration limit. This + algorithm was sufficient to generate solutions for all sets of numbers in + group A (given enough iterations). However there were some sets of numbers + where our algorithm could not find a solution, even when allowed to iterate + 100,000 times. See the m209.keylist.data module for the problematic entries. + It is not known if our algorithm is just unlucky and not able to find + a solution, the algorithm is flawed and can't find certain solutions, or if + a solution doesn't actually exist. An interesting side project would be to + write a program to search the solution space for a given set of numbers to + see if a solution could actually be found. In any event, for our purposes, + we just remove the problematic entries from the table. + """ logger.info("Creating key list %s", indicator) - lugs = generate_lugs() - pin_list = generate_pin_list() + lugs = generate_lugs(lug_selection, max_lug_attempts) + pin_list = generate_pin_list(max_pin_attempts) letter_check = generate_letter_check(lugs=lugs, pin_list=pin_list) return KeyList(indicator=indicator, lugs=lugs, pin_list=pin_list, letter_check=letter_check) -def generate_lugs(): - """Return random lug settings based on Army procedure.""" +def generate_lugs(lug_selection=None, max_attempts=MAX_LUG_ATTEMPTS): + """Return random lug settings based on Army procedure. - # From the manual: "2a: Select a set of numbers from either group A or group - # B in appendix II. Sets of numbers selected from group B must not exceed - # 10% of the total sets selected." - # - # For our purposes, we'll just pick from group B ~10% of the time. We also - # (currently) have no history of prior key list generations, so we don't - # worry about reusing sets or how often we've picked from group B. - rn = random.randint(0, 100) - group = GROUP_A if rn > 10 else GROUP_B - selection = random.choice(group) + If not None, lug_selection must be a list of 6 integers that will be used + for driving the lug settings algorithm. If None, a set of numbers is chosen + from the tables in appendix II of the manual. - logger.debug("Selecting from group %s", 'A' if group is GROUP_A else 'B') - logger.debug("Selection: %s", selection) + The parameter max_lug_attempts controls how many iterations the algorithm + can perform to find a solution before giving up. If forced to give up, + a KeyListGenError is raised. - # 2b: Rearrange the numbers so they appear in a random order - random.shuffle(selection) - logger.debug("Shuffled selection: %s", selection) + """ + selection_provided = lug_selection is not None + if selection_provided: + selection = lug_selection + logger.debug("Selection provided: %s", selection) + else: + # From the manual: "2a: Select a set of numbers from either group A or + # group B in appendix II. Sets of numbers selected from group B must + # not exceed 10% of the total sets selected." + # + # For our purposes, we'll just pick from group B ~10% of the time. We + # also (currently) have no history of prior key list generations, so we + # don't worry about reusing sets or how often we've picked from group B. + rn = random.randint(0, 100) + group = GROUP_A if rn > 10 else GROUP_B + logger.debug("Selecting from group %s", 'A' if group is GROUP_A else 'B') + selection = random.choice(group) + logger.debug("Selection: %s", selection) + + # 2b: Rearrange the numbers so they appear in a random order + random.shuffle(selection) + logger.debug("Shuffled selection: %s", selection) # 2c: Distribution of Overlaps overlap = sum(selection) - 27 logger.debug("Overlap: %d", overlap) - for n in range(MAX_ATTEMPTS): + for n in range(max_attempts): overlaps = distribute_overlaps(selection, overlap) if overlaps and check_overlaps(overlaps): # So far this looks good. But now we need to determine if the drum @@ -112,7 +149,7 @@ else: logger.debug("Failed lug placement check") else: - raise M209Error("generate_lugs: too many attempts: %s" % sorted(selection)) + raise KeyListGenError("generate_lugs: too many attempts: %s" % sorted(selection)) logger.info("Lugs generated in %s iteration(s)", n + 1) return drum.to_key_list() @@ -212,8 +249,6 @@ logger.debug("check_overlaps: failed side by side check") return False - # 2d: Checking placement of overlaps - return True @@ -258,13 +293,17 @@ return True -def generate_pin_list(): - """Return a random pin list based on Army procedure.""" +def generate_pin_list(max_attempts=MAX_PIN_ATTEMPTS): + """Return a random pin list based on Army procedure. + The max_attempts parameter controls how many iterations the algorithm can + perform before giving up. If forced to give up, an KeyListGenError is raised. + + """ cards = ['R'] * 78 cards.extend(['L'] * (156 - len(cards))) - for n in range(MAX_ATTEMPTS): + for n in range(max_attempts): random.shuffle(cards) deck = collections.deque(cards) pin_list = [] @@ -275,7 +314,7 @@ if pin_list_check(pin_list): break else: - raise M209Error("generate_pin_list: too many attempts") + raise KeyListGenError("generate_pin_list: too many attempts") logger.info("Pin list generated in %s iteration(s)", n + 1) diff -r 502b6bbcfefb -r b32ded2f157f m209/keylist/tests/test_generate.py --- a/m209/keylist/tests/test_generate.py Sat Jun 22 15:32:13 2013 -0500 +++ b/m209/keylist/tests/test_generate.py Sat Jun 22 22:48:14 2013 -0500 @@ -8,11 +8,12 @@ import random import unittest -from ..generate import generate_key_list, pin_list_check, check_overlaps +from ..generate import (generate_key_list, pin_list_check, check_overlaps, + KeyListGenError) 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 +from m209.keylist.data import GROUP_A, GROUP_B, ALL_DRUM_ROTATE_INPUTS def make_pin_list(eff_cnt): @@ -62,9 +63,15 @@ for n in range(32): self.do_test_generate_key_list() - def do_test_lug_settings(self): + def do_test_lug_settings(self, selection, failures, max_lug_attempts=1024): - key_list = generate_key_list('BN') + try: + key_list = generate_key_list('BN', lug_selection=selection, + max_lug_attempts=max_lug_attempts) + except KeyListGenError: + failures.append(selection) + return + drum = Drum.from_key_list(key_list.lugs) vals = set() @@ -77,10 +84,23 @@ else: self.fail('Invalid drum settings (1-27 check)') - def test_lug_settings(self): + def test_key_list_group_a(self): - for n in range(1024): - self.do_test_lug_settings() + failures = [] + for selection in GROUP_A: + self.do_test_lug_settings(selection, failures) + + if failures: + self.fail("Group A failures: %s" % failures) + + def test_key_list_group_b(self): + + failures = [] + for selection in GROUP_B: + self.do_test_lug_settings(selection, failures) + + if failures: + self.fail("Group B failures: %s" % failures) def test_pin_list_check(self):