# HG changeset patch # User Brian Neal # Date 1371327690 18000 # Node ID 941590d946c01b4ee7473714ff00875349908fa3 # Parent 425981f2787602d5e088b4fd35a70e270193bbec Reworked the consecutive pin checks. Added tests. diff -r 425981f27876 -r 941590d946c0 m209/keylist/generate.py --- a/m209/keylist/generate.py Fri Jun 14 21:46:42 2013 -0500 +++ b/m209/keylist/generate.py Sat Jun 15 15:21:30 2013 -0500 @@ -5,6 +5,7 @@ """This module contains routines to generate key lists.""" import collections +import itertools import random from .key_list import KeyList @@ -20,6 +21,26 @@ # Total number of pins on all 6 wheels: TOTAL_PINS = sum(len(letters) for letters, _ in KEY_WHEEL_DATA) +# CONSEC_MAPS is a list of dicts, one for each key wheel. Each dict key is +# a letter. The value is the string of 7 consecutive letters that would make the +# key setting invalid according to Army procedure. The consecutive string +# accounts for the letters on the key wheel and wrap-around. + +def build_consec_map(letters): + """Builds a "consecutive map" for the list of letters on a key wheel. This + is used to validate a pin list to make sure there are not too many effective + or ineffective pins in a consecutive sequence. + + """ + deque = collections.deque(letters) + consec = {} + for c in letters: + consec[c] = ''.join(itertools.islice(deque, 0, 7)) + deque.rotate(-1) + return consec + +CONSEC_MAPS = [build_consec_map(letters) for letters, _ in KEY_WHEEL_DATA] + def generate_key_list(indicator): """Create a key list at random with the given indicator. @@ -96,26 +117,43 @@ return False # Check for more than 6 consecutive effective pins on a wheel - # TODO: not all letters are on every wheel - for pins in pin_list: - run = 0 - for i in range(len(pins) - 1): - if ord(pins[i]) + 1 == ord(pins[i + 1]): - run = 2 if run == 0 else run + 1 - else: - run = 0 - if run >= 7: - return False + for n, pins in enumerate(pin_list): + if check_consecutive(n, pins): + return False # Check for more than 6 consecutive ineffective pins on a wheel - # TODO: not all letters are on every wheel - for pins in pin_list: - x = 'A' - for y in pins: - if ord(y) - ord(x) >= 8: - return False - x = y + for n, pins in enumerate(pin_list): + if check_consecutive(n, invert_pins(n, pins)): + return False return True + + +def check_consecutive(n, pins): + """Check for consecutive pins on key wheel n. The pins parameter must be + a string of the pins that are effective. Returns True if there are more than + 6 consecutive effective pins and False otherwise. + + """ + consec = CONSEC_MAPS[n] + deque = collections.deque(pins) + for c in pins: + if consec[c] == ''.join(itertools.islice(deque, 0, 7)): + return True + deque.rotate(-1) + return False + + +def invert_pins(n, pins): + """Given a string of effective pins on key wheel n, return a string where + all the effective pins are pushed to the left and all the ineffective pins + are pushed to the right, thus flipping which pins are effective + / ineffective. + + """ + all_letters = set(KEY_WHEEL_DATA[n][0]) + effective = set(pins) + inverse = sorted(all_letters - effective) + return ''.join(inverse) diff -r 425981f27876 -r 941590d946c0 m209/keylist/tests/test_generate.py --- a/m209/keylist/tests/test_generate.py Fri Jun 14 21:46:42 2013 -0500 +++ b/m209/keylist/tests/test_generate.py Sat Jun 15 15:21:30 2013 -0500 @@ -81,7 +81,7 @@ self.assertFalse(pin_list_check(make_pin_list(100))) self.assertFalse(pin_list_check(make_pin_list(125))) - def test_consecutive_effective_pins(self): + def test_consecutive_effective_pins_0(self): pin_list = self.valid_pin_list pin_list[0] = 'ABEGHIJKLNOSUZ' @@ -96,8 +96,84 @@ self.assertFalse(pin_list_check(pin_list)) pin_list[0] = 'BEFGHIJKSUX' self.assertFalse(pin_list_check(pin_list)) + pin_list[0] = 'ABCDGKOTXYZ' + self.assertFalse(pin_list_check(pin_list)) - def test_consecutive_noneffective_pins(self): - pass + def test_consecutive_effective_pins_1(self): + pin_list = self.valid_pin_list + pin_list[1] = 'BCEGIKMOTUVXYZ' + self.assertTrue(pin_list_check(pin_list)) + pin_list[1] = 'ABCEGIKMOTUVXYZ' + self.assertFalse(pin_list_check(pin_list)) + def test_consecutive_effective_pins_2(self): + + pin_list = self.valid_pin_list + pin_list[2] = 'ACEGIKMOSTUVX' + self.assertTrue(pin_list_check(pin_list)) + pin_list[2] = 'ABEGIKMOSTUVX' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_effective_pins_3(self): + + pin_list = self.valid_pin_list + pin_list[3] = 'ACEGIKMOSTU' + self.assertTrue(pin_list_check(pin_list)) + pin_list[3] = 'ABCDGIKMOSTU' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_effective_pins_4(self): + + pin_list = self.valid_pin_list + pin_list[4] = 'ABCEGIKMOQRS' + self.assertTrue(pin_list_check(pin_list)) + pin_list[4] = 'ABGIKMOPQRS' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_effective_pins_5(self): + + pin_list = self.valid_pin_list + pin_list[5] = 'ABCEGIKMOQ' + self.assertTrue(pin_list_check(pin_list)) + pin_list[5] = 'ABGIKMNOPQ' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_0(self): + + pin_list = self.valid_pin_list + pin_list[0] = 'ABCDENOPQSUWYZ' + self.assertFalse(pin_list_check(pin_list)) + pin_list[0] = 'BCDFGHJKLMOPRST' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_1(self): + + pin_list = self.valid_pin_list + pin_list[1] = 'CDEGHJKLNOPQRST' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_2(self): + + pin_list = self.valid_pin_list + pin_list[2] = 'CDEFHIJKMNOPQRS' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_3(self): + + pin_list = self.valid_pin_list + pin_list[3] = 'CDEGHIKLNOP' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_4(self): + + pin_list = self.valid_pin_list + pin_list[4] = 'EFGIJKMOP' + self.assertFalse(pin_list_check(pin_list)) + + def test_consecutive_noneffective_pins_5(self): + + pin_list = self.valid_pin_list + pin_list[5] = 'DEFHIKLM' + self.assertFalse(pin_list_check(pin_list)) +